Chapitre 9 - Stockage des objets

pages : 1 2 3 4 5 6 7 8 9 10 11 12 13 14

Arrays.binarySearch() renvoie une valeur supérieure ou égale à zéro si l'item recherché est trouvé. Dans le cas contraire, elle renvoie une valeur négative représentant l'endroit où insérer l'élément si on désirait maintenir le tableau trié à la main. La valeur retournée est :

-(point d'insertion) - 1

Le point d'insertion est l'index du premier élément plus grand que la clef, ou a.size() si tous les éléments du tableau sont plus petits que la clef spécifiée.

Si le tableau contient des éléments dupliqués, aucune garantie n'est apportée quant à celui qui sera trouvé. L'algorithme n'est donc pas conçu pour les tableaux comportant des doublons, bien qu'il les tolère. Dans le cas où on a besoin d'une liste triée d'éléments sans doublons, mieux vaut se tourner vers un TreeSet (qui sera introduit plus loin dans ce chapitre) qui gère tous ces détails automatiquement, plutôt que de maintenir un tableau à la main (à moins que des questions de performance ne se greffent là-dessus).

Il faut fournir à binarySearch() le même objet Comparator que celui utilisé pour trier le tableau d'objets (les tableaux de scalaires n'autorisent pas les tris avec des Comparator), afin qu'elle utilise la version redéfinie de la fonction de comparaison. Ainsi, le programme AlphabeticSorting.java peut être modifié pour effectuer une recherche :

//: c09:AlphabeticSearch.java
// Rechercher avec un Comparator.
import com.bruceeckel.util.*;
import java.util.*;

public class AlphabeticSearch {
  public static void main(String[] args) {
    String[] sa = new String[30];
    Arrays2.fill(sa,
      new Arrays2.RandStringGenerator(5));
    AlphabeticComparator comp =      new AlphabeticComparator();
    Arrays.sort(sa, comp);
    int index =      Arrays.binarySearch(sa, sa[10], comp);
    System.out.println("Index = " + index);
  }
} ///:~

binarySearch() accepte le Comparator en troisième argument. Dans l'exemple précédent, le succès de la recherche est garanti puisque l'item recherché est tiré du tableau lui-même.

Résumé sur les tableaux

Pour résumer ce qu'on a vu jusqu'à présent, un tableau se révèle la manière la plus simple et la plus efficace pour stocker un groupe d'objets, et le seul choix possible dans le cas où on veut stocker un ensemble de scalaires. Dans le reste de ce chapitre nous allons étudier le cas plus général dans lequel on ne sait pas au moment de l'écriture du programme combien d'objets seront requis, ainsi que des moyens plus sophistiqués de stocker les objets. Java propose en effet des classes conteneurs qui adressent différents problèmes. Les types de base en sont les Lists, les Sets et les Maps. Un nombre surprenant de problèmes peuvent être facilement résolus grâce à ces outils.

Entre autres caractéristiques - les Sets, par exemple, ne stockent qu'un objet de chaque valeur, les Maps sont des tableaux associatifs qui permettent d'associer n'importe quel objet avec n'importe quel autre objet - les classes conteneurs de Java se redimensionnent automatiquement. A l'inverse des tableaux, ils peuvent donc stocker un nombre quelconque d'objets et on n'a pas besoin de se soucier de leur taille lors de l'écriture du programme.

Introduction sur les conteneurs

Les classes conteneurs sont à mon sens l'un des outils les plus puissants disponibles parce qu'ils augmentent de façon significative la productivité du développement. Les conteneurs de Java 2 résultent d'une reconception approfondie [47] des implémentations relativement pauvres disponibles dans Java 1.0 et 1.1. Cette reconception a permis d'unifier et de rationnaliser certains fonctionnements. Elle a aussi comblé certains manques de la bibliothèque des conteneurs tels que les listes chaînées, les files (queues) et les files doubles (queues à double entrée).

La conception d'une bibliothèque de conteneurs est difficile (de même que tous les problèmes de conception des bibliothèques). En C++, les classes conteneurs couvrent les bases grâce à de nombreuses classes différentes. C'est mieux que ce qui était disponible avant (ie, rien), mais le résultat ne se transpose pas facilement dans Java. J'ai aussi rencontré l'approche opposée, où la bibliothèque de conteneurs consistait en une seule classe qui fonctionnait à la fois comme une séquence linéaire et un tableau associatif. La bibliothèque de conteneurs de Java 2 essaie de trouver un juste milieu : les fonctionnalités auxquelles on peut s'attendre de la part d'une bibliothèque de conteneurs mâture, mais plus facile à appréhender que les classes conteneurs du C++ ou d'autres bibliothèques de conteneurs similaires. Le résultat peut paraître étrange dans certains cas. Mais contrairement à certaines décisions prises dans la conception des premières bibliothèques Java, ces bizarreries ne sont pas des accidents de conception, mais des compromis minutieusement examinés sur la complexité. Il vous faudra peut-être un petit moment avant d'être à l'aise avec certains aspects de la bibliothèque, mais je pense que vous adopterez quand même très rapidement ces nouveaux outils.

Le but de la bibliothèque de conteneurs de Java 2 est de « stocker des objets » et le divise en deux concepts bien distincts :

Collection : un groupe d'éléments individuels, souvent associé à une règle définissant leur comportement. Une List doit garder les éléments dans un ordre précis, et un Set ne peut contenir de doublons (les sacs [NdT : bag en anglais], qui ne sont pas implémentés dans la bibliothèque de conteneurs de Java - les Lists fournissant des fonctionnalités équivalentes - ne possèdent pas une telle règle).
Map : un ensemble de paires clef - valeur. A première vue, on pourrait penser qu'il ne s'agit que d'une Collection de paires, mais lorsqu'on essaie de l'implémenter de cette manière, le design devient très rapidement bancal et lourd à mettre en oeuvre ; il est donc plus simple d'en faire un concept séparé. D'un autre côté, il est bien pratique d'examiner certaines portions d'une Map en créant une Collection représentant cette portion. Une Map peut donc renvoyer un Set de ses clefs, une Collection de ses valeurs, ou un Set de ses paires. Les Maps, comme les tableaux, peuvent facilement être étendus dans de multiples dimensions sans ajouter de nouveaux concepts : il suffit de créer une Map dont les valeurs sont des Maps (les valeurs de ces Maps pouvant elles-mêmes être des Maps, etc.).

Nous allons d'abord examiner les fonctionnalités générales des conteneurs, puis aller dans les spécificités des conteneurs et enfin nous apprendrons pourquoi certains conteneurs sont déclinés en plusieurs versions, et comment choisir entre eux.

Imprimer les conteneurs

A l'inverse des tableaux, les conteneurs s'affichent correctement sans aide. Voici un exemple qui introduit en même temps les conteneurs de base :

//: c09:PrintingContainers.java
// Les conteneurs savent comment s'afficher.
import java.util.*;

public class PrintingContainers {
  static Collection fill(Collection c) {
    c.add("dog");
    c.add("dog");
    c.add("cat");
    return c;
  }
  static Map fill(Map m) {
    m.put("dog", "Bosco");
    m.put("dog", "Spot");
    m.put("cat", "Rags");
    return m;
  }
  public static void main(String[] args) {
    System.out.println(fill(new ArrayList()));
    System.out.println(fill(new HashSet()));
    System.out.println(fill(new HashMap()));
  }
} ///:~

Comme mentionné précédemment, il existe deux catégories de base dans la bibliothèque de conteneurs Java. La distinction est basée sur le nombre d'items stockés dans chaque cellule du conteneur. La catégorie Collection ne stocke qu'un item dans chaque emplacement (le nom est un peu trompeur puisque les bibliothèques des conteneurs sont souvent appelées des « collections »). Elle inclut la List, qui stocke un groupe d'items dans un ordre spécifique, et le Set, qui autorise l'addition d'une seule instance pour chaque item. Une ArrayList est un type de List, et HashSet est un type de Set. La méthode add() permet d'ajouter des éléments dans une Collection.

Une Map contient des paires clef - valeur, un peu à la manière d'une mini base de données. Le programme précédent utilise un type de Map, le HashMap. Si on dispose d'une Map qui associe les états des USA avec leur capitale et qu'on souhaite connaître la capitale de l'Ohio, il suffit de la rechercher - comme si on indexait un tableau (les Maps sont aussi appelés des tableaux associatifs). La méthode put(), qui accepte deux arguments - la clef et la valeur -, permet de stocker des éléments dans une Map. L'exemple précédent se contente d'ajouter des éléments mais ne les récupère pas une fois stockés. Ceci sera illustré plus tard.

Les méthodes surchargées fill() remplissent respectivement des Collections et des Maps. En examinant la sortie produite par le programme, on peut voir que le comportement par défaut pour l'affichage (fourni par les méthodes toString() des différents conteneurs) produit un résultat relativement clair, il n'est donc pas nécessaire d'ajouter du code pour imprimer les conteneurs comme nous avons du le faire avec les tableaux :

[dog, dog, cat]
[cat, dog]
{cat=Rags, dog=Spot}

Une Collection est imprimée entre crochets, chaque élément étant séparé par une virgule. Une Map est entourée par des accolades, chaque clef étant associée à sa valeur avec un signe égal (les clefs à gauche, les valeurs à droite).

Le comportement de base des différents conteneurs est évident dans cet exemple. La List stocke les objets dans l'ordre exact où ils ont été ajoutés, sans aucun réarrangement ni édition. Le Set, lui, n'accepte qu'une seule instance d'un objet et utilise une méthode interne de tri (en général, un Set sert à savoir si un élément est un membre d'un Set ou non, et non l'ordre dans lequel il apparaît dans ce Set - pour cela il faut utiliser une List). La Map elle aussi n'accepte qu'une seule instance d'un objet pour la clef, possède elle aussi sa propre organisation interne et ne tient pas compte de l'ordre dans lequel les éléments ont été insérés.

Remplir les conteneurs

Bien que le problème d'impression des conteneurs soit géré pour nous, le remplissage des conteneurs souffre des mêmes limitations que java.util.Arrays. De même que pour les Arrays, il existe une classe compagnon appelée Collections contenant des méthodes static dont l'une s'appelle fill(). Cette méthode fill() ne fait que dupliquer une unique référence sur un objet dans le conteneur, et ne fonctionne que sur les objets List, pas sur les Sets ni les Maps :

//: c09:FillingLists.java
// La méthode Collections.fill().
import java.util.*;

public class FillingLists {
  public static void main(String[] args) {
    List list = new ArrayList();
    for(int i = 0; i < 10; i++)
      list.add("");
    Collections.fill(list, "Hello");
    System.out.println(list);
  }
} ///:~

Cette méthode est encore moins intéressante parce qu'elle ne fait que remplacer les éléments déjà présents dans la List, sans ajouter aucun élément.

Pour être capable de créer des exemples intéressants, voici une bibliothèque complémentaire Collections2 (appartenant par commodité à com.bruceeckel.util) disposant d'une méthode fill() utilisant un générateur pour ajouter des éléments, et permettant de spécifier le nombre d'éléments qu'on souhaite ajouter. L'interface Generator définie précédemment fonctionne pour les Collections, mais les Maps requièrent leur propre interface générateur puisqu'un appel à next() doit produire une paire d'objets (une clef et une valeur). Voici tout d'abord la classe Pair :

//: com:bruceeckel:util:Pair.java
package com.bruceeckel.util;
public class Pair {
  public Object key, value;
  Pair(Object k, Object v) {
    key = k;
    value = v;
  }
} ///:~

Ensuite, l'interface générateur qui produit un objet Pair :

//: com:bruceeckel:util:MapGenerator.java
package com.bruceeckel.util;
public interface MapGenerator {
Pair next();
} ///:~

Avec ces deux objets, un ensemble d'utilitaires pour travailler avec les classes conteneurs peuvent être développés :

//: com:bruceeckel:util:Collections2.java
// Remplir n'importe quel type de conteneur en
// utilisant un objet générateur.
package com.bruceeckel.util;
import java.util.*;

public class Collections2 {
  // Remplit une Collection en utilisant un générateur :
  public static void
  fill(Collection c, Generator gen, int count) {
    for(int i = 0; i < count; i++)
      c.add(gen.next());
  }
  public static void
  fill(Map m, MapGenerator gen, int count) {
    for(int i = 0; i < count; i++) {
      Pair p = gen.next();
      m.put(p.key, p.value);
    }
  }
  public static class RandStringPairGenerator
  implements MapGenerator {
    private Arrays2.RandStringGenerator gen;
    public RandStringPairGenerator(int len) {
      gen = new Arrays2.RandStringGenerator(len);
    }
    public Pair next() {
      return new Pair(gen.next(), gen.next());
    }
  }
  // Objet par défaut afin de ne pas avoir
  // à en créer un de notre cru :
  public static RandStringPairGenerator rsp =    new RandStringPairGenerator(10);
  public static class StringPairGenerator
  implements MapGenerator {
    private int index = -1;
    private String[][] d;
    public StringPairGenerator(String[][] data) {
      d = data;
    }
    public Pair next() {
      // Force l'index dans la plage de valeurs :
      index = (index + 1) % d.length;
      return new Pair(d[index][0], d[index][1]);
    }
    public StringPairGenerator reset() {
      index = -1;
      return this;
    }
  }
  // Utilisation d'un ensemble de données prédéfinies :
  public static StringPairGenerator geography =    new StringPairGenerator(
      CountryCapitals.pairs);
  // Produit une séquence à partir d'un tableau 2D :
  public static class StringGenerator
  implements Generator {
    private String[][] d;
    private int position;
    private int index = -1;
    public
    StringGenerator(String[][] data, int pos) {
      d = data;
      position = pos;
    }
    public Object next() {
      // Force l'index dans la plage de valeurs :
      index = (index + 1) % d.length;
      return d[index][position];
    }
    public StringGenerator reset() {
      index = -1;
      return this;
    }
  }
  // Utilisation d'un ensemble de données prédéfinies :
  public static StringGenerator countries =    new StringGenerator(CountryCapitals.pairs,0);
  public static StringGenerator capitals =    new StringGenerator(CountryCapitals.pairs,1);
} ///:~

Ce livre a été écrit par Bruce Eckel ( télécharger la version anglaise : Thinking in java )
Ce chapitre a été traduit par Jérome Quelin ( groupe de traduction )
télécharger la version francaise (PDF) | Commandez le livre en version anglaise (amazon) | télécharger la version anglaise

pages : 1 2 3 4 5 6 7 8 9 10 11 12 13 14

Penser en Java 2nde édition

Thinking in Java