std::map и std::unordered_map в C++: что выбрать и как использовать

Два разных «словаря»

В стандартной библиотеке C++ нет контейнера «dict» — есть std::map и std::unordered_map. Оба хранят пары ключ-значение, но построены принципиально по-разному, и это определяет всё остальное.

std::map — это красно-чёрное дерево. Ключи всегда отсортированы. Поиск, вставка и удаление — O(log n). Требование к ключу: должен существовать operator< (или свой компаратор).

std::unordered_map — хэш-таблица. Порядок ключей не определён, средняя сложность операций — O(1). Требования к ключу: operator== и хэш-функция (для встроенных типов есть std::hash).

#include <map>
#include <unordered_map>

std::map<std::string, int> sorted;         // дерево, упорядочено
std::unordered_map<std::string, int> fast; // хэш-таблица, быстрее

Практическое правило: нужен порядок или диапазоны — map; нужна только скорость поиска — unordered_map. По умолчанию на больших данных берите unordered_map.

Базовые операции

std::unordered_map<std::string, int> scores;

// вставка / обновление
scores["alice"] = 10;            // создаст или перезапишет
scores.emplace("bob", 20);       // не перезапишет существующий
scores.insert_or_assign("bob", 25); // C++17: вставит или обновит

// поиск
auto it = scores.find("alice");
if (it != scores.end()) {
    std::cout << it->second;     // доступ к значению
}
if (scores.contains("bob")) { }  // C++20 — удобная проверка

// безопасное чтение с дефолтом
int v = scores.count("carol") ? scores.at("carol") : 0;

Осторожно с operator[]: чтение scores["missing"] создаёт элемент со значением по умолчанию. Это частый источник раздутых мап и скрытых багов. Для «чтения без создания» — find, count или at (кидает out_of_range).

Типичная задача: счётчики и группировка

Подсчёт частот — идеальный пример, где operator[] как раз удобен:

std::unordered_map<std::string, int> freq;
for (const auto& word : words)
    ++freq[word];                // отсутствующее слово -> 0, затем инкремент

Группировка объектов по признаку:

struct User { std::string city; int age; };

std::map<std::string, std::vector<User>> byCity;
for (const auto& u : users)
    byCity[u.city].push_back(u); // города автоматически отсортированы

try_emplace и шаблон «вставь, если нет»

В C++17 появился try_emplace: вставляет, только если ключа нет, и — главное — не конструирует значение, если ключ уже есть. Это важно для тяжёлых объектов:

std::map<int, Expensive> cache;

// создаст объект, даже если ключ уже есть — потому что аргумент уже сконструирован
cache.emplace(1, Expensive{/*...*/});

// сконструирует только при отсутствии ключа
cache.try_emplace(1, /*аргументы конструктора*/);

Результат — пара iterator + bool:

auto [it, inserted] = cache.try_emplace(5, arg1, arg2);
if (inserted) { /* новый элемент */ }

Итерация и порядок

По map итерируемся в порядке возрастания ключей, по unordered_map — в «случайном» (порядок бакетов, не гарантирован и может меняться при рехэшировании):

for (const auto& [key, value] : scores)   // structured bindings C++17
    std::cout << key << " = " << value << "\n";

Если нужен и быстрый поиск, и порядок вставки — комбинируют unordered_map с vector указателей/индексов, либо берут flat-мапы из сторонних библиотек (boost::flat_map, absl).

Свои типы как ключи

Для map достаточно сравнения:

struct Key {
    int a, b;
    bool operator<(const Key& o) const {
        return std::tie(a, b) < std::tie(o.a, o.b);
    }
};
std::map<Key, std::string> m;

Для unordered_map нужны равенство и хэш:

struct KeyHash {
    std::size_t operator()(const Key& k) const {
        // комбинируем хэши полей; xor + сдвиги или boost::hash_combine
        return std::hash<int>{}(k.a) ^ (std::hash<int>{}(k.b) << 1);
    }
};
std::unordered_map<Key, std::string, KeyHash> um;

Правило для хэша: равные ключи обязаны давать равный хэш (обратное не обязано).

multiset, multimap и прочие родственники

std::set / std::unordered_set — только ключи, без значений.
std::multimap / std::multiset — ключи могут повторяться; equal_range даёт диапазон одинаковых.
lower_bound/upper_bound в map/set — поиск границ диапазона: удобно для интервалов, «ближайшего ключа» и т.п.

std::map<int, std::string> timeline;
timeline[100] = "старт"; timeline[300] = "финиш";

// ближайшее событие не позже времени t
auto it = timeline.upper_bound(150);   // первый ключ > 150
if (it != timeline.begin()) --it;      // 100 — "старт"

Производительность: что реально важно

unordered_map медленнее ожиданий на маленьких данных из-за хэширования и плохой локальности кэша; выигрывает на тысячах+ элементов.
Резервирование: um.reserve(n) и um.max_load_factor(0.7) уменьшают рехэширование.
Строковые ключи: unordered_map<std::string, ...> хэширует всю строку; для коротких ключей приемлемо.
Вставки по месту: emplace/try_emplace вместо operator[] с временными объектами.

Итог

unordered_map — поиск за O(1) и работа в большинстве задач. map — когда нужны сортировка ключей, диапазоны и lower_bound. Помните про побочный эффект operator[] при чтении, используйте try_emplace для дорогих значений, а для своих ключей — std::tie в < и комбинирование хэшей.

Практический пример: инвертированный индекс

Классическая задача «слово → список документов»:

std::unordered_map<std::string, std::vector<int>> index;

for (int docId = 0; docId < docs.size(); ++docId)
    for (const auto& word : tokenize(docs[docId]))
        index[word].push_back(docId);

// поиск всех документов со словом
auto it = index.find("arduino");
if (it != index.end())
    for (int id : it->second) showDoc(id);

Мапа здесь — именно индекс: поиск за O(1) вместо сканирования всех документов.

Пример: LRU-кэш на map + list

LRU-кэш — комбинация list (порядок использования) и unordered_map (доступ за O(1)):

std::list<std::pair<Key, Val>> lru;                 // свежие в начале
std::unordered_map<Key, decltype(lru.begin())> pos; // ключ → итератор

Val get(Key k) {
    auto it = pos.find(k);
    if (it == pos.end()) return {};
    lru.splice(lru.begin(), lru, it->second);       // элемент в начало
    return it->second->second;
}

Так устроены кэши в реальных системах — каждый доступ поднимает элемент в начало, вытеснение с хвоста.

Выбор между map и unordered_map: чек-лист

Берите map, если:

нужна итерация по отсортированным ключам;
нужны диапазоны (lower_bound, upper_bound, equal_range);
данных мало (< нескольких сотен) — дерево эффективнее хэша по кэшу.

Берите unordered_map, если:

порядок ключей не важен;
много вставок и поисков на большом объёме;
ключи быстро хэшируются (int, короткие строки).

Сет вместо мапы

Когда нужно «есть/нет» без значения — unordered_set:

std::unordered_set<std::string> banned;
if (banned.count(ip)) { /* заблокировать */ }
banned.insert(ip);

unordered_set — та же хэш-таблица, только без значений.

Частая ошибка: изменение ключа

Ключи в map/set немутируемы: изменение ключа ломает дерево/хэш. Чтобы «переименовать» — удалите старый и вставьте новый. В C++17 есть extract — вынуть узел, поменять ключ, вставить обратно без перевыделения:

auto node = m.extract(oldKey);
if (node) { node.key() = newKey; m.insert(std::move(node)); }