232 lines
10 KiB
Plaintext
232 lines
10 KiB
Plaintext
[set
|
||
title = "Tableaux associatifs"
|
||
partAs = chapitre
|
||
translator = "Raphaël Jakse"
|
||
proofreader = "Stéphane Goujet"
|
||
]
|
||
|
||
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 [[part:tableaux | chapitre sur les tableaux] comme des conteneurs qui stockent leurs éléments côte à côte, éléments auxquels ont peut accéder par des indices. Un tableau qui stocke les noms des jours de la semaine peut être définit comme suit~ :
|
||
|
||
[code=d <<<
|
||
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~ :
|
||
|
||
[code=d <<<
|
||
writeln(nomsDesJours[1]); // affiche "mardi"
|
||
>>>]
|
||
|
||
Le fait que l'on peut accéder aux éléments par les valeurs d'indices 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és [* clés] (''keys''), plutôt qu'indices. Les tableaux associatifs donnent accès à chacun de leurs éléments par leurs clés.
|
||
|
||
[ = 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.
|
||
|
||
]
|
||
[ = 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~ :
|
||
|
||
[code=d <<<
|
||
type_des_éléments[type_des_clés] nom_du_tableau_associatif;
|
||
>>>]
|
||
|
||
Par exemple, un tableau associatif qui associe des noms de jours de type [c string] à des numéros de type [c int] peut être défini de cette manière~ :
|
||
|
||
[code=d <<<
|
||
int[string] numerosDesJours;
|
||
>>>]
|
||
|
||
La variable [c numerosDesJours] est un tableau associatif qui peut être utilisé comme un tableau qui fournit une association des noms de jours à leurs numéros. En d'autres termes, il peut être utilisé comme l'inverse du tableau [c nomsDesJours] du début de ce chapitre. On utilisera le tableau associatif [c 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.
|
||
|
||
]
|
||
[ = Ajouter des éléments
|
||
|
||
L'opérateur d'affectation est suffisant pour construire l'association entre une clé et une valeur~ :
|
||
|
||
[code=d <<<
|
||
// 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, [c numerosDesJours] contient deux éléments après les opérations précédentes. On peut le montrer en affichant le tableau entier~ :
|
||
|
||
[code=d <<<
|
||
writeln(numerosDesJours);
|
||
>>>]
|
||
|
||
La sortie indique que les éléments de valeur 0 et 1 correspondent respectivement aux clés de valeur [c "lundi"] et [c "mardi"]~ :
|
||
|
||
[code=d <<<
|
||
["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é~ :
|
||
|
||
[code=d <<<
|
||
numerosDesJours["mardi"] = 222; // modification d'un élément existant
|
||
writeln(numerosDesJours);
|
||
>>>]
|
||
|
||
La sortie~ :
|
||
|
||
[code=d <<<
|
||
["lundi":0, "mardi":222]
|
||
>>>]
|
||
|
||
]
|
||
[ = 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-point séparant chaque clé de son élément~ :
|
||
|
||
[code=d <<<
|
||
// 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
|
||
>>>]
|
||
|
||
]
|
||
[ = Supprimer des éléments
|
||
|
||
L'élément qui correspond à une clé est supprimé par [c .remove()] :
|
||
|
||
[code=d <<<
|
||
numerosDesJours.remove("mardi");
|
||
writeln(numerosDesJours["mardi"]); // ← ERREUR lors de l'exécution
|
||
>>>]
|
||
|
||
La première ligne supprime l'élément de la clé [c "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.
|
||
]
|
||
[ = Déterminer la présence d'un élément
|
||
|
||
L'opérateur [c in] détermine si l'élément pour une clé donnée existe dans le tableau associatif :
|
||
|
||
[code=d <<<
|
||
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 [c codesDeCouleurs]. [c .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 [c .get()]~ :
|
||
|
||
[code=d <<<
|
||
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", [c .get()] returne -1~ :
|
||
|
||
[output <<<
|
||
-1
|
||
>>>]
|
||
|
||
]
|
||
[ = Propriétés
|
||
|
||
- [c .length] retourne le nombre d'éléments dans le tableau.
|
||
- [c .keys] retourne les copies des clés du tableau associatif dans un tableau dynamique.
|
||
- [c .byKey] donne un accès aux clés du tableau associatif sans les copier~ ; nous verrons comment [c .byKey] est utilisé dans les boucles [c foreach] dans le chapitre suivant.
|
||
- [c .values] retourne les copies de toutes les valeurs du tableau associatif dans un tableau dynamique.
|
||
- [c .byValue] donne un accès aux éléments du tableau associatif sans les copier.
|
||
- [c .rehash] peut rendre le tableau plus efficace dans certains cas comme après avoir inséré un grand nombre d'élements et avant d'effectivement utiliser le tableau associatif.
|
||
- [c .sizeof] est la taille de la référence du tableau (cela n'a rien n'a voir avec le nombre d'éléments dans le tableau et a la même valeur pour tous les tableaux associatifs).
|
||
- [c .get] retourne l'élement s'il existe, la valeur par défaut sinon.
|
||
- [c .remove] supprime l'élément indiqué du tableau.
|
||
|
||
]
|
||
|
||
[ = Exemple
|
||
|
||
Voici un programme qui affiche les noms turcs des couleurs qui sont indiqués en français~ :
|
||
|
||
[code=d <<<
|
||
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-moi 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.");
|
||
}
|
||
}
|
||
>>>]
|
||
|
||
]
|
||
[ = Exercices
|
||
|
||
# [
|
||
Comment tous les éléments d'un tableau associatif peuvent-ils être supprimés~ ? Il y a au moins trois méthodes~ :
|
||
# Supprimer les éléments un par un.
|
||
# Affecter un tableau associatif vide.
|
||
# De façon similaire à la méthode précédente, affecter la propriété [c .init] du tableau.
|
||
|
||
[p Note~ : | la propriété [c .init] de n'importe quelle variable est la valeur initiale de ce type~ :]
|
||
|
||
[code=d <<<
|
||
nombre = int.init; // 0 pour int
|
||
>>>]
|
||
]
|
||
# [
|
||
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 [c 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~ :
|
||
|
||
[code=d <<<
|
||
int[string] notes;
|
||
notes["pierre"] = 18;
|
||
notes["pierre"] = 17; // ← Remplace la note précédente !
|
||
>>>]
|
||
|
||
Comment pouvez-vous résoudre ce problème~ ? Définir un tableau associatif qui peut stocker plusieurs notes par étudiant.
|
||
]
|
||
|
||
[[part:corrections/tableaux_associatifs | … Les solutions]]
|
||
]
|