Контейнеры (Коллекции). Stl бибилиотеки. Линейные контейнеры array

Двусвязный список  list> предоставляет доступ к элементам через двунаправленный итератор. В отличие от односвязного списка элементы вставляются перед заданной позицией (функции insert, emplace, splice), доступна вставка и удаление с конца (push_back, emplace_back, pop_back), удаление элемента, на который указывает итератор (erase). Функции вида *_after отсутствуют.

Дек  deque> предоставляет доступ к элементам через итератор произвольного доступа. Так же, как и list, позволяет эффективно добавлять и удалять элементы с обоих концов. Для доступа по индексу предназначены две функции: оператор [] и at(индекс). В отличие от первой вторая проверяет индекс и в случае недопустимого значения бросает исключение out_of_range.
Контейнер deque допускает выполнение вставки и удаления элементов в произвольной позиции аналогично list, однако в случае deque эти операции затратны: могут требовать времени линейного по размеру контейнера. Кроме того, необходимо помнить, что вставка и удаление элементов может “испортить” ранее сохраненные итераторы или указатели из-за потенциального перемещения хранимых элементов в памяти (в то время как итераторы списков сохраняются, если элементы, на которые они указывают, не были удалены).

Динамический массив  или вектор (см. также здесь) vector> предоставляет доступ к элементам через итератор произвольного доступа. В отличие от deque не позволяет вставлять и удалять элементы в начале. Динамический массив гарантирует расположение хранимых элементов подряд в непрерывном участке памяти, адрес которого возвращает функция data. При добавлении элементов и исчерпании заранее выделенного хранилища может быть выделен новый динамический массив большего размера, куда будут перенесены элементы. Старое хранилище при этом удаляется, все сохраненные итераторы “портятся” и становятся эквивалентны указателям на удаленные объекты.
Массив позволяет заранее подготовить хранилище достаточного размера с помощью функции reserve (может вызвать перемещение элементов). Узнать размер хранилища можно с помощью функции capacity. Функция shrink_to_fit выделяет хранилище размера, равного реально занятому, и переносит туда элементы, освобождая незанятую память.