unordered_map w C++: szybka tablica mieszająca (hash map)

Gdy kolejność nie ma znaczenia

Poprzednia strona przedstawia std::map, które trzyma klucze posortowane w zrównoważonym drzewie i daje operacje w O(log n). Sortowanie ma jednak swoją cenę, a bardzo często nie obchodzi cię, w jakiej kolejności wychodzą klucze: chcesz tylko jak najszybciej zapytać "czy ten klucz tu jest i jaka jest jego wartość?".

Do tego służy std::unordered_map. To tablica mieszająca (hash table): przepuszcza każdy klucz przez funkcję mieszającą, żeby zdecydować, gdzie go zapisać, dzięki czemu wstawianie, wyszukiwanie i usuwanie mają średnio O(1) zamiast O(log n). Ceną jest nieokreślona kolejność iteracji: klucze wychodzą w takiej kolejności, w jakiej akurat leżą w kubełkach.

#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";
}

Interfejs jest celowo prawie identyczny jak w map: często możesz zamienić jedno na drugie, zmieniając tylko typ. Dołącz <unordered_map> (a nie <map>), a klucze będą wychodzić nieposortowane.

Wstawianie i aktualizacja

Jest kilka sposobów dodawania wpisów i nie wszystkie zachowują się tak samo. Najczęściej używane to operator[] i insert:

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

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

    votes["alice"] = 3;              // tworzy albo nadpisuje
    votes["alice"] = 5;              // nadpisuje -> 5
    votes.insert({"bob", 2});        // wstawia tylko, jeśli "bob" nie istnieje
    votes.insert({"bob", 99});       // zignorowane, "bob" już istnieje

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

Kluczowa różnica: operator[] nadpisuje istniejącą wartość, a insert zostawia istniejący klucz w spokoju. W C++17 insert_or_assign(key, value) daje semantykę "ustaw bez względu na wszystko", a try_emplace(key, args...) tworzy wartość w miejscu tylko wtedy, gdy klucz jest nowy, co przydaje się przy wartościach kosztownych w budowie.

Pułapka operator[]: wstawia przy odczycie

To najczęstszy błąd związany z unordered_map, więc ma własną sekcję. m[key] nie jest czystym odczytem. Jeśli klucza brakuje, operator tworzy wartość domyślną i ją wstawia (int staje się 0, string staje się ""), a potem zwraca referencję. Kod, który wygląda na wyszukiwanie, po cichu powiększa więc mapę:

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

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

    // Chcieliśmy tylko SPRAWDZIĆ "y", ale [] go wstawił:
    if (seen["y"] == 0) {
        cout << "y looked missing...\n";
    }

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

seen["y"] utworzyło wpis "y" -> 0 samym tym, że zostało użyte. Aby sprawdzić obecność bez zmieniania mapy, użyj count (zwraca 0 lub 1) albo 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() czyta się lepiej niż count()
    if (seen.contains("x")) cout << "x is here\n";
}

Praktyczna zasada: używaj [] tylko wtedy, gdy chcesz utworzyć lub zaktualizować wpis. Do czystych odczytów służą count, contains (C++20) albo find.

find i at: bezpieczne wyszukiwanie

find zwraca iterator do wpisu albo end(), gdy klucza nie ma. Nigdy niczego nie wstawia i pozwala w jednym wyszukiwaniu dostać się zarówno do klucza, jak i do wartości przez it->first oraz 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";
    }
}

Gdy wiesz, że klucz powinien istnieć, i chcesz twardego błędu, jeśli go nie ma, użyj at. W przeciwieństwie do [] metoda at niczego nie wstawia: dla brakującego klucza rzuca std::out_of_range:

int p = prices.at("pen");   // w porządku
int q = prices.at("hat");   // rzuca std::out_of_range: klucza nie ma

Masz więc trzy style wyszukiwania: [] (wstawia), at (rzuca wyjątek) oraz find/count (informują o obecności, nie ruszając mapy). Wybierz ten, którego zachowanie przy braku klucza pasuje do twojego zamiaru.

Iteracja i usuwanie

Pętla for po zakresie ze structured bindings to czysty sposób na przejście po wszystkich wpisach. Pamiętaj, że kolejność jest dowolna: nigdy na niej nie polegaj:

#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";   // kolejność jest nieokreślona
    }
}

Aby usunąć wpis, erase przyjmuje bezpośrednio klucz i zwraca liczbę usuniętych elementów (0 lub 1). Ważna pułapka: usuwanie w trakcie iteracji unieważnia w unordered_map tylko iterator usuniętego elementu, więc do bezpiecznego przejścia dalej używaj wartości zwracanej przez 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}};

    // Usuń każdą drużynę z wynikiem poniżej 3
    for (auto it = wins.begin(); it != wins.end(); ) {
        if (it->second < 3)
            it = wins.erase(it);   // erase zwraca następny poprawny iterator
        else
            ++it;
    }

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

Zapis w stylu wins.erase(it++) albo ++it po zwykłym erase(it) to klasyczna pułapka wiszącego iteratora: usunięty iterator jest martwy, więc zawsze bierz iterator zwrócony przez erase.

map czy unordered_map?

Oba kontenery przechowują pary klucz-wartość z podobnym API, więc wybór zależy od tego, czego potrzebujesz:

// std::map            -> klucze posortowane, O(log n), zapytania o zakresy (lower_bound)
// std::unordered_map  -> bez kolejności,     średnio O(1), najszybsze zwykłe wyszukiwanie

Sięgaj po unordered_map, gdy potrzebujesz tylko szybkiego wyszukiwania po kluczu, a kolejność jest bez znaczenia (liczenie częstości słów, cache, usuwanie duplikatów). Wybierz map, gdy potrzebujesz kluczy w kolejności posortowanej, chcesz iterować po kolei albo wykonujesz zapytania o zakresy. Dwa zastrzeżenia dotyczące unordered_map: jego O(1) to wartość średnia, którą słaba funkcja mieszająca może pogorszyć, a własny typ klucza wymaga specjalizacji hash albo funktora mieszającego, podczas gdy map potrzebuje tylko operator<.

Dalej: set

Znasz już oba rodzaje kontenerów klucz-wartość. Czasem jednak w ogóle nie potrzebujesz wartości: interesuje cię tylko, czy coś jest obecne, na przykład w kolekcji unikalnych tagów albo odwiedzonych identyfikatorów. Następnie przyjrzymy się std::set (i jego kuzynowi opartemu na haszowaniu, unordered_set), które przechowują same klucze i automatycznie dbają o ich unikalność.