STL-контейнеры: что выбрать под задачу и чем платишь

Задача звучит невинно: «нужно хранить набор объектов и быстро находить нужный». Разработчик берёт std::map, потому что «там же поиск за логарифм», и через полгода профилировщик показывает, что программа половину времени гуляет по указателям и промахивается мимо кеша. При том же алгоритмическом классе сложности разница между контейнерами на реальных данных доходит до 10–50 раз. Ниже — как выбирать, исходя из паттерна доступа, а не из привычки.

Всё, что описано, относится к стандартной библиотеке C++ по стандарту C++17 и новее (компиляторы GCC 11+, Clang 13+, MSVC 19.3x). Конкретные константы вроде размера узла или коэффициента роста vector стандартом не заданы — это детали реализации, и полагаться на них нельзя.

Почему «сложность в нотации O» решает не всё

Асимптотика описывает, как растёт время с увеличением N, но молчит про константу. А именно константа определяет, кто победит на N в тысячи и десятки тысяч элементов — то есть на размерах, которые встречаются чаще всего.

Главный источник этой константы сегодня — не число операций, а обращения к памяти. Процессор читает память кеш-линиями (обычно 64 байта). Данные, лежащие подряд, подтягиваются пачкой и обрабатываются почти бесплатно. Данные, разбросанные по куче узлами связного списка или дерева, вызывают промах кеша на каждом шаге — а промах в L3 или в RAM стоит сотни тактов.

Линейный проход по vector из миллиона int часто быстрее «логарифмического» поиска по map с тем же миллионом элементов — просто потому, что первый идёт по кешу, а второй прыгает по указателям.

Отсюда практический принцип: сначала спросите, как вы обращаетесь к данным (в конце, в начале, в середине, по ключу, по порядку), и только потом выбирайте контейнер.

Последовательные контейнеры

vector — выбор по умолчанию

std::vector хранит элементы в одном непрерывном блоке. Это даёт лучшую в STL локальность и произвольный доступ по индексу за O(1). Вставка и удаление в конце амортизированно O(1), но в начале или в середине — O(N), потому что хвост приходится сдвигать.

Скрытая цена — реаллокация. Когда ёмкость исчерпана, vector выделяет новый блок (обычно в 1.5–2 раза больше, коэффициент зависит от реализации), копирует или перемещает элементы и освобождает старый. Это инвалидирует все указатели, ссылки и итераторы на элементы. Если вы знаете размер заранее — вызывайте reserve, это убирает лишние реаллокации.

#include <vector>

std::vector<int> ids;
ids.reserve(10000);        // одна аллокация вместо десятка
for (int i = 0; i < 10000; ++i)
    ids.push_back(i);      // без reserve здесь были бы реаллокации

Отдельная ловушка — std::vector<bool>. Это не контейнер булей, а специализация с битовой упаковкой: operator[] возвращает прокси-объект, а не bool&. Если нужен обычный массив булей — берите std::vector<char> или std::deque<bool>.

deque — когда растёт с обоих концов

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

Типичное применение — очередь или буфер, куда пишут с одной стороны и читают с другой. std::queue и std::stack по умолчанию построены как раз на deque.

list и forward_list — почти всегда мимо

std::list (двусвязный) и std::forward_list (односвязный) дают O(1) вставку и удаление в любой точке — если у вас уже есть итератор на это место. Итераторы и указатели остаются валидными при любых вставках и удалениях соседей. Это единственное реальное преимущество.

Плата тяжёлая: каждый элемент — отдельная аллокация с указателями, никакого доступа по индексу, и катастрофическая локальность. На практике list проигрывает vector даже там, где алгоритмически «должен» выигрывать: удаление из середины vector со сдвигом часто быстрее прыжков по узлам списка. Берите list, только если вам критична стабильность итераторов при частых перестановках, либо нужен дешёвый splice — перенос узлов между списками без копирования.

Ассоциативные контейнеры

map / set — упорядоченные, на дереве

std::map и std::set обычно реализованы как красно-чёрное дерево. Операции поиска, вставки и удаления — O(log N). Ключи хранятся в отсортированном порядке, поэтому обход даёт элементы по возрастанию, а lower_bound/upper_bound позволяют искать диапазоны. Указатели и итераторы на элементы стабильны при вставках и удалениях других элементов.

Цена — та же, что у списка: каждый узел отдельно в куче, обход дерева прыгает по указателям. Логарифм здесь с большой константой.

unordered_map / unordered_set — хеш-таблица

std::unordered_map и std::unordered_set дают поиск, вставку и удаление за амортизированные O(1), но порядок элементов не определён. Реализация — хеш-таблица с цепочками (bucket'ы со списками), поэтому по локальности она ближе к list, чем к vector.

Что бьёт по производительности на практике:

• Рехеш. Когда фактор загрузки превышает max_load_factor (по умолчанию 1.0), таблица перестраивается. Если знаете число элементов — вызовите reserve, чтобы избежать серии рехешей.
• Плохой хеш. Свой тип ключа требует специализации std::hash. Слабая хеш-функция скучивает ключи в одни bucket'ы, и O(1) вырождается в O(N).
• Инвалидация. Рехеш инвалидирует итераторы, но указатели и ссылки на сами элементы остаются валидны — узлы не двигаются. Это отличие от vector.

#include <unordered_map>
#include <string>

std::unordered_map<std::string, int> counters;
counters.reserve(100000);   // избегаем серии рехешей при наполнении
++counters["clicks"];       // вставка ключа при отсутствии — тоже O(1) амортизированно

Таблица сравнения

* амортизированно; ** амортизированно, при хорошем хеше.

Когда что выбирать

• Просто набор, перебор целиком, добавление в конец — vector. По умолчанию берите его и меняйте, только когда профиль показал проблему.
• Поиск по ключу, порядок не важен — unordered_map. Не забудьте reserve и вменяемый хеш.
• Поиск по ключу и нужен порядок или диапазоны (lower_bound, обход по возрастанию) — map.
• Очередь с двух концов, буфер FIFO — deque.
• Частые вставки/удаления в середине с сохранением итераторов, splice — list. Это узкий случай.
• Маленький набор (единицы–десятки элементов) с поиском — часто быстрее отсортированный vector с std::lower_bound, чем map: линейный блок памяти бьёт дерево на малых N.

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

• Висячие указатели после push_back. Сохранили указатель или итератор на элемент vector, потом добавили ещё — реаллокация, указатель невалиден. Либо reserve заранее, либо храните индекс, либо берите контейнер со стабильными адресами.
• Дефолтный хеш для своего типа. Компилятор не найдёт std::hash для вашей структуры и упадёт с ошибкой. Нужно писать специализацию или передавать хешер третьим параметром шаблона.
• map::operator[] вставляет. Обращение m[key] при отсутствии ключа создаёт элемент со значением по умолчанию. Для «только проверить наличие» — find или contains (C++20).
• Выбор по чувству, а не по замеру. «list быстрее вставляет» — теория; на кеше современного процессора это часто неправда. Проверяйте на своих данных.

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

Перед тем как менять контейнер «на глаз», снимите профиль: perf stat на Linux покажет долю промахов кеша (cache-misses), а обычный профилировщик — где программа реально проводит время. Если узкое место — обход структуры с прыжками по указателям, это сигнал в сторону vector или плоских (open-addressing) хеш-таблиц из сторонних библиотек. Смотрите на две метрики: время операции на ваших N и число промахов кеша до и после замены — именно они, а не буква O, скажут, стало ли лучше.