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, 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 Zugriffsschritt 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, so wie 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 ( genannt) sowie durch Selbstmodifizierung auf das nächste Element in der Menge zeigen ( 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 besteht darin, 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.
Implizite Iteratoren Mehrere objektorientierte Sprachen wie Perl, Python, C#, Ruby sowie neuere Java- und Delphi-Versionen stellen eine intrinsische Art zur Verfügung, durch Elemente zu iterieren, 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 for_each-Befehl oder seine Äquivalente, wie unten stehendes Python-Beispiel zeigt: for value in iterable: print(value) Die Menge/Liste iterable wird mittels der for-Schleife durchlaufen; in jedem Schleifendurchlauf enthält die Variable value jeweils das aktuelle Element aus iterable.
Manchmal werden Iteratoren auch direkt vom Objekt der Datensammlung generiert, wie unten stehendes Ruby-Beispiel zeigt:
iterable.each do |value| puts value end Der Aufruf der Methode each der Menge/Liste iterable liefert einen Iterator, den die do-Schleife Element für Element abschreitet. Für jedes Element wird der Schleifenkörper puts value ausgeführt, wobei die Variable value das jeweils aktuelle Element enthält.
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] for ... in ... ist hier die „Schleife“ über der Menge/Liste roster mit „aktuelles-Element-Variable“ person. Für jedes Element wird geprüft, ob (für das Element) eine Bedingung zutrifft (if person.male), die Menge wird also gefiltert. Von den verbleibenden Elementen wird jeweils person.name in die Ergebnisliste names übernommen – eine Liste der Namen.
Manchmal ist die implizite, versteckte Natur nur teilweise vorhanden. Die Programmiersprache C++ stellt die for_each-Funktionalität über Funktionstemplates zur Verfügung, und 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 in einen Index umgewandelt werden.
Die Fähigkeit eines Containers zur Selbstmodifizierung, während durch seine Elemente iteriert wird, hat sich in modernen, objektorientierten Programmiersprachen als wichtig erwiesen. Die Beziehungen zwischen den einzelnen Objekten und zwischen den Effekten ihrer Operationen sind in solchen Sprachen nicht mehr eindeutig. Um dieses Problem zu lösen, werden Iteratoren eingesetzt.
Generatoren Ein Generator ist eine spezielle Form einer Koroutine, die bei jedem Aufruf ein (oder mehrere) Element(e) einer Folge liefert. Diese Folge kann eine gegebene Liste sein, dann entspricht der Generator weitgehend einem Iterator. Ein Generator kann die (nächsten) Elemente aber auch erst beim jeweiligen Aufruf erzeugen – dann benötigt er keine bestehende Liste, wie sie beim Iterator notwendig ist.
Die meisten Iteratoren lassen sich in natürlicher, intuitiver Art und Weise durch Generatoren implementieren. Da Generatoren ihren lokalen Status zwischen Funktionsaufrufen beibehalten, eignen sie sich hervorragend zur Implementierung von komplexen zustandsorientierten Iteratoren wie beispielsweise Binärbaumtraversierern.
Beispiel für einen Generator, der Elemente erzeugt, statt sie aus einer Liste zu lesen:
(Fibonacci-Folge; „Rückgabe“ des jeweiligen Werts mit Hilfe des Python-Befehls yield) # Ein Generator für die Fibonacci-Folge def fibonacci(limit_anzahl_elemente): a, b = 0, 1
for _ in range(limit_anzahl_elemente): a, b = b, a + b yield a
# Die ersten Zahlen der Folge werden berechnet und ausgegeben for number in fibonacci(100): print(number)
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, damit an den Anfang zurückgekehrt werden kann. 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 for_each-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 item in list) Console.WriteLine(item);
C# 2.0 unterstützt ebenfalls Generatoren: Eine Funktion, welche als IEnumerable (oder auch IEnumerator) 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 die Zeigerarithmetik von C angelehnt. Die Operatoren * und -> werden zur Referenzierung der Elemente benutzt. Weitere Operatoren wie ++ werden zum Navigieren durch die Elemente benutzt.
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 Definition und Verwendung eines Iterators in C++11: #include <iostream> #include <stdexcept> #include <initializer_list>
class Vector { public: using iterator = double*; iterator begin() { return elem; } iterator end() { return elem + sz; }
Vector(std::initializer_list<double> lst) :elem(nullptr), sz(0) { sz = lst.size(); elem = new double[sz]; double* p = elem; for (auto i = lst.begin(); i != lst.end(); ++i, ++p) { *p = *i;
~Vector() { delete[] elem; } int size() const { return sz; } double& operator[](int n) { if (n < 0 || n >= sz) throw std::out_of_range("Vector::operator[]"); return elem[n];
Vector(const Vector&) = delete; // Dreierregel Vector& operator=(const Vector&) = delete; private: double* elem; int sz;
int main() { Vector v = {1.1*1.1, 2.2*2.2};
for (const auto& x : v) { std::cout << x << '\n';
for (auto i = v.begin(); i != v.end(); ++i) { std::cout << *i << '\n';
for (auto i = 0; i <= v.size(); ++i) { std::cout << v[i] << '\n';
Die Programmausgabe ist:
1.21 4.84 1.21 4.84 1.21 4.84 terminate called after throwing an instance of 'std::out_of_range' what(): Vector::operator[]
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::for_each() std::copy()std::copy() und std::accumulate()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 weitere Benutzung des Iteratorobjekts. Das unten stehende Beispiel zeigt die Verwendung von for_each: // Ein beliebiger Standard-Containertyp jedes ItemType Elements ContainerType<ItemType> c;