Исполняемые доки C++: unordered_map

Q: В чём разница между map и unordered_map в C++?

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

Q: Вставляет ли unordered_map[] ключ, если его нет?

Да. m[key] создаёт по умолчанию и вставляет ключ, если он отсутствует, а затем возвращает ссылку на него. Это значит, что даже выглядящий как чтение if (m[key] == ...) незаметно увеличивает map. Чтобы проверить наличие без вставки, используйте m.count(key) или m.find(key).

Q: Всегда ли unordered_map быстрее map в C++?

Нет. Это O(1) в среднем, но у хеширования есть накладные расходы, и плохой хеш (или враждебно подобранные ключи) может ухудшить поиск до O(n). Для небольших map постоянные множители и худшее поведение кеша могут сделать отсортированный map таким же быстрым или даже быстрее. Замеряйте, если это важно, но по умолчанию выбирайте unordered_map, когда нужен только поиск по ключу.

Когда порядок не важен

Вы только что видели std::map, который держит ключи отсортированными с помощью сбалансированного дерева и даёт операции за O(log n). Но сортировка чего-то стоит, и зачастую вам всё равно, в каком порядке выходят ключи — вы просто хотите как можно быстрее спросить: «есть ли здесь этот ключ и каково его значение?»

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

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> stock = {
        {"apple", 12},
        {"banana", 7},
        {"cherry", 30}
    };

    cout << "bananas: " << stock["banana"] << "\n";
    stock["apple"] += 5;
    cout << "apples now: " << stock["apple"] << "\n";
}

Интерфейс намеренно почти идентичен map — зачастую вы можете заменить один на другой, просто изменив тип. Подключите <unordered_map> (а не <map>), и ключи будут выходить неотсортированными.

Вставка и обновление

Есть несколько способов добавить записи, и ведут они себя по-разному. Два, которые вы будете использовать чаще всего, — это operator[] и insert:

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> votes;

    votes["alice"] = 3;              // создать или перезаписать
    votes["alice"] = 5;              // перезаписывает -> 5
    votes.insert({"bob", 2});        // вставляет, только если "bob" отсутствует
    votes.insert({"bob", 99});       // игнорируется, "bob" уже есть

    cout << "alice: " << votes["alice"] << "\n";   // 5
    cout << "bob:   " << votes["bob"] << "\n";      // 2, не 99
}

Ключевое различие: operator[] перезаписывает существующее значение, тогда как insert оставляет уже существующий ключ нетронутым. Если вы на C++17, insert_or_assign(key, value) даёт семантику «установить это в любом случае», а try_emplace(key, args...) создаёт значение на месте только тогда, когда ключ новый — удобно для значений, дорогих в построении.

Ловушка operator[]: он вставляет при чтении

Это самая частая ошибка с unordered_map, поэтому ей посвящён отдельный раздел. m[key] — это не чистое чтение. Если ключ отсутствует, он создаёт его по умолчанию и вставляет (int становится 0, string становится ""), а затем возвращает ссылку. Так что код, который выглядит как поиск, незаметно увеличивает map:

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> seen;
    seen["x"] = 1;

    // Мы хотели лишь ПРОВЕРИТЬ "y", но [] вставил его:
    if (seen["y"] == 0) {
        cout << "y looked missing...\n";
    }

    cout << "size is now " << seen.size() << "\n";   // 2, а не 1!
}

seen["y"] создал запись "y" -> 0 лишь от одного упоминания. Чтобы проверить наличие, не изменяя map, используйте count (возвращает 0 или 1) или find:

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> seen{{"x", 1}};

    if (seen.count("y")) {
        cout << "found y\n";
    } else {
        cout << "no y, size still " << seen.size() << "\n";   // 1
    }

    // C++20: contains() читается чище, чем count()
    if (seen.contains("x")) cout << "x is here\n";
}

Правило большого пальца: используйте [] только тогда, когда намерены создать или обновить. Для чистого чтения используйте count, contains (C++20) или find.

find и at: безопасный поиск

find возвращает итератор на запись или end(), если ключ отсутствует. Он никогда не вставляет и позволяет добраться и до ключа, и до значения через it->first и it->second за один поиск:

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> prices = {{"pen", 2}, {"mug", 9}};

    auto it = prices.find("mug");
    if (it != prices.end()) {
        cout << it->first << " costs " << it->second << "\n";
    } else {
        cout << "not found\n";
    }
}

Когда вы знаете, что ключ должен существовать, и хотите жёсткого отказа, если это не так, используйте at. В отличие от [], at не вставляет — он бросает std::out_of_range при отсутствующем ключе:

int p = prices.at("pen");   // нормально
int q = prices.at("hat");   // бросает std::out_of_range - ключа нет

Итак, у вас есть три стиля поиска: [] (вставляет), at (бросает) и find/count (сообщают о наличии, не трогая map). Выбирайте тот, чьё поведение при сбое соответствует вашему намерению.

Перебор и удаление

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

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> wins = {{"red", 4}, {"blue", 7}, {"green", 2}};

    for (const auto& [team, score] : wins) {
        cout << team << ": " << score << "\n";   // порядок не определён
    }
}

Чтобы удалить запись, erase принимает ключ напрямую и возвращает, сколько было удалено (0 или 1). Важная ловушка: в unordered_map удаление во время перебора делает недействительным только итератор удалённого элемента, поэтому используйте возвращаемое значение erase(it), чтобы безопасно продвигаться:

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> wins = {{"red", 4}, {"blue", 1}, {"green", 2}};

    // Удалить каждую команду со счётом меньше 3
    for (auto it = wins.begin(); it != wins.end(); ) {
        if (it->second < 3)
            it = wins.erase(it);   // erase возвращает следующий действительный итератор
        else
            ++it;
    }

    cout << "remaining entries: " << wins.size() << "\n";
}

Запись в стиле wins.erase(it++) или ++it после простого erase(it) — это классическая ловушка повисшего итератора: удалённый итератор мёртв, поэтому всегда берите итератор, возвращаемый erase.

map или unordered_map?

Оба хранят пары ключ-значение со схожим API, так что выбор сводится к тому, что вам нужно:

// std::map            -> отсортированные ключи, O(log n), запросы по диапазону (lower_bound)
// std::unordered_map  -> без порядка,           O(1) в ср., самый быстрый простой поиск

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

Далее: Set

Теперь вы видели обе разновидности контейнеров ключ-значение. Однако иногда значение вам вовсе не нужно — вас интересует лишь то, присутствует ли что-то, например коллекция уникальных тегов или посещённых ID. Далее мы рассмотрим std::set (и его основанного на хешах родственника unordered_set), которые хранят только ключи и автоматически держат их уникальными.

Часто задаваемые вопросы

В чём разница между map и unordered_map в C++?

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

Вставляет ли unordered_map[] ключ, если его нет?

Да. m[key] создаёт по умолчанию и вставляет ключ, если он отсутствует, а затем возвращает ссылку на него. Это значит, что даже выглядящий как чтение if (m[key] == ...) незаметно увеличивает map. Чтобы проверить наличие без вставки, используйте m.count(key) или m.find(key).

Всегда ли unordered_map быстрее map в C++?

Нет. Это O(1) в среднем, но у хеширования есть накладные расходы, и плохой хеш (или враждебно подобранные ключи) может ухудшить поиск до O(n). Для небольших map постоянные множители и худшее поведение кеша могут сделать отсортированный map таким же быстрым или даже быстрее. Замеряйте, если это важно, но по умолчанию выбирайте unordered_map, когда нужен только поиск по ключу.

Связанные концепции