Iteratore

In informatica, un iteratore è un oggetto che consente di visitare tutti gli elementi contenuti in un altro oggetto, tipicamente un contenitore, senza doversi preoccupare dei dettagli di una specifica implementazione. Un iteratore è talvolta chiamato cursore, specialmente nel contesto delle basi dati.

Descrizione

Un iteratore può essere considerato un tipo di puntatore specializzato che fornisce un punto di accesso sequenziale agli elementi di un oggetto che contiene un numero finito di oggetti più semplici, detto aggregato.

L'iteratore offre due operazioni fondamentali:

• Accesso all'elemento dell'aggregato attualmente puntato;
• Aggiornamento del puntatore così che punti all'elemento successivo nella sequenza.

Queste semplici operazioni permettono di accedere agli elementi di un aggregato in modo uniforme e indipendente dalla struttura interna dell'aggregato, che può essere ben più complessa delle sequenze lineari implementate da array e liste. Esempi di aggregati complessi sono l'array associativo, l'albero e la hash table.

Oltre all'accesso e all'aggiornamento, un iteratore deve fornire come minimo due operazioni:

• Inizializzazione o ripristino dello stato iniziale, in cui l'elemento puntato dall'iteratore è il primo della sequenza;
• Verifica se l'iteratore ha esaurito tutti gli elementi dell'aggregato, cioè se è stato aggiornato oltre l'ultimo elemento della sequenza.

A seconda del linguaggio e delle necessità, gli iteratori possono fornire operazioni aggiuntive o esibire comportamenti diversi. Un esempio di iteratori specializzati è offerto dagli iteratori bidirezionali, che permettono di visitare l'insieme degli elementi di un aggregato partendo dall'ultimo elemento e procedendo verso il primo. Un altro esempio è offerto dagli iteratori filtranti, che consentono di visitare soltanto il sottoinsieme degli elementi di un aggregato che soddisfa a condizioni pre-impostate all'interno dell'iteratore.

Una classe iteratore viene solitamente progettata in stretta coordinazione con la corrispondente classe contenitore. Solitamente il contenitore fornisce i metodi per creare iteratori su di esso.

Motivazioni e benefici

Lo scopo primario di un iteratore è di consentire al codice che ne fruisce di visitare ogni elemento di un contenitore senza dipendere dalla struttura interna e dai dettagli di implementazione del contenitore stesso.

Questo permette di riutilizzare, con variazioni minime, il codice che accede ai dati. È possibile cioè modificare o sostituire un contenitore con uno di struttura diversa senza compromettere la correttezza del codice che visita i suoi elementi.

Confronto con l'uso di indici

Nei linguaggi procedurali è comune usare indici interi per scorrere gli elementi di un array. Sebbene con alcuni contenitori orientati agli oggetti possano essere usati anche indici interi, l'uso degli iteratori ha i seguenti vantaggi:

• I cicli di conteggio non sono adatti per tutte le strutture dati; in particolare, per le strutture dati in cui l'accesso diretto è lento o assente, come le liste e gli alberi.

• Gli iteratori possono fornire un modo coerente di iterare sulle strutture dati di ogni categoria, e perciò rendono il codice più leggibile, riusabile, e meno sensibile ai cambiamenti nella struttura dati.

• Un iteratore può imporre restrizioni di accesso aggiuntive, come assicurare non si saltino degli elementi o che non si visiti più volte lo stesso elemento.

• Un iteratore può consentire all'oggetto contenitore di essere modificato senza invalidare l'iteratore. Per esempio, dopo che un iteratore è avanzato oltre il primo elemento può essere possibile inserire elementi aggiuntivi all'inizio del contenitore con risultati predicibili. Con l'uso di indici, questo è problematico dal momento che gli indici devono cambiare.

Gli iteratori impliciti

Alcuni linguaggi orientati agli oggetti, come Perl e Python, forniscono un modo intrinseco di iterare sugli elementi di un oggetto contenitore senza l'introduzione di un oggetto iteratore esplicito. Ciò si manifesta spesso in qualche tipo di operatore "for-each", come nei seguenti esempi:

   # Perl, iterazione implicita
   foreach $val (@list) {
       print "$val\n";
   }

   # Python, iterazione implicita
   for Value in List:
       print Value

Anche il linguaggio C++ ha un template di funzione std::for_each() che permette una simile iterazione implicita, ma richiede ancora oggetti iteratori espliciti come input iniziale.

I generatori

Un generatore è una categoria speciale di iteratore in cui l'oggetto contenitore non è realizzato pienamente. Ciò permette di elaborare un elemento alla volta di collezioni astratte o addirittura infinite. I generatori sono comuni nei linguaggi di programmazione funzionali, o nei linguaggi che prendono in prestito alcuni concetti funzionali. I generatori sono spesso implementati in termini di continuazioni.

Gli iteratori in vari linguaggi di programmazione

C++

Il linguaggio C++ fa ampio uso di iteratori nella sua Standard Template Library. Tutti i template di tipi di contenitori standard forniscono un insieme ricco e coerente di tipi di iteratori. La sintassi degli iteratori standard è progettata per somigliare a quella dell'ordinaria aritmetica dei puntatori del linguaggio C, in cui gli operatori * e -> si usano per referenziare l'elemento a cui l'iteratore punta, e gli operatori di aritmetica dei puntatori come ++ si usano per far avanzare l'iteratore al prossimo elemento.

Gli iteratori sono solitamente usati a coppie, dove uno viene usato per l'iterazione effettiva e il secondo serve a marcare la fine della collezione. Gli iteratori vengono creati dalla corrispondente classe contenitore usando metodi standard come begin() e end(). L'iteratore reso da begin() punta al primo elemento, mentre l'iteratore reso da end() è un valore speciale che non fa riferimento a nessun elemento.

Quando un iteratore viene fatto avanzare oltre l'ultimo elemento è per definizione uguale allo speciale valore reso da end(). Il seguente esempio mostra un tipico uso di un iteratore.

ContainerType C; // Qualunque tipo di contenitore standard, come std::list<qualchetipo>
ContainerType::iterator A = C.begin();
ContainerType::iterator Z = C.end();
while( A != Z ) {
   ContainerType::value_type value = *A;
   std::cout << value << std::endl;
    ++A;
}

Ci sono molte varietà di iteratori, ognuno con un comportamento leggermente diverso, tra i quali: iteratori in avanti, all'indietro, e bidirezionali; iteratori ad accesso diretto; iteratori di input e di output; e iteratori "const" (che proteggono dalle modifiche il contenitore o i suoi elementi). Comunque non tutti i tipi di contenitori supportano ogni tipo di iteratore. È possibile per gli utenti creare i loro tipi di iteratore derivando delle sottoclassi dal template standard di classe std::iterator.

La sicurezza degli iteratori viene definita separatamente per i diversi tipi dei contenitori standard; in alcuni casi l'iteratore è molto permissivo nel consentire modifiche al contenitore durante l'iterazione.

Java

Introdotta con lo standard Java 1.2, l'interfaccia java.util.Iterator permette di iterare su classi contenitore. Ogni Iterator fornisce un metodo next() e un metodo hasNext(), e può opzionalmente supportare un metodo remove(). Gli iteratori vengono creati dal metodo iterator() fornito dalla corrispondente classe contenitore.

Il metodo next() avanzerà l'iteratore e poi renderà il valore puntato da quell'iteratore. Appena dopo essere stato creato, un iteratore punta a un valore speciale che precede il primo elemento, cosicché il primo elemento si ottiene con la prima chiamata a next(). Per determinare se tutti gli elementi del contenitore sono stati visitati, si usa il metodo booleano hasNext(). Il seguente esempio mostra un semplice uso degli iteratori:

   Iterator it = list.iterator();
   while (it.hasNext()) {
       Object val = it.next();
       System.out.println(val.toString());
   }

Per i tipi di collezioni che lo supportano, il metodo remove() dell'iteratore può essere usato per togliere dal contenitore l'elemento visitato per ultimo. La maggior parte degli altri tipi di modifica al contenitore non sono sicuri mentre si sta iterando.

Python

Gli iteratori in Python sono una parte fondamentale del linguaggio e in molti casi non vengono notati siccome sono usati implicitamente tramite l'istruzione "for". Tutti i tipi di sequenza incorporati in Python supportano l'iterazione, così come molte classi che fanno parte della libreria standard. Il seguente esempio mostra una tipica iterazione implicita su un sequenza:

   for value in sequence:
       print value

Tuttavia, gli iteratori possono essere usati e definiti esplicitamente. Per ogni tipo o classe di sequenza iterabile, la funzione incorporata iter() viene usata per creare un oggetto iteratore. Tale oggetto iteratore fornisce un metodo next() che rende l'elemento successivo del contenitore. Quando non rimangono più elementi, verrà sollevata un'eccezione di tipo StopIteration. Il seguente esempio mostra un'iterazione equivalente su una sequenza usando iteratori espliciti:

   it = iter(sequence)
   try:
       while True:
           print it.next()
   except StopIteration:
       pass

Qualunque classe definita dall'utente può supportare l'iterazione standard (sia implicita che esplicita) definendo un metodo __iter__() che crea un oggetto iteratore (che dovrà definire il metodo next()).

Anche Python supporta i generatori, che sono una categoria speciale di iteratori su una collezione non realizzata. Un generatore è una funzione "congelata". Dopo che ogni valore è stato emesso (con l'istruzione "yield"), lo stato della funzione viene congelato. Quando la funzione viene invocata nuovamente, l'esecuzione riprende dal punto in cui l'istruzione 'yield' l'aveva abbandonata, con tutte le variabili della funzione nello stato in cui erano. Ecco un esempio di un generatore che rende ogni numero della successione di Fibonacci:

   def fibo_gen():
       x = 0
       y = 1
       while True:
           yield x
           x, y = y, x+y

Collegamenti esterni

• Boost C++ Iterator Library