Cicli che non devi scrivere
Nella pagina precedente hai visto che ogni contenitore fornisce degli iteratori, cursori leggeri con begin() e end(). Questa astrazione è il motivo stesso per cui esistono gli algoritmi standard. Invece di scrivere un ciclo for ogni volta che vuoi cercare, contare o trasformare dei dati, chiami una funzione con un nome preciso da <algorithm> e le passi un range.
Un range è semplicemente una coppia di iteratori: dove iniziare e la posizione subito dopo quella in cui fermarsi. Dato che ogni algoritmo parla lo stesso linguaggio degli iteratori, lo stesso find funziona su un vector, una string o un array semplice.
Lo schema da memorizzare: un algoritmo di ricerca restituisce l'iteratore end() per dire "non trovato". Confronta sempre con end() prima di dereferenziare il risultato: dereferenziare end() è comportamento indefinito.
Contare e verificare con i predicati
Molti algoritmi accettano un predicato, cioè una funzione (di solito una lambda) che restituisce bool per ogni elemento. count_if conta le corrispondenze; all_of, any_of e none_of rispondono sì o no a domande sull'intero range.
std::count (senza _if) è il cugino più semplice che conta un valore esatto invece di una condizione. Passa alle versioni con predicato non appena il tuo test diventa "qualsiasi cosa che rispetti una regola" invece di "questo valore specifico".
Trasformare e ridurre un range
Due cavalli di battaglia coprono la maggior parte dell'elaborazione dei dati: std::transform applica una funzione a ogni elemento, e std::accumulate (da <numeric>, non da <algorithm>) riduce un range a un singolo valore.
transform scrive i risultati attraverso un iteratore di output. Un errore comune e pericoloso è puntare l'output a un vector vuoto: l'algoritmo presume che lo spazio esista già e scrive oltre la fine. Dimensiona prima la destinazione, oppure usa un back_inserter in modo che ogni risultato venga aggiunto con push_back.
accumulate parte da un valore iniziale e combina gli elementi da sinistra a destra. Il tipo del valore iniziale conta: passa 0 (un int) e la somma viene calcolata in int, che può andare in overflow o troncare a seconda del tipo di dato degli elementi.
Se avessi scritto accumulate(prices.begin(), prices.end(), 0) con un valore iniziale int, ogni somma avverrebbe in int e i centesimi sparirebbero. Il tipo del valore iniziale determina silenziosamente il tipo del risultato.
L'idioma erase-remove
Ecco l'insidia che sorprende tutti. std::remove non rimuove nulla dal contenitore. Gli algoritmi hanno solo iteratori, quindi non possono cambiare la dimensione di un contenitore: non sanno nemmeno che un contenitore esiste. Quello che remove fa davvero è spostare in testa tutti gli elementi da tenere, lasciare la coda in uno stato non specificato e restituire un iteratore alla nuova fine logica.
// remove da solo lascia la dimensione invariata, ecco l'errore:
remove(v.begin(), v.end(), 0); // restituisce un iteratore che hai ignorato
// v ha ancora la sua dimensione originale; la coda è spazzatura
Per eliminare davvero gli elementi, abbini remove al metodo erase del contenitore, ed è per questo che si chiama idioma erase-remove:
Usa remove_if per un predicato invece di un valore esatto. In C++20 puoi saltare del tutto questo balletto con le funzioni libere std::erase / std::erase_if, che fanno entrambi i passaggi per te: erase(v, 0);.
Iteratori usati oltre la loro validità, a tuo rischio
Dato che gli algoritmi restituiscono iteratori, questi iteratori sono soggetti alle stesse regole di invalidazione viste nella pagina precedente. Salvare un iteratore e poi modificare il contenitore, con un push_back che provoca una riallocazione o con un erase, può lasciare l'iteratore salvato pendente, e usarlo è comportamento indefinito.
auto it = find(v.begin(), v.end(), 16);
v.push_back(99); // può riallocare la memoria di v
cout << *it; // BUG: `it` ora può puntare a memoria liberata
L'abitudine sicura: usa l'iteratore restituito da un algoritmo subito, prima di qualsiasi operazione che possa ridimensionare o riallocare il contenitore. Se devi modificare il contenitore in base a un risultato, salva invece un indice (it - v.begin()), perché gli indici sopravvivono alla riallocazione.
Prossimo: Ordinamento
Hai visto come cercare, contare, trasformare e ridurre, ma un algoritmo è abbastanza importante da meritare una pagina tutta sua. std::sort riordina un range sul posto, e una volta ordinati i dati si apre un'intera famiglia di algoritmi più veloci che funzionano solo su dati ordinati (binary_search, lower_bound, equal_range). Nella prossima pagina approfondiremo l'ordinamento: come fornire un comparatore personalizzato, la differenza tra sort e stable_sort e le regole che la tua funzione di confronto deve rispettare per evitare comportamenti indefiniti.
Domande frequenti
Cos'è l'header <algorithm> in C++?
<algorithm> è l'header della libreria standard che contiene funzioni generiche come std::find, std::sort, std::count_if e std::transform. Operano su range descritti da una coppia di iteratori (di solito begin() e end()), quindi lo stesso algoritmo funziona su un vector, un array, una string o qualsiasi contenitore che esponga iteratori.
Come verifico se un valore esiste in un vector in C++?
Usa std::find: auto it = find(v.begin(), v.end(), target);. Se it == v.end() il valore non c'è; altrimenti it punta alla prima corrispondenza. Per verificare una condizione invece di un valore esatto, usa std::any_of con un predicato.
Perché std::remove non rimuove davvero gli elementi dal mio contenitore?
Gli algoritmi vedono solo gli iteratori, non il contenitore, quindi std::remove non può ridurne la dimensione: sposta in testa gli elementi da tenere e restituisce un iteratore alla nuova fine logica. Devi farlo seguire da v.erase(...) (l'idioma erase-remove) per eliminare fisicamente gli avanzi.
