1. Introduzione
La rimozione di elementi da un contenitore è il momento in cui il programmatore smette di essere romantico e diventa adulto. Finché leggiamo semplicemente elementi o creiamo un nuovo contenitore, è tutto abbastanza sicuro. Ma non appena si decide: "sto attraversando il contenitore e ora elimino alcuni elementi", si inizia a segare il ramo su cui si è appoggiati. A volte va bene (e perfino necessario), ma solo se si sa dov'è il supporto del ramo.
La motivazione pratica di solito è questa: è importante non solo "filtrare tutto", ma eseguire il lavoro durante l'iterazione. Per esempio, si attraversa la lista delle task ed si eliminano quelle completate, stampando contemporaneamente cosa è stato rimosso. Oppure si scorre una map e si cancellano elementi in base a una condizione complessa, dove la decisione dipende dall'elemento corrente e, per esempio, da qualche contatore/logica. In queste situazioni si preferisce rimanere in un unico ciclo e non creare un "secondo passaggio".
Per non parlare astrattamente di "elementi", continuiamo con la mini-applicazione TaskBook (un ipotetico task manager da console), dove abbiamo una lista di task e talvolta bisogna pulirla proprio durante l'iterazione.
2. Perché erase in un ciclo spesso rompe il codice
La prima cosa che fa il principiante (e a volte anche l'esperto, se è stanco) sembra più o meno così: "scorro il vector, vedo un elemento cattivo, faccio erase, poi continuo in qualche modo". E qui compaiono due problemi classici: saltare elementi e usare iteratori/indici "scaduti".
La cosa peggiore è che il codice può funzionare a volte. E a volte — "non cancellare tutto", "cancellare a salti", "crashare" o "comportarsi in modo strano". È come tentare di riparare una presa con un cacciavite di cioccolato: in teoria lo strumento c'è, ma nella pratica ci sono sorprese.
Esempio di cattiva idea: erase nel range-for
Il range-for nasconde l'iteratore. E erase è un'operazione che modifica la struttura del contenitore. Quindi serve gestire "dove andare dopo", ma il range-for non ce lo permette.
#include <vector>
int main() {
std::vector<int> v{1, 2, 3, 4};
// PESSIMO: range-for nasconde l'iteratore.
// Quando si prova a erase si perde il controllo su come continuare l'iterazione.
// for (int x : v) {
// if (x % 2 == 0) {
// v.erase(...); // da qui in poi cominciano i guai
// }
// }
}
Sì, a volte la gente cerca di "dentro il range-for" trovare l'indice e poi rimuovere. Non migliora la situazione — si trasforma semplicemente in "range-for + rattoppi".
Esempio di cattiva idea: ciclo per indice e erase senza correggere l'indice
Con gli indici c'è un'altra trappola: dopo la cancellazione gli elementi si spostano, mentre il vostro i continua a crescere come se nulla fosse. Di conseguenza spesso saltate l'elemento che si è spostato nella posizione cancellata.
#include <vector>
int main() {
std::vector<int> v{1, 2, 2, 3};
for (std::size_t i = 0; i < v.size(); ++i) {
if (v[i] == 2) {
v.erase(v.begin() + static_cast<long long>(i));
// Dopo erase l'elemento successivo si sposta nella posizione i,
// e il ciclo fa ++i e lo salta.
}
}
}
Si può, certo, dopo erase fare --i (e controllare che non diventi negativo), ma questo si trasforma rapidamente in una costruzione fragile, da non toccare.
3. Pattern sicuro: it = c.erase(it)
Ora la buona notizia. Nella STL c'è un'idea molto pratica: la cancellazione per iteratore di solito restituisce l'iteratore al prossimo elemento. E non è un caso: è esattamente ciò che serve per continuare l'iterazione correttamente.
Il pattern affidabile è il seguente:
- se l'elemento va rimosso, eseguiamo it = c.erase(it) e non incrementiamo manualmente it;
- se l'elemento non va rimosso, facciamo il normale ++it.
Dal punto di vista algoritmico è quasi come "spostare un puntatore", ma tenendo conto che il contenitore può riorganizzare internamente gli elementi.
Mini-schema (logica del ciclo)
flowchart TD
A["it punta all'elemento corrente"] --> B{Rimuovere?}
B -- "sì" --> C["it = c.erase(it)"]
C --> A
B -- "no" --> D["++it"]
D --> A
Esempio su std::vector: rimuovere numeri negativi
#include <vector>
int main() {
std::vector<int> v{3, -1, 2, -5, 7};
for (auto it = v.begin(); it != v.end(); ) {
if (*it < 0) {
it = v.erase(it); // prendiamo il prossimo iteratore valido
} else {
++it; // ci muoviamo noi
}
}
}
Perché questo funziona stabilmente? Perché sappiamo sempre con certezza che it dopo la chiamata a erase punta esattamente al posto dove continuare. Non "da qualche parte vicino", non "più o meno al prossimo", ma proprio al luogo corretto per continuare l'iterazione.
Incorporiamo in TaskBook: rimozione dei titoli vuoti
Supponiamo che una task debba avere almeno del testo. Se il titolo è vuoto, consideriamo la task spazzatura e la cancelliamo. Per ora senza classi complesse — usiamo una struct.
#include <string>
#include <vector>
struct Task {
int id = 0;
std::string title;
};
int main() {
std::vector<Task> tasks{
{1, "Buy milk"},
{2, ""},
{3, "Read C++ book"},
{4, ""}
};
for (auto it = tasks.begin(); it != tasks.end(); ) {
if (it->title.empty()) {
it = tasks.erase(it);
} else {
++it;
}
}
}
Nota: usiamo it->title, perché it è un iteratore, e -> è l'accesso comodo ai campi della struct (come se it "puntasse" all'elemento).
4. Dove il pattern è applicabile: vector, list, map, set
Quando si scrive codice con la STL è utile tenere a mente due cose. Primo — non tutti i contenitori sono organizzati allo stesso modo internamente. Secondo — non tutti i contenitori reagiscono allo stesso modo, in termini di "dolore", alla cancellazione nel mezzo.
Ora ci interessa l'aspetto pratico: "posso in questo contenitore cancellare per iteratore in un ciclo e continuare con lo stesso pattern?". Nella maggior parte dei contenitori standard la risposta è: sì. Ma i dettagli (cosa viene invalidato, quanto costa) variano.
Di seguito una tabella molto pratica. Non pretende di essere formale rispetto allo standard, ma fornisce una "memoria di lavoro".
| Contenitore | È possibile fare it = erase(it)? | Cosa ricordare per i principianti |
|---|---|---|
|
sì | Dopo erase gli elementi si spostano, gli iteratori sugli elementi dopo il rimosso di solito vengono invalidati. Ma l'iteratore restituito è valido. |
|
sì | Simile a vector in concetto, ma internamente organizzato diversamente. La regola "usa l'iteratore restituito" è particolarmente importante. |
|
sì | La rimozione è economica, gli altri iteratori non si "rovinano" nello stesso modo massiccio del vector. Ma il pattern rimane lo stesso. |
|
sì | Gli elementi risiedono in nodi. erase(it) restituisce l'iteratore successivo — molto comodo per la filtrazione. |
|
sì | Anche qui di solito è possibile, ma ricordate: in alcune operazioni il contenitore può riassegnare le bucket (rehash). In un semplice ciclo "rimuovo l'elemento corrente" questo pattern è pratica normale. |
|
"quasi", ma diverso | Qui non esiste erase(it) perché l'iteratore è singolarmente collegato: si usa erase_after(prev). È uno stile a parte. |
È importante accettare un'idea: nella maggior parte dei contenitori erase "rompe" alcuni dei vostri vecchi iteratori/riferimenti, ma l'iteratore restituito è la vostra ancora di salvezza. Per questo costruiamo il ciclo intorno ad esso.
Esempio su std::map: rimuovere task con id piccoli
In TaskBook possiamo conservare le task non solo in vector, ma anche in una map<int, Task>, dove la chiave è id. È comodo quando serve trovare rapidamente una task per numero. E sì, qui rimuovere durante l'iterazione è fattibile.
#include <map>
#include <string>
struct Task {
std::string title;
};
int main() {
std::map<int, Task> tasks{
{1, {"Buy milk"}},
{2, {"Read C++ book"}},
{3, {"Walk"}}
};
for (auto it = tasks.begin(); it != tasks.end(); ) {
if (it->first < 2) {
it = tasks.erase(it);
} else {
++it;
}
}
}
La chiave della map si trova in it->first, il valore in it->second. E di nuovo: o cancelliamo e prendiamo il nuovo it, o facciamo ++it.
5. Differenza rispetto a erase-remove e std::erase_if
Adesso una distinzione importante "di significato", non di sintassi. Esistono due stili di cancellazione.
Il primo stile — rimozione durante l'iterazione — è quando volete controllo sul processo: rimuovete, contate qualcosa, registrate, a volte prendete decisioni basate su quanto visto un attimo prima. Qui il nostro eroe è il ciclo e il pattern it = c.erase(it).
Il secondo stile — rimozione massiva per condizione — è quando volete dire: "rimuovi tutti gli elementi che soddisfano il predicato, punto". È più vicino alla "filtrazione". Qui si usa spesso l'idioma erase-remove (remove_if + erase), e nel C++ moderno anche le funzioni pronte std::erase_if.
A partire da C++20 la standard library offre funzioni non membro std::erase e std::erase_if, che esprimono proprio l'idea "rimuovi tutto secondo la condizione e restituisci quanti hai cancellato". Ottimo strumento, ma risolve un problema diverso: non "rimuovo e continuo il mio percorso", ma "pulisco il contenitore".
Mini-contrasto con un esempio
Immaginiamo di voler rimuovere tutte le task vuote. Se non serve stampare ogni task cancellata e non servono effetti collaterali, allora si può pensare in termini di "filtro". Per vector<Task> (e molti altri contenitori) si legge molto chiaramente:
#include <string>
#include <vector>
// #include <algorithm> // potrebbe non servire se si usa std::erase_if
struct Task {
int id = 0;
std::string title;
};
int main() {
std::vector<Task> tasks{{1, ""}, {2, "Read"}, {3, ""}};
// Idea: "rimuovi tutto dove title è vuoto"
// std::erase_if(tasks, [](const Task& t){ return t.title.empty(); });
}
Non esploderemo qui l'idioma erase-remove "in dettaglio", perché è una tecnica separata e nel corso c'è già spazio per discuterla. L'importante è: se rimuovi come filtro — usa lo stile filtro; se rimuovi come processo — usa it = c.erase(it).
6. Quando il ciclo con erase è preferibile
Qui voglio dare un'idea del "perché ricordarsene". Perché std::erase_if (o erase-remove) sembra più semplice e a volte lo è davvero. Ma ci sono scenari dove il ciclo con erase non è "vecchio stile", ma appropriato.
Scenario A: rimuovere e stampare cosa è stato eliminato
Facciamo una mini-funzione che rimuove le task col titolo vuoto e stampa i loro id. Questo non è più solo un filtro: abbiamo un effetto collaterale (output) legato al momento della rimozione.
#include <iostream>
#include <string>
#include <vector>
struct Task {
int id = 0;
std::string title;
};
int main() {
std::vector<Task> tasks{{1, ""}, {2, "Read"}, {3, ""}};
for (auto it = tasks.begin(); it != tasks.end(); ) {
if (it->title.empty()) {
std::cout << "Removed task id=" << it->id << '\n'; // Removed task id=1 ...
it = tasks.erase(it);
} else {
++it;
}
}
}
Si potrebbe teoricamente fare anche con una rimozione massiva, ma bisognerebbe raccogliere separatamente gli elementi da cancellare e poi stampare. A volte è corretto farlo, ma spesso è una complicazione inutile. Qui il ciclo legge onestamente: "scorro e rimuovo, segnalando".
Scenario B: rimuovere "a blocchi", ma la decisione dipende dai vicini
Immaginiamo la regola: se troviamo una task con titolo "TEMP", la rimuoviamo e anche la task successiva, perché quella dopo è "intermedia". Questo non è affatto un semplice predicato t -> bool, perché la decisione dipende dalla posizione nella sequenza.
#include <string>
#include <vector>
struct Task {
std::string title;
};
int main() {
std::vector<Task> tasks{{"A"}, {"TEMP"}, {"B"}, {"C"}};
for (auto it = tasks.begin(); it != tasks.end(); ) {
if (it->title == "TEMP") {
it = tasks.erase(it); // rimosso TEMP, it ora su "B"
if (it != tasks.end()) {
it = tasks.erase(it); // rimosso "B"
}
} else {
++it;
}
}
}
Qui serve logica, ed è per questo che serve il controllo esplicito sull'iteratore.
Scenario C: rimozione in un set durante l'iterazione
Per un insieme di tag (per esempio un set di "parole bloccate" o "tag") il set è comodo per l'unicità. Spesso si fa "scorri e rimuovi gli elementi indesiderati".
#include <set>
#include <string>
int main() {
std::set<std::string> tags{"work", "temp", "cpp"};
for (auto it = tags.begin(); it != tags.end(); ) {
if (*it == "temp") {
it = tags.erase(it);
} else {
++it;
}
}
}
Il codice appare identico, anche se il contenitore è completamente diverso. E questa è, a dirla tutta, una delle ragioni per apprezzare la STL: con uno stile accurato il codice diventa portabile tra contenitori.
Dettaglio: erase può restituire end()
Se rimuovete l'ultimo elemento, il "prossimo" è end(). E questo è normale. Il pattern del ciclo lo contempla: la condizione it != end() verrà valutata e il ciclo terminerà correttamente.
È importante non dereferenziare l'iteratore dopo una erase senza prima controllare che non sia end(). Nell'esempio con "TEMP" abbiamo fatto if (it != tasks.end()) prima della seconda cancellazione — è esattamente la protezione necessaria.
7. Errori tipici quando si rimuovono elementi durante l'iterazione del contenitore
Errore n.1: fare ++it dopo it = c.erase(it).
Questo è l'errore più comune "automatico". Sembra che, essendo in un ciclo, sia obbligatorio incrementare l'iteratore. Ma erase vi ha già restituito il prossimo elemento. Se fate un ulteriore ++it, salterete un elemento e otterrete il mistero del "non rimuove tutto".
Errore n.2: rimuovere elementi dentro un range-for sperando che "si sistemi da solo".
Il range-for è pensato per leggere (o modificare con cautela i valori), ma non per cambiamenti strutturali del contenitore. La rimozione modifica la struttura e, senza un iteratore esplicito, si perde il controllo su cosa sia il "prossimo elemento". Di solito porta a salti o crash, o peggio — a comportamenti "funzionanti a volte".
Errore n.3: mescolare indici e erase su vector, senza aggiornare la logica degli indici.
In un vector la rimozione sposta la coda. Se avete rimosso v[i], l'ex v[i+1] diventa il nuovo v[i]. Se il ciclo poi fa ++i, quell'elemento viene saltato. I principianti spesso aggiungono --i e comincia il balletto dei controlli ai bordi.
Errore n.4: conservare iteratori/riferimenti agli elementi del vector, e poi rimuovere elementi dal vector.
Anche se si rimuove "un altro elemento", il vector può spostare gli elementi e il vostro riferimento/iteratore a un "vecchio oggetto" diventa invalido. L'errore può manifestarsi molto lontano dal punto di rimozione. In stile semplice e sicuro conviene dire: "dopo cambi strutturali del vector non fidatevi di iteratori e riferimenti vecchi".
Errore n.5: dimenticare il controllo it != end() in scenari dove, dopo la rimozione, si fanno altre azioni.
Il pattern it = erase(it) è di per sé sicuro, ma spesso dopo una rimozione si vuole rimuovere ancora o leggere l'elemento successivo. Se avete cancellato l'ultimo elemento, l'iteratore diventerà end(). Quindi nelle rimozioni "in due step" (come nell'esempio con "TEMP") aggiungete sempre il controllo su end(), altrimenti dereferenzierete la fine del range.
GO TO FULL VERSION