Контейнеры STL в C++: чек-лист перед выбором

Классическая ошибка: взяли std::list, потому что «часто вставляем в середину», получили в три раза более медленный проход по данным, чем на std::vector, — и не поняли почему. Или выбрали std::map, где нужен был std::unordered_map, и логарифм на каждом поиске превратился в заметную долю времени функции. Контейнер STL выбирается не по названию операции, а по тому, что с ним будет происходить в горячем цикле. Ниже — чек-лист, который проходишь до того, как зафиксировать тип. Ориентир — C++17 и новее (структурные привязки, try_emplace, contains для C++20).

Это разбор про выбор, а не про устройство красно-чёрного дерева. Внутренности упоминаются ровно настолько, насколько влияют на решение.

Вопрос первый: как вы обращаетесь к данным

Прежде чем спорить про сложность вставки, ответьте, что происходит чаще: обход всех элементов подряд или поиск по ключу. От этого зависит половина выбора.

• Обход подряд, доступ по индексу — std::vector. Данные лежат в непрерывной памяти, префетчер процессора работает на вас, кеш не промахивается. Ни один узловой контейнер (list, map, set) к этому близко не подойдёт.
• Поиск по ключу — std::unordered_map (в среднем O(1)) или std::map (O(log n), но с упорядоченным обходом).
• Проверка «есть ли элемент» в наборе — std::unordered_set / std::set.

Непрерывная память бьёт алгоритмическую сложность на реальных объёмах. Проход по vector из миллиона int почти всегда быстрее прохода по list из тех же элементов — даже если у списка вставка «дешевле» на бумаге.

Вопрос второй: инвалидация итераторов и ссылок

Это то, что ломает код молча — компилятор ничего не скажет, а при следующей вставке вы получите обращение к освобождённой памяти. Держите таблицу перед глазами.

Практический вывод: если вы держите указатель или ссылку на элемент и параллельно вставляете новые, vector — мина. Для такого сценария берут deque, list или узловой ассоциативный контейнер.

Вопрос третий: реальная стоимость операций

Асимптотика — это половина правды. Вторая половина — константа и поведение кеша.

vector: вставка не в конец дорогая

Вставка в конец через push_back — амортизированное O(1). Вставка или удаление в середине — O(n), потому что сдвигаются все элементы правее. Если вы часто удаляете из середины и порядок не важен, используйте приём swap-and-pop:

#include <vector>
#include <utility>

// Удаление элемента по индексу без сдвига хвоста.
// Порядок элементов при этом нарушается — годится, когда он не важен.
void remove_unordered(std::vector<int>& data, std::size_t index) {
    std::swap(data[index], data.back()); // меняем с последним
    data.pop_back();                     // удаляем последний за O(1)
}

map против unordered_map

std::map — дерево, ключи всегда отсортированы, поиск O(log n), обход в порядке ключей. std::unordered_map — хеш-таблица, поиск в среднем O(1), но обход в произвольном порядке и риск деградации до O(n) при плохой хеш-функции или атаке на коллизии.

Берите map, когда нужен упорядоченный обход, диапазонные запросы (lower_bound, upper_bound) или предсказуемая латентность без всплесков от рехеша. Берите unordered_map, когда нужен максимально быстрый поиск и порядок безразличен.

Вопрос четвёртый: вставка без лишних копий

Частая потеря производительности — временный объект, который создаётся и тут же копируется в контейнер. С C++11 есть emplace, с C++17 — try_emplace для ассоциативных контейнеров.

#include <map>
#include <string>

std::map<int, std::string> cache;

// try_emplace конструирует значение только если ключа ещё нет.
// Если ключ есть — второй аргумент даже не вычисляется.
cache.try_emplace(42, "expensive_default");

// insert_or_assign обновляет значение, если ключ уже есть.
cache.insert_or_assign(42, "new_value");

Разница с operator[]: map[key] = value сначала вставит дефолтный элемент, потом присвоит — для тяжёлых типов это лишняя работа. try_emplace её избегает.

Чек-лист перед фиксацией типа

1. Что чаще — обход или поиск по ключу? Обход подряд — vector. Поиск — ассоциативный контейнер.
2. Нужен ли порядок элементов? Да, по ключу — map/set. Порядок вставки — vector. Безразличен — unordered_*.
3. Держите ли вы ссылки/указатели на элементы при модификации? Да — избегайте vector, смотрите таблицу инвалидации.
4. Знаете ли размер заранее? Да и это vector — вызовите reserve(), чтобы убить реаллокации.
5. Часто вставляете/удаляете в середину? Да и порядок важен — list. Порядок не важен — swap-and-pop на vector.
6. Ключи — строки или сложные объекты? Для unordered_* проверьте, что хеш-функция вменяемая; иначе map предсказуемее.

Что ломается на практике

• Итератор после erase. vector::erase и ассоциативные контейнеры возвращают итератор на следующий элемент — используйте его: it = c.erase(it);. Не инкрементируйте вручную удалённый итератор.
• operator[] у map создаёт элемент. Обращение m[key] к отсутствующему ключу молча вставит дефолтное значение. Для проверки наличия — find() или contains() (C++20).
• Реаллокация vector в цикле. Push_back в цикле без reserve — это серия реаллокаций и копирований. Если храните указатели на элементы этого же вектора — они станут висячими.
• Хеш пользовательского типа. Чтобы положить свой тип в unordered_map, нужна специализация std::hash и оператор ==. Забыли — не скомпилируется, но сообщение об ошибке будет длинным и неочевидным.

Инвалидация в многопоточном доступе — отдельная тема: контейнеры STL не потокобезопасны для одновременной записи, здесь это не рассматриваем.

Что делать дальше

После выбора контейнера прогоните горячий участок под профилировщиком — perf на Linux или встроенный профайлер вашей IDE — и посмотрите на промахи кеша (cache-misses в perf), а не только на время. Если vector с reserve и swap-and-pop закрывает сценарий, узловые контейнеры чаще всего проигрывают. Для узкоспециализированных случаев смотрите в сторону std::flat_map (C++23) — упорядоченный map поверх непрерывной памяти, который в чтении обгоняет обычный map.