Itérer des collections en Java

Chaque fois que vous avez une collection de choses, vous aurez besoin d'un mécanisme pour parcourir systématiquement les éléments de cette collection. Comme exemple de tous les jours, considérons la télécommande du téléviseur, qui nous permet de parcourir différentes chaînes de télévision. De même, dans le monde de la programmation, nous avons besoin d'un mécanisme pour itérer systématiquement à travers une collection d'objets logiciels. Java comprend divers mécanismes d'itération, notamment l' index (pour l'itération sur un tableau), le curseur (pour l'itération sur les résultats d'une requête de base de données), l' énumération (dans les premières versions de Java) et l' itérateur (dans les versions plus récentes de Java).

Le modèle Iterator

Un itérateur est un mécanisme qui permet d'accéder séquentiellement à tous les éléments d'une collection, certaines opérations étant effectuées sur chaque élément. Essentiellement, un itérateur fournit un moyen de «boucler» sur une collection encapsulée d'objets. Des exemples d'utilisation d'itérateurs incluent

  • Visitez chaque fichier dans un répertoire ( aka dossier) et affichez son nom.
  • Visitez chaque nœud dans un graphique et déterminez s'il est accessible à partir d'un nœud donné.
  • Rendez visite à chaque client dans une file d'attente (par exemple, simulant une ligne dans une banque) et découvrez depuis combien de temps il ou elle attend.
  • Visitez chaque nœud dans l'arbre de syntaxe abstraite d'un compilateur (qui est produit par l'analyseur) et effectuez une vérification sémantique ou une génération de code. (Vous pouvez également utiliser le modèle Visiteur dans ce contexte.)

Certains principes s'appliquent à l'utilisation d'itérateurs: en général, vous devriez pouvoir avoir plusieurs traversées en cours en même temps; autrement dit, un itérateur doit permettre le concept de boucle imbriquée. Un itérateur doit également être non destructif dans le sens où l'acte d'itération ne doit pas, à lui seul, modifier la collection. Bien entendu, l'opération effectuée sur les éléments d'une collection peut éventuellement modifier certains éléments. Il peut également être possible pour un itérateur de prendre en charge la suppression d'un élément d'une collection ou l'insertion d'un nouvel élément à un point particulier de la collection, mais ces modifications doivent être explicites dans le programme et non un sous-produit de l'itération. Dans certains cas, vous aurez également besoin d'itérateurs avec différentes méthodes de parcours; par exemple, le parcours de pré-ordre et de post-ordre d'un arbre, ou le parcours de profondeur d'abord et de largeur d'abord d'un graphe.

Itérer des structures de données complexes

J'ai d'abord appris à programmer dans une première version de FORTRAN, où la seule capacité de structuration des données était un tableau. J'ai rapidement appris à parcourir un tableau en utilisant un index et une boucle DO. À partir de là, ce n'était qu'un bref saut mental vers l'idée d'utiliser un index commun dans plusieurs tableaux pour simuler un tableau d'enregistrements. La plupart des langages de programmation ont des fonctionnalités similaires aux tableaux, et ils prennent en charge la boucle directe sur les tableaux. Mais les langages de programmation modernes prennent également en charge des structures de données plus complexes telles que des listes, des ensembles, des cartes et des arbres, où les capacités sont rendues disponibles via des méthodes publiques mais les détails internes sont cachés dans les parties privées de la classe. Les programmeurs doivent pouvoir parcourir les éléments de ces structures de données sans exposer leur structure interne, ce qui est le but des itérateurs.

Les itérateurs et les modèles de conception du groupe des quatre

Selon le Gang of Four (voir ci-dessous), le modèle de conception Iterator est un modèle comportemental, dont l'idée clé est de "prendre la responsabilité de l'accès et du parcours hors de l'objet de la liste [ ed. Think collection ] et de le mettre dans un itérateur objet." Cet article ne concerne pas autant le modèle Iterator que la façon dont les itérateurs sont utilisés dans la pratique. Pour couvrir entièrement le modèle, il faudrait discuter de la façon dont un itérateur serait conçu, des participants (objets et classes) dans la conception, des conceptions alternatives possibles et des compromis entre différentes alternatives de conception. Je préfère me concentrer sur la façon dont les itérateurs sont utilisés dans la pratique, mais je vais vous indiquer quelques ressources pour étudier le modèle Iterator et les modèles de conception en général:

  • Design Patterns: Elements of Reusable Object-Oriented Software (Addison-Wesley Professional, 1994) écrit par Erich Gamma, Richard Helm, Ralph Johnson et John Vlissides (également connu sous le nom de Gang of Four ou simplement GoF) est la ressource définitive pour l'apprentissage sur les modèles de conception. Bien que le livre ait été publié pour la première fois en 1994, il reste un classique, comme en témoigne le fait qu'il y a eu plus de 40 impressions.
  • Bob Tarr, professeur à l'Université du Maryland Baltimore County, a un excellent jeu de diapositives pour son cours sur les modèles de conception, y compris son introduction au modèle Iterator.
  • Les modèles de conception Java de la série JavaWorld de David Geary présentent de nombreux modèles de conception Gang of Four, y compris les modèles Singleton, Observer et Composite. Toujours sur JavaWorld, l'aperçu en trois parties plus récent de Jeff Friesen sur les modèles de conception comprend un guide des modèles GoF.

Itérateurs actifs vs itérateurs passifs

Il existe deux approches générales pour implémenter un itérateur en fonction de qui contrôle l'itération. Pour un itérateur actif (également appelé itérateur explicite ou itérateur externe ), le client contrôle l'itération dans le sens où le client crée l'itérateur, lui dit quand passer à l'élément suivant, teste pour voir si chaque élément a été visité, etc. Cette approche est courante dans des langages comme C ++, et c'est l'approche qui reçoit le plus d'attention dans le livre du GoF. Bien que les itérateurs en Java aient pris différentes formes, l'utilisation d'un itérateur actif était essentiellement la seule option viable avant Java 8.

Pour un iterator passif (aussi connu sous le nom d' un iterator implicite , itérateur interne ou rappel automatique iterator ), l'itérateur contrôle lui - même l'itération. Le client dit essentiellement à l'itérateur, "effectuez cette opération sur les éléments de la collection". Cette approche est courante dans les langages comme LISP qui fournissent des fonctions anonymes ou des fermetures. Avec la sortie de Java 8, cette approche de l'itération est désormais une alternative raisonnable pour les programmeurs Java.

Schémas de dénomination Java 8

Bien que pas aussi mauvais que Windows (NT, 2000, XP, VISTA, 7, 8, ...), l'historique des versions de Java comprend plusieurs schémas de dénomination. Pour commencer, devrions-nous faire référence à l'édition standard de Java sous le nom de «JDK», «J2SE» ou «Java SE»? Les numéros de version de Java ont commencé assez simplement - 1.0, 1.1, etc. - mais tout a changé avec la version 1.5, qui était de marque Java (ou JDK) 5. Quand je me réfère aux premières versions de Java, j'utilise des expressions comme "Java 1.0" ou "Java 1.1, "mais après la cinquième version de Java, j'utilise des expressions comme" Java 5 "ou" Java 8. "

Pour illustrer les différentes approches de l'itération en Java, j'ai besoin d'un exemple de collection et de quelque chose qui doit être fait avec ses éléments. Pour la première partie de cet article, j'utiliserai une collection de chaînes représentant des noms de choses. Pour chaque nom de la collection, j'imprimerai simplement sa valeur sur la sortie standard. Ces idées de base sont facilement étendues à des collections d'objets plus complexes (tels que les employés), et où le traitement de chaque objet est un peu plus complexe (comme donner à chaque employé hautement noté une augmentation de 4,5%).

Autres formes d'itération dans Java 8

Je me concentre sur l'itération des collections, mais il existe d'autres formes d'itération plus spécialisées en Java. Par exemple, vous pouvez utiliser un JDBC ResultSetpour parcourir les lignes renvoyées d'une requête SELECT vers une base de données relationnelle, ou utiliser a Scannerpour parcourir une source d'entrée.

Itération avec la classe Enumeration

Dans Java 1.0 et 1.1, les deux classes de collection principales étaient Vectoret Hashtable, et le modèle de conception Iterator a été implémenté dans une classe appelée Enumeration. Rétrospectivement, c'était une mauvaise réputation pour la classe. Ne pas confondre la classe Enumerationavec le concept de types de ENUM , qui ne semble pas que Java 5. Aujourd'hui , les deux Vectoret Hashtablesont des classes génériques, mais à l' époque génériques ne faisaient pas partie du langage Java. Le code pour traiter un vecteur de chaînes en utilisant Enumerationressemblerait à quelque chose comme le Listing 1.

Listing 1. Utilisation de l'énumération pour itérer sur un vecteur de chaînes

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

Itération avec 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

Considérons maintenant quelque chose d'un peu plus compliqué que simplement imprimer les noms dans notre liste. Supposons, par exemple, que nous voulons compter le nombre de noms qui commencent par la lettre A . Nous pourrions implémenter la logique plus compliquée dans le cadre de l'expression lambda, ou nous pourrions utiliser la nouvelle API Stream de Java 8. Prenons la dernière approche.