Iteratore

Nella programmazione orientata agli oggetti, un iteratore è un oggetto che consente di scorrere tutti gli elementi contenuti in qualche altro oggetto, tipicamente un contenitore. Un iteratore è talvolta chiamato cursore, specialmente nel contesto di un database.

Descrizione

Un iteratore può essere pensato come un tipo di puntatore che ha quattro operazioni primarie:

• Inizializzare l'iteratore cosicché punti al primo elemento del contenitore.
• Determinare quando l'iteratore ha esaurito tutti gli elementi del contenitore.
• Modificare l'iteratore cosicché punti all'elemento successivo del contenitore.
• Referenziare l'elemento corrente del contenitore.

A seconda del linguaggio e delle intenzioni d'uso, gli iteratori possono anche fornire operazioni aggiuntive o esibire comportamenti diversi.

Lo scopo primario di un iteratore è di consentire al codice utilizzatore di elaborare ogni elemento di un contenitore, mantenendolo isolato dalla struttura interna del contenitore. Questo consente al codice del contenitore di cambiare la propria implementazione senza compromettere il codice utilizzatore. 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.

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

Link esterni

• Boost C++ Iterator Library