C++17 STL Стандартная библиотека шаблонов

Добавление (или удаление) в начало (или конец) контейнера std::vector сразу многих объектов может повлечь выполнение большого количества операций выделения памяти для получения пространства, а также потенциально затратных операций по перемещению объектов. В таких ситуациях стоит воспользоваться контейнером std::deque (deque («дек») расшифровывается как double-ended queue (двусторонняя очередь)). Объекты хранятся в непрерывных фрагментах памяти, которые не зависят друг от друга. Это позволяет быстро увеличивать размер дека, поскольку объекты, расположенные в таких фрагментах памяти, не будут перемещаться, когда выделяется память для нового фрагмента и размещается в начале или конце контейнера.

Хранение списков

Контейнер std::list представляет собой классический двухсвязный список. Ни больше ни меньше. Если вам нужно выполнять обход списка только в одном направлении, то больше подойдет контейнер std::forward_list — он быстрее работает и занимает меньше места, поскольку в нем хранятся лишь указатели на следующий элемент. Пройти список можно только последовательно, за время O(n). Вставку и удаление элементов в заданную позицию можно выполнить за время O(1).

Деревья поиска

Если для объектов характерен естественный порядок, такой, что их можно отсортировать с использованием математического отношения <, то их можно поддерживать в этом же порядке с помощью деревьев поиска. Из названия следует: конкретный элемент дерева легко находится благодаря ключу поиска, что дает возможность выполнять эту операцию за время O(log(n)).

В STL есть несколько видов таких деревьев, самым простым является std::set — в нем хранятся уникальные сортируемые объекты.

Контейнер std::map отличается тем, что данные в нем хранятся парами. Пара состоит из ключа и значения. Дерево поиска использует ключ для сортировки элементов, таким образом можно задействовать std::map в качестве ассоциативного контейнера. Как и в случае с контейнером std::set, все ключи в дереве должны быть в единственном экземпляре.

Контейнеры std::multiset и std::multimap являются частными случаями контейнеров, показанных выше, для которых отсутствует требование уникальности ключей.

Хеш-таблицы

Деревья поиска не единственный способ реализации ассоциативных контейнеров. В хеш-таблицах элементы можно найти за время O(1), но они игнорируют естественный порядок элементов, поэтому не так просто пройти по упорядоченному списку. Пользователь может изменять размеры хеш-таблицы, можно даже выбрать отдельно хеш-функцию, что немаловажно, поскольку от этого зависят производительность и потребление памяти.

Контейнеры std::unordered_set и std::unordered_map весьма похожи на std::set и std::map, что можно утверждать на основании их взаимозаменяемости.

Как и реализации поисковых деревьев, у обоих контейнеров есть «коллеги» std::unordered_multiset и std::unordered_multimap, которые не имеют ограничения на уникальность объектов/ключей, поэтому можно хранить несколько элементов для одного ключа.

Адаптеры контейнеров

Массивы, списки, деревья и хеш-таблицы не единственный способ хранения данных и получения к ним доступа. Еще есть стеки, очереди и т.д. Аналогично тому, как более сложные структуры могут быть реализованы с использованием более примитивных, в STL такие структуры создаются благодаря следующим классам — адаптерам контейнеров: std::stack, std::queue и std::priority_queue.

Приятная новость: если нам нужна подобная структура данных, можно просто выбрать адаптер. Далее, понимая, что нас не устраивает производительность, мы можем просто изменить параметр шаблона, чтобы адаптер выбрал другую реализацию контейнера. На практике это значит, например, возможность замены находящейся в основе экземпляра std::stack реализации с std::vector на std::deque. 

Используем идиому erase-remove для контейнера std::vector

Многие программисты-новички узнают о существовании класса std::vector, который в основном работает как автоматически увеличивающийся массив, и останавливаются на этом. Далее они лишь ищут в документации сведения о том, как решать конкретные задачи, например удалять элементы. Такого рода использование контейнеров STL не задействует и сотой доли их возможностей в создании чистого, удобного в сопровождении и быстрого кода.