Skip to content

Readme.md

Latest commit

 

History

History
177 lines (116 loc) · 7.48 KB

Readme.md

File metadata and controls

177 lines (116 loc) · 7.48 KB
Raw

Iterator Pattern

Zurück

(Credits: Blog von Vishal Chovatiya)

Wesentliche Merkmale

Kategorie: Behavioral Pattern

Ziel / Absicht:

In einem Satz:

„Das Iterator Pattern stellt eine einheitliche Möglichkeit bereit, die Elemente einer Sammlung nacheinander zu durchlaufen, ohne deren interne Struktur (Array, Liste, Baum, ...) offenzulegen.”

Das Iterator Pattern gehört zu den Verhaltensmustern (Behavioral Patterns) und trennt die Logik zum Durchlaufen einer Sammlung von der Sammlung selbst. Eine Collection-Klasse muss so nicht mehr wissen, wie auf ihre Elemente zugegriffen wird, sondern delegiert diese Aufgabe an ein eigenes Iterator-Objekt. Dieses Iterator-Objekt kennt den aktuellen Zustand des Durchlaufs (z. B. die aktuelle Position) und bietet eine einheitliche Schnittstelle, typischerweise mit Operationen wie „gibt es ein nächstes Element?” und „liefere das nächste Element”.

Dadurch können verschiedenste Datenstrukturen – Arrays, verkettete Listen, Bäume, Graphen – auf dieselbe Weise durchlaufen werden, ganz unabhängig davon, wie sie intern aufgebaut sind.

Abbildung 1: Eine Collection kann auf verschiedene Arten durchlaufen werden: Depth-First Traversal (links) versus Breadth-First Traversal (rechts).

Ein weiterer Vorteil ist, dass mehrere Iteratoren gleichzeitig und unabhängig voneinander über dieselbe Sammlung laufen können, ohne sich gegenseitig zu beeinflussen.

Das Pattern folgt außerdem dem Single-Responsibility-Prinzip, da die Traversierungslogik nicht mehr die Collection-Klasse aufbläht, sowie dem Open/Closed-Prinzip, weil neue Durchlaufstrategien (z. B. rückwärts, gefiltert, in Baumreihenfolge) als zusätzliche Iterator-Implementierungen ergänzt werden können, ohne bestehenden Code zu ändern.

In C++ ist dieses Pattern besonders interessant, weil die Sprache mit ihren eingebauten Iteratoren (z. B. in der STL) und dem Range-based-for-Loop bereits eine sehr elegante, idiomatische Umsetzung dieses Konzepts anbietet – ein guter Anknüpfungspunkt, um das klassische GoF-Pattern mit modernem C++ zu vergleichen.

Struktur (UML):

Das folgende UML-Diagramm beschreibt eine Implementierung des Iterator Patterns. Es besteht im Wesentlichen aus fünf Teilen:

  • Client: Fordert das Iterator-Objekt von einem aggregierten Objekt an und "konsumiert" es, wenn die Elemente durchlaufen werden sollen.
  • AggregateBase: Abstrakte Basisklasse (oder Schnittstelle) für alle konkreten Aggregate. Diese Klasse enthält eine Methode, die auf Anfrage ein Iterator-Objekt zurückgibt.
  • ConcreteAggregate: Repräsentiert die konkrete Implementierung der AggregateBase-Schnittstelle. Hat Zugriff auf die Elemente, die mit dem Iterator durchlaufen werden sollen.
  • IteratorBase: Abstrakte Klasse (oder Schnittstelle) eines konkreten Iterators. Enthält Methoden (präziser: die Signaturen von Methoden), mit denen die Elemente durchlaufen werden können.
  • ConcreteIterator: Konkrete Realisierung von IteratorBase.

Abbildung 2: Schematische Darstellung des Iterator Patterns.

Conceptual Example:

Quellcode 1 – C++ spezifische Variante
Quellcode 2 – Standard Variante

Die erste Umsetzung des Iterator Patterns berücksichtigt, dass es in C++ für Container bereits vordefinierte Iteratoren gibt. Dies kann man - wenn es sich bei der ConcreteAggregate-Klasse um einen STL-Standardcontainer handelt - ausnutzen. Im zweiten Beispiel wird mittels

using TIterator = typename std::vector<TElement>::iterator;

der Standard-Iterator des STL-Containers std::vector<TElement> verwendet.

Sollte die ConcreteAggregate-Klasse kein STL-Standardcontainer sein, und dies dürfte in der Mehrzahl der zu betrachtenden Beispiele der Fall sein, dann muss containerspezifisch eine Realisierung der Iteratoren-Methoden reset, getCurrent und hasNext erfolgen, siehe dazu folgende Definition der Basisklasse IteratorBase:

template <typename T>
class IteratorBase
{
public:
    virtual ~IteratorBase() = default;
    virtual void reset() = 0;
    virtual const T& getCurrent() const = 0;
    virtual bool hasNext() = 0;
};

Regelwerk für die Methoden reset, getCurrent und hasNext:

Ähnlich wie für C++ Standard-Iteratoren gelten auch für die drei Methoden reset, getCurrent und hasNext einige Regeln bzw. Konventionen:

  • Der Aufruf von getCurrent muss „geschützt” sein:

    while (iter.hasNext()) { 
    elem = iter.getCurrent();
}

  • Ein Aufruf von getCurrent ohne vorhergehenden Aufruf von hasNext bewirkt ein „undefined behaviour”:

    // no preceding call of 'hasNext':
elem = iter.getCurrent();  // "undefined behaviour", z.B. exception

  • Wiederholter Aufruf von getCurrent() ohne hasNext():

    In diesem Fall liefert getCurrent immer dasselbe Objekt bzw. Element der Aufzählung zurück.

  • reset-Methode

    Mit reset kann man eine aktive Traversierung / Iteration von Anfang an neu beginnen.

  • Aufruf einer reset()-Methode am Ende einer Iteration:

    Die Frage, die sich hier stellt, lautet: "Muss ich reset am Ende einer Iteration aufrufen, wenn ich mit demselben Iterator den Container zum zweiten Mal durchlaufen möchte?" Die Antwort lautet: Nein.

  • Prinzipieller Aufruf von hasNext():

    Wie reagiert ein Aufruf von hasNext(), wenn der Rückgabewert false ist? Wenn ich genau dann hasNext() wieder aufrufe, sollte hasNext() true zurückliefern und damit eine zweite Iteration von Beginn an einleiten.

Hinweis 1: Mehrere Iterator-Objekte zu einem Container:

Natürlich ist es möglich, von einem Container mehrere Iterator-Objekte zu erzeugen. Wie immer Sie die Klasse ConcreteIterator realisieren: Wenn gleichzeitig mehrere Iterator-Objekte einen Container traversieren, dann muss jeder Iterator für sich autark arbeiten.

Hinweis 2: Änderungen am Container während des Iterierens:

Prinzipiell sollte man erwähnen, dass Sie bei der Realisierung eines Iterators zugrunde legen sollten, dass während des Iterierens keine Änderungen am Container erfolgen dürfen.

Würden Sie das Verändern des Containers hier zulassen, würde die Komplexität in der Realisierung eines korrekt funktionierenden Iterators unverhältnismäßig stark ansteigen. Dies ist auch der Grund, warum Standard-Iteratoren in den Frameworks J2SE und .NET in derartigen Fällen eine Ausnahme werfen (Java: ConcurrentModificationException, C#: System.InvalidOperationException).

Eine einfache Lösung dieses Problems bestünde darin, die zu iterierenden Elemente vor dem Beginn des Traversierens einfach zu kopieren. In der Regel dürfte dies aus Gründen der Performance und des benötigten Arbeitsspeichers aber ausscheiden.

Literaturhinweise

Die Anregungen zum konzeptionellen Beispiel finden Sie unter

https://refactoring.guru/design-patterns

und

https://www.codeproject.com

vor.

Zurück