РУКОВОДСТВО ПО СТАНДАРТНОЙ БИБЛИОТЕКЕ ШАБЛОНОВ (STL)

Контейнеры

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

В следующей таблице мы полагаем, что 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 (обратимым) и удовлетворяет следующим дополнительным требованиям: