Dictionnaire

Nous allons présenter l’utilisation des dictionnaires (map). Plusieurs syntaxes existent, nous nous concentrons cependant sur les syntaxes les plus intuitives.

Création

La STL fournit la classe map pour gérer une sorte de tableau dont les indices peuvent être autre chose que des entiers. Par exemple, avec un dictionnaire on peut écrire :

Dict["TOTO"] = "TATA";
cout << Dict["TOTO"];
>> TATA

On ne peut plus parler d’indice, car dans cette exemple nous n’utilisons plus d’entiers. Le terme consacré sera clef, ainsi chaque clef donne accès à une unique valeur.

Les dictionnaires offrent plusieurs avantages :

Cette classe est une classe template, elle peut donc se spécialiser pour tout type d’éléments.

Contrairement aux tableaux, nous n’avons pas besoin d’avoir des indices contigus. Ainsi, si vous avez seulement 1000 indices utilisés sur une plage d’un million, il serait maladroit de choisir un tableau pour stocker ces 1000 éléments car la plupart des cases du tableau resteront inutilisées. Un dictionnaire vient donc résoudre ce problème en ne stockant que les clefs requises.

Grâce aux dictionnaires, on peut associer tout à n’importe quoi et c’est vraiment cool !

Note

Si les dictionnaires sont si souples et si pratiques, pourquoi ne pas utiliser que des dictionnaires ? Oui cette question peut être posée ! En fait ils sont plus souples, mais chaque opération sur un dictionnaire est plus longue que sur une liste, il y a donc un surcoût à cette souplesse.

Pour instancier un objet map, vous devez :

Mettre une directive #include <map>

En l’absence de : using namespace std, vous devez écrire std::map

Préciser le type des clefs et des éléments stockés en écrivant map< type_clef , type_valeur >.

Voici un exemple :

#include <iostream>
#include <map>
using namespace std;

int main()
{
   map<string,int>  D;

   D["TATA"] = 3;
   D["TITI"] = 7;

   cout << D["TATA"] << endl;
   cout << D["TITI"] << endl;
}
>> 3
>> 7

Parcours

La STL a voulu décrire une sorte de généralisation de l’indice des tableaux pour l’ensemble de ses structures de données. Ainsi sont nés les itérateurs. Voici un exemple permettant de lister toutes les paires (clef,valeur) contenues dans un dictionnaire, ne serait-ce, par exemple, qu’à des fins de débogage.

#include <iostream>
#include <map>
using namespace std;

int main()
{
        map<string,int>  D;

        D["TATA"] = 3;
        D["TITI"] = 7;

        for (auto it = D.begin(); it != D.end(); it++)
        {
                std::cout << it->first    // clef
                                  << ':'
                                  << it->second   // valeurs
                                  << std::endl;
        }
}
>> TATA:3
>> TITI:7

Quelques conseils pour comprendre cette syntaxe :

L.begin() est une méthode retournant un objet itérateur désignant le premier élément.

L.end() est une méthode retournant un objet itérateur désignant la fin de la liste, une sorte d’élément fictif positionné après le dernier élément.

On n’utilise plus le signe < pour vérifier si l’on a parcouru tous les éléments, mais l’opérateur != afin vérifier que nous n’avons pas atteint la fin de la liste.

L’opérateur ++ ne s’applique pas à un entier, mais sur l’itérateur nommé it. L’opérateur ++ a donc été surchargé pour passer à l’élément suivant.

L’opérateur -> a été surchargé pour accéder au contenu désigné par l’itérateur it. Même si cette syntaxe ressemble à celle des pointeurs, l’itérateur ne correspond pas forcément à un pointeur.

Le mot-clef auto permet d’éviter d’écrire le type de l’itérateur, c’est ici trés utile !

Vérifier l’existence d’une clef

Si l’on utilise une clef incorrecte pour accéder à un dictionnaire, une erreur va être levée. Dans ce contexte, il faut d’abord vérifier si la clef existe :

Voici un exemple :

#include <iostream>
#include <map>
using namespace std;

int Read(map<string,int>  & D, string key)
{
   if ( D.find(key) == D.end() ) return 0;  // si la clef est absente, on retourne une valeur par défaut
   return D[key];
}


int main()
{
        map<string,int>  D;

        D["TATA"] = 3;
        D["TITI"] = 7;

        cout << Read(D,"TATA") << endl;
        cout << Read(D,"TOTO") << endl;
}
>> 3
>> 0

L’agrégation face à l’héritage

A ce niveau, l’autre option en conception qui concurrence l’héritage et l’agrégation dynamique. L’agrégation, vous la connaissez largement, c’est la capacité d’un objet à avoir des champs. Ainsi, dans la logique de l’agrégation, un personnage magicien se décrit comme ayant:

un nom

des points de vie

un niveau d’énergie magique

une baguette magique

des pierres magiques

Et le chevalier :

un nom

des points de vie

une ou plusieurs armes

Dans un jeu où les personnages peuvent évoluer, il sera plus simple d’utiliser une classe Personnage comportant :

un nom

des points de vie

un dictionnaire

Le dictionnaire permet ainsi de stocker tous les éléments évoluant dans le temps. Cela peut aller d’un sort de protection, à de l’équipement ou encore des caractéristiques spéciales.

Cependant, les valeurs associées aux clefs dans un dictionnaire doivent être de même type. Ainsi, on peut utiliser des strings car ce type permet de représenter tous les autres ! En effet, on peut stocker un entier en écrivant : « int: 3 » ou un couple de valeur en écrivant « (int,int): (3,3) » ou encore une liste en écrivant « Lint: 2 99 33 ».

Il faut donc écrire des fonctions permettant de décoder chaque type de données. Ce problème s’appelle la sérialisation. On le rencontre lorsque l’on essaye de sauvegarder un objet sur le disque. Il faut donc avoir un moyen de transformer -tout objet- en chaîne de caractères et inversement. Cela peut sembler exagérée comme approche, mais de toute façon, dans un jeu vous devez pouvoir sauvegarder la partie en cours, et pour cela, il faut mettre en place la sérialisation pour chaque classe.