1. Introduzione
Quando si inizia a programmare, si tende a cercare un "contenitore universale" da usare ovunque: come un telecomando universale per tutto. In C++ un candidato frequente sembra essere std::map: ricerca veloce, c'è l'ordine, sembra serio. Ma nella pratica si nota presto qualcosa di strano: in certi casi map è improvvisamente "pesante", mentre in altri un semplice std::vector vince inaspettatamente anche nella ricerca. E non è frutto di magia, ma di normale ingegneria.
Semplificando a un'idea, la scelta del contenitore è la scelta di un insieme di compromessi. Bisogna capire cosa è più importante nel vostro scenario: velocità di ricerca, velocità di inserimento/cancellazione, memoria, ordine stabile, facilità di mantenere invarianti. Oggi confronteremo due approcci che si contendono spesso l'uso nei progetti reali: il albero (std::map) e il array denso (std::vector), ma ordinato.
Caso didattico: "rubrica contatti" e find by id
Per rendere il confronto concreto, teniamo in mente lo stesso problema. Immaginate una semplice applicazione console "Rubrica contatti": ogni contatto ha un id, un nome e un telefono. Vogliamo poter trovare rapidamente un contatto per id, talvolta aggiungere nuovi contatti e talvolta stampare la lista.
Notate che qui prendiamo consapevolmente il ricerca per chiave intera: è l'esempio più semplice, dove ci si può concentrare sui contenitori, non sulle particolarità delle stringhe, localizzazione e simili. I modelli li definiamo spesso come struct, quindi non c'è nulla di nuovo o spaventoso.
Ecco il modello di base:
#include <string>
struct Contact {
int id{};
std::string name;
std::string phone;
};
Da qui parte il bivio: come memorizzare la collezione di contatti in modo che la ricerca per id sia "piacevole"?
2. Variante di base: std::vector e ricerca lineare
Prima di "migliorare", è utile guardare onestamente la versione base. Se i contatti sono pochi, si possono tenere in std::vector<Contact> e cercare per scansione. Si legge in modo elementare, si debugga facilmente e spesso… funziona più velocemente di quanto i principianti si aspettino.
Esempio di ricerca lineare:
#include <vector>
const Contact* find_by_id_linear(const std::vector<Contact>& contacts, int id) {
for (const auto& c : contacts) {
if (c.id == id) return &c;
}
return nullptr;
}
In termini Big‑O è O(N), e formalmente è "peggio" di O(log N). Ma nel mondo reale, per piccoli N (ad esempio 30–200 elementi) la ricerca lineare su un vector denso può essere molto agile grazie alla buona località dei dati e al minimo overhead.
Il problema è che appena i dati crescono in modo significativo, si inizia a sentire l'O(N). A questo punto emergono due opzioni mature: il vector ordinato e la map.
4. std::vector ordinato: ricerca veloce a costo di inserimento
Invariante di ordinamento e rappresentazione dei dati
Il vector ordinato è quasi una filosofia. Si prende un contenitore buono per densità e semplicità e si aggiunge una regola-invariante: gli elementi sono sempre ordinati per chiave. Accettando questa regola, si può cercare in O(log N) usando la ricerca binaria.
È importante capire: il vector ordinato non è "vector più magia", è "vector più disciplina". Il prezzo della disciplina si paga quando inseriamo o cancelliamo elementi. Ma per ora suona allettante: ricerca veloce, memoria compatta, iterazione ordinata naturale.
Per comodità spesso si memorizzano non gli oggetti "a caso", ma coppie key → value, cioè std::pair<int, Contact>. Quindi manteniamo l'ordine su first.
#include <utility>
#include <vector>
using ContactRow = std::pair<int, Contact>; // first = id
using ContactTable = std::vector<ContactRow>;
Sì, sembra un po' una "base dati della pietra", ma proprio così si costruiscono molti indici veloci nella pratica: semplice, comprensibile, prevedibile.
Ricerca binaria su vector ordinato
La parola "ricerca binaria" suona spesso come un incantesimo da libro di testo, ma è semplicemente giocare a "indovina la metà". Manteniamo l'intervallo [left, right) e ogni volta scartiamo metà. Il punto cruciale: senza ordinamento la ricerca binaria non funziona affatto. Non dà una risposta sbagliata, si trasforma in generatore di azioni senza senso.
Implementiamo la ricerca della posizione per id. Torneremo std::optional<std::size_t>: o l'indice trovato, o "non trovato". Questo stile dovrebbe già risultarvi familiare dai temi sull'"errore come valore".
#include <cstddef>
#include <optional>
std::optional<std::size_t> find_pos_by_id_sorted(const ContactTable& t, int id) {
std::size_t left = 0;
std::size_t right = t.size(); // [left, right)
while (left < right) {
std::size_t mid = left + (right - left) / 2;
if (t[mid].first < id) left = mid + 1;
else right = mid;
}
if (left < t.size() && t[left].first == id) return left;
return std::nullopt;
}
Qui è utile abituarsi a un'idea: la ricerca binaria di solito trova prima il "posto dove dovrebbe essere" e poi verifica se coincide. È comodo perché lo stesso "posto" può servire per l'inserimento, evitando di scrivere due logiche diverse.
Inserimento in vector ordinato
Finché godevamo di O(log N) tutto era bello. Poi la realtà: se il vector è ordinato, inserire un nuovo elemento richiede di mantenere l'ordine. E il vector è un array contiguo. Quindi per inserire nel mezzo bisogna spostare la coda. Questo è tipicamente O(N).
Quindi si ottiene il classico compromesso: ricerca veloce, inserimento costoso. È ideale per scenari "i dati cambiano poco ma si leggono spesso". Per esempio: rubrica di codici paese, lista tariffe, tabella di costanti, dizionario di comandi caricato una sola volta all'avvio.
Facciamo l'inserimento così: troviamo la posizione d'inserimento, verifichiamo duplicati di chiave e poi inseriamo.
#include <utility> // std::pair
bool insert_sorted(ContactTable& t, const Contact& c) {
// Troviamo il posto dove dovrebbe stare l'id
std::size_t left = 0;
std::size_t right = t.size();
while (left < right) {
std::size_t mid = left + (right - left) / 2;
if (t[mid].first < c.id) left = mid + 1;
else right = mid;
}
if (left < t.size() && t[left].first == c.id) return false; // già presente
t.insert(t.begin() + static_cast<std::ptrdiff_t>(left), {c.id, c});
return true;
}
Nota il dettaglio: t.begin() + left richiede un indice compatibile con la differenza di iteratori (std::ptrdiff_t). Sì, è uno di quei momenti in cui C++ ricorda: "sono potente, ma sii prudente". Non approfondiamo, facciamo solo il cast esplicito.
5. std::map: ordine senza spostamenti di array
Ora guardiamo a std::map. Intuizione importante: map non è "un vector che sa cercare". È un'altra struttura: un albero (di solito bilanciato). Tiene coppie key → value in modo da mantenere l'ordine delle chiavi ed eseguire ricerca/inserimento/cancellazione a circa O(log N).
Dal punto di vista pratico map è utile perché l'inserimento non richiede lo spostamento di metà del contenitore. Aggiungi un nuovo nodo all'albero, l'albero si riaggiusta internamente e l'ordine è preservato.
Esempio: memorizzare i contatti direttamente in map<int, Contact>.
#include <map>
using ContactMap = std::map<int, Contact>;
const Contact* find_by_id_map(const ContactMap& m, int id) {
if (auto it = m.find(id); it != m.end()) {
return &it->second;
}
return nullptr;
}
Anche l'inserimento appare tranquillo:
bool insert_map(ContactMap& m, const Contact& c) {
auto [it, inserted] = m.insert({c.id, c});
return inserted; // false se la chiave era già presente
}
Ed ecco la "trappola morale" comune ai principianti: il codice con map risulta più corto e semplice rispetto alla nostra ricerca binaria + inserimento manuale. Si vorrebbe proclamare un vincitore. Ma non giudichiamo i contenitori dal numero di righe — C++ spesso punisce tali valutazioni con prestazioni o memoria.
6. Confronto: velocità, memoria e ordine
Per confrontare gli approcci è utile guardare più assi contemporaneamente. Big‑O è una buona mappa del territorio, ma la mappa non mostra le zanzare nella foresta. map ha overhead per i nodi e i puntatori, vector offre ottima densità e friendly cache, ma inserimenti costosi.
Riassumiamo il confronto in una tabella. Non come "legge della natura", ma come promemoria pratico.
| Caratteristica / operazione | Vector ordinato vector<pair<K,V>> | std::map<K,V> |
|---|---|---|
| Ricerca per chiave | O(log N), molto veloce in pratica grazie alla memoria densa | O(log N), ma con più "salti" in memoria |
| Inserimento nuova chiave | di solito O(N) a causa degli spostamenti | O(log N), senza spostamenti di array |
| Cancellazione | di solito O(N) a causa degli spostamenti | O(log N) |
| Ordine di iterazione | naturale per chiave (come è posizionato nell'array) | anche per chiave (determinato dal comparatore) |
| Memoria per elemento | minima (quasi solo dati) | maggiore (nodi, link interni) |
| Miglior scenario | "leggere molte volte, modificare raramente" | "inserire/cancellare spesso + serve ordine" |
Una piccola analogia visiva per ricordare. vector è come una scatola di schede impilate in ordine: cercare è comodo, ma per inserire una scheda nel mezzo bisogna spostare il mucchio. map è come un archivio con cassetti e scomparti: inserire è più semplice, ma l'accesso alle schede vicine salta fisicamente tra posti diversi.
Si può anche rappresentare così:
flowchart LR
A[Ricerca per chiave] --> B{I dati cambiano spesso?}
B -->|Raramente| C[Vector ordinato: ricerca veloce, memoria economica]
B -->|Spesso| D{Serve ordine per chiave?}
D -->|Sì| E[map: inserimento/cancellazione logaritmici]
D -->|No| F["unordered_map: di solito O(1) in media"]
Non approfondiamo unordered_map (argomento correlato), ma è utile vedere l'intero "albero decisionale".
7. Regola di scelta: fatevi 3 domande
Quando uno sviluppatore sceglie un contenitore, raramente dimostra teoremi alla lavagna. Di solito si pone alcune domande pratiche e sceglie ciò che è più semplice da mantenere e meno soggetto a errori. Ora formuliamo queste domande in modo comprensibile.
Prima domanda: i dati vengono caricati una volta e cambiano poco, oppure si aggiungono/cancellano continuamente elementi? Se le modifiche sono rare, il vector ordinato spesso è una soluzione sorprendentemente efficace. Se le modifiche sono frequenti, map di solito dà meno dolore.
Seconda domanda: serve un ordine garantito per l'iterazione per chiave? Se sì — map e il vector ordinato sono entrambi adatti. Se l'ordine non è necessario, spesso conviene considerare unordered_map, ma è un altro discorso.
Terza domanda: quanto è importante la memoria e il layout semplice dei dati? Su grandi volumi la differenza tra array denso e heap di nodi diventa evidente non solo in memoria, ma anche in prestazioni dovute alla cache.
8. Nascondere il contenitore dietro un'API
Per non trasformare il programma in uno "zoo di contenitori", conviene mirare a uno stile di API uniforme. Per esempio, può essere indifferente dove sono memorizzati i contatti se vogliamo solo "trovare per id e stampare".
Facciamo una funzione di stampa che riceve un puntatore a Contact. È una tecnica semplice che illustra l'idea: la ricerca può restituire "null" e questo va gestito correttamente.
#include <iostream>
void print_contact(const Contact* c) {
if (!c) {
std::cout << "Contact not found\n";
return;
}
std::cout << c->id << ": " << c->name << " (" << c->phone << ")\n";
}
Ora si può scrivere:
// Per map
// print_contact(find_by_id_map(m, 10));
// Per vector (lineare)
// print_contact(find_by_id_linear(v, 10));
Sì, è una "piccola architettura", ma è così che si impara a progettare codice in modo che sostituire il contenitore non rompa metà del programma.
9. Quando quale opzione vince
Quando il vector ordinato è una buona scelta
A volte il vector ordinato è visto come un trucco: "è roba da competitive programming" o "è quando non si può usare map". In pratica è un'opzione ingegneristica valida quando i dati sono immutabili o cambiano a lotti. Per esempio, carichi la lista contatti da file, ordini una volta e poi solo ricerche. Oppure costruisci la tabella dei comandi all'avvio e poi la usi.
In questi scenari il vector ordinato spesso vince anche perché è facile da serializzare, copiare, scorrere con algoritmi lineari e non richiede memoria per strutture ausiliarie. Paghi per gli inserimenti, ma se gli inserimenti sono quasi assenti non paghi quasi nulla.
Quando std::map vince
map non è un contenitore "obsoleto" né un ripiego per chi non conosce unordered_map. È utile quando c'è un flusso di modifiche: inserimenti, cancellazioni, aggiornamenti. È utile se vuoi che la struttura mantenga l'ordine da sola, senza dover gestire manualmente l'invariante di ordinamento dopo ogni operazione.
Inoltre map spesso è preferibile se vuoi operazioni come "trovare la chiave più vicina a sinistra/destra" o "iterare su un intervallo di chiavi". Non allarghiamo troppo il tema (qui il focus è la scelta della struttura), ma ricorda: l'albero non è solo ricerca, è anche "ordine come infrastruttura".
10. Errori tipici
Errore #1: fare ricerca binaria su un vector non ordinato.
È uno degli errori più insidiosi: il codice compila, il programma gira, ma le risposte sono talvolta sbagliate. La ragione è semplice: la ricerca binaria si basa sull'invariante di ordine. Se hai inserito almeno una volta un elemento "a caso" e non hai ripristinato l'ordine, l'algoritmo comincia a prendere decisioni sbagliate su quale metà scartare.
Errore #2: dimenticare che inserire nel mezzo di un vector comporta spostamenti, e ritrovarsi con rallentamenti.
Il principiante vede O(log N) sulla ricerca e pensa che "ora tutto è veloce". Poi compaiono inserimenti frequenti e il programma rallenta inspiegabilmente, pur avendo formalmente "fatto ricerca binaria". Importa considerare il costo dell'intero scenario. Se ci sono molte inserzioni, il vector ordinato può diventare costoso proprio per gli spostamenti degli elementi.
Errore #3: scegliere map "di default" senza definire i requisiti.
Questa scelta porta spesso a codice che sembra "solido" ma consuma più memoria e talvolta è più lento nelle ricerche di quanto ci si aspetti. È particolarmente evidente su dataset di dimensione media, dove il vector grazie alla sua densità può essere molto efficace. Buona abitudine: prima capire cosa è più importante: modifiche rare o frequenti, serve ordine, quale il volume dei dati.
Errore #4: confondere "comodo da scrivere" con "comodo da manutenere".
map spesso produce codice più corto, mentre il vector ordinato richiede disciplina manuale. Ma la manutenzione non è solo la lunghezza della funzione, è anche la chiarezza degli invarianti. Se il team non è pronto a ricordare costantemente l'ordinamento e gli inserimenti accurati, il vector ordinato può diventare fonte di bug silenziosi. In quel caso è meglio scegliere map, anche se non ideale per l'overhead.
Errore #5: ignorare il costo della memoria e della località dei dati, confrontando solo Big‑O.
Sulla carta O(log N) è uguale in entrambi i casi. Ma nella realtà un contenitore salta tra nodi heap, l'altro legge memoria in modo lineare e prevedibile. Quindi l'approccio corretto è ricordare che "asimptotica" non cancella l'architettura della memoria. Su volumi piccoli o medi questo a volte pesa più delle belle formule.
GO TO FULL VERSION