Cours complet pour apprendre à programmer en D


précédentsommairesuivant

32. Tableaux associatifs

Les tableaux associatifs sont une fonctionnalité que l'on trouve dans la plupart des langages modernes de haut niveau. Ils constituent une structure de données très rapide qui fonctionne comme une mini base de données et sont couramment utilisés dans beaucoup de programmes.

Nous avons vu les tableaux dans le chapitre sur les tableauxTableaux comme des conteneurs qui stockent leurs éléments côte à côte, éléments auxquels on peut accéder par des indices. Un tableau qui stocke le nom des jours de la semaine peut être défini comme suit :

 
Sélectionnez
string[] nomsDesJours =
      [ "lundi", "mardi", "mercredi", "jeudi",
         "vendredi", "samedi", "dimanche" ];

On peut accéder au nom d'un jour donné par son indice dans ce tableau :

 
Sélectionnez
writeln(nomsDesJours[1]);   // affiche "mardi"

Le fait que l'on peut accéder aux éléments par les valeurs d'indice peut être décrit comme une association d'indices avec les éléments. En d'autres termes, les tableaux associent les indices aux éléments. Les tableaux ne peuvent utiliser que des entiers comme indices.

Les tableaux associatifs permettent d'indexer les éléments par des entiers, mais également par n'importe quel autre type. Ils associent les valeurs d'un type à des valeurs d'un autre type. Les valeurs qui servent d'indices dans un tableau associatif sont appelées clés (keys), plutôt qu'indices. Les tableaux associatifs donnent accès à chacun de leurs éléments par leur clé.

32-1. Très rapide, mais désordonné

Les tableaux associatifs sont une implémentation de table de hashage. Les tables de hashage font partie des collections les plus rapides pour stocker et accéder à des éléments. Sauf cas pathologique, le temps de stockage d'accès à un élément est indépendant du nombre d'éléments qu'il y a dans le tableau associatif.

La contrepartie de la grande efficacité des tableaux associatifs est leur stockage désordonné. À la différence des tableaux, les éléments des tables de hashage ne sont pas côte à côte. Ils ne sont triés d'aucune manière particulière.

32-2. Définition

La syntaxe des tableaux associatifs est similaire à la syntaxe des tableaux. La différence est que c'est le type des clés qui est spécifié entre les crochets, et non la taille du tableau :

 
Sélectionnez
type_des_éléments[type_des_clés] nom_du_tableau_associatif;

Par exemple, un tableau associatif qui associe le nom des jours de type string à un numéro de type int peut être défini de cette manière :

 
Sélectionnez
int[string] numerosDesJours;

La variable numerosDesJours est un tableau associatif qui peut être utilisé comme un tableau qui fournit une association du nom de jour à son numéro. En d'autres termes, il peut être utilisé comme l'inverse du tableau nomsDesJours du début de ce chapitre. On utilisera le tableau associatif numerosDesJours dans les exemples qui suivent.

Les clés des tableaux associatifs peuvent être de n'importe quel type, structures et classes définies par l'utilisateur comprises. Nous verrons les types définis par l'utilisateur dans des chapitres ultérieurs.

La taille des tableaux associatifs ne peut pas être spécifiée lors de la définition. Ceux-ci grandissent automatiquement quand des éléments sont ajoutés.

32-3. Ajouter des éléments

L'opérateur d'affectation est suffisant pour construire l'association entre une clé et une valeur :

 
Sélectionnez
// associe l'élément 0 avec la clé "lundi"
numerosDesJours["lundi"] = 0;
 
// associe l'élément 1 avec la clé "mardi"
numerosDesJours["mardi"] = 1;

La table grandit automatiquement avec chaque association. Par exemple, numerosDesJours contient deux éléments après les opérations précédentes. On peut le montrer en affichant le tableau entier :

 
Sélectionnez
writeln(numerosDesJours);

La sortie indique que les éléments de valeur 0 et 1 correspondent respectivement aux clés de valeur "lundi" et "mardi" :

 
Sélectionnez
["lundi":0, "mardi":1]

Il ne peut y avoir qu'un élément par clé. Pour cette raison, quand on affecte une valeur à une clé déjà existante, le tableau ne grandit pas. L'élément associé à la clé est simplement remplacé :

 
Sélectionnez
numerosDesJours["mardi"] = 222;   // modification d'un élément existant
writeln(numerosDesJours);

La sortie :

 
Sélectionnez
["lundi":0, "mardi":222]

32-4. Initialisation

Parfois, certaines associations entre les clés et les valeurs sont déjà connues au moment de la définition du tableau associatif. Les tableaux associatifs sont initialisés de façon similaire aux tableaux, avec un deux-points séparant chaque clé de son élément :

 
Sélectionnez
// clé : élément
int[string] numerosDesJours =
   [ "lundi"    : 0, "mardi"    : 1, "mercredi" : 2,
     "jeudi"    : 3, "vendredi" : 4, "samedi"   : 5,
     "dimanche" : 6 ];
 
writeln(numerosDesJours["mardi"]);    // affiche 1

32-5. Supprimer des éléments

L'élément qui correspond à une clé est supprimé par .remove() :

 
Sélectionnez
numerosDesJours.remove("mardi");
writeln(numerosDesJours["mardi"]);    //  ERREUR lors de l'exécution

La première ligne supprime l'élément de la clé "mardi". Comme cet élément n'est plus dans le conteneur, la seconde ligne entraîne une exception et l'arrêt du programme si l'exception n'est pas attrapée. Nous verrons les exceptions dans un chapitre ultérieur.

Il est possible de supprimer tous les éléments en une fois, comme nous le verrons dans le premier exercice de fin de chapitre.

32-6. Déterminer la présence d'un élément

L'opérateur in détermine si l'élément pour une clé donnée existe dans le tableau associatif :

 
Sélectionnez
int[string] codesDeCouleurs = [ /* ... */ ];
 
if ("violet" in codesDeCouleurs) {
   // il y a un élément pour la clé "violet"
 
} else {
   // aucun élément pour la clé "violet"
}

Parfois, utiliser une valeur par défaut pour les clés qui n'existent pas dans le tableau associatif a un sens. Par exemple, la valeur spéciale -1 peut être utilisée comme le code des couleurs qui ne sont pas dans codesDeCouleurs. .get() est utile dans de telles situations : elle retourne la valeur de l'élément si l'élément pour la clé donnée existe, la valeur par défaut sinon. La valeur par défaut est indiquée en second paramètre de .get() :

 
Sélectionnez
int[string] codesDeCouleurs = [ "bleu" : 10, "vert" : 20 ];
writeln(codesDeCouleurs.get("violet", -1));

Comme le tableau ne contient pas d'élément pour la clé « violet », .get() returne -1 :

 
Sélectionnez
-1

32-7. Propriétés

  • .length retourne le nombre d'éléments dans le tableau.
  • .keys retourne les copies des clés du tableau associatif dans un tableau dynamique.
  • .byKey donne un accès aux clés du tableau associatif sans les copier ; nous verrons comment .byKey est utilisé dans les boucles foreach dans le chapitre suivant.
  • .values retourne les copies de toutes les valeurs du tableau associatif dans un tableau dynamique.
  • .byValue donne un accès aux éléments du tableau associatif sans les copier.
  • .rehash peut rendre le tableau plus efficace dans certains cas comme après avoir inséré un grand nombre d'éléments et avant d'effectivement utiliser le tableau associatif.
  • .sizeof est la taille de la référence du tableau (cela n'a rien à voir avec le nombre d'éléments dans le tableau et a la même valeur pour tous les tableaux associatifs).
  • .get retourne l'élément s'il existe, la valeur par défaut sinon.
  • .remove supprime l'élément indiqué du tableau.

32-8. Exemple

Voici un programme qui affiche le nom turc des couleurs qui sont indiquées en français :

 
Sélectionnez
import std.stdio;
import std.string;
 
void main()
{
   string[string] couleurs = [ "noir" : "siyah",
                              "blanc" : "beyaz",
                              "rouge" : "kırmızı",
                              "vert"  : "yeşil",
                              "bleu"  : "mavi"
                             ];
 
   writefln("Je connais les noms turcs de ces %s couleurs : %s",
            couleurs.length, couleurs.keys);
 
   write("Demandez-m'en une : ");
   string enFrancais = chomp(readln());
 
   if (enFrancais in couleurs) {
      writefln("\"%s\" est \"%s\" en turc.",
               enFrancais, couleurs[enFrancais]);
 
   } else {
      writeln("Je ne connais pas cette couleur.");
   }
}

32-9. Exercices

  1. Comment tous les éléments d'un tableau associatif peuvent-ils être supprimés ? Il y a au moins trois méthodes :

    1. Supprimer les éléments un par un ;
    2. Affecter un tableau associatif vide ;
    3. De façon similaire à la méthode précédente, affecter la propriété .init du tableau.

       
      Sélectionnez
      nombre = int.init;    // 0 pour int

    Note : la propriété .init de n'importe quelle variable est la valeur initiale de ce type :

  2. Comme pour les tableaux, il ne peut y avoir qu'une valeur par clé. Ceci peut être vu comme une limitation pour certaines applications.
    Supposons qu'un tableau associatif soit utilisé pour stocker des notes d'étudiants. Par exemple, supposons que les notes 18, 17, 19, etc. soient à stocker pour l'étudiant « pierre ».
    Les tableaux associatifs permettent facilement d'accéder aux notes par le nom de l'étudiant comme dans notes["pierre"]. Cependant, les notes ne peuvent pas être ajoutées de la manière suivante parce que chaque note remplacerait la précédente :

     
    Sélectionnez
    int[string] notes;
    notes["pierre"] = 18;
    notes["pierre"] = 17;   //  Remplace la note précédente !
  3. Comment pouvez-vous résoudre ce problème ? Définir un tableau associatif qui peut stocker plusieurs notes par étudiant.

Les solutionsTableaux associatifs - Correction.


précédentsommairesuivant

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+