Александр Степанов - РУКОВОДСТВО ПО СТАНДАРТНОЙ БИБЛИОТЕКЕ ШАБЛОНОВ (STL)

class allocator {

public:

 typedef T* pointer;

 typedef const T* const_pointer;

 typedef T& reference;

 typedef const T& const_reference;

 typedef T value_type;

 typedef size_t size_type;

 typedef ptrdiff_t difference_type;

 allocator();

 ~allocator();

 pointer address(reference x);

 const_pointer const_address(const_reference x);

 pointer allocate(size_type n);

 void deallocate(pointer p);

 size_type init_page_size();

 size_type max_size();

};

class allocator‹void› {

public:

 typedef void* pointer;

 allocator();

 ~allocator();

};

Предполагается, что в дополнение к allocator поставщики библиотеки обеспечивают распределители для всех моделей памяти.

Контейнеры - это объекты, которые содержат другие объекты. Они управляют размещением в памяти и свобождением этих объектов через конструкторы, деструкторы, операции вставки и удаления.

В следующей таблице мы полагаем, что X - контейнерный класс, содержащий объекты типа T, a и b - значения X, u - идентификатор, r - значение X&.

Таблица 8. Требования контейнеров

выражение возвращаемый тип семантика исполнения утверждение/примечание состояние до/после сложность X::value_type Т - -  время компиляции X::reference - - - время компиляции X::const_reference - - - время компиляции X::pointer тип указателя, указывающий на X::reference - указатель на T в модели памяти, используемой контейнером время компиляции X::iterator тип итератора, указывающий на X::reference - итератор любой категории, кроме итератора вывода. время компиляции X::const_iterator тип итератора, указывающий на X::const_reference - постоянный итератор любой категории, кроме итератора вывода. время компиляции X::difference_type знаковый целочисленный тип - идентичен типу расстояния X::iterator и X::const_iterator время компиляции X::size_type беззнаковый целочисленный тип -  size_type может представлять любое неотрицательное значение difference_type время компиляции X u; - -  после: u.size()==0. постоянная X() - - X().size()==0. постоянная X(a) - - a==X(a). линейная X u(a); X u==a; - X u; u = a; после: u==a. линейная (&a)-›~X() результат не используется -  после: a.size()==0. примечание: деструктор применяется к каждому элементу a, и вся память возвращается. линейная a.begin() iterator; const_iterator для постоянного a - - постоянная a.end() iterator; const_iterator для постоянного a - - постоянная a==b обратимый в bool a.size()==b.size() && equal(a.begin(), a.end(), b.begin()) == - это отношение эквивалентности. примечание: equal определяется в разделе алгоритмов. линейная a!= b обратимый в bool !(a==b) - линейная r = a X& if(&r!=&a){ (&r)-›X::~X(); new(&r)X(a); return r;} после: r==a. линейнaя a.size() size_type size_type n = 0; distance(a.begin(), a.end(), n); return n; - постоянная a.max_size() size_type - size() самого большого возможного контейнера. постоянная a.empty() обратимый в bool a.size()==0 - постоянная a ‹ b обратимый в bool lexicographical_compare(a.begin(), a.end(), b.begin(), b.end()) до: ‹ определён для значений T. ‹ - отношение полного упорядочения. lexicographical_compare определяется в разделе алгоритмов. линейная a › b обратимый в bool b ‹ a - линейнaя a ‹= b обратимый в bool !(a › b) - линейная a ›= b обратимый в bool !(a ‹ b) - линейная a.swap(b) void swap(a, b) - постоянная

Функция-член size() возвращает число элементов в контейнере. Её семантика определяется правилами конструкторов, вставок и удалений.

begin() возвращает итератор, ссылающийся на первый элемент в контейнере. end() возвращает итератор, который является законечным.

Если тип итератора контейнера принадлежит к категории двунаправленных итераторов или итераторов произвольного доступа, то контейнер называется reversible (обратимым) и удовлетворяет следующим дополнительным требованиям:

Таблица 9. Требования обратимых контейнеров (в дополнение к контейнерам)

выражение возвращаемый тип семантика исполнения сложность X::reverse_iterator - reverse_iterator‹iterator, value_type, reference, difference_type› для итератора произвольного доступа. reverse_bidirectional_iterator‹iterator, value_type, reference, difference_type› для двунаправленного итератора время компиляции X::const_reverse_iterator - reverse_iterator‹const_iterator, value_type, const_reference, difference_type› для итератора произвольного доступа. reverse_bidirectional_iterator‹const_iterator, value_type, const_reference, difference_type› для двунаправленного итератора. время компиляции a.rbegin() reverse_iterator; const_reverse_iterator для постоянного a reverse_iterator(end()) постоянная a.rend() reverse_iterator; const_reverse_iterator для постоянного a reverse_iterator(begin()) постоянная

Последовательность - это вид контейнера, который организует конечное множество объектов одного и того же типа в строгом линейном порядке. Библиотека обеспечивает три основных вида последовательных контейнеров: vector (вектор), list (список) и deque (двусторонняя очередь). Она также предоставляет контейнерные адаптеры, которые облегчают создание абстрактных типов данных, таких как стеки или очереди, из основных видов последовательностей (или из других видов последовательностей, которые пользователь может сам определить).