Руководство по стандартной библиотеке шаблонов (STL) - [8]

 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())	постоянная

Последовательности (Sequences)

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

В следующих двух таблицах X - последовательный класс, a - значение X, i и j удовлетворяют требованиям итераторов ввода, [i, j) - допустимый диапазон, n - значение X::size_type, p - допустимый итератор для a, q - разыменовываемый итератор для a, [q1, q2) - допустимый диапазон в a, t - значение X::value_type.