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, 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 (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.
Implizite Iteratoren
Mehrere Objektorientierte Sprachen wie Perl, Python, C#, Ruby sowie neuere Java- und Delphi-Versionen 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)
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, 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 zur 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.
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ärbaumtraversierer.
Beispiel eines Generators, der Elemente erzeugt anstatt 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, 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 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 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(),[1] std::copy()[2] und std::accumulate()[3] 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:
// Ein beliebiger Standard-Containertyp jedes ItemType Elements
ContainerType<ItemType> c;
// Funktion, die Zugriff auf jedes Element besitzt
void processItem(const ItemType& i) {
std::cout << i << '\n';
}
// Eine for-each-Iterationsschleife
std::for_each(c.begin(), c.end(), processItem);
Dasselbe kann durch den Einsatz von std::copy und std::ostream_iterator[4] 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,[5] die im Java JDK 1.2 eingeführt wurde, erlaubt das Iterieren von Containerklassen. Jeder Iterator stellt Funktionen namens next(),[6] hasNext()[7] sowie eine optionale Funktion namens remove()[8] 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, ob das letzte Element bereits zurückgegeben wurde. Das folgende Beispiel zeigt eine simple Verwendung von Iteratoren in Java:
Iterator iter = list.iterator();
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[9] einen Iterator namens ListIterator,[10] 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[11] eingeführt, welche eine erweiterte for-Schleife im Sinne von foreach darstellt. Iterable definiert die Funktion iterator(),[12] 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[13] 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 melden, 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
foreach (array_expression as $value)
echo "$value\n"
- Beispiel B
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.
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
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
IteratorJava API - .NET Interface im MSDN
- Boost C++ Iterator Library (englisch)
- PHP: Object Iteration (englisch)
Einzelnachweise
-
std::for_each() -
std::copy() -
std::accumulate() -
std::ostream_iterator -
java.util.IteratorJava API Specification -
next()Java API Specification -
hasNext()Java API Specification -
remove()Java API Specification -
java.util.ListJava API Specification -
java.util.ListIteratorJava API Specification -
IterableJava API Specification -
iterator()Java API Specification - Entwurfsmuster: Iterator (Verhalten)