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

Для любого шаблона распределителя Alloc имеется определение для типа void. У Alloc‹void› определены только конструктор, деструктор и Alloc‹void›::pointer. Преобразования определены из любого Alloc‹T›::pointer в Alloc‹void›::pointer и обратно, так что для любого p будет p == Alloc‹T›::pointer(Alloc‹void›::pointer(p)).

Распределитель по умолчанию (The default allocator)

template ‹class T›

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