Quelltext der Seite Iterator (Entwurfsmuster)

Der '''Iterator''' ist ein [[Entwurfsmuster]] aus dem Bereich der [[Softwareentwicklung]], das zur Kategorie der [[Verhaltensmuster (Software)|Verhaltensmuster]] (englisch {{lang|en|''behavioral design patterns''}}) gehört. Das Muster ist eines der sogenannten GoF-Muster (siehe [[Viererbande (Softwareentwicklung)|Viererbande]]). Es stellt Möglichkeiten zur Verfügung, auf Elemente einer [[Aggregation (Informatik)|aggregierten]] Struktur sequenziell zuzugreifen, ohne die Struktur zu enthüllen.<ref>{{Literatur|Autor=[[Erich Gamma]], [[Richard Helm]], [[Ralph Johnson]], [[John Vlissides]]| Titel=Entwurfsmuster| Auflage=5.| Verlag=Addison-Wesley| Ort=| Jahr=1996| ISBN=3-8273-1862-9|Seiten=335}}</ref>

Das Muster ist auch als ''Cursor'' bekannt. Mitunter wird durch Wahl des einen oder anderen Begriffes ein Unterschied im Verhalten ausgedrückt.

== Verwendung ==
In der Praxis werden häufig Objekte zu einer [[Datentyp#Zusammengesetzte Datentypen|Sammlung]] zusammengefasst. Auf die Elemente solch einer Sammlung soll möglichst generisch und ohne Rücksicht auf die Implementierungsdetails zugegriffen werden können.

== UML-Diagramm ==
[[Datei:Iterator Klassen.png|ohne|Klassendiagramm]]

Das Diagramm ist nur als grobes Beispiel zu sehen. Die konkrete Realisierung kann stark abweichen:
* Anstelle der Ableitungspfeile kann z.&nbsp;B. die Realisierung eines Konzeptes stehen. D.&nbsp;h., es gibt gar keine Basisklasse, lediglich eine unverbindliche Vorgabe.
* Die Methoden sind nicht in jedem Fall sinnvoll. <code>Zurueck()</code> oder <code>IstFertig()</code> sind nicht immer realisierbar.
* Navigationspfeile zwischen KonkretesAggregat und KonkreterIterator können nur in eine Richtung gehen oder ganz fehlen.

== Akteure ==
* '''Iterator''' definiert die Schnittstelle zum Zugriff auf die Elemente und zum Traversieren des Aggregates.
* '''Konkreter Iterator''' implementiert diese Schnittstelle und speichert die Position im Aggregat.
* '''Aggregat''' definiert die Schnittstelle zum Erzeugen eines Iterators. Oft enthält die Schnittstelle auch Methoden zum Erzeugen von Iteratoren, die auf spezielle Elemente zeigen, wie z.&nbsp;B. erstes, letztes oder Element mit bestimmten Eigenschaften.
* '''Konkretes Aggregat''' implementiert diese Schnittstelle.

== Vorteile ==
Die Implementierung der zugrunde liegenden Datenstruktur bleibt verborgen.

== Nachteile ==
Je nach Variante der Implementierung können sich Nachteile durch erhöhte Laufzeit- und Speicherkosten ergeben.
* Bei polymorphen Iteratoren muss man den Preis für [[Virtuelle Methode|virtuelle Methoden]] zahlen.
* Wenn der Iterator sein Aggregat kennt und/oder das Aggregat über seine Iteratoren Buch führt, verteuern sich vor allem das Erzeugen und Vernichten von Aggregaten. (Im Gegenzug erhält man eine höhere Sicherheit)

== Implementierung ==
Aufgrund einiger Designentscheidungen ergeben sich Iterator-Varianten mit verschiedenen Eigenschaften:

=== Wer steuert die Iteration? ===
Bei einem ''externen'' Iterator steuert der Klient die Iteration. Der Klient muss dafür sorgen, dass der Iterator weiterrückt.

Ein ''interner'' Iterator tut dies selbst. Dazu muss ihm die Operation übergeben werden, die er auf das aktuelle Element anwenden soll. Interne Iteratoren werden oft gar nicht als solche erkannt oder bezeichnet, da die Iteration nicht sichtbar ist oder aber über externe Iteratoren realisiert ist.

Die Vorteile des externen Iterationsmodells liegen darin, dass der Aufrufer mehr Kontrolle über die Iteration hat. Der Iterator kann nur teilweise oder zu verschiedenen Zeiten im [[Programmcode]], etwa bei einer Nutzerinteraktion, fortgeschritten werden. Dies ist beim internen Iterator nicht der Fall. Dafür kann dieser einfacher zu implementieren sein, unter anderem, weil eine [[Rekursive Programmierung|rekursive]] Implementation möglich ist.<ref>{{Internetquelle |url=https://docs.rs/internal-iterator/latest/internal_iterator/index.html |titel=internal_iterator - Rust |abruf=2022-09-24}}</ref>

[[Grady Booch]] nennt den externen Iterator ''aktiv'' und den internen ''passiv''.

=== Traversionsalgorithmus ===
Der Traversionsalgorithmus kann durch den Iterator oder das Aggregat vorgegeben werden.
Im letzteren Fall wird oft von einem ''Cursor'' gesprochen.

=== Robustheit ===
Wenn das Aggregat während der [[Traversion]] verändert wird, kann das zu falschen Ergebnissen oder gar zum Programmabsturz führen.
Ein robuster Iterator ist gegen Modifikationen des Aggregats gesichert.
Typischerweise werden dazu die Iteratoren beim Aggregat registriert. Das führt zu höheren Kosten beim Erzeugen der Iteratoren,
aber auch beim Ändern des Aggregates.

=== Polymorphie ===
Polymorphe Iteratoren bieten eine hohe Flexibilität. Da Iteratoren meist in Schleifen verwendet werden, sind die Kosten dafür allerdings sehr hoch.

=== Nulliteratoren ===
Je nach Implementation kann es, in Analogie zum Null-[[Zeiger (Informatik)|Zeiger]], einen Nulliterator geben. Dieser signalisiert das Ende einer Iteration oder einen ungültigen Iterator. Das ist recht bequem in der Benutzung, da man einem Iterator seine Gültigkeit „ansieht“, aber die Implementation wird dadurch u.&nbsp;U. komplizierter.

Daher wurde z.&nbsp;B. in der [[C-Plusplus-Standardbibliothek#Iteratoren|C++-Standardbibliothek]] diese Alternative gewählt. Dabei besitzt jedes Aggregat seinen eigenen Nulliterator, mit dem man dann den jeweiligen Iterator vergleichen muss.

=== Privilegien ===
Ein Iterator kann privilegierten Zugriff auf die Interna des Aggregates besitzen.
Das ist bei komplexen Datenstrukturen teilweise nicht zu vermeiden.
Allerdings wird dadurch die Implementation neuer Traversionsalgorithmen erschwert oder gar verhindert.

== Beispiele ==
Diese C++11 Implementierung basiert auf dem Kapitel „Generalizing vector yet again“.<ref>{{Literatur| Autor=Bjarne Stroustrup| Titel=Programming: Principles and Practice using C++ | Auflage=2| Verlag=Addison-Wesley| Jahr=2014| ISBN=978-0-321-99278-9|Seiten=729 ff.}}</ref>

<syntaxhighlight lang="cpp">
#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';
  }
}
</syntaxhighlight>

Die Programmausgabe ist:

<syntaxhighlight lang="cpp">
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[]
</syntaxhighlight>

Ein einfacher Fall eines '''externen''' Iterators wäre etwa (in [[Java (Programmiersprache)|Java]]):
<syntaxhighlight lang="java">
class ObjectIterator {
  private Object[] m_source;
  private int m_current;

  public ObjectIterator(Object[] source) {
    m_source = source;
    m_current = 0;
  }

  public boolean hasNext() {
    return m_current < m_source.length;
  }

  public Object next() {
    return m_source[m_current++];
  }
}
</syntaxhighlight>
Anwendung:
<syntaxhighlight lang="java">
Object[] myList = new Object[] {new Integer(1), new Integer(2), new Integer(3)};
ObjectIterator iterator = new ObjectIterator(myList);
while(iterator.hasNext()) {
  System.out.println(iterator.next());
}
</syntaxhighlight>

Eine andere Variation dieses Entwurfsmusters wäre ein '''interner''' Iterator:
<syntaxhighlight lang="java">
class MyObjectIterator extends ObjectIterator {
  public MyObjectIterator(Object[] source) {
    super(source);
  }

  public void print() {
    while(hasNext()) {
      System.out.println(next());
    }
  }

  public void apply(ObjectHandler handler) {
    while(hasNext()) {
      handler.handle(next());
    }
  }
}

interface ObjectHandler {
  void handle(Object o);
}
</syntaxhighlight>
Anwendung:
<syntaxhighlight lang="java">
class MyObjectHandler implements ObjectHandler {
  public void handle(Object o) {
    System.out.println(o);
  }
}

Object[] myList = new Object[] {new Integer(1), new Integer(2), new Integer(3)};
MyObjectIterator iterator = new MyObjectIterator(myList);
iterator.print();
iterator.apply(new MyObjectHandler());
</syntaxhighlight>

Ein interner Iterator kapselt die Iteration selber und macht sie so im gesamten Programm einfach und konsistent wiederverwendbar, ohne sie wie im Fall eines externen Iterators immer wieder neu programmieren zu müssen. Durch Anwendung des [[Strategie (Entwurfsmuster)|Strategie Entwurfsmusters]] lässt sich der [[Algorithmus]] auch einfach austauschen, wie in der letzten Beispielzeile gezeigt.

Obwohl sich diese Beispiele mit sequenziellem Zugriff begnügen, sind natürlich auch Iteratoren mit wahlfreiem Zugriff möglich. Viele Implementierungen bieten zusätzlich die Möglichkeit die iterierte Sammlung direkt zu verändern, etwa durch Entfernen des aktuellen Elementes.

Die [[C++-Standardbibliothek#Iteratoren|STL]] enthält Iteratoren für ihre [[C++-Standardbibliothek#Container|Container]].

== Verwandte Entwurfsmuster ==
* [[Kompositum (Entwurfsmuster)|Kompositum]], als Variante eines zusammengesetzten Objektes, benötigt Iteratoren zum Traversieren.
* Polymorphe Iteratoren werden durch [[Fabrikmethode]]n erzeugt.

== Weblinks ==
{{Wikibooks|Muster: Iterator}}

== Einzelnachweise ==
<references />

{{Navigationsleiste Entwurfsmuster}}

[[Kategorie:Verhaltensmuster (Software)]]
[[Kategorie:Viererbande-Entwurfsmuster]]

[[fr:Itérateur (motif de conception)]]