Les Conteneurs de la STL

Introduction du cours

Il est nécessaire de connaître le contenu de la première partie et le début de la deuxième partie (notions de bases sur les classes) du cours de C++ de M@teo21/Nanoc. Ce tutoriel étant un (gros) complément au chapitre sur les tableaux dynamiques : std::vector.

Salut les zéros ! :)

Vous avez découvert le conteneur std::vector sur le tutoriel de Nanoc et vous l'avez trouvé super pratique.
Mais comme dit dans le dernier chapitre du tutoriel C++ de M@teo21, il existe plein d'autres classes que le std::vector pour créer des tableaux ! o_O
Ces autres classes sont appellées "conteneurs" car elles ont toutes pour but de contenir des éléments. (Étonnant n'est-ce pas ?)

Comme indiqué sur ce schéma, en fonction de l'utilisation à laquelle votre tableau est utilisé, il existera peut-être une classe qui sera plus optimisée pour cette utilisation, ou qui vous fournira des fonctions plus appropriées.
C'est parti ! Laissez-moi vous présenter ces conteneurs ! :D

La découverte par l'exempleUn groupe de personnages

Imaginez un jeu où l'utilisateur peut créer des personnages ayant chacun un nom.
Comment coder cet exemple avec un tableau classique ou un std::vector ?
Supposons que nous utilisons la même classe Personnage du tutoriel de Nanoc et M@teo21 (Moi je la trouve très sympatique cette classe :p ). Au stade où les personnages ont un nom et sont capables de se présenter.

class Personnage { public: Personnage(std::string nom); void recevoirDegats(int degats); void boirePotionDeVie(int pvAjoutes); void coupDePoing(Personnage& cible); std::string getNom() const; void sePresenter() const; protected: int m_vie; std::string m_nom; }; void Personnage::sePresenter() const { cout << "Bonjour, je m'appelle " << m_nom << "." << endl; cout << "J'ai encore " << m_vie << " points de vie." << endl; }

L'utilisateur pourra créer des personnages par leur nom dans un std::vector :

int main(int argc, char ** argv) { string nom; vector<Personnage> groupe; while(1) { cout << endl << "Entrez le nom du Personnage que vous voulez creer" << endl; cin >> nom; groupe.push_back(nom); cout << "Voici maintenant votre groupe de personnages : " << endl; for(int i = 0;i<groupe.size();i++) { cout << "<Perso numero " << i << ">" << endl; groupe[i].sePresenter(); } } system("PAUSE"); return 0; }

Il pourrait alors créer les personnages du nom qu'il veut, comme Bob, ou Michael_Jordan. :p

Appel des personnages

Imaginons maintenant qu'après une longue série de combat, l'utilisateur veut savoir combien de vie il reste à Michael_Jordan.
On peut créer une fonction affichant tous les personnages et il trouvera bien ce qu'il veut dedans. Mais évidemment ce n'est pas une bonne méthode si le groupe contient 500 personnages (j'envisage de grandes armées moi :p ).
Comme chaque Personnage a un numéro dans le tableau (un indice), l'utilisateur pourrait retenir le numéro de Michael_Jordan et nous créerions une fonction du style :

void presentation(const vector<Personnage> & groupe, int numeroDuPerso) { groupe[numeroDuPerso].sePresenter(); }

Ayant retenu que Michael Jordan avait le numéro 23 dans le groupe, on écrirait dans le main presentation(groupe,23);
Mais évidemment l'utilisateur ne pourra pas se rappeler des indices de tous les Personnages... Il ne connaît juste que leur nom. Alors pourquoi ne pas surcharger la fonction presentation prenant comme paramètre un std::string ?

Le problème est là : à quel indice est placé Michael_Jordan ? Il faudra donc rechercher ce Personnage dans le groupe :

void presentation(const vector<Personnage> & groupe, string nom) { for(int i = 0;i < groupe.size();i++) { if(groupe[i].getNom() == nom) { groupe[i].sePresenter(); break; } } if(i == groupe.size()) cout << "Il n'existe pas de Personnage avec ce nom" << endl; }

Cette technique fonctionne bien entendu mais si le tableau a 500 personnages... La performance ne sera pas géniale : une boucle de 500 itérations maximum pour juste trouver un Personnage, ce n'est pas utile. Pour info, la complexité de cet algorithme est en O(n).

Voilà un exemple où le std::vector n'est pas adapté à la situation :) , la STL fournit une classe de tableau associatif prévue pour des cas comme ça !
Attention voici ... std::map !

Le tableau associatif de la STL : std::mapCréer un std::map

Nous allons créer un autre tableau qui permettra de savoir à quel indice a été placé quel nom. Imaginez cela comme un tableau classique où les indices sont remplacés par des std::string :

Clef

Clef

$\Rightarrow$

Valeur associée

Bob

$\Rightarrow$

0

Georges

$\Rightarrow$

1

...

$\Rightarrow$

...

Michael_Jordan

$\Rightarrow$

23

Nous utiliserons alors ce tableau pour connaître l'indice auquel le personnage correspondant a été placé afin d'y accéder.
Je vais tout de suite vous montrer comment utiliser std::map.
Bien entendu il faudra inclure :

#include <map>

La création du tableau se fera comme ceci : :)

map<string, int> indices;

Observons les paramètres template de std::map :

• La première classe à indiquer est appelée la classe de clef (en anglais key value), c'est la classe qui est utilisée pour accéder aux éléments. Pour chaque clef correspondra une et une seule valeur associée.

• La deuxième classe sera la classe de valeur associée (en anglais mapped value, d'où le nom). C'est la classe des éléments contenus dans le tableau.

En l'occurence ici nous utilisons une std::string pour obtenir un int qui est l'indice auquel le Personnage correspondant a été placé.

Ajout et accès à une valeur associée d'une std::map

L'avantage maintenant est que les éléments sont accessibles par leur nom. Ajouter un élément est très facile ! :p
Voyez par vous-même.
En dessous du push_back j'écrirai cette ligne pour pouvoir accéder à l'élément créé par son nom :

indices[nom] = groupe.size() - 1;

(Après l'ajout, le Personnage a été placé à l'indice size() - 1)

Moi, quand j'ai vu ça, j'ai trouvé ça très logique comme écriture

Citation : Moi

La valeur associée à la clef "nom" du tableau "indices" est égale à "groupe.size() -1"

ou encore :

Citation : Moi

"indices" à "nom" = "groupe.size() - 1"

Cela s'utilise comme un tableau en C !

double tab[5]; //Création d'un tableau C tab[3] = 25.1101992; //Ajout d'une valeur

Maintenant je peux utiliser ma std::map pour coder la surcharge de la fonction presentation que j'avais écrite :

void presentation(vector<Personnage> & tab, map<Personnage*> & indices, string nom) { int indice = indices[nom]; tab[indice].sePresenter(); }

Simple n'est-ce pas ? :D
L'avantage des conteneurs STL est qu'ils s'utilisent tous un peu de la même manière, on accède à un élément d'un std::map de la même manière qu'avec un std::vector : avec l'opérateur [].

Néanmoins, pour std::map, il existe une différence dans le comportement de cet opérateur, je vous en parlerai un peu plus tard après un exemple. ;)

La complexité de l'opérateur [] est de O(log2 n), contrairement à notre recherche dans un vector qui était de O(n).
Pour des grands tableaux le changement sera très efficace ! :D
Cependant l'accès à une valeur dans un tableau par un indice est le plus rapide possible : O(1). Si vous voulez utiliser un accès rapide aux éléments, utilisez une table de hachage. Celles-ci ont une complexité de O(1) en moyenne, même si le pire des cas est en O(n). Pour plus d'infos : lisez cette page sur wikipédia ou bien entendu les tutoriels de zéros traitant de ce sujet.

Vous pourriez très bien créer une autre std::map qui permettra par exemple d'appeler un Personnage par son numéro de téléphone !

map<int,int> annuaire; // Le premier int étant le numéro, le deuxième étant l'indice annuaire[027336572] = 23; //Waw, le numéro de téléphone de Michael Jordan o_O en base 8 ! Utiliser une std::map en tant que conteneur

std::map est un conteneur me direz-vous, alors à quoi sert de garder encore un std::vector ?
Bien entendu, vous ne pourrez plus accéder aux éléments par un indice car justement on ne sait pas à quel indice notre élément recherché a été placé.
Alors, comment ferait-on ? :p

Been, comme ceci ? En ajoutant les éléments comme cela ?

std::map<string, Personnage> groupe; groupe["Jean-Claude"] = Personnage("Jean-Claude");

Bien vu mais il faut bien se mettre en tête que ce code fera ceci :

1. Il créera un Personnage temporaire appelé Jean-Claude via le constructeur surchargé avec std::string.

2. Il essaiera d'accéder à l'élément "Jean-Claude" du groupe via l'opérateur []. Deux cas se présentent alors :

   • L'élément existe déjà, il renvoie une référence vers cet élément.

   • L'élément n'existe pas, il en crée un en utilisant le constructeur par défaut et renvoie une référence vers cet élément.

3. L'opérateur = est appelé, les données du personnage temporaire Jean-Claude sont copiées dans celles du Personnage du tableau qui est l'élément qui a été renvoyé par l'opérateur [].

4. Le personnage Jean-Claude temporaire sera détruit à la fin du bloc.

Deux Personnages seront alors créés alors qu'un seul aurait suffit.
(D'ailleurs si vous mettez quelques cout dans les constructeurs par défaut, de copie et avec paramètre(s) vous verrez qu'il crée beaucoup plus que deux Personnages...).
Cependant vous pouvez utiliser cette méthode si créer beaucoup de Personnages ne vous dérange pas. ;)

Je trouve que cette manière de faire pour ce code convient très bien à la phrase que j'avais dite plus haut :

Citation

la valeur associée à la clef "Jean-Claude" du tableau "groupe" est égale à "Personnage("Jean-Claude")"

Effet : peu importe s'il existait déjà une valeur associée pour cette clef, après cette instruction, la valeur associée sera "Personnage("Jean-Claude")". A nouveau, comme un tableau en C :

double tab[5]; //Création d'un tableau C tab[3] = 25.1101992; //Ajout d'une valeur tab[3] = 24.1101996; //Modification de la valeur

Comme vous pouvez le voir, l'opérateur [] crée un objet avec le constructeur par défaut si aucune valeur n'est associée à la clef entrée, ainsi écrire groupe["Jean-Claude"]; suffit pour créer un élément.
Contrairement à l'opérateur [] de std::vector qui lui vous aurait simplement fait bugger le programme pour cause d'accès à une case de mémoire non autorisée (essaiez de faire vect[5] avec un vecteur long de 3 si vous ne voyez pas ce que je veux dire :p ). Par contre la fonction membre map::at fonctionne exactement de la même manière qu'avec std::vector. ;)

J'utiliserai alors un std::map<string, Personnage*> afin de contenir mes éléments, que je créerai dynamiquement, un Personnage de créé avec new et ensuite je garde un pointeur de celui-ci dans le tableau :p (Un peu à la Java ^^).
Voici alors comment j'ajouterai Bob à mon tableau de Personnage :

std::map<string, Personnage*> groupe; groupe["Bob"] = new Personnage("Bob");

Ma fonction presentation devient alors toute simple :

void presentation(map<Personnage*> &...