Iterable
und Iterator
Was sind Iterable
und Iterator
?
Es handelt sich hierbei um zwei Interfaces, die zur Standard-Bibliothek von Java gehören. Ihre Semantik lässt sich sehr gut so formulieren:
Implementiert eine Datenstruktur das Interface Iterable
, dann ist sie (im Sinne dieses Interfaces) “iterierbar”, d.h. man kann - unabhängig von der internen Funktionsweise der Datenstruktur (!) - über ihre Elemente iterieren. Iterable
gibt eine einizge Methode vor, nämlich iterator()
, die eine Instanz des für die Datenstruktur implementierten Iterator
zum Iterieren über die Elemente zurückgibt.
Beide Interfaces, Iterable
und Iterator
arbeiten jeweils mit Generics, um den Typ der verarbeiteten Elemente festzulegen (siehe Beispiel unten).
Beispiel
Nehmen wir als Beispiel eine generische Datenstruktur List
, die intern ihre Elemente in einem Array verwaltet (die genaue Implementation lassen wir weg - es geht hier nur um die Anwendung von Iterable
und Iterator
):
import java.util.Iterator;
public class List<T> implements Iterable<T> {
private T[] elements;
@Override
public Iterator<T> iterator() {
//TODO
return null;
}
}
Das Beispiel lässt im Moment auch noch die Implementation der Methode iterator()
außen vor, zeigt aber bereits das Verhältnis der beiden Interfaces: Ein Iterable<T>
besitzt eine Methode iterator()
, die einen Iterator<T>
zurückgibt.
Aber was ist nun ein Iterator
? Das ist eigentlich ganz einfach: Ein Iterator
ist ein Objekt, das uns drei hilfreiche Methoden anbietet:
-
boolean hasNext()
- Hat die Datenstruktur ein weiteres Element? -
T next()
- Gib mir das nächste Element der Datenstruktur! -
remove()
(optional!) - Entferne das letzte durchnext()
zurückgegebene Element! (siehe Abschnitt zuremove()
unten!)
Die Implementation der beiden ersten (unbedingt nötigen) Methoden könnte für unser Beispiel von oben etwa so aussehen (für den Überblick noch mal im vollständigen Kontext):
import java.util.Iterator;
public class List<T> implements Iterable<T> {
private T[] elements;
@Override
public Iterator<T> iterator() {
return new Iterator<T>(){
private int pos = 0;
@Override
public boolean hasNext() {
return pos < elements.length;
}
@Override
public T next() {
return elements[pos++];
}
};
}
}
Im Ergebnis ermöglicht die korrekte Implementation von Iterable
also die Benutzung eines passenden Iterator
-Objekts, das uns - unabhängig von der Funktionsweise der Datenstruktur - über ihre Elemente iterieren lässt.
Bezug zur for-each-Schleife
Aber nicht nur uns ermöglichen diese Interfaces dieses generische Iterieren! Auch ein wichtiges Sprach-Feature von Java ist nur für Iterable
s (und Arrays) verfügbar: Die for-each-Schleife. Diese Variation der for
-Schleife benötigt ein solches Interface, um unabhängig von der Implementation der Datenstruktur ihren Dienst tun zu können.
Angewendet auf unser Beispiel von oben könnte man etwa über eine List<String>
dann folgendermaßen iterieren:
for (String element : list){
System.out.println("Aktuelles Element: " + element);
}
Im Hintergrund ändert der Compiler diesen (sehr schönen und lesbaren) Code nämlich zu diesem hier:
Iterator<String> iter = list.iterator();
while (iter.hasNext()){
String element = iter.next();
System.out.println("Aktuelles Element: " + element);
}
Die optionale Methode remove()
Normalerweise lassen sich beim Iterieren über eine Datenstruktur keine Elemente aus dieser entfernen. Dies würde (bzw. sollte) eine ConcurrentModificationException
auslösen, weil nicht sichergestellt werden kann, dass der iterierende Code mit der veränderten Datenstruktur umgehen kann.
Das Interface Iterator
enthält jedoch eine default
-Methode remove()
, mit der man genau dies tun kann - sofern sie denn implementiert ist. Die default
-Implementation von remove()
wirft nämlich einfach nur eine UnsupportedOperationException
(Methode ist nicht implementiert!). Möchte man seinem Iterator
allerdings eine funktionierende remove()
-Methode schenken, sollte man sich bei der Implementierung genau nach der Javadoc-Dokumentation von remove()
richten (die stellt nämlich einige Anforderungen!):
default void remove()
Removes from the underlying collection the last element returned by this iterator (optional operation). This method can be called only once per call to
next()
. The behavior of an iterator is unspecified if the underlying collection is modified while the iteration is in progress in any way other than by calling this method.Implementation Requirements:
The
default
implementation throws an instance ofUnsupportedOperationException
and performs no other action.Throws:
UnsupportedOperationException
- if the remove operation is not supported by this iterator
IllegalStateException
- if the next method has not yet been called, or the remove method has already been called after the last call to the next method
Quelle: Offizielle Dokumentation von Iterator
Eine Implementation von remove()
für unsere Beispiel-Struktur von oben könnte z.B. so aussehen (es mussten einige Dinge am bestehenden Code geändert werden, siehe Erläuterungen unten!):
import java.util.Iterator;
public class List<T> implements Iterable<T> {
private T[] elements;
@Override
public Iterator<T> iterator() {
return new Iterator<T>(){
private int pos = -1;
private boolean elementRemoved = false;
@Override
public boolean hasNext() {
return pos < elements.length;
}
@Override
public T next() {
elementRemoved = false;
return elements[++pos];
}
@SuppressWarnings("unchecked")
@Override
public void remove() {
/*
* Prüfen, ob next() noch nie aufgerufen wurde ODER ob remove()
* seit dem letzten next() bereits aufgerufen wurde (wie es in
* der Dokumentation vorgegeben ist) - in einem dieser Fälle:
* IllegalStateException werfen!
*/
if (pos < 0 || elementRemoved) {
throw new IllegalStateException("You have to call next() "
+ "before calling remove() at least once!");
}
// temporäres "neues" Array anlegen
final Object[] temp = new Object[elements.length];
// Elemente kopieren (außer das gelöschte)
for (int i = 0; i < temp.length; i++)
temp[i] = elements[i >= pos ? i + 1 : i];
// neues Array zuweisen
elements = (T[]) temp;
// merken, dass wir etwas entfernt haben
elementRemoved = true;
}
};
}
}
Für diese Implementation von remove()
mussten ein paar Kleinigkeiten am Code geändert werden: Der initiale Wert von pos
ist nun -1
, damit wir nachvollziehen können, ob next()
wenigstens einmal aufgerufen wurde. Außerdem muss remove()
prüfen, ob gerade eben (nach dem letzten next()
-Aufruf) schon ein Element mit remove()
entfernt wurde. Dazu haben wir eine weitere Instanzvariable elementRemoved
eingeführt, die an den richtigen Stellen entsprechend gesetzt wird.
Anmerkung zur Annotation
@SuppressWarnings
: Hier unterdrücken wir eine Warnung des Compilers, denn es wird am Ende der Methode zu einem generischen Array gecastet - eine Operation, die vom Compiler nicht auf Korrektheit geprüft werden kann.