Durch Sammlungen in Java iterieren

Jedes Mal, wenn Sie eine Sammlung von Dingen haben, benötigen Sie einen Mechanismus, um die Elemente in dieser Sammlung systematisch zu durchlaufen. Betrachten Sie als alltägliches Beispiel die Fernsehfernbedienung, mit der wir verschiedene Fernsehkanäle durchlaufen können. In ähnlicher Weise benötigen wir in der Programmierwelt einen Mechanismus, um eine Sammlung von Softwareobjekten systematisch zu durchlaufen. Java enthält verschiedene Mechanismen für die Iteration, einschließlich Index (zum Iterieren über ein Array), Cursor (zum Iterieren über die Ergebnisse einer Datenbankabfrage), Aufzählung (in früheren Versionen von Java) und Iterator (in neueren Versionen von Java).

Das Iteratormuster

Ein Iterator ist ein Mechanismus, mit dem nacheinander auf alle Elemente einer Sammlung zugegriffen werden kann, wobei für jedes Element eine Operation ausgeführt wird. Im Wesentlichen bietet ein Iterator ein Mittel zum "Schleifen" einer gekapselten Sammlung von Objekten. Beispiele für die Verwendung von Iteratoren sind

  • Besuchen Sie jede Datei in einem Verzeichnis (auch bekannt als Ordner) und zeigen Sie ihren Namen an.
  • Besuchen Sie jeden Knoten in einem Diagramm und bestimmen Sie, ob er von einem bestimmten Knoten aus erreichbar ist.
  • Besuchen Sie jeden Kunden in einer Warteschlange (z. B. um eine Leitung in einer Bank zu simulieren) und finden Sie heraus, wie lange er gewartet hat.
  • Besuchen Sie jeden Knoten im abstrakten Syntaxbaum eines Compilers (der vom Parser erstellt wird) und führen Sie eine semantische Überprüfung oder Codegenerierung durch. (In diesem Zusammenhang können Sie auch das Besuchermuster verwenden.)

Für die Verwendung von Iteratoren gelten bestimmte Grundsätze: Im Allgemeinen sollten mehrere Durchläufe gleichzeitig ausgeführt werden können. Das heißt, ein Iterator sollte das Konzept der verschachtelten Schleife berücksichtigen. Ein Iterator sollte auch in dem Sinne zerstörungsfrei sein, dass der Iterationsvorgang die Sammlung an sich nicht ändern sollte. Natürlich kann die Operation, die an den Elementen in einer Sammlung ausgeführt wird, möglicherweise einige der Elemente ändern. Es kann für einen Iterator auch möglich sein, das Entfernen eines Elements aus einer Sammlung oder das Einfügen eines neuen Elements an einem bestimmten Punkt in der Sammlung zu unterstützen. Solche Änderungen sollten jedoch innerhalb des Programms explizit und kein Nebenprodukt der Iteration sein. In einigen Fällen benötigen Sie auch Iteratoren mit unterschiedlichen Durchlaufmethoden. Zum Beispiel das Durchlaufen eines Baums vor und nach dem Bestellen oder das Durchlaufen eines Diagramms mit der Tiefe und der Breite zuerst.

Iterieren komplexer Datenstrukturen

Ich habe zuerst gelernt, in einer frühen Version von FORTRAN zu programmieren, in der die einzige Fähigkeit zur Datenstrukturierung ein Array war. Ich habe schnell gelernt, wie man mit einem Index und einer DO-Schleife über ein Array iteriert. Von dort war es nur ein kurzer mentaler Sprung zu der Idee, einen gemeinsamen Index in mehreren Arrays zu verwenden, um ein Array von Datensätzen zu simulieren. Die meisten Programmiersprachen verfügen über ähnliche Funktionen wie Arrays und unterstützen das einfache Durchlaufen von Arrays. Moderne Programmiersprachen unterstützen aber auch komplexere Datenstrukturen wie Listen, Mengen, Karten und Bäume, bei denen die Funktionen über öffentliche Methoden verfügbar gemacht werden, die internen Details jedoch in privaten Teilen der Klasse verborgen sind. Programmierer müssen in der Lage sein, die Elemente dieser Datenstrukturen zu durchlaufen, ohne ihre interne Struktur freizulegen, was der Zweck von Iteratoren ist.

Iteratoren und die Gang of Four-Entwurfsmuster

Laut der Viererbande (siehe unten) ist das Iterator-Entwurfsmuster ein Verhaltensmuster, dessen Schlüsselidee darin besteht, "die Verantwortung für den Zugriff und das Durchlaufen aus dem Listenobjekt [ ed. Think collection ] herauszunehmen und es in einen Iterator zu setzen Objekt." In diesem Artikel geht es nicht so sehr um das Iteratormuster, sondern darum, wie Iteratoren in der Praxis verwendet werden. Um das Muster vollständig abzudecken, müssten diskutiert werden, wie ein Iterator entworfen werden soll, Teilnehmer (Objekte und Klassen) am Entwurf, mögliche alternative Entwürfe und Kompromisse zwischen verschiedenen Entwurfsalternativen. Ich möchte mich lieber darauf konzentrieren, wie Iteratoren in der Praxis verwendet werden, aber ich verweise Sie auf einige Ressourcen zur Untersuchung des Iteratormusters und der Entwurfsmuster im Allgemeinen:

  • Entwurfsmuster: Elemente wiederverwendbarer objektorientierter Software (Addison-Wesley Professional, 1994), geschrieben von Erich Gamma, Richard Helm, Ralph Johnson und John Vlissides (auch bekannt als Gang of Four oder einfach GoF), sind die endgültige Lernressource über Designmuster. Obwohl das Buch erstmals 1994 veröffentlicht wurde, bleibt es ein Klassiker, wie die Tatsache zeigt, dass es mehr als 40 Drucke gegeben hat.
  • Bob Tarr, Dozent an der University of Maryland im Baltimore County, verfügt über eine hervorragende Auswahl an Folien für seinen Kurs über Entwurfsmuster, einschließlich seiner Einführung in das Iteratormuster.
  • Die JavaWorld-Serie Java Design Patterns von David Geary führt viele der Gang of Four-Entwurfsmuster ein, einschließlich der Singleton-, Observer- und Composite-Muster. Ebenfalls auf JavaWorld enthält Jeff Friesens neuere dreiteilige Übersicht über Entwurfsmuster eine Anleitung zu den GoF-Mustern.

Aktive Iteratoren gegen passive Iteratoren

Es gibt zwei allgemeine Ansätze zum Implementieren eines Iterators, je nachdem, wer die Iteration steuert. Bei einem aktiven Iterator (auch als expliziter Iterator oder externer Iterator bezeichnet ) steuert der Client die Iteration in dem Sinne, dass der Client den Iterator erstellt, ihm mitteilt, wann zum nächsten Element übergegangen werden soll, und prüft, ob jedes Element besucht wurde. und so weiter. Dieser Ansatz ist in Sprachen wie C ++ üblich und wird im GoF-Buch am meisten beachtet. Obwohl Iteratoren in Java unterschiedliche Formen angenommen haben, war die Verwendung eines aktiven Iterators vor Java 8 im Wesentlichen die einzig praktikable Option.

Bei einem passiven Iterator (auch als impliziter Iterator , interner Iterator oder Rückrufiterator bezeichnet ) steuert der Iterator selbst die Iteration. Der Client sagt im Wesentlichen zum Iterator: "Führen Sie diese Operation für die Elemente in der Sammlung aus." Dieser Ansatz ist in Sprachen wie LISP üblich, die anonyme Funktionen oder Schließungen bereitstellen. Mit der Veröffentlichung von Java 8 ist dieser Ansatz zur Iteration nun eine sinnvolle Alternative für Java-Programmierer.

Java 8-Namensschemata

Der Versionsverlauf von Java ist zwar nicht ganz so schlecht wie Windows (NT, 2000, XP, VISTA, 7, 8, ...), enthält jedoch mehrere Namensschemata. Sollten wir die Java Standard Edition zunächst als "JDK", "J2SE" oder "Java SE" bezeichnen? Die Versionsnummern von Java begannen ziemlich einfach - 1.0, 1.1 usw. - aber alles änderte sich mit Version 1.5, die als Java (oder JDK) 5 bezeichnet wurde. Wenn ich mich auf frühere Versionen von Java beziehe, verwende ich Sätze wie "Java 1.0" oder "Java" 1.1, "aber nach der fünften Version von Java verwende ich Sätze wie" Java 5 "oder" Java 8 ".

Um die verschiedenen Ansätze zur Iteration in Java zu veranschaulichen, benötige ich ein Beispiel für eine Sammlung und etwas, das mit ihren Elementen gemacht werden muss. Für den ersten Teil dieses Artikels werde ich eine Sammlung von Zeichenfolgen verwenden, die Namen von Dingen darstellen. Für jeden Namen in der Sammlung drucke ich einfach seinen Wert in die Standardausgabe. Diese Grundideen lassen sich leicht auf Sammlungen komplizierterer Objekte (z. B. Mitarbeiter) erweitern, bei denen die Verarbeitung für jedes Objekt etwas aufwändiger ist (z. B. wenn jeder hoch bewertete Mitarbeiter eine Erhöhung um 4,5 Prozent erhält).

Andere Formen der Iteration in Java 8

Ich konzentriere mich auf das Iterieren über Sammlungen, aber es gibt andere, spezialisiertere Formen der Iteration in Java. Beispielsweise können Sie einen JDBC verwenden ResultSet, um die von einer SELECT-Abfrage an eine relationale Datenbank zurückgegebenen Zeilen zu durchlaufen, oder einen Scanner, um eine Eingabequelle zu durchlaufen.

Iteration mit der Enumeration-Klasse

In Java 1.0 und 1.1 waren die beiden primären Sammlungsklassen Vectorund Hashtable, und das Iterator-Entwurfsmuster wurde in einer Klasse namens implementiert Enumeration. Rückblickend war dies ein schlechter Name für die Klasse. Verwechseln Sie die Klasse nicht Enumerationmit dem Konzept der Aufzählungstypen , das erst in Java 5 auftauchte. Heute sind beide Vectorund Hashtablegenerische Klassen, aber damals waren Generika nicht Teil der Java-Sprache. Der Code zum Verarbeiten eines Vektors von Zeichenfolgen mit Enumerationwürde ungefähr wie in Listing 1 aussehen.

Listing 1. Verwenden der Aufzählung zum Durchlaufen eines Vektors von Zeichenfolgen

 Vector names = new Vector(); // ... add some names to the collection Enumeration e = names.elements(); while (e.hasMoreElements()) { String name = (String) e.nextElement(); System.out.println(name); } 

Iteration mit der Iterator-Klasse

Java 1.2 introduced the collection classes that we all know and love, and the Iterator design pattern was implemented in a class appropriately named Iterator. Because we didn't yet have generics in Java 1.2, casting an object returned from an Iterator was still necessary. For Java versions 1.2 through 1.4, iterating over a list of strings might resemble Listing 2.

Listing 2. Using an Iterator to iterate over a list of strings

 List names = new LinkedList(); // ... add some names to the collection Iterator i = names.iterator(); while (i.hasNext()) { String name = (String) i.next(); System.out.println(name); } 

Iteration with generics and the enhanced for-loop

Java 5 gave us generics, the interface Iterable, and the enhanced for-loop. The enhanced for-loop is one of my all-time-favorite small additions to Java. The creation of the iterator and calls to its hasNext() and next() methods are not expressed explicitly in the code, but they still take place behind the scenes. Thus, even though the code is more compact, we are still using an active iterator. Using Java 5, our example would look something like what you see in Listing 3.

Listing 3. Using generics and the enhanced for-loop to iterate over a list of strings

 List names = new LinkedList(); // ... add some names to the collection for (String name : names) System.out.println(name); 

Java 7 gave us the diamond operator, which reduces the verbosity of generics. Gone were the days of having to repeat the type used to instantiate the generic class after invoking the new operator! In Java 7 we could simplify the first line in Listing 3 above to the following:

 List names = new LinkedList(); 

A mild rant against generics

The design of a programming language involves tradeoffs between the benefits of language features versus the complexity they impose on the syntax and semantics of the language. For generics, I am not convinced that the benefits outweigh the complexity. Generics solved a problem that I did not have with Java. I generally agree with Ken Arnold's opinion when he states: "Generics are a mistake. This is not a problem based on technical disagreements. It's a fundamental language design problem [...] The complexity of Java has been turbocharged to what seems to me relatively small benefit."

Fortunately, while designing and implementing generic classes can sometimes be overly complicated, I have found that using generic classes in practice is usually straightforward.

Iteration with the forEach() method

Before delving into Java 8 iteration features, let's reflect on what's wrong with the code shown in the previous listings–which is, well, nothing really. There are millions of lines of Java code in currently deployed applications that use active iterators similar to those shown in my listings. Java 8 simply provides additional capabilities and new ways of performing iteration. For some scenarios, the new ways can be better.

The major new features in Java 8 center on lambda expressions, along with related features such as streams, method references, and functional interfaces. These new features in Java 8 allow us to seriously consider using passive iterators instead of the more conventional active iterators. In particular, the Iterable interface provides a passive iterator in the form of a default method called forEach().

A default method, another new feature in Java 8, is a method in an interface with a default implementation. In this case, the forEach() method is actually implemented using an active iterator in a manner similar to what you saw in Listing 3.

Collection classes that implement Iterable (for example, all list and set classes) now have a forEach() method. This method takes a single parameter that is a functional interface. Therefore the actual parameter passed to the forEach() method is a candidate for a lambda expression. Using the features of Java 8, our running example would evolve to the form shown in Listing 4.

Listing 4. Iteration in Java 8 using the forEach() method

 List names = new LinkedList(); // ... add some names to the collection names.forEach(name -> System.out.println(name)); 

Note the difference between the passive iterator in Listing 4 and the active iterator in the previous three listings. In the first three listings, the loop structure controls the iteration, and during each pass through the loop, an object is retrieved from the list and then printed. In Listing 4, there is no explicit loop. We simply tell the forEach() method what to do with the objects in the list — in this case we simply print the object. Control of the iteration resides within the forEach() method.

Iteration with Java streams

Lassen Sie uns nun überlegen, etwas mehr zu tun, als nur die Namen in unserer Liste auszudrucken. Nehmen wir zum Beispiel an, wir möchten die Anzahl der Namen zählen, die mit dem Buchstaben A beginnen . Wir könnten die kompliziertere Logik als Teil des Lambda-Ausdrucks implementieren oder die neue Stream-API von Java 8 verwenden. Nehmen wir den letzteren Ansatz.