Iterator

Der Begriff Iterator stammt aus dem Bereich der Softwareentwicklung und bezeichnet einen Zeiger, mit dem die Elemente einer Menge durchlaufen werden können (z. B. eine Liste). Der Begriff leitet sich aus der mathematischen Methode der Iteration ab. Der Iterator wird insbesondere im Bereich der Datenbanken meist Cursor genannt.

Beschreibung

Ein Iterator ist ein spezieller Zeiger, der innerhalb eines Programms vom Software-Entwickler dazu verwendet werden kann, um auf Elemente einer Menge, vereinfacht eine Liste, zuzugreifen. Iteratoren arbeiten nach dem Grundprinzip "Wenn es ein weiteres Element in der Liste gibt, dann stelle es zur Verfügung."

Dies ist vereinfacht damit vergleichbar, wie man einen Text, der eine Liste von Worten ist, liest: "Wenn es ein nächstes Wort gibt, dann lies es. Wenn kein weiteres Wort mehr folgt, ist der Text beendet." In jedem als Iteration bezeichneten Zugriffs-Schritt steht somit exakt ein Wort des Textes zur Bearbeitung zur Verfügung.

Viele der in der Programmierpraxis verwendeten Iteratoren stellen über die lesende Zugriffsmöglichkeit hinaus Mechanismen zur Verfügung, die ein aktuell gelesenes Element aus der Liste entfernen oder ein neues Element in die Liste aufnehmen, sowie bei der Bearbeitung eines Textes Worte eingefügt oder gelöscht werden können.

Externe Iteratoren und das Iterator-Entwurfsmuster

Ein externer Iterator kann als eine Art Zeiger betrachtet werden, der zwei primäre Funktionen besitzt: Ein bestimmtes Element in einer Menge von Objekten referenzieren (element access genannt) sowie durch selbst-Modifizierung auf das nächste Element in der Menge zu zeigen (element traversal genannt). Abhängig von der verwendeten Programmiersprache und der Anwendung können Iteratoren zusätzliche Funktionalität sowie verschiedenes Verhalten aufweisen.

Der Hauptzweck des Iterators ist es, dem Benutzer zu erlauben, auf jedes Element in einer Menge zuzugreifen, während es ihn von der Datenstruktur der Menge isoliert. Dies befähigt die Menge, die Elemente auf jede mögliche Art und Weise zu verwalten, während sie sich dem Benutzer gegenüber so verhält, als wäre sie eine simple Sequenz oder eine Liste. Eine Iteratorklasse wird in enger Koordination mit ihrer Containerklasse, also ihrer Menge, entworfen. Üblicherweise stellt die Containerklasse die Funktionen zur Verfügung, die zur Erstellung von Iteratoren benutzt werden. Ein Zähler in einer Schleife (auch loop Counter genannt) wird manchmal auch als Schleifeniterator bezeichnet. Dabei ist zu beachten, dass ein solcher Zähler nur die element traversal Funktionalität abbildet und nicht die element access Funktionalität.

Generatoren

Eine Art, Iteratoren zu implementieren, ist es, eine spezielle Funktion zu erstellen, welche als Generator bekannt ist. Diese kann, anstatt ein Element auf einmal zurückzuliefern, mehrere Elemente in mehreren Schritten dem Benutzer zurückliefern. Die meisten Iteratoren lassen sich in natürlicher, intuitiver Art und Weise durch Generatoren abbilden. Da Generatoren ihren lokalen Status zwischen Funktionsaufrufen beibehalten, eignen sie sich hervorragend zur Implementierung von komplexen zustandsorientierten Iteratoren wie sogenannte Binärbaumtraversierer. Als Beispiel sei hier ein Generator angeführt, welcher Zahlen einer Fibonacci-Folge mit Hilfe des Pythonbefehls yield zurückliefert:

 def fibonacci():
     a, b = 0, 1
     while True:
         yield a
         a, b = b, a+b

 for number in fibonacci(): # Benutze den Generator als Iterator
     print(number)

Implizite Iteratoren

Mehrere Objektorientierte Sprachen wie Perl, Python, C#, Ruby sowie neuere Java- und Delphiversionen stellen eine intrinsische Art durch Elemente zu iterieren zur Verfügung, ohne dabei ein explizites Iteratorobjekt zu benutzen. Dieses kann allerdings auch vorhanden sein, ist aber nicht im Code der jeweiligen Programmiersprache verfügbar, wenn dies der Fall sein sollte.

Implizite Iteratoren manifestieren sich oft durch den foreach Befehl oder seine Äquivalente, wie unten stehendes Python Beispiel zeigt:

for value in iterable:
    print(value)

Manchmal werden Iteratoren auch direkt vom Objekt der Datensammlung generiert, wie unten stehendes Ruby-Beispiel zeigt:

iterable.each do |value|
  puts value
end

Dieser Iterationsstil wird auch internal iteration genannt, da sein Code vollständig im Kontext des zu iterierenden Objektes ausgeführt wird. Dieses kontrolliert somit sämtliche Aspekte der Iteration, der jeweilige Benutzer respektive Programmierer stellt nur die Operation für die einzelnen Iterationsschritte zur Verfügung, indem er eine anonyme Subroutine benutzt.

Sprachen, welche sogenannte Listenkomprehensionen oder ähnliche Konstrukte unterstützen, bedienen sich analog zu Python ebenfalls der impliziten Iteratoren während der Erstellung der Resultatsliste:

names = [person.name for person in roster if person.male]

Manchmal ist die implizite, versteckte Natur nur teilweise vorhanden. Die Programmiersprache C++ stellt die for_each Funktionalität über Funktionstemplates zur Verfügung, diese erlaubt die implizite Iteration.

Der Gegensatz zum Indizieren

Der Iterator steht dabei im Gegensatz zu einem Index oder Schlüssel:

• Über einen Iterator kann man direkt auf das zugehörige Element zugreifen, ohne die Datenstruktur selber zu kennen. Bei einem Index benötigt man immer Index und Datenstruktur.
• Ein Iterator ist nur für genau eine Datenstruktur gültig. Ein Index kann auf andere Datenstrukturen übertragen werden.
• Iteratoren lassen sich nicht serialisieren. Sie müssen dazu erst zu einem Index gewandelt werden.

Die Fähigkeit eines Containers der Selbst-Modifizierung, während durch seine Elemente iteriert wird, hat sich in modernen, objektorientierten Programmiersprachen als wichtig erwiesen. Die Zwischenbeziehungen zwischen den einzelnen Objekten und der Effekte ihrer Operationen sind in solchen Sprachen nicht mehr eindeutig. Um dieses Problem zu lösen, werden Iteratoren eingesetzt.

Iteratoren in verschiedenen Programmiersprachen

C# und andere .NET-Sprachen

Iteratoren im .NET Framework werden als Enumeratoren bezeichnet und von der Schnittstelle IEnumerator repräsentiert. IEnumerator stellt eine Funktion namens MoveNext() zur Verfügung, die jeweils zum nächsten Element der Menge geht und anzeigt, wenn das Ende erreicht ist, sowie eine Eigenschaft namens Current, um den Wert des aktuellen Elementes zu erhalten. Des Weiteren wird eine optionale reset Funktion angeboten, um an den Anfang zurückzukehren. Der Enumerator gibt als Initialisierungswert einen speziellen Wert zurück, der den Anfang markiert. Aus diesem Grund ist es nötig, nach der Initialisierung MoveNext() auszuführen.

Enumeratoren werden typischerweise von einer GetEnumerator() Funktion zurückgegeben, welche einem Objekt zugehörig ist, das die IEnumerable Schnittstelle implementiert. Der foreach Befehl in C# operiert allerdings auf jeder solchen Funktion, selbst wenn diese nicht von einem Objekt stammt, welches die IEnumerable Schnittstelle implementiert. Das folgende Beispiel zeigt eine simple Verwendung von Iteratoren in C# 2.0:

// explizite Version
IEnumerator<MyType> iter = list.GetEnumerator();
while (iter.MoveNext())
    Console.WriteLine(iter.Current);

// implizite Version
foreach (MyType value in list)
    Console.WriteLine(value);

C# 2.0 unterstützt ebenfalls Generatoren: Eine Funktion, welche als IEnumerator oder als IEnumerable zurückkehrt, aber den Befehl yield return dabei benutzt, wird vom Compiler automatisch in eine neue Klasse umgewandelt, welche die angemessene Schnittstelle implementiert.

C++

Die Programmiersprache C++ setzt Iteratoren im großen Stil ein und stellt über die C++-Standardbibliothek Iteratoren verschiedener Typen wie sogenannte forward iterators, bidirectional iterators und random access iterators zur Verfügung. Jede der Standard-Containerklassen besitzt Iteratortypen. Die Syntax der Standarditeratoren wurde an der Zeigerarithmetik von C angelehnt. Die Operatoren * und -> werden zur Referenzierung der Elemente benutzt. Weitere Operatoren wie ++ werden benutzt, um durch die Elemente zu navigieren.

Iteratoren werden üblicherweise paarweise eingesetzt. Der eine Iterator stellt die aktuelle Iteration dar, während der andere das Ende der Iteration darstellt. Die Iteratoren werden von der entsprechenden Containerklasse durch die Benutzung der Standardfunktionen begin() und end() generiert. Der Iterator, der durch begin() zurückgegeben wird, zeigt auf das erste Element, während der Iterator, der von end() zurückgeliefert wird, auf einen speziellen Wert zeigt, welcher kein Element referenziert. Wenn ein Iterator hinter das letzte Element gesetzt wird, gibt dieser den speziellen Wert von end() zurück. Das folgende Beispiel zeigt die typische Verwendung eines Iterators in C++:

ContainerType C; // Ein beliebiger Standard-Containertyp, wie std::list<sometype>

for (ContainerType::const_iterator constIt = C.begin(); constIt != C.end(); ++constIt) {
    std::cout << *constIt << '\n';
}

Es existieren viele verschiedene Iteratortypen mit leicht voneinander abweichendem Verhalten. Nicht jeder Iteratortyp unterstützt jeden Containertyp. Es ist allerdings für Programmierer möglich, eigene Iteratortypen zu definieren, indem sie eine Klasse vom Template std::iterator ableiten. Die Iteratorsicherheit ist für die verschiedenen Typen separat definiert. Die implizite Iteration ist in C++ teilweise vorhanden und wird von den Funktionen std::for_each(), std::copy() und std::accumulate() zur Verfügung gestellt. Iteratoren benötigen allerdings immer ein explizites Objekt zu ihrer Initialisierung, üblicherweise diejenigen, welche von begin() und end() zurückgegeben werden. Sobald diese ausgeführt wurde, geschieht die Iteration auf implizite Weise ohne das Iteratorobjekt weiter zu benutzen. Das unten stehende Beispiel zeigt die Verwendung von for_each:

ContainerType<ItemType> C; // Ein beliebiger Standard-Containertyp jedes ItemType Elements

void ProcessItem( const ItemType& I ) // Funktion, die Zugriff auf jedes Element besitzt
{
   std::cout << I << '\n';
}

std::for_each(C.begin(), C.end(), ProcessItem); // Eine for-each-Iterationsschleife

Dasselbe kann durch den Einsatz von std::copy und std::ostream_iterator erreicht werden:

std::copy(C.begin(), C.end(), std::ostream_iterator<ItemType>(std::cout, "\n"));

Eine Einschränkung dieser Technik ist, dass es dem Rumpf nicht erlaubt inline deklariert zu sein. Zudem benötigt dies einen Funktionszeiger, welcher an anderer Stelle deklariert werden und als Parameter übergeben werden muss. Dies kann teilweise durch die Benutzung von Bibliotheken wie Boost und der Anwendung von Lambda kompensiert werden, die gebraucht werden um, Funktionsobjekte mit verwandter Infix Syntax zu generieren. Da diese Funktionalität nur über externe Bibliotheken zur Verfügung gestellt wird, müssen diverse Problemumgehungen, auch Workarounds genannt, eingesetzt werden.

Java

Die Schnittstelle java.util.Iterator, die im Java JDK 1.2 eingeführt wurde, erlaubt das Iterieren von Containerklassen. Jeder Iterator stellt Funktionen namens next(), hasNext() sowie eine optionale Funktion namens remove() zur Verfügung. Iteratoren werden üblicherweise von einer Funktion namens iterator() generiert, welche von der dementsprechenden Containerklasse zur Verfügung gestellt wird. Ein Iterator gibt als Initialisierungwert einen speziellen Wert zurück, der den Anfang markiert. Aus diesem Grund ist es nötig, nach der Initialisierung next() auszuführen, womit das erste Element zurückgegeben wird. Die Funktion hasNext() wird dazu benutzt, um herauszufinden, wann das letzte Element zurückgegeben worden war. Das folgende Beispiel zeigt eine simple Verwendung von Iteratoren in Java:

Iterator iter = list.iterator();
//Iterator<MyType> iter = list.iterator(); in J2SE 5.0
while (iter.hasNext()){
    System.out.println(iter.next());
}

Für Kollektionen, die es unterstützen, entfernt die optionale Funktion remove() das letzte Element, auf das zugegriffen wurde. Die meisten anderen Modifikationen dieser Art sind unsicher. Zusätzlich besitzt java.util.List einen Iterator namens ListIterator, welcher eine ähnliche Schnittstelle zur Verfügung stellt, die Vorwärts- und Rückwärtsiteration erlaubt sowie den Index des aktuellen Elementes zurückgibt und das Element an einer gegebenen Position einfügen kann.

Mit der J2SE 5.0 wurde die Schnittstelle Iterable eingeführt, welche eine erweiterte for-Schleife im Sinne von foreach darstellt. Iterable definiert die Funktion iterator(), welche einen Iterator zurückliefert. Mit der Benutzung der erweiterten for-Schleife kann das vorhergehende Beispiel auf folgende Art und Weise geschrieben werden:

for (MyType obj : list){
    System.out.print(obj);
}

MATLAB

MATLAB unterstützt externe sowie interne Iteratoren. Im Falle einer externen Iteration, bei welcher der Benutzer dazu verpflichtet ist das nächste Element bereitzustellen, können mehrere Elemente definiert werden und mit einer for-Schleife anschließend durchgelaufen werden wie folgendes Beispiel zeigt:

% Definition eines an integer arrays
myArray = [1,3,5,7,11,13];

for n = myArray
   % ... etwas mit n machen...
   disp(n) %Integerausgabe zur Kommandozeile
end

Im Falle einer internen Iteration kann der Benutzer eine Operation dem Iterator übergeben um auf jedes Element in einem Array zuzugreifen. Viele nativen Operatoren und MATLAB Funktionen werden überladen um ein korrespondierendes Ausgabearray als impliziten Rückgabewert zu erhalten. Des Weiteren können die Funktionen arrayfun und cellfun für Benutzerdefinierte Operationen über native und sogenannte cell Arrays gebraucht werden.

function simpleFun
% Definition eines an integer arrays
myArray = [1,3,5,7,11,13];

% Benutzerdefinierte Operation für jedes Element durchführen
myNewArray = arrayfun(@(a)myCustomFun(a),myArray);

% %Arrayausgabe zur Kommandozeile
myNewArray

function outScalar = myCustomFun(inScalar)
% Mit 2 multiplizieren
outScalar = 2*inScalar;

Alternativerweise kann es wünschenswert sein, die Speichermechanismen des Arrays vom Programmieren zu abstrahieren, indem eine benutzerdefinierte, objektorientierte Implementierung des Iteratorentwurfsmusters zur Verfügung gestellt wird. Eine solche Implementierung, welche die externe Iteration unterstützt, wird im MATLAB Central File Exchange item angeboten. Dieses Entwurfsmuster ist nach der neuen Klassendefinitionssyntax geschrieben welche mit der MATLAB Version 7.6 (R2008a) eingeführt wurde. Des Weiteren ist eine eindimensionale cell Array Realisierung des List Abstract Data Type enthalten um eine heterogene Speicherung jedes Datentyps vorzunehmen. Es stellt die Funktionalität zur Verfügung um eine Liste mit hasNext(), next() und reset() in einer while Schleife zu verarbeiten.

PHP

Mit PHP4 wurde ein foreach Konstrukt eingeführt das ähnlich wie in Perl und vielen anderen Programmiersprachen aufgebaut war. Dieses Konstrukt erlaubt eine einfache Art über Arrays zu iterieren. Der foreach Befehl funktioniert nur mit Arrays in PHP4 und wird einen Fehler aufwerfen wenn versucht wird ihn über einen anderen Datentyp oder einer uninitialisierten Variable zu benutzen. In PHP5 ist der foreach Befehl zur Iteration über alle public members erlaubt. Das folgende Beispiel zeigt zwei unterschiedliche Schreibweisen, die zweite ist eine nützliche Erweiterung zur ersten Schreibweise:

Beispiel A

<?php
  foreach (array_expression as $value)
    echo "$value\n";
?>

Beispiel B

<?php
  foreach (array_expression as $key => $value)
    echo "($key)$value\n";
?>

Im Beispiel A wird über ein Array welches von array_expression dargestellt wird iteriert. Bei jedem Schleifendurchlauf wird der Wert des Arrayelementes an $value zugewiesen sowie der interne Zeiger des Arrays um eins nach vorne geschoben. Somit wird beim nächsten Schleifendurchlauf das nächste Arrayelement zurückgegeben. Das Beispiel B besitzt dieselbe Funktionalität wie das Beispiel A. Zusätzlich wird der Index des Elementes bei jedem Schleifendurchlauf der Variable $key zugewiesen.

In PHP5 ist die Iteratorschnittstelle vordefiniert, Objekte können verändert werden um die Iteration zu handhaben.

<?php
  class MyIterator implements Iterator
  {
     private $var = array();

     public function __construct($array)
     {
       if (is_array($array)) {
           $this->var = $array;
       }
     }

     public function rewind() {
       echo "rewinding\n";
       reset($this->var);
     }

     public function current() {
       $var = current($this->var);
       echo "current: $var\n";
       return $var;
     }

     public function key() {
       $var = key($this->var);
       echo "key: $var\n";
       return $var;
     }

     public function next() {
       $var = next($this->var);
       echo "next: $var\n";
       return $var;
     }

     public function valid() {
       $var = $this->current() !== false;
       echo "valid: {$var}\n";
       return $var;
     }
  }
?>

Diese Funktionen werden alle in einer kompletten foreach($obj AS $key=>$value) sequenz genutzt. Die Iteratormethoden werden in der folgenden Reihenfolge ausgeführt:

  1. rewind()
  2. while valid()
     {
          2.1 current() in $value
          2.3 key() in $key
          2.4 next()
     }

Python

Iteratoren in Python stellen einen fundamentalen Teil der Sprache dar, allerdings werden sie vielfach implizit und somit unsichtbar in Sprachbefehlen versteckt genutzt. Solche Befehle sind z. B. for(foreach) in sogenannten list comprehensions und in Generatorausdrücken. Alle sequentiellen Basistypen sowie viele Klassen der Standardbibliothek in Python unterstützen Iterationen. Das folgende Beispiel zeigt eine typische Iteration über einer Sequenz:

 for value in sequence:
     print(value)

Python Dictionaries, eine Form von Assoziativem Array erlaubt es direkt über sich zu iterieren wenn die sogenannten dictionary keys zurückgegeben werden. Es kann aber auch über die items Funktion eines dictionary iteriert werden, wo es die Werte dem nachfolgenden Beispiel entsprechend zu key und value zurückgibt:

for key in dictionary:
    value = dictionary[key]
    print(key, value)

for key, value in dictionary.items():
    print(key, value)

Iteratoren in Python können aber auch explizit definiert und benutzt werden. Für jeden iterierbaren Sequenztypen oder jede iterierbare Klasse steht die eingebaute iter() Funktion zur Verfügung um ein Iteratorobjekt zu generieren. Mit dem Iteratorobjekt kann mit den Funktionen next(), oder __next__() zum nächsten Element navigiert werden. Ist das Ende der Menge erreicht wird ein StopIteration Fehler aufgeworfen. Das nachfolgende Beispiel zeigt eine Äquivalente Implementation von expliziten Iteratoren:

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

Jede benutzerdefinierte Klasse kann die Standarditeration unterstützen wenn eine _iter__() Funktion definiert wurde welche ein Iteratorobjekt generiert, der Iterator muss dann eine __next__() Funktion definieren die das nächste Element zurückgibt. Die Python-Generatoren implementieren dieses Iterationsprotokoll.

Ruby

Die Implementation der Iteratoren in Ruby unterscheidet sich von den meisten anderen Programmiersprachen: Alle Iterationen gehen dem Gedanken nach, sogenannte callback closures an Containermethoden durchzureichen. Auf diese Art und Weise implementiert Ruby nicht nur eine Basisfunktionalität an Iteratoren, sondern bildet viele Iteratorentwurfsmuster ab wie z. B. sogenanntes function mapping, Filter und sogenanntes reducing.

Ruby unterstützt des Weiteren noch eine alternative Syntax für jede Basisfunktion zur Iteration:

(0...42).each do |n|
 puts n
end

… und …

for n in 0...42
 puts n
end

oder noch kürzer

42.times do |n|
 puts n
end

Siehe auch

• Iterator Entwurfsmuster

Weblinks

• Joshua Gatcomb: Understanding and Using Iterators. (englisch)
• A Technique for Generic Iteration and Its Optimization. (PDF; englisch; 216 kB)
• STL Iterators. (englisch)
• What are iterators? – Referenzbeschreibung. (englisch)
• Interface Iterator Java API
• .NET Interface im MSDN
• Boost C++ Iterator Library (englisch)
• PHP: Object Iteration (englisch)