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

Статический массив  array предоставляет доступ к элементам через итератор произвольного доступа и является оберткой над статическим массивом T[N], адрес которого можно получить функцией data. В отличие от T[N] array является полноценным типом, значения которого можно копировать (передавать в функции по значению), значения которого не конвертируются автоматически в указатели на них. Наконец, при желании array можно использовать в качестве базового класса (но с осторожностью, как и любой контейнер, так как стандартные контейнеры не предназначены для такой цели и, в частности, не содержат виртуальных функций). Адресовать элементы по индексу можно так же, как в случае deque и vector. Изменять количество элементов нельзя, поэтому никаких функций для вставки и удаления элементов array не предоставляет. Функция fill заполняет массив копиями переданного значения.
2. Контейнеры
Контейнеры библиотеки STL можно разделить на четыре категории: последовательные, ассоциативные, контейнеры-адаптеры и псевдоконтейнеры.

Контейнер	Описание
Последовательные контейнеры
vector	C-подобный динамический массив произвольного доступа с автоматическим изменением размера при добавлении/удалении элемента. Доступ по индексу за O(1). Добавление-удаление элемента в конец vector занимает амортизированное O(1) время, та же операция в начале или середине vector — O(n). Стандартная быстрая сортировка за O(n * log(n)). Поиск элемента перебором занимает O(n). Существует специализация шаблона vector для типа bool, которая требует меньше памяти за счёт хранения элементов в виде битов, однако она не поддерживает всех возможностей работы с итераторами.
list	Двусвязный список, элементы которого хранятся в произвольных кусках памяти, в отличие от контейнера vector, где элементы хранятся в непрерывной области памяти. Поиск перебором медленнее, чем у вектора из за большего времени доступа к элементу. Доступ по индексу за O(n). В любом месте контейнера вставка и удаление производятся очень быстро - за O(1).
deque	Дэк. Контейнер похож на vector, но с возможностью быстрой вставки и удаления элементов на обоих концах за O(1). Реализован в виде двусвязанного списка линейных массивов.