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

Предполагается, что в дополнение к 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() возвращает итератор, который является законечным.