Muster: Iterator

Zurück zu Interpreter | Hoch zu Inhaltsverzeichnis | Vor zu Kommando

Iterator

Greife auf alle Elemente einer Sammlung zu.

Zweck

Häufig besteht die Notwendigkeit auf alle Elemente einer Sammlung (engl. Collection) (z.B. eines Arrays oder einer Liste) zuzugreifen - beispielsweise um diese an eine Funktion zu übergeben. Der Iterator ermöglicht es, dies sequentiell (d.h. in einer bestimmten Reihenfolge) zu tun, ohne dabei wissen zu müssen, wie die Sammlung aufgebaut ist.

Beispielsweise könnten natürliche Zahlen (oder andere Objekte, auf denen eine Ordnung definiert ist) in einer Liste oder einem Binärbaum gespeichert abgelegt sein. Wollen wir die bisher abgelegten Zahlen z.B. mit einer besonderen Formatierung ausgeben, stehen wir vor dem Problem, dass sich die Algorithmen zum Traversieren (d.h. Durchlaufen) eines Baumes und einer Liste stark unterscheiden - wir müssten in unserem Programm also eine Abfrage einbauen, die - je nachdem ob wir es mit einem Baum oder einer Liste zu tun haben - zu unterschiedlichen Unterprogrammen springt. Der Einsatz eines Iterators macht diese umständliche Vorgehensweise überflüssig: Über die eigentliche Sammlung wird einfach ein passender Iterator "gestülpt" und wir können nacheinander auf die einzelnen Zahlen zugreifen, indem wir uns der (einfachen und immer gleichen) Schnittstelle des Iterators bedienen (polymorphe Traversierung).

Weiterhin erlaubt das Iterator-Muster die mehrfache und gleichzeitige Traversierung derselben Sammlung: Dazu reicht es aus, mehrere Iterator-Objekte zu erzeugen!

UML

Entscheidungshilfen

Wenn auf alle Elemente verschiedenartiger Sammlungen zugegriffen werden soll, kann man das Iterator-Muster verwenden. Meist verursacht es jedoch Probleme, wenn die Sammlung während der Traversierung geändert werden soll (insbesondere falls diese Änderungen die Anzahl der Elemente in der Sammlung beeinflussen). Diesbezüglich existieren jedoch verschiedenen Lösungsansätze. Die 2 trivialsten Möglichkeiten sind die folgenden. Die einfachste Variante ist vor dem Durchlauf eine Kopie der Daten anzulegen und auf diesen die Traversierung durchzuführen("Snapshot"-Variante). Eine dynamische Lösung der Problematik würde bei Veränderungen dem Iterator diejenigen Aktionen mitteilen, um dann, falls es notwendig ist, darauf zu reagieren. Problematisch ist der Zugriff gegebenenfalls auch in Multithread-Umgebungen.

Implementation

Kernstück der Implementierung ist eine einheitliche Schnittstelle, die alle für die Traversierung benötigten Funktionen bereitstellt:

• start() springt zum ersten Element der Sammlung. Üblicherweise ist der Aufruf dieser Funktion beim ersten Durchlauf nicht erforderlich; soll aber in der Mitte abgebrochen und wieder von vorne begonnen werden, leistet sie das Gewünschte.
• gibElement() greift auf das aktuelle Element zu,
• weiter() springt zum nächsten Element,
• gibtWeiteres() prüft, ob das letzte Element erreicht ist oder noch weitere vorhanden sind.

Diese Schnittstelle muss nun für jede Sammlung, für die ein Iterator verfügbar sein soll, getrennt implementiert werden.

Dazu wird meistens intern ein Zeiger auf das aktuelle Element, so wie es in der zugrundeliegenden Sammlung enthalten ist, gespeichert; zusätzlich bedarf es eines Algorithmus, der für ein Element der Sammlung dessen Nachfolger bestimmt. Dieser Algorithmus hängt natürlich in besonderer Weise von der Art der Sammlung ab, für die der Iterator implementiert werden soll: Bei einer einfach verketteten Liste wird häufig geradewegs der Verkettung gefolgt, bei einem Binärbaum hat man bereits die Wahl zwischen einer Pre-, In- oder Post-Order-Traversierung und bei Hashtabellen ist von Fall zu Fall zu entscheiden.

Weitergehende Iteratoren ermöglichen auch die Vor- und Rückwärtsnavigation durch die Sammlung, oder beeinflussen die Reihenfolge nach bestimmten Sortierkriterien.

Man kann des Weiteren bei der Implementierung verschiedene Varianten eines Iterators unterscheiden. Bezüglich der Kontrolle der Iteration sind 2 Varianten denkbar:

• Externer Iterator( Die Traversierung ist im Aggregat enthalten)
• Interner Interator( Die Traversierung wird im Iterator selbst durchgeführt)

Beispielimplementationen sind verfügbar in

• C# und
• Java

Verwandte Muster

• Der Iterator wird oft verwendet, um innerhalb des Besucher-Musters alle Objekte zu besuchen.
• Kompositum :Innerhalb rekursiver Datenstrukturen werden Iteratoren häufig benutzt
• Fabrik Methode: polymorphe Iteratoren basieren oft auf der Fabrik Methoden Muster um die jeweilige Unterklasse des zu benutzenden Iterators zu instanzieren
• Memento : Mementos können benutzt werden um einen Status einer Iteration zu speichern

Weblinks

Wikipedia: Iterator (Entwurfsmuster)

Hoch zum Inhaltsverzeichnis