Cercare le cose per chiave
Un vector è ottimo quando accedi per posizione: elemento 0, elemento 1 e così via. Ma spesso non hai una posizione; hai un nome e vuoi ciò che vi è associato: un nome utente e il suo punteggio, una parola e il numero di occorrenze, un codice paese e la sua capitale. Scorrere un vector per trovare una corrispondenza costa O(n) e diventa lento in fretta.
std::map risolve il problema. Memorizza coppie chiave-valore, le tiene ordinate per chiave e ti permette di trovare un valore tramite la sua chiave in tempo O(log n). Includi <map> per usarla:
map<string, int> si legge "una map da chiavi string a valori int". Le chiavi sono uniche: se assegni due volte alla stessa chiave, vince il secondo valore. Internamente una map è un albero binario di ricerca bilanciato, ed è per questo che tutto resta ordinato e le ricerche sono logaritmiche invece che costanti.
Inserire elementi
Ci sono diversi modi per aggiungere voci, e la differenza tra loro conta. Il più comune è operator[], che crea la chiave se non esiste e restituisce un riferimento a cui puoi assegnare:
Se vuoi un inserimento che rifiuti di sovrascrivere una chiave esistente, usa insert o emplace. Entrambi restituiscono una pair il cui .second è un bool che ti dice se l'inserimento è avvenuto davvero:
Usa [] quando vuoi che "vinca l'ultima scrittura", e insert/emplace quando una chiave esistente va lasciata com'è.
La trappola di operator[]: inserisce quando leggi
È in assoluto il bug più comune con map. operator[] non è una semplice lettura: se la chiave manca, la inserisce senza avvisare con un valore costruito di default (0 per int, "" per string, ecc.) e restituisce un riferimento a quel valore. Quindi il semplice controllo di una chiave con [] modifica la map:
map<string, int> m;
if (m["maybe"] == 0) { // BUG: questo ha appena creato "maybe" -> 0
// ...
}
cout << m.size(); // 1, non 0: hai inserito una chiave per sbaglio
Ti colpisce anche con una const map, dove operator[] non compila nemmeno perché potrebbe dover inserire. Per leggere senza inserire, usa find, count/contains oppure at (che lancia un'eccezione invece di inserire quando la chiave non c'è):
Regola pratica: se vuoi leggere, non usare mai []. Usa at quando la chiave deve esistere, e find/contains quando potrebbe mancare.
Iterare in ordine
Poiché una map si basa su un albero, iterarla visita le chiavi in ordine crescente, sempre e senza costi aggiuntivi. Ogni elemento è una pair<const Key, Value>, quindi usa una structured binding per estrarre chiave e valore in modo pulito:
Nota che la chiave nella binding è const: puoi cambiare un valore nel ciclo con auto&, ma non puoi mai modificare una chiave sul posto (romperebbe l'ordinamento). L'output esce in ordine alfabetico (blue, sea, sky) senza alcun passaggio di ordinamento, ed è proprio per questo che si sceglie map invece di una tabella hash quando conta l'ordine di attraversamento.
L'idioma wordCount[w]++ è anche l'uso canonico dell'inserimento all'accesso: qui vuoi che una chiave mancante parta da 0, quindi [] è lo strumento giusto.
Rimuovere elementi e dimensione
Elimina per chiave con erase, che restituisce quanti elementi sono stati rimossi (0 o 1 per una map). Puoi anche cancellare tramite un iteratore ottenuto da find. Controlla lo stato del container con size() ed empty():
Una trappola quando cancelli dentro un ciclo: m.erase(it) invalida l'iteratore it, quindi dopo non puoi fare ++it. Lo schema sicuro da C++11 è it = m.erase(it), che restituisce un iteratore all'elemento successivo. Per una rimozione condizionale su tutta la map in un colpo solo, std::erase_if(m, predicate) (C++20) è più pulito.
Prossimo passo: unordered_map
std::map ti offre chiavi ordinate e operazioni O(log n) prevedibili, ma quell'ordinamento lo paghi a ogni ricerca. Quando l'ordine delle chiavi non ti interessa e vuoi solo le ricerche più veloci possibili, unordered_map sostituisce l'albero ordinato con una tabella hash: accesso O(1) in media. Nella prossima pagina vedremo come funziona, quando il suo tempo costante medio batte il logaritmo di map e le trappole dell'hashing (tipi di chiave personalizzati, collisioni nel caso peggiore) che porta con sé.
Domande frequenti
Cos'è una std::map in C++?
Una std::map è un container associativo che memorizza coppie chiave-valore ordinate per chiave. Ricerche, inserimenti ed eliminazioni sono tutti O(log n) perché si basa su un albero binario di ricerca bilanciato. Ogni chiave è unica: inserire una chiave duplicata non tocca il valore esistente.
Qual è la differenza tra operator[] e at() di map in C++?
map[key] restituisce un riferimento al valore e, se la chiave manca, la inserisce senza avvisare con un valore costruito di default. Anche map.at(key) restituisce un riferimento, ma se la chiave non c'è lancia std::out_of_range invece di inserirla. Usa at() (o find()) quando vuoi solo leggere.
Come verifico se una chiave esiste in una map C++?
Usa m.contains(key) (C++20), m.count(key), che restituisce 0 o 1, oppure m.find(key) != m.end(). Evita di verificare con m[key]: inserisce la chiave se manca, e raramente è ciò che vuoi.
