Guida C++ interattiva: unordered_map

Q: Qual è la differenza tra map e unordered_map in C++?

std::map è un albero binario bilanciato: le chiavi restano ordinate e le operazioni costano O(log n). std::unorderedmap è una tabella hash: le chiavi non hanno un ordine particolare, ma inserimento e ricerca sono in media O(1). Usa unorderedmap quando ti serve solo una ricerca veloce per chiave e l'ordine non conta; usa map quando ti serve un'iterazione ordinata o delle query per intervalli.

Q: unordered_map[] inserisce una chiave se non esiste?

Sì. m[key] costruisce con il valore predefinito e inserisce la chiave se manca, poi restituisce un riferimento. Questo significa che anche un if (m[key] == ...) che sembra una semplice lettura fa crescere la map in silenzio. Per controllare se una chiave è presente senza inserirla, usa invece m.count(key) o m.find(key).

Q: unordered_map è sempre più veloce di map in C++?

No. È O(1) in media, ma l'hashing ha un costo e una cattiva funzione hash (o chiavi scelte apposta) possono far degradare le ricerche a O(n). Per map piccole, i fattori costanti e il peggior uso della cache possono rendere una map ordinata altrettanto veloce o anche di più. Fai un benchmark se conta, ma scegli unordered_map di default quando ti serve solo la ricerca per chiave.

Quando l'ordine non conta

Hai appena visto std::map, che tiene le chiavi ordinate usando un albero bilanciato e ti dà operazioni in O(log n). Ma ordinare ha un costo, e molto spesso non ti interessa in che ordine escono le chiavi: vuoi solo chiedere "questa chiave c'è, e qual è il suo valore?" il più velocemente possibile.

A questo serve std::unordered_map. È una tabella hash: passa ogni chiave attraverso una funzione hash per decidere dove memorizzarla, il che rende inserimento, ricerca ed eliminazione O(1) in media invece di O(log n). Il compromesso è che l'ordine di iterazione non è specificato: le chiavi escono nell'ordine in cui si trovano nei bucket.

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

L'interfaccia è quasi identica a quella di map, ed è voluto: spesso puoi passare dall'una all'altra cambiando solo il tipo. Includi <unordered_map> (non <map>), e le chiavi escono non ordinate.

Inserire e aggiornare

Ci sono vari modi per aggiungere elementi, e non si comportano tutti allo stesso modo. I due che userai di più sono operator[] e insert:

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

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

    votes["alice"] = 3;              // crea o sovrascrive
    votes["alice"] = 5;              // sovrascrive -> 5
    votes.insert({"bob", 2});        // inserisce solo se "bob" non c'è
    votes.insert({"bob", 99});       // ignorato, "bob" esiste già

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

La differenza fondamentale: operator[] sovrascrive un valore esistente, mentre insert lascia intatta una chiave già presente. Se usi C++17, insert_or_assign(key, value) ti dà la semantica "imposta questo in ogni caso", e try_emplace(key, args...) costruisce il valore sul posto solo quando la chiave è nuova, comodo per valori costosi da creare.

L'insidia di operator[]: inserisce anche in lettura

Questo è in assoluto il bug più comune con unordered_map, quindi merita una sezione tutta sua. m[key] non è una semplice lettura. Se la chiave manca, la costruisce con il valore predefinito e la inserisce (un int diventa 0, una string diventa ""), poi restituisce un riferimento. Così un codice che sembra una ricerca fa crescere la map in silenzio:

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

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

    // Volevamo solo CONTROLLARE "y", ma [] l'ha inserita:
    if (seen["y"] == 0) {
        cout << "y looked missing...\n";
    }

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

seen["y"] ha creato un elemento "y" -> 0 solo per essere stato nominato. Per verificare la presenza senza modificare la map, usa count (restituisce 0 o 1) oppure 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() si legge meglio di count()
    if (seen.contains("x")) cout << "x is here\n";
}

Regola pratica: usa [] solo quando vuoi creare o aggiornare. Per le letture pure, usa count, contains (C++20) o find.

find e at: ricerche sicure

find restituisce un iteratore all'elemento, oppure end() se la chiave non c'è. Non inserisce mai, e ti permette di raggiungere sia la chiave sia il valore tramite it->first e it->second con una sola ricerca:

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

Quando sai che la chiave dovrebbe esistere e vuoi un errore netto se non c'è, usa at. A differenza di [], at non inserisce: lancia std::out_of_range se la chiave manca:

int p = prices.at("pen");   // va bene
int q = prices.at("hat");   // lancia std::out_of_range: la chiave non c'è

Quindi hai tre modi di cercare: [] (inserisce), at (lancia un'eccezione) e find/count (dicono se la chiave c'è senza toccare la map). Scegli quello il cui comportamento in caso di chiave mancante corrisponde alla tua intenzione.

Iterare ed eliminare

Un ciclo for basato su intervallo con le structured binding è il modo pulito per scorrere tutti gli elementi. Ricorda che l'ordine è arbitrario: non farci mai affidamento:

#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";   // l'ordine non è specificato
    }
}

Per rimuovere un elemento, erase accetta direttamente una chiave e restituisce quanti elementi ha rimosso (0 o 1). Un'insidia importante: in una unordered_map, eliminare durante l'iterazione invalida solo l'iteratore dell'elemento eliminato, quindi usa il valore restituito da erase(it) per avanzare in sicurezza:

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

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

    // Elimina ogni squadra con un punteggio sotto 3
    for (auto it = wins.begin(); it != wins.end(); ) {
        if (it->second < 3)
            it = wins.erase(it);   // erase restituisce il prossimo iteratore valido
        else
            ++it;
    }

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

Scrivere nello stile wins.erase(it++) o fare ++it dopo un semplice erase(it) è la classica trappola dell'iteratore pendente: l'iteratore eliminato è morto, quindi prendi sempre l'iteratore restituito da erase.

map o unordered_map?

Entrambe memorizzano coppie chiave-valore con un'API simile, quindi la scelta dipende da ciò che ti serve:

// std::map            -> chiavi ordinate, O(log n), query per intervalli (lower_bound)
// std::unordered_map  -> nessun ordine,   O(1) medio, ricerca semplice più veloce

Scegli unordered_map quando ti serve solo una ricerca veloce per chiave e l'ordine è irrilevante (contare la frequenza delle parole, cache, deduplicazione). Scegli map quando ti servono le chiavi in ordine, vuoi iterare in ordine o fare query per intervalli. Due avvertenze per unordered_map: il suo O(1) è una media, e una cattiva funzione hash può peggiorarlo; inoltre un tipo di chiave personalizzato richiede una specializzazione di hash o un functor di hash, mentre a map basta operator<.

Prossimo: set

Ora hai visto entrambe le versioni dei contenitori chiave-valore. A volte però non ti serve affatto un valore: ti interessa solo se qualcosa è presente, come in una raccolta di tag unici o di ID già visitati. Adesso vedremo std::set (e il suo cugino basato su hash, unordered_set), che memorizzano solo le chiavi e le mantengono uniche in automatico.

Domande frequenti

Qual è la differenza tra map e unordered_map in C++?

std::map è un albero binario bilanciato: le chiavi restano ordinate e le operazioni costano O(log n). std::unordered_map è una tabella hash: le chiavi non hanno un ordine particolare, ma inserimento e ricerca sono in media O(1). Usa unordered_map quando ti serve solo una ricerca veloce per chiave e l'ordine non conta; usa map quando ti serve un'iterazione ordinata o delle query per intervalli.

unordered_map[] inserisce una chiave se non esiste?

Sì. m[key] costruisce con il valore predefinito e inserisce la chiave se manca, poi restituisce un riferimento. Questo significa che anche un if (m[key] == ...) che sembra una semplice lettura fa crescere la map in silenzio. Per controllare se una chiave è presente senza inserirla, usa invece m.count(key) o m.find(key).

unordered_map è sempre più veloce di map in C++?

No. È O(1) in media, ma l'hashing ha un costo e una cattiva funzione hash (o chiavi scelte apposta) possono far degradare le ricerche a O(n). Per map piccole, i fattori costanti e il peggior uso della cache possono rendere una map ordinata altrettanto veloce o anche di più. Fai un benchmark se conta, ma scegli unordered_map di default quando ti serve solo la ricerca per chiave.

Concetti correlati