Iterazione sulle raccolte in Java

Ogni volta che hai una raccolta di cose, avrai bisogno di un meccanismo per passare sistematicamente agli elementi di quella raccolta. Come esempio quotidiano, si consideri il telecomando del televisore, che ci consente di scorrere diversi canali televisivi. Allo stesso modo, nel mondo della programmazione, abbiamo bisogno di un meccanismo per iterare sistematicamente attraverso una raccolta di oggetti software. Java include vari meccanismi per l'iterazione, inclusi l' indice (per l'iterazione su un array), il cursore (per l'iterazione sui risultati di una query sul database), l' enumerazione (nelle prime versioni di Java) e l' iteratore (nelle versioni più recenti di Java).

Il pattern Iterator

Un iteratore è un meccanismo che consente a tutti gli elementi di una raccolta di accedere in sequenza, con alcune operazioni eseguite su ogni elemento. Essenzialmente, un iteratore fornisce un mezzo per "eseguire il ciclo" su una raccolta incapsulata di oggetti. Esempi di utilizzo degli iteratori includono

  • Visita ogni file in una directory ( ovvero cartella) e visualizza il suo nome.
  • Visita ogni nodo in un grafico e determina se è raggiungibile da un dato nodo.
  • Visita ogni cliente in coda (ad esempio, simulando una linea in una banca) e scopri da quanto tempo sta aspettando.
  • Visita ogni nodo nell'albero della sintassi astratta di un compilatore (che è prodotto dal parser) ed esegui il controllo semantico o la generazione di codice. (Puoi anche usare il pattern Visitor in questo contesto.)

Alcuni principi valgono per l'uso degli iteratori: in generale, dovresti essere in grado di avere più attraversamenti in corso allo stesso tempo; cioè, un iteratore dovrebbe consentire il concetto di ciclo annidato. Un iteratore dovrebbe anche essere non distruttivo, nel senso che l'atto di iterazione non dovrebbe, di per sé, modificare la raccolta. Ovviamente l'operazione eseguita sugli elementi di una collezione potrebbe eventualmente modificare alcuni degli elementi. Potrebbe anche essere possibile per un iteratore supportare la rimozione di un elemento da una raccolta o l'inserimento di un nuovo elemento in un punto particolare della raccolta, ma tali modifiche dovrebbero essere esplicite all'interno del programma e non un sottoprodotto dell'iterazione. In alcuni casi, sarà anche necessario disporre di iteratori con diversi metodi di attraversamento; per esempio, l'attraversamento del preordine e del postordine di un albero o l'attraversamento della prima e dell'ampiezza di un grafico.

Iterazione di strutture dati complesse

Ho imparato a programmare in una prima versione di FORTRAN, dove l'unica capacità di strutturazione dei dati era un array. Ho imparato rapidamente come iterare su un array utilizzando un indice e un ciclo DO. Da lì è stato solo un breve salto mentale all'idea di utilizzare un indice comune in più array per simulare un array di record. La maggior parte dei linguaggi di programmazione ha caratteristiche simili agli array e supportano il semplice looping sugli array. Ma i linguaggi di programmazione moderni supportano anche strutture di dati più complesse come elenchi, insiemi, mappe e alberi, dove le capacità sono rese disponibili tramite metodi pubblici ma i dettagli interni sono nascosti nelle parti private della classe. I programmatori devono essere in grado di attraversare gli elementi di queste strutture di dati senza esporre la loro struttura interna, che è lo scopo degli iteratori.

Iteratori e i modelli di design Gang of Four

Secondo la Gang of Four (vedi sotto), il design pattern Iterator è un pattern comportamentale, la cui idea chiave è "prendere la responsabilità per l'accesso e l'attraversamento dall'oggetto elenco [ ed. Think collection ] e metterlo in un iteratore oggetto." Questo articolo non riguarda tanto il pattern Iterator quanto il modo in cui gli iteratori vengono utilizzati nella pratica. Per coprire completamente il modello sarebbe necessario discutere su come sarebbe progettato un iteratore, partecipanti (oggetti e classi) al design, possibili design alternativi e compromessi di diverse alternative di design. Preferisco concentrarmi su come gli iteratori vengono utilizzati nella pratica, ma ti indicherò alcune risorse per studiare il pattern Iterator e i design pattern in generale:

  • Design Patterns: Elements of Reusable Object-Oriented Software (Addison-Wesley Professional, 1994) scritto da Erich Gamma, Richard Helm, Ralph Johnson e John Vlissides (noto anche come Gang of Four o semplicemente GoF) è la risorsa definitiva per l'apprendimento sui modelli di design. Sebbene il libro sia stato pubblicato per la prima volta nel 1994, rimane un classico, come dimostra il fatto che ci sono state più di 40 stampe.
  • Bob Tarr, docente presso l'Università del Maryland Baltimore County, ha un'eccellente serie di diapositive per il suo corso sui modelli di progettazione, inclusa la sua introduzione al modello Iterator.
  • La serie JavaWorld di David Geary Java Design Patterns introduce molti dei design pattern Gang of Four, inclusi i pattern Singleton, Observer e Composite. Sempre su JavaWorld, la più recente panoramica in tre parti dei modelli di progettazione di Jeff Friesen include una guida ai modelli GoF.

Iteratori attivi vs iteratori passivi

Esistono due approcci generali per implementare un iteratore a seconda di chi controlla l'iterazione. Per un iteratore attivo (noto anche come iteratore esplicito o iteratore esterno ), il client controlla l'iterazione nel senso che il client crea l'iteratore, gli dice quando passare all'elemento successivo, verifica se ogni elemento è stato visitato, e così via. Questo approccio è comune in linguaggi come il C ++ ed è l'approccio che riceve la maggior attenzione nel libro GoF. Sebbene gli iteratori in Java abbiano assunto forme diverse, l'utilizzo di un iteratore attivo era essenzialmente l'unica opzione praticabile prima di Java 8.

Per un iteratore passivo (noto anche come iteratore implicito , iteratore interno o iteratore di callback ), l'iteratore stesso controlla l'iterazione. Il client essenzialmente dice all'iteratore, "esegui questa operazione sugli elementi nella raccolta". Questo approccio è comune in linguaggi come LISP che forniscono funzioni o chiusure anonime. Con il rilascio di Java 8, questo approccio all'iterazione è ora un'alternativa ragionevole per i programmatori Java.

Schemi di denominazione Java 8

Sebbene non sia così grave come Windows (NT, 2000, XP, VISTA, 7, 8, ...), la cronologia delle versioni di Java include diversi schemi di denominazione. Per iniziare, dovremmo fare riferimento all'edizione standard di Java come "JDK", "J2SE" o "Java SE"? I numeri di versione di Java sono iniziati abbastanza semplici - 1.0, 1.1, ecc. - ma tutto è cambiato con la versione 1.5, che era denominata Java (o JDK) 5. Quando mi riferisco alle prime versioni di Java, utilizzo frasi come "Java 1.0" o "Java 1.1 ", ma dopo la quinta versione di Java utilizzo frasi come" Java 5 "o" Java 8. "

Per illustrare i vari approcci all'iterazione in Java, ho bisogno di un esempio di una raccolta e di qualcosa che deve essere fatto con i suoi elementi. Per la parte iniziale di questo articolo userò una raccolta di stringhe che rappresentano i nomi delle cose. Per ogni nome nella raccolta, stamperò semplicemente il suo valore sull'output standard. Queste idee di base possono essere facilmente estese a raccolte di oggetti più complicati (come i dipendenti) e in cui l'elaborazione per ogni oggetto è un po 'più complicata (come dare a ogni dipendente altamente valutato un aumento del 4,5%).

Altre forme di iterazione in Java 8

Mi sto concentrando sull'iterazione sulle raccolte, ma ci sono altre forme più specializzate di iterazione in Java. Ad esempio, è possibile utilizzare un JDBC ResultSetper eseguire l'iterazione sulle righe restituite da una query SELECT a un database relazionale o utilizzare a Scannerper eseguire l'iterazione su un'origine di input.

Iterazione con la classe Enumeration

In Java 1.0 e 1.1, le due classi di raccolta primarie erano Vectore Hashtablee il modello di progettazione Iterator è stato implementato in una classe chiamata Enumeration. In retrospettiva questo era un brutto nome per la classe. Non confondere la classe Enumerationcon il concetto di tipi enum , che non appare fino Java 5. Oggi sia Vectore Hashtablesono classi generiche, ma allora i generici non facevano parte del linguaggio Java. Il codice per elaborare un vettore di stringhe utilizzando Enumerationsarebbe simile al Listato 1.

Listato 1. Utilizzo dell'enumerazione per iterare su un vettore di stringhe

 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); } 

Iterazione con la classe Iterator

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

Ora consideriamo di fare qualcosa di leggermente più complicato della semplice stampa dei nomi nella nostra lista. Supponiamo, per esempio, che vogliamo contare il numero di nomi che iniziano con la lettera A . Potremmo implementare la logica più complicata come parte dell'espressione lambda, oppure potremmo usare la nuova API Stream di Java 8. Prendiamo quest'ultimo approccio.