Iterera över samlingar i Java

När som helst du har en samling saker behöver du någon mekanism för att systematiskt kliva genom objekten i den samlingen. Tänk på fjärrkontrollen för tv, som låter oss itera igenom olika tv-kanaler. På samma sätt behöver vi i programmeringsvärlden en mekanism för att systematiskt itera genom en samling programvaruobjekt. Java innehåller olika mekanismer för iteration, inklusive index (för iterering över en matris), markör (för iterering över resultaten av en databasfråga), uppräkning (i tidiga versioner av Java) och iterator (i nyare versioner av Java).

Iteratormönstret

En iterator är en mekanism som möjliggör åtkomst till alla element i en samling sekventiellt, med viss operation som utförs på varje element. I huvudsak tillhandahåller en iterator ett sätt att "loopa" över en inkapslad samling objekt. Exempel på användning av iteratorer inkluderar

  • Besök varje fil i en katalog ( aka mapp) och visa dess namn.
  • Besök varje nod i en graf och avgöra om den kan nås från en given nod.
  • Besök varje kund i en kö (till exempel att simulera en rad i en bank) och ta reda på hur länge han eller hon har väntat.
  • Besök varje nod i en kompilators abstrakta syntaxträd (som produceras av parsern) och utför semantisk kontroll eller kodgenerering. (Du kan också använda besökarmönstret i detta sammanhang.)

Vissa principer gäller för användningen av iteratorer: I allmänhet bör du kunna ha flera påkörningar på gång samtidigt; det vill säga en iterator bör möjliggöra begreppet kapslad looping. En iterator bör också vara oförstörande i den meningen att iterationshandlingen inte i sig skulle förändra samlingen. Naturligtvis kan operationen som utförs på elementen i en samling möjligen förändra några av elementen. Det kan också vara möjligt för en iterator att stödja att ta bort ett element från en samling eller infoga ett nytt element vid en viss punkt i samlingen, men sådana ändringar bör vara explicita inom programmet och inte en biprodukt av iterationen. I vissa fall måste du också ha iteratorer med olika genomkörningsmetoder; till exempel förbeställning och efterbeställning av ett träd, eller djupförst och bredd först genomgång av ett diagram.

Iterera komplexa datastrukturer

Jag lärde mig först att programmera i en tidig version av FORTRAN, där den enda datastruktureringsfunktionen var en matris. Jag lärde mig snabbt hur man iterera över en matris med hjälp av ett index och en DO-loop. Därifrån var det bara ett kort mentalt steg till idén att använda ett gemensamt index i flera matriser för att simulera en rad poster. De flesta programmeringsspråk har funktioner som liknar matriser, och de stöder enkel looping över matriser. Men moderna programmeringsspråk stöder också mer komplexa datastrukturer som listor, uppsättningar, kartor och träd, där funktionerna görs tillgängliga via offentliga metoder men de interna detaljerna är dolda i privata delar av klassen. Programmerare måste kunna korsa elementen i dessa datastrukturer utan att avslöja deras interna struktur, vilket är syftet med iteratorer.

Iterators and the Gang of Four designmönster

Enligt Gang of Four (se nedan) är Iterator-designmönstret ett beteendemönster, vars nyckelidé är att "ta ansvaret för åtkomst och traversering ur listan [ red. Tänkesamling ] och placera det i en iterator. objekt." Den här artikeln handlar inte lika mycket om Iteratormönstret som om hur iteratorer används i praktiken. För att helt täcka mönstret krävs att man diskuterar hur en iterator skulle utformas, deltagare (objekt och klasser) i designen, möjliga alternativa design och avvägningar mellan olika designalternativ. Jag vill hellre fokusera på hur iteratorer används i praktiken, men jag pekar på några resurser för att undersöka Iterator-mönstret och designmönstren i allmänhet:

  • Designmönster: Elements of Reusable Object-Oriented Software (Addison-Wesley Professional, 1994) skriven av Erich Gamma, Richard Helm, Ralph Johnson och John Vlissides (även känd som Gang of Four eller helt enkelt GoF) är den definitiva resursen för lärande om designmönster. Även om boken först publicerades 1994 är den fortfarande en klassiker, vilket framgår av det faktum att det har varit mer än 40 tryckningar.
  • Bob Tarr, en lektor vid University of Maryland Baltimore County, har en utmärkt uppsättning bilder för sin kurs om designmönster, inklusive hans introduktion till Iterator-mönstret.
  • David Gearys JavaWorld-serie Java Design Patterns introducerar många av Gang of Four-designmönstren, inklusive Singleton-, Observer- och Composite-mönster. Även på JavaWorld innehåller Jeff Friesens nyare tredelade översikt över designmönster en guide till GoF-mönstren.

Aktiva iteratorer kontra passiva iteratorer

Det finns två allmänna metoder för att implementera en iterator beroende på vem som kontrollerar iterationen. För en aktiv iterator (även känd som uttrycklig iterator eller extern iterator ), styr klienten iterationen i den meningen att klienten skapar iteratorn, säger när den ska gå vidare till nästa element, testar för att se om varje element har besökts, och så vidare. Detta tillvägagångssätt är vanligt på språk som C ++, och det är det tillvägagångssätt som får mest uppmärksamhet i GoF-boken. Även om iteratorer i Java har tagit olika former, var det i princip det enda lönsamma alternativet före Java 8 att använda en aktiv iterator.

För en passiv iterator (även känd som en implicit iterator , intern iterator eller callback-iterator ) styr iteratorn själv iterationen. Klienten säger i huvudsak till iteratorn: "Utför denna operation på elementen i samlingen." Detta tillvägagångssätt är vanligt på språk som LISP som tillhandahåller anonyma funktioner eller stängningar. Med lanseringen av Java 8 är detta tillvägagångssätt för iteration nu ett rimligt alternativ för Java-programmerare.

Java 8 namngivningsscheman

Även om det inte är lika dåligt som Windows (NT, 2000, XP, VISTA, 7, 8, ...) innehåller Java: s versionshistorik flera namngivningsscheman. För att börja, ska vi hänvisa till Java-standardutgåvan som "JDK", "J2SE" eller "Java SE"? Java's versionsnummer började ganska enkelt - 1.0, 1.1, etc. - men allt förändrades med version 1.5, som var märkt Java (eller JDK) 5. När jag hänvisar till tidiga versioner av Java använder jag fraser som "Java 1.0" eller "Java 1.1, "men efter den femte versionen av Java använder jag fraser som" Java 5 "eller" Java 8. "

För att illustrera de olika metoderna för iteration i Java behöver jag ett exempel på en samling och något som måste göras med dess element. För den första delen av den här artikeln använder jag en samling strängar som representerar namnen på saker. För varje namn i samlingen skriver jag helt enkelt ut värdet till standardutdata. Dessa grundläggande idéer utvidgas enkelt till samlingar av mer komplicerade objekt (till exempel anställda), och där behandlingen för varje objekt är lite mer involverad (som att ge varje högt rankad anställd 4,5 procents höjning).

Andra former av iteration i Java 8

Jag fokuserar på iterering över samlingar, men det finns andra, mer specialiserade former av iteration i Java. Du kan till exempel använda en JDBC för ResultSetatt iterera över raderna som returneras från en SELECT-fråga till en relationsdatabas eller använda a för Scanneratt iterera över en ingångskälla.

Iteration med klassen Uppräkning

I Java 1.0 och 1.1 var de två primära samlingsklasserna Vectoroch Hashtableoch Iterator-designmönstret implementerades i en klass som kallades Enumeration. I efterhand var detta ett dåligt namn för klassen. Blanda inte ihop klassen Enumerationmed begreppet ENUM typer , som inte visas förrän Java 5. Idag båda Vectoroch Hashtableär generiska klasser, men då generika var inte en del av Java. Koden för att bearbeta en vektor av strängar med Enumerationskulle se ut ungefär som Listing 1.

Listning 1. Använd uppräkning för att itera över en vektor av strängar

 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 med Iterator-klassen

Java 1.2 introducerade de samlingsklasser som vi alla känner och älskar, och Iterator-designmönstret implementerades i en klass som passar namnet Iterator. Eftersom vi ännu inte hade generics i Java 1.2 Iteratorvar det fortfarande nödvändigt att kasta ett objekt som returnerats från en . För Java-versionerna 1.2 till 1.4 kan iterering över en lista med strängar likna Listing 2.

Listning 2. Använd en Iterator för att itera över en lista med strängar

 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 med generika och den förbättrade 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

Låt oss nu överväga att göra något lite mer involverat än att bara skriva ut namnen i vår lista. Anta till exempel att vi vill räkna antalet namn som börjar med bokstaven A . Vi kan implementera den mer komplicerade logiken som en del av lambdauttrycket, eller så kan vi använda Java 8: s nya Stream API. Låt oss ta det senare tillvägagångssättet.