Б.4. Контейнеры
Контейнер содержит последовательность элементов. Элементы этой последовательности имеют тип
value_type
. Наиболее полезными контейнерами являются следующие.
Эти контейнеры определены в классах
<vector>
,
<list>
и др. (см. раздел Б.1.1). Последовательные контейнеры занимают непрерывную область памяти или представляют собой связанные списки, содержащие элементы соответствующего типа
value_type
(выше мы обозначали его буквой
T
). Ассоциативные контейнеры представляют собой связанные структуры (деревья) с узлами соответствующего типа value_type (выше мы обозначали его как
pair(K,V)
). Последовательность элементов в контейнерах
set
,
map
или
multimap
упорядочена по ключу (K). Последовательность в контейнерах, название которых начинается со слова
unordered
, не имеет гарантированного порядка. Контейнер
multimap
отличается от контейнера
map
тем, что в первом случае значение ключа может повторяться много раз. Адаптеры контейнеров — это контейнеры со специальными операциями, созданные из других контейнеров.
Если сомневаетесь, используйте класс
vector
. Если у вас нет весомой причины использовать другой контейнер, используйте класс
vector
.
Для выделения и освобождения памяти (см. раздел 19.3.6) контейнеры используют распределители памяти. Мы не описываем их здесь; при необходимости читатели найдут информацию о них в профессиональных справочниках. По умолчанию распределитель памяти использует операторы
new
и
delete
, для того чтобы занять или освободить память, необходимую для элементов контейнера.
Там, где это целесообразно, операция доступа реализована в двух вариантах: один — для константных объектов, другой — для неконстантных (см. раздел 18.4).
В этом разделе перечислены общие и “почти общие” члены стандартных контейнеров (более подробную информацию см. в главе 20). Члены, характерные для какого-то конкретного контейнера, такие как функция
splice()
из класса
list
, не указаны; их описание можно найти в профессиональных справочниках.
Некоторые типы данных обеспечивают большинство операций, требующихся от стандартного контейнера, но все-таки не все. Иногда такие типы называют “почти контейнерами”. Перечислим наиболее интересные из них.
Б.4.1. Обзор
Операции, предусмотренные в стандартных контейнерах, можно проиллюстрировать следующим образом:
Б.4.2. Типы членов
Контейнер определяет множество типов его членов.
Б.4.3. Конструкторы, деструкторы и присваивания
Контейнеры имеют много разнообразных конструкторов и операторов присваивания. Перечислим конструкторы, деструкторы и операторы присваивания для контейнера C (например, типа
vector<double>
или
map<string,int>
).
Для некоторых контейнеров и типов элементов конструктор или операция копирования может генерировать исключения.
Б.4.4. Итераторы
Контейнер можно интерпретировать как последовательность, порядок следования элементов в которой определен либо итератором контейнера, либо является обратным к нему. Для ассоциативного контейнера порядок определяется критерием сравнения (по умолчанию оператором
<
).
Б.4.5. Доступ к элементам
К некоторым элементам можно обратиться непосредственно.
Некоторые реализации — особенно их тестовые версии — всегда выполняют проверку диапазонов, но рассчитывать на корректность или наличие такой проверки на разных компьютерах нельзя. Если этот вопрос важен, просмотрите документацию.
Б.4.6. Операции над стеком и двусторонней очередью
Стандартные контейнеры
vector
и
deque
обеспечивают эффективные операции над концами (
back
) последовательности элементов. Кроме того, контейнеры
list
и
deque
обеспечивают аналогичные операции над началом (
front
) своей последовательности.
Обратите внимание на то, что функции
push_front()
и
push_back()
копируют элемент в контейнер. Это значит, что размер контейнера увеличивается (на единицу). Если копирующий конструктор элемента может генерировать исключения, то вставка может завершиться отказом.
Отметим, что операции удаления элементов не возвращают значений. Если бы они это делали, то копирующие конструкторы, генерирующие исключения, могли бы серьезно усложнить реализацию. Для доступа к элементам стека и очереди рекомендуем использовать функции
front()
и
back()
(см. раздел Б.4.5). Мы не ставили себе задачу перечислить все ограничения; попробуйте догадаться об остальных (как правило, компиляторы сообщают пользователям об их неверных догадках) или обратитесь к более подробной документации.
Б.4.7. Операции над списком
Ниже приведены операции над списком.
Результат
q
функции
insert()
ссылается на последний вставленный элемент. Результат
q
функции
erase()
ссылается на элемент, следующий за последним удаленным элементом.
