Iteratori: il collante della STL
Comprendi le categorie di iteratori, dagli iteratori di input a quelli contigui. Scopri l'aritmetica degli iteratori, la convenzione begin/end e come gli iteratori connettono i contenitori agli algoritmi.
L'astrazione degli iteratori
Gli iteratori sono il collante tra i contenitori STL e gli algoritmi. Invece di scrivere N algoritmi per M contenitori (N*M implementazioni), la STL definisce un'interfaccia comune basata sugli iteratori. Ogni contenitore fornisce iteratori e ogni algoritmo opera su intervalli di iteratori — ottenendo N+M implementazioni che funzionano insieme.
Un iteratore è un oggetto che:
1. Punta a un elemento in una sequenza
2. Può essere dereferenziato (*it) per accedere all'elemento
3. Può essere incrementato (++it) per passare all'elemento successivo
4. Può essere confrontato (it != end) per rilevare la fine della sequenza
Diverse categorie di iteratori supportano diversi insiemi di operazioni, formando una gerarchia dalla più debole alla più forte.
Categorie di iteratori
Le categorie di iteratori del C++ formano una gerarchia (ogni livello include le capacità di tutti i livelli inferiori):
| Categoria | Operazioni | Contenitori di esempio |
|---|---|---|
| Input | Lettura, avanzamento a passaggio singolo (++, *, ==) | istream_iterator |
| Output | Scrittura, avanzamento a passaggio singolo (++, *=) | ostream_iterator, back_inserter |
| Forward | Lettura/scrittura, avanzamento multi-passaggio | forward_list, unordered_set |
| Bidirezionale | Forward + indietro (--) | list, set, map |
| Ad accesso casuale | Bidirezionale + salti (+n, -n, [], <) | deque |
| Contiguo (C++17) | Ad accesso casuale + elementi adiacenti in memoria | vector, array, string |
Gli algoritmi dichiarano la categoria minima richiesta. std::sort richiede iteratori ad accesso casuale, quindi funziona con vector ma non con list (che fornisce la propria funzione membro sort()).
La convenzione begin/end
Ogni contenitore STL fornisce begin() e end() — un intervallo semi-aperto [begin, end) dove end punta a un elemento oltre l'ultimo. Le funzioni libere std::begin() e std::end() funzionano con contenitori, array C e qualsiasi tipo che fornisca i membri .begin() e .end().
#include <vector>
#include <list>
#include <algorithm>
#include <iostream>
#include <iterator>
int main() {
std::vector<int> vec = {5, 3, 1, 4, 2};
// Member functions
auto first = vec.begin(); // points to 5
auto last = vec.end(); // points past 2
// Free functions — preferred for generic code
auto first2 = std::begin(vec);
auto last2 = std::end(vec);
// Works with C-arrays too
int arr[] = {10, 20, 30};
std::sort(std::begin(arr), std::end(arr));
// const iterators — read-only access
auto cit = vec.cbegin(); // const_iterator
// *cit = 99; // ERROR: cannot modify through const_iterator
// Reverse iterators — iterate backward
for (auto rit = vec.rbegin(); rit != vec.rend(); ++rit) {
std::cout << *rit << ' '; // 2, 4, 1, 3, 5 (reversed, pre-sort was applied)
}
std::cout << '\n';
}Utilità per iteratori: next, prev, advance, distance
L'header
#include <iterator>
#include <vector>
#include <list>
#include <iostream>
int main() {
std::vector<int> vec = {10, 20, 30, 40, 50};
// std::next — returns iterator n positions forward (default 1)
auto it = std::next(vec.begin(), 2); // points to 30
std::cout << *it << '\n'; // 30
// std::prev — returns iterator n positions backward
auto it2 = std::prev(vec.end()); // points to 50
std::cout << *it2 << '\n'; // 50
// std::advance — modifies iterator in place (no return)
auto it3 = vec.begin();
std::advance(it3, 3); // now points to 40
std::cout << *it3 << '\n'; // 40
// std::distance — number of increments from first to last
auto d = std::distance(vec.begin(), vec.end()); // 5
std::cout << "Distance: " << d << '\n';
// These work with non-random-access iterators too
std::list<int> lst = {1, 2, 3, 4, 5};
auto lit = std::next(lst.begin(), 2); // O(n) for list, O(1) for vector
std::cout << *lit << '\n'; // 3
auto ld = std::distance(lst.begin(), lst.end()); // O(n) for list
std::cout << "List distance: " << ld << '\n'; // 5
}Iteratori di inserimento e iteratori di stream
Gli iteratori di inserimento permettono agli algoritmi di inserire nei contenitori anziché sovrascrivere gli elementi esistenti. Gli iteratori di stream adattano gli stream I/O all'interfaccia degli iteratori.
#include <iterator>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
int main() {
std::vector<int> src = {1, 2, 3, 4, 5};
std::vector<int> dst;
// back_inserter — calls push_back on each assignment
std::copy(src.begin(), src.end(), std::back_inserter(dst));
// dst: {1, 2, 3, 4, 5}
// front_inserter — calls push_front (works with deque, list)
// inserter — calls insert at a given position
// ostream_iterator — write to an output stream
std::copy(dst.begin(), dst.end(),
std::ostream_iterator<int>(std::cout, ", "));
std::cout << '\n'; // 1, 2, 3, 4, 5,
// istream_iterator — read from an input stream
std::istringstream iss("10 20 30 40");
std::vector<int> from_stream(
std::istream_iterator<int>(iss),
std::istream_iterator<int>() // end-of-stream sentinel
);
// from_stream: {10, 20, 30, 40}
}Incrementare un iteratore oltre end() o decrementare oltre begin() è comportamento indefinito. Lo stesso vale per il dereferenziamento di end() — è una sentinella, non un elemento valido.
Un errore comune è scrivere it + 1 senza verificare se it è già a o vicino alla fine:
auto it = vec.end();
++it; // UB — oltre la fine
*it; // UB — dereferenziamento di end()Verifica sempre la validità dell'iteratore prima delle operazioni. Usa std::next e std::prev con controlli di distanza, oppure usa cicli range-based for che gestiscono i limiti automaticamente.
Quando scrivi funzioni generiche che operano su sequenze:
1. Accetta coppie di iteratori (o range in C++20) anziché contenitori specifici
2. Usa typename o auto per il tipo dell'iteratore
3. Usa std::distance al posto della sottrazione (che richiede accesso casuale)
4. Usa std::next/std::prev al posto dell'aritmetica +/-
5. In C++20, preferisci i concept per vincolare i requisiti degli iteratori:
template<std::forward_iterator Iter>
auto my_algorithm(Iter first, Iter last) { ... }Questo assicura che il tuo codice funzioni con la più ampia gamma di contenitori.
- Gli iteratori disaccoppiano i contenitori dagli algoritmi — il principio di design fondamentale della STL
- Esistono sei categorie di iteratori: input, output, forward, bidirezionale, ad accesso casuale, contiguo
- Usa le funzioni libere
std::begin()/std::end()per codice generico che funziona con contenitori e array C std::next,std::prev,std::advance,std::distancefunzionano con tutte le categorie di iteratori- Gli iteratori di inserimento (
back_inserter,front_inserter,inserter) permettono agli algoritmi di far crescere i contenitori - Non dereferenziare mai
end()e non incrementare oltre — entrambi sono comportamento indefinito
Quiz — Metti alla prova le tue conoscenze
(15 XP)1. Quale categoria di iteratori richiede `std::sort`?
2. Cosa crea `std::back_inserter(vec)`?
3. Qual è la complessità temporale di `std::distance(first, last)` su una `std::list`?