`std::unordered_map` în C++

Dicționar bazat pe tabelă hash: căutare în timp mediu constant, dar fără o ordine anume a elementelor.

Sintaxă

#include <unordered_map>

std::unordered_map<Cheie, Valoare> nume;

Ce face `std::unordered_map`

std::unordered_map are aceeași interfață de bază ca std::map: operator[] (care adaugă cheia, dacă lipsește), at, find, contains, insert, try_emplace, erase. Diferența este organizarea: cheile sunt împărțite în „găleți” (buckets) după valoarea lor hash, așa că o căutare durează în medie O(1), indiferent de numărul de elemente.

Prețul: elementele nu au o ordine previzibilă. Ordinea la parcurgere depinde de bibliotecă, de numărul de găleți și se poate schimba după inserări. Dacă vrei să afișezi rezultatele într-o ordine fixă, copiază-le într-un vector și sortează-l (ca în exemplele de mai jos), sau folosește std::map.

Cheia trebuie să aibă o funcție hash (std::hash există pentru numere, texte, pointeri) și ==. Când tabela crește, are loc un rehash, care invalidează toți iteratorii (dar nu referințele la elemente).

Parametri

Parametru	Descriere
`Cheie`	Tipul cheilor; are nevoie de `std::hash<Cheie>` și de `==`.
`Valoare`	Tipul valorilor.

Ce returnează

Un obiect unordered_map.

Exemple

Exemplul 1: Numărarea cuvintelor, afișate sortat

Parcurgerea directă a unui unordered_map ar da altă ordine pe alt compilator. Copiem perechile într-un vector și le sortăm după frecvență, apoi alfabetic.

#include <algorithm>
#include <print>
#include <sstream>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>

int main() {
    std::istringstream text("mere pere mere prune mere pere caise");
    std::unordered_map<std::string, int> frecventa;
    std::string cuvant;
    while (text >> cuvant) {
        ++frecventa[cuvant];
    }

    std::vector<std::pair<std::string, int>> sortat(frecventa.begin(), frecventa.end());
    std::ranges::sort(sortat, [](const auto& a, const auto& b) {
        return a.second != b.second ? a.second > b.second : a.first < b.first;
    });
    for (const auto& [c, n] : sortat) {
        std::println("{}: {}", c, n);
    }
}

Rezultat

mere: 3
pere: 2
caise: 1
prune: 1

Exemplul 2: Căutare rapidă după cod

#include <print>
#include <string>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, std::string> judete{
        {"IS", "Iași"}, {"CJ", "Cluj"}, {"B", "București"}, {"TM", "Timiș"},
    };
    for (std::string cod : {"CJ", "XX", "IS"}) {
        if (auto it = judete.find(cod); it != judete.end()) {
            std::println("{} = {}", cod, it->second);
        } else {
            std::println("{} = cod necunoscut", cod);
        }
    }
    std::println("contains(\"TM\"): {}", judete.contains("TM"));
}