STL e iteratori

Gli iteratori sono degli oggetti che ci permettono di accedere agli elementi di un container di prima classe (quindi non quelli che al loro interno contengono a loro volta un container, come lo stack o la coda), in modo causale (tramite indice) o in avanti o indietro. La caratteristica del container è che le modalità con cui li utilizziamo su container diversi sono sempre le stesse, anche se poi per ciascun container esiste un iterator specifico i cui metodi implementano logiche specifiche e ottimizzate per ciascun container.

Un iterator in sostanza si comporta come un puntatore, mantenendo un riferimento a un certo elemento del container, e possiamo quindi accedere al valore a cui fa riferimento con l’operatore *, o avanzare all’elemento successivo con l’operatore ++, o a quello precedente con l’operatore –, e cosi via.

le diverse implementazioni degli iteratori sono in realtà delle classi innestate nelle classi del rispettivo contenitore; questo significa che nel container “vector” c’è una classe vector::iterator che definisce metodi e membri del relativo iterator e il comportamento che deve avere.

I container hanno due metodi fondamentali, begin() e end(), che restituiscono rispettivamente un iteratore che punta al primo elemento del container, e un iteratore che punta all’indirizzo di memoria successivo all’ultimo elemento, quindi a una POSIZIONE VUOTA.

Vediamo come utilizzare un iterator:

vector v; // dichiaro un container di tipo vector di int
v.push_back(1);// inserisco valori
v.push_back(2);// inserisco valori
v.push_back(3);// inserisco valori
v.push_back(4);// inserisco valori

vector::iterator it = v.begin(); // dichiaro una variabile di tipo iteratore di vector, e la inizializzo chiamando il metodo begin() del vettore, che restituisce un iteratore alla prima posizione

count << *it; // stampo il valore referenziato dall’iteratore, che è al primo posto del container

it++; // incremento l’iteratore di una posizione, a prescindere da come è fatto il container. Al suo interno l’iteratore ha un suo overload dell’operatore ++ ottimizzato per la struttura dati del vector. Se fosse stata una list, avrei sempre utilizzato it++, ma al suo interno l’iteratore avrebbe avuto un overload diverso dell’operatore ++, basato sulla struttura dati della lista.

Oppure possiamo fare un ciclo dal primo all’ultimo elemento in questo modo:

for(vector::iterator it = v.begin(); it < v.end(); ++it)
{
count << *it;
}

la prima parte del for dichiara una variabile di tipo iteratore di vector e la inizializza con l’iteratore alla prima posizione del mio vector.
La seconda parte controlla che l’iteratore sia sempre ad una posizione precedente a quella restituita da end() (ovvero la posizione dopo l’ultimo elemento).
La terza parte incrementa l’iteratore per spostarlo alla posizione successiva.

Esistono inoltre diversi tipi di iteratori, come ad esempio il reverse_iterator, che ridefiniscono l’effetto di alcuni operatori per consentire di utilizzare la stessa logica avendo comportamenti diversi.
Ad esempio il reverse_iterator si comporta in modo opposto all’iterator, infatti usando l’operatore ++, otteniamo uno spostamento indietro dell’operatore, mentre usando il — otteniamo uno spostamento in avanti.
La sintassi del ciclo cambierà solo per quanto riguarda il tipo di iteratore istanziato, mentre il resto rimane invariato.
Per ciclare un vector dalla fine all’inizio, possiamo ad esempio fare cosi:

vector::reverse_iterator revIt = v.end();
while (revIt != v.begin()) {
std::cout << ‘ ‘ << *revIt;
++revIt;
}

in questo caso l’istruzione ++revIt decrementa l’iteratore, invece di incrementarlo, proprio perchè il reverse_iterator ha un’implementazione diversa dall’operatore ++ rispetto all’iterator normale.

Come visto per i costruttori dei container, si può istanziare un container specificando due iteratori come indirizzi di inizio e fine memoria da cui copiare, e lo si può fare passando degli iteratori, in questo modo:

vector<int> v2(v.begin(), v.end());

in questo modo indico a v2 di copiarsi e aggiungere al suo interno degli elementi presi dall’iteratore restituito da v.begin(), e iterato fino a v.end(). Ovviamente v.end() non contiene elementi, per cui è escluso dai limiti della copia.

 

Annunci
  1. Lascia un commento

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger hanno fatto clic su Mi Piace per questo: