map и unordered_map: разница

Вопрос-крючок: «В чём разница между std::map и std::unordered_map, и почему их вывод на экран выглядит по-разному?»

#include <map>
#include <unordered_map>
#include <iostream>

int main() {
    std::map<std::string, int> ordered;
    std::unordered_map<std::string, int> hashed;

    for (auto& key : {"banana", "apple", "cherry"}) {
        ordered[key] = 1;
        hashed[key] = 1;
    }

    for (auto& [k, v] : ordered)
        std::cout << k << " ";
    std::cout << std::endl;

    for (auto& [k, v] : hashed)
        std::cout << k << " ";
}

Вывод:

apple banana cherry
cherry apple banana

Первая строка — map — вывела ключи строго по алфавиту, хотя вставляли мы их в другом порядке. Вторая строка — unordered_map — выдала порядок, который выглядит случайным (и на другом компьютере или в другой версии компилятора может быть вообще другим). Это не баг, а прямое следствие того, как устроены эти два контейнера внутри.

Что происходит и почему. std::map хранит элементы в виде сбалансированного дерева поиска — на практике почти всегда это красно-чёрное дерево. Каждый узел дерева знает, где лежат меньшие ключи (слева) и большие (справа), и структура дерева поддерживается автоматически сбалансированной при каждой вставке и удалении. Обход дерева «слева направо» (in-order обход) всегда даёт ключи в отсортированном порядке — вот почему map при переборе выводит ключи по алфавиту или числовому возрастанию, даже не прилагая к этому специальных усилий.

std::unordered_map устроен принципиально иначе — это хеш-таблица. У каждого ключа вычисляется хеш (число, полученное по специальной формуле из значения ключа), и по этому числу определяется, в какую «корзину» (bucket) положить пару ключ-значение. Порядок хранения корзин не имеет никакого отношения к алфавиту или величине ключей — он зависит от хеш-функции и текущего размера таблицы. Поэтому порядок обхода unordered_map непредсказуем и может отличаться даже между двумя запусками программы.

Как это работает под капотом. Из устройства контейнеров прямо следует разница в скорости. Поиск, вставка и удаление в красно-чёрном дереве — это спуск от корня до нужного листа, а высота сбалансированного дерева из n элементов — O(log n). Поэтому у map все основные операции стоят O(log n) — гарантированно, в худшем случае тоже.

У unordered_map поиск по хешу в среднем — O(1): вычислили хеш, сразу попали в нужную корзину, там обычно один-два элемента. Но это «в среднем» — важная оговорка. Если много разных ключей случайно (или намеренно, атакой) получают одинаковый хеш, в одной корзине скапливается много элементов, и поиск внутри неё вырождается в линейный перебор — O(n) в худшем случае. Хорошая хеш-функция такое явление (коллизии) сводит к минимуму, но теоретически оно возможно всегда.

Частые ошибки на собеседовании. Говорят «unordered_map всегда быстрее map» — это неточно: unordered_map быстрее в среднем, но map даёт предсказуемую гарантию O(log n) без просадок, что критично для систем реального времени. Забывают, что если алгоритму нужен отсортированный порядок ключей (например, для обхода диапазона значений через lower_bound/upper_bound) — с unordered_map это не сделать эффективно, там таких операций просто нет. И третья ошибка — не задумываются, что для unordered_map с пользовательским типом ключа (своя структура или класс) нужно самому написать хеш-функцию и оператор сравнения на равенство, иначе код не скомпилируется.

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