Контейнеры

Как уже было отмечено, под контейнером понимают объект, содержащий другие (однотипные) объекты, называемые элементами контейнера. Стандартная библиотека С++ предоставляет типичные контейнеры, такие как: список, вектор, очередь, карта, множество и др.Доступ к элементам контейнера осуществляется через итераторы.

К контейнерам выдвигается ряд общих требований. Это осуществляется для того, чтобы использование контейнеров было одинаковым, независимо от его реализации. Соответственно, часто контейнеры бывают взаимозаменяемы.

Требования контейнеров

выражение	возвращаемый тип	утверждение/примечание состояние до/после
X::value_type	Т
X::reference	T&
X::const_refe rence	const T&
X::pointer	тип указателя, указывающий на X::reference	указатель на T в модели памяти, используемой контейнером
X::iterator	тип итратора, указывающий на X::reference	итератор любой категории, кроме итератора вывода.
X::const_iter ator	тип итератора, указывающий на 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;		конструктор копирования. после: u = a.
(&a)->~X()	результат не используется	после: a.size() == 0. примечание: деструктор применяется к каждому элементу a, и вся память возвращается.
a.begin()	iterator; const_iterator для постоянного a	итератор, указывающий на первый элемент
a.end()	iterator; const_iterator для постоянного a	итератор, указывающий на конец контейнера
a == b	обратимый в bool	== - это отношение эквивалентности. примечание: equal определяется в разделе алгоритмов.
a != b	обратимый в bool
r = a	X&	после: r == a.
a.size()	size_type	количество элементов в контейнере
a.max_size()	size_type	size() самого большого возможного контейнера.
a.empty()	обратимый в bool
a < b	обратимый в bool	до: < определён для значений T. < - отношение полного упорядочения. lexicographical _compare определяется в разделе алгоритмов.
a > b	обратимый в bool
a <= b	обратимый в bool
a >= b	обратимый в bool
a.swap(b)	void

Последовательные контейнеры

Последовательные контейнеры хранят свои элементы в строго линейном порядке. К последовательным контейнерам относятся хорошо известные структуры данных вектор (vector), список (list), очередь (deque), а также строка символов (string). Существуют также некоторые последовательные контейнеры, которые могут отсутствовать в стандартной библиотеке С++: стек (stack) и массив (array).

В таблице 7 указаны требования к последовательным контейнерам (обязательные операции).

Таблица 7 Требования последовательностей (в дополнение к контейнерам)

выражение	возвращаемый тип	утверждение/примечание состояние до/после
X(n, t) X a(n, t);		после: size() == n. создаёт последовательность с n копиями t.
X(i, j) X a(i, j);		после: size() == расстоянию между i и j. создаёт последовательность, равную диапазону [i, j).
a.insert(p, t)	iterator	вставляет копию t перед p. возвращаемое значение указывает на вставленную копию.
a.insert(p, n, t)	результат не используется	вставляет n копий t перед p.
a.insert(p, i, j)	результат не используется	вставляет копии элементов из диапазона [i, j) перед p.
a.erase(q)	результат не используется	удаляет элемент, указываемый q.
a.erase(ql, q2)	результат не используется	удаляет элементы в диапазоне [ql, q2).

В таблице 8 указаны операции, которые выражаются через обязательные операции контейнеров. В различных типах контейнеров эти опреации могут отсутствовать, например, у контейнера типа вектор нет возможности вставлять элементы в начало контейнера.

Таблица 8 Необязательные операции последовательностей

выражение	возвращаемый тип	семантика исполнения	контейнер
a.front()	reference; const_reference для постоянного a	*a.begin()	vector, list, deque
a.back()	reference; const_reference для постоянного a	*(--a. end())	vector, list, deque
a.push_front(t)	void	a.insert(a.begin(), t)	list, deque
a.push_back(t)	void	a.insert(a.end(), t)	vector, list, deque
a.pop_front ()	void	a.erase(a.begin())	list, deque
a.pop_back ()	void	a.erase(-- a.end())	vector, list, deque
a[n]	reference; const_reference для постоянного a	*(a.begin() + n)	vector, deque

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

Ассоциативные контейнеры

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

выражение	возвращаемый тип	утверждение/примечание состояние до/после
X::key_type	Key
X::key_compare	Compare	по умолчанию less<key_type>.
X::value_compare	тип бинарного предиката	то же, что key_compare для set и multiset; отношение упорядочения пар, вызванное первым компонентом (т.е. Key), для map и multimap.
X(c) X a(c);		создает пустой контейнер; использует с как объект сравнения.
X() X a;		создает пустой контейнер; использует Compare() как объект сравнения.
X(i,j,c) X a(i,j,c);		cоздает пустой контейнер и вставляет в него элементы из диапазона [i, j); использует с как объект сравнения.
X(i,j) X a(i,j);		то же, что выше, но использует Compare() как объект сравнения.
a.key_comp()	X::key_compare	возвращает объект сравнения, из которого а был создан.
a.value_comp()	X::value_compare	возвращает объект value_compare, созданный из объекта сравнения.
a_uniq.insert(t)	pair<iterator, bool>	вставляет t, если и только если в контейнере нет элемента с ключом, равным ключу t. Компонент boolвозвращенной пары показывает, происходит ли вставка, а компонент пары iterator указывает на элемент с ключом, равным ключу t.
a_eq.insert(t)	iterator	вставляет t и возвращает итератор, указывающий на вновь вставленный элемент.
a.insert(p, t)	iterator	вставляет t, если и только если в контейнерах с уникальными ключами нет элемента с ключом, равным ключу t; всегда вставляет t в контейнеры с дубликатами. всегда возвращает итератор, указывающий на элемент с ключом, равным ключу t. итератор p - подсказка, указывающая, где вставка должна начать поиск.
a.insert(i, j)	результат не используется	вставляет в контейнер элементы из диапазона [i, j);
a.erase(k)	size_type	стирает все элементы в контейнере с ключом, равным k. возвращает число уничтоженных элементов.
a.erase(q)	результат не используется	стирает элемент, указанный q.
a.erase(ql, q2)	результат не используется	стирает все элементы в диапазоне [ql, q2).
a.find(k)	iterator; const_iterator для константы a	возвращает итератор, указывающий на элемент с ключом, равным k, или a.end(), если такой элемент не найден.
a.count(k)	size_type	возвращает число элементов с ключом, равным k.
a.lower_bound(k)	iterator; const_iterator для константы a	возвращает итератор, указывающий на первый элемент с ключом не меньше, чем k.
a.upper_bound(k)	iterator; const_iterator для константы a	возвращает итератор, указывающий на первый элемент с ключом больше, чем k.
a.equal_range(k)	pair<iterator, itеrator>; pair<const_iter ator, const_iterator>для константы a	эквивалент make_pair(lower_boud(k), upper_bound (k)).