Программирование. Принципы и практика использования C++ Исправленное издание, стр. 425

Б.4. Контейнеры

Контейнер содержит последовательность элементов. Элементы этой последовательности имеют тип

value_type
. Наиболее полезными контейнерами являются следующие.

Программирование. Принципы и практика использования C++ Исправленное издание - _384.png
Программирование. Принципы и практика использования C++ Исправленное издание - _385.png
Программирование. Принципы и практика использования C++ Исправленное издание - _386.png

Эти контейнеры определены в классах

<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
, не указаны; их описание можно найти в профессиональных справочниках.

Некоторые типы данных обеспечивают большинство операций, требующихся от стандартного контейнера, но все-таки не все. Иногда такие типы называют “почти контейнерами”. Перечислим наиболее интересные из них.

Программирование. Принципы и практика использования C++ Исправленное издание - _387.png

Б.4.1. Обзор

Операции, предусмотренные в стандартных контейнерах, можно проиллюстрировать следующим образом:

Программирование. Принципы и практика использования C++ Исправленное издание - _388.png

Б.4.2. Типы членов

Контейнер определяет множество типов его членов.

Программирование. Принципы и практика использования C++ Исправленное издание - _389.png

Б.4.3. Конструкторы, деструкторы и присваивания

Контейнеры имеют много разнообразных конструкторов и операторов присваивания. Перечислим конструкторы, деструкторы и операторы присваивания для контейнера C (например, типа

vector<double>
или
map<string,int>
).

Программирование. Принципы и практика использования C++ Исправленное издание - _390.png

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

Б.4.4. Итераторы

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

<
).

Программирование. Принципы и практика использования C++ Исправленное издание - _391.png

Б.4.5. Доступ к элементам

К некоторым элементам можно обратиться непосредственно.

Программирование. Принципы и практика использования C++ Исправленное издание - _392.png

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

Б.4.6. Операции над стеком и двусторонней очередью

Стандартные контейнеры

vector
и
deque
обеспечивают эффективные операции над концами (
back
) последовательности элементов. Кроме того, контейнеры
list
и
deque
обеспечивают аналогичные операции над началом (
front
) своей последовательности.

Программирование. Принципы и практика использования C++ Исправленное издание - _393.png

Обратите внимание на то, что функции

push_front()
и
push_back()
копируют элемент в контейнер. Это значит, что размер контейнера увеличивается (на единицу). Если копирующий конструктор элемента может генерировать исключения, то вставка может завершиться отказом.

Отметим, что операции удаления элементов не возвращают значений. Если бы они это делали, то копирующие конструкторы, генерирующие исключения, могли бы серьезно усложнить реализацию. Для доступа к элементам стека и очереди рекомендуем использовать функции

front()
и
back()
(см. раздел Б.4.5). Мы не ставили себе задачу перечислить все ограничения; попробуйте догадаться об остальных (как правило, компиляторы сообщают пользователям об их неверных догадках) или обратитесь к более подробной документации.

Б.4.7. Операции над списком

Ниже приведены операции над списком.

Программирование. Принципы и практика использования C++ Исправленное издание - _394.png

Результат

q
функции
insert()
ссылается на последний вставленный элемент. Результат
q
функции
erase()
ссылается на элемент, следующий за последним удаленным элементом.