> Le Site du Zéro - Informatique

> Cours

> Tutoriels

> Programmation

> C++

> Programmez avec le langage C++

> [Théorie] Utilisez la bibliothèque standard

> Les conteneurs

> Lecture du tutoriel

Les conteneurs

Par

Mathieu Nebra (M@teo21) et Avatar

Matthieu Schaller (Nanoc)

Mise à jour : 27/05/2011

Difficulté : Intermédiaire

Durée d'étude : 1 jour

75 639 visites depuis 7 jours, dont 658 sur ce chapitre classé 5/786

Après cette brève introduction à la SL et aux éléments venus du C, il est temps de se plonger dans ce qui fait la force de la bibliothèque standard, la fameuse STL.
Ce sigle signifie Standard Template Library, que l'on pourrait traduire par "Bibliothèque standard basée sur des templates". Pour l'instant, vous ne savez pas ce que sont les templates, nous les découvrirons plus tard. Mais cela ne veut pas dire que vous n'avez pas le niveau requis ! Souvenez-vous de la classe string, vous avez appris à l'utiliser bien avant de savoir ce qu'était un objet. Il en sera de même ici, nous allons utiliser (beaucoup) de templates sans que vous ayez besoin d'en savoir plus à leur sujet.

L'élément de base autour duquel toute la STL est basée est le conteneur. Ce sont des objets permettant de stocker d'autres objets. D'ailleurs, vous en connaissez déjà un : le vector. Dans ce premier vrai chapitre sur la SL, vous allez découvrir qu'il existe d'autres sortes de conteneur pour tous les usages.

La vraie difficulté sera alors de faire son choix parmi tous ces conteneurs. Mais ne vous en faites pas, je serai là pour vous guider.

Retour en haut

Sommaire du chapitre :

Stocker des éléments
Les séquences et leurs adaptateurs
Les tables associatives
Choisir le bon conteneur
Q.C.M.

Retour en haut

Stocker des éléments

Vous l'avez vu tout au long de ce cours, stocker des objets dans d'autres objets est une opération très courante. Pensez par exemple aux collections hétérogènes lorsque nous avons vu le polymorphisme ou aux différents layouts dans Qt qui permettaient d'arranger les boutons et autres objets dans les widgets. Ces moyens de stockage s'appellent des conteneurs en langage informatique. Ce sont des objets qui peuvent contenir toute une série d'autres objets et qui proposent des méthodes permettant de les manipuler.
A priori, cette définition peut faire un peu peur. :euh:

Mais ce ne devrait pas être le cas. Cela fait bien longtemps que vous avez appris à utiliser les vector, le membre le plus connu de la STL. Voici un petit rappel basique pour ceux qui dormaient au fond de la salle de cours.

Code : C++ - Petit rappel sur vector

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

int main()
{
    vector<int> tab(5,4);    //Un tableau contenant 5 entiers dont la valeur est 4
    tab.pop_back();          //On supprime la dernière case du tableau.
    tab.push_back(6);        //On ajoute un 6 à la fin du tableau.
     
    for(int i(0); i<tab.size(); ++i)  //On utilise size() pour connaitre le nombre d'éléments dans le vector
        cout << tab[i] << endl;    //On utilise les crochets [] pour accéder aux éléments

    return 0;
}

Souvenez-vous, la première case d'un vector possède toujours l'indice 0.

Les vector sont des tableaux dynamiques. Autrement dit, les éléments qu'ils contiennent sont stockés les uns à coté des autres dans la mémoire. On pourrait se dire que c'est la seule manière de ranger des objets. En tout cas, c'est comme ça que la plupart des gens rangent leurs caves ou leurs étagères. Je suis sûr que vous faites de même.

Cette manière de ranger des livres sur une bibliothèque est sans doute la plus simple que l'on puisse imaginer. On peut accéder directement au 3^ème ou au 8^ème livre en tendant simplement le bras. Et comme on le voit sur l'illustration, ajouter des livres à droite de la collection est aussi très rapide : il suffit de les poser à côté des autres.

Mais pour d'autres opérations, cette méthode de rangement n'est pas forcément la meilleure. Si vous devez ajouter un livre au milieu de la collection (entre le vert et le rouge sur l'image), vous allez devoir décaler tous ceux situés à droite. Ici, ce n'est pas un gros travail. Mais imaginez que votre bibliothèque contienne des centaines de livres, tout décaler va prendre du temps. De même, ôter un livre au milieu de l'étagère va être coûteux, il va à nouveau falloir tout déplacer !

Ce ne sont pas les seules opérations difficiles à effectuer avec des livres. Trier les livres selon le nom de l'auteur est aussi quelque chose de long et difficile à réaliser. Si le tri avait été effectué au moment où les livres ont été posés pour la première fois, on n'aurait plus à le faire. Par contre, ajouter un livre dans la collection implique une réflexion préalable. Il faut, en effet, placer le bouquin au bon endroit pour que la collection reste triée.

Inverser l'ordre des livres est aussi un long travail dans une grande bibliothèque. Bref, ranger des objets n'est pas aussi simple qu'on pourrait le penser.

Vous l'avez sûrement constaté, toutes les bibliothèques rangent leurs livres les uns à cotés des autres. Mais les informaticiens sont des gens malins. Ils ont inventé d'autres méthodes de rangement. Nous allons les découvrir à partir de maintenant.

Il n'existe pas de "conteneur ultime", pour lequel toutes les opérations sont rapides. Il faut choisir la méthode de stockage adaptée à chaque problème en fonction des opérations que l'on veut privilégier. Je vous donnerai quelques astuces à la fin de ce chapitre.

Les deux catégories de conteneurs

Les différents conteneurs peuvent être partagés en deux catégories selon que les éléments sont classés à la suite les uns des autres ou pas. On parle alors de séquences et de conteneurs associatifs. Les vector sont bien évidemment des séquences puisque comme je vous l'ai dit, toutes les cases sont arrangées de manière contiguë dans la mémoire.
Nous allons voir tous ces conteneurs en détail. Pour l'instant, voici un tableau contenant tous les conteneurs de la STL selon leur catégorie.

Séquences	Conteneurs associatifs
vector deque list stack queue priority_queue	set multiset map multimap

Les noms des conteneurs sont en anglais et peut-être un peu bizarres, mais vous allez vite vous y faire. Et puis, les noms, bien que compliqués, décrivent plutôt bien à quoi ils servent.

Pour utiliser ces conteneurs, il faut inclure le fichier d'en-tête correspondant. Et là rien de bien sorcier. Pour utiliser des list, il faut ajouter la ligne #include <list> en haut de votre code. De même pour utiliser une map, c'est #include <map> en début de fichier qui fera votre bonheur.

Vous vous dites peut-être qu'apprendre à utiliser 15 conteneurs différents va demander beaucoup de travail. Je vous rassure tout de suite, ils sont quand même très similaires. Après tout, ils sont tous là pour stocker des objets ! Et comme les concepteurs de la STL sont sympas, ils ont donnés les mêmes noms aux méthodes communes de tous les conteneurs. :-°

Par exemple, la méthode size() renvoie la taille d'un vector, d'une list ou d'une map. Magique ! :magicien:

Quelques méthodes communes

Connaître la taille, c'est bien, mais on a parfois juste besoin de savoir si le conteneur est vide ou pas. Pour cela, il existe la méthode empty() qui renvoie true si le conteneur est vide et false sinon.

Code : C++

list<double> a; //Une liste de double
if(a.empty())
    cout << "La liste est vide." << endl;
else
    cout << "La liste n'est pas vide." << endl;

Vous ne savez pas encore ce que sont les listes ni comment et quand les utiliser mais je crois que vous n'avez pas eu de peine à comprendre cet extrait de code.

Une autre méthode bien pratique est celle qui permet de vider entièrement un conteneur. Il s'agit de clear(). Cela ne devrait pas surprendre les anglophones parmi vous !

Code : C++

1
2
3

set<string> a; //Un ensemble de chaines de caractères
//Quelques actions...
a.clear();  //Et on vide le tout !

A nouveau, rien de bien difficile, même avec une classe dont vous ne savez rien.

Finalement, il arrive qu'on ait besoin d'échanger le contenu de deux conteneurs de même type. Et plutôt que de devoir copier les éléments un à un à la main, les concepteurs de la STL ont créé une méthode swap() qui effectue cet échange de la manière la plus efficace possible.

Code : C++

vector<double> a(8,3.14);  //Un vector contenant 8 fois le nombre 3.14
vector<double> b(5,2.71);  //Un autre vector contenant 5 fois le nombre 2.71

a.swap(b); //On échange le contenu des deux tableaux. 
//b a maintenant une taille de 8 et a un taille de 5.

Comme nous le verrons dans la partie suivante du cours, vector<int> et vector<double> sont des types différents. On ne peut donc pas échanger le contenu de deux conteneurs dont les éléments sont de type différent.

Bon bon, moi ça m'a donné envie d'en savoir plus sur ces conteneurs. Tournons nous donc vers les séquences.

Retour en haut

Les séquences et leurs adaptateurs

Commençons avec notre vieil ami, le vector.

Les vector, encore et toujours

Si vous parlez la langue de Shakespeare, vous aurez certainement reconnu dans le nom de ces objets, le mot "vecteur", ces drôles d'objets mathématiques que l'on représente par des flèches. Eh bien, ils n'ont pas énormément de choses en commun ! o_O

Les vector ne sont vraiment pas adaptés pour effectuer des opérations mathématiques. Et en plus, ils n'en ont même pas les caractéristiques. On pourrait dire que c'est un mauvais choix de nom de la part des concepteurs de la STL. Mais bon, il est trop tard pour changer... Vous allez donc devoir vous habituer à ce faux-ami.

Comme vous l'avez vu depuis longtemps, les vector sont très simples à utiliser. On accède aux éléments via les crochets [], comme pour les tableaux statiques et l'ajout d'éléments à la fin se fait via la méthode push_back(). En réalité cette méthode est une opération commune à toutes les séquences. Il en est de même pour pop_back().

Il existe en plus de ça deux méthodes plus rarement utilisées permettant d'accéder au premier et au dernier élément d'un vector ou de toute autre séquence. Il s'agit des méthodes front() et back(). Mais comme il n'est que peu souvent utile d'accéder qu'au premier ou qu'au dernier élément, ces méthodes ne présentent que peu d'intérêt.

Finalement, il existe la méthode assign() permettant de remplir tous les éléments d'une séquence avec la même valeur.

Récapitulons tout ça dans un tableau.

Méthode

Description

Mini exemple

push_back()

Ajout d'un élément à la fin du tableau.

Code : C++

1 2	vector<int> a(5,3); //Un vector de 5 entiers valant 3 a.push_back(4); //Ajout d'une case avec le nombre 4 à la fin du tableau

pop_back()

Suppression de la dernière case du tableau.

Code : C++

1 2	vector<int> a(5,3); //Un vector de 5 entiers valant 3 a.pop_back(); //Suppression de la dernière case

front()

Accès à la première case du tableau.

Code : C++

1 2	vector<int> a(5,3); //Un vector de 5 entiers valant 3 a.front() = 4; //Le premier élément du tableau vaut maintenant 4

back()

Accès à la dernière case du tableau.

Code : C++

1 2	vector<int> a(5,3); //Un vector de 5 entiers valant 3 a.back() = 4; //Le dernier élément du tableau vaut maintenant 4

assign()

Modifie le contenu d'un tableau.

Code : C++

1 2	vector<int> a(5,3); //Un vector de 5 entiers valant 3 a.assign(6,2); //Le tableau contient maintenant 6 fois le nombre 2.

Si vous appelez assign(4,5) sur un vector de 8 éléments, seuls les 4 premiers seront modifiés. Le tableau sera donc plus petit.

En plus des crochets, il est possible d'accéder aux éléments d'un vector en utilisant des itérateurs. C'est ce que nous allons découvrir dans le prochain chapitre. :euh:

Pour l'instant, tournons-nous vers les autres types de séquences.

Les deque, ces drôles de tableaux

"deque" est en fait un acronyme (bizarre) pour double ended queue, ce qui donne en français, "queue à deux bouts". Derrière ce nom un peu original se cache un concept très simple : c'est un tableau auquel on peut ajouter des éléments aux deux extrémités.
Les vector proposent les méthodes push_back() et pop_back() pour manipuler ce qui se trouve à la fin du tableau. Modifier ce qui se trouve au début n'est pas possible. Les deque lèvent cette limitation en proposant des méthodes push_front() et pop_front(). Elles sont aussi très simples à utiliser. La seule difficulté vient du fait que le premier élément possède toujours l'indice 0. Les indices sont donc décalés à chaque ajout en début de deque.

Code : C++ - Ajout d'éléments au début d'une deque

#include <deque> //Ne pas oublier !
#include <iostream>
using namespace std;

int main()
{ 
    deque<int> d(4,5); //Une deque de 4 entiers valant 5
    
    d.push_front(2);   //On ajoute le nombre 2 au début
    d.push_back(8);    //Et le nombre 8 à la fin

    for(int i(0); i<d.size(); ++i)
        cout << d[i] << " ";    //Affiche 2 5 5 5 5 8

    return 0;
}

Et pour bien comprendre le tout, je vous propose un petit schéma :

Même si l'on ajoute des éléments au début d'une deque, l'indice du premier élément est toujours le 0. Je vous l'ai déjà dit, mais je préfère vous éviter des soucis avec votre compilateur.

Bon, je crois que vous avez compris.

Si vous avez survécu aux premiers chapitres de ce cours, tout ça doit vous sembler bien facile.

Les stack, une histoire de pile

La classe stack est la première structure de donnée un peu spéciale que vous rencontrez. C'est un conteneur qui n'autorise l'accès qu'au dernier élément ajouté. o_O

En fait, il n'y a que 3 opérations autorisées :

Ajouter un élément.
Consulter le dernier élément ajouté.
Supprimer le dernier élément ajouté.

Cela se fait via les trois méthodes push(), top() et pop().

Je ne comprends pas bien l'intérêt d'un tel stockage !

En termes techniques, on parle de structure LIFO. Le dernier élément ajouté est le premier à pouvoir être ôté. Comme sur une pile d'assiette ! Vous ne pouvez accéder qu'à la dernière assiette posée sur la pile.

Cela permet d'effectuer des traitements sur les données en ordre inverse de leur arrivée dans la pile. Comme pour les assiettes. La dernière assiette sale sur la pile est la première à être lavée. Alors que celle arrivée en premier (et qui est donc tout en-bas de la pile) sera traitée en dernier.

Un exemple plus informatique serait la gestion d'un stock. On ajoute le nombre d'articles vendus chaque mois à notre pile et on consulte les trois derniers ajouts sans s'occuper du reste pour créer le bilan trimestriel.

Code : C++ - Utilisation d'une pile

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

int main()
{
    stack<int> pile;    //Une pile vide
    pile.push(3);       //On ajoute le nombre 3 à la pile
    pile.push(4);
    pile.push(5);

    cout << pile.top() << endl; //On consulte le sommet de la pile (le nombre 5)
 
    pile.pop();        //On supprime le dernier élément ajouté (le nombre 5)

    cout << pile.top() << endl; //On consulte le sommet de la pile (le nombre 4)

    return 0;
}

Peut-être que vous aurez un jour besoin de ce genre de structures. Repensez alors à ce chapitre !

Les queue, une histoire de file

Les files sont très similaires aux piles (et pas que pour leurs noms !). En termes techniques, on parle de structure FIFO. La différence ici est que l'on ne peut accéder qu'au premier élément ajouté. Exactement comme dans une file de supermarché. Les gens attendent les uns derrière les autres et la caissière traite les courses de la première personne arrivée. Quand elle a terminé, elle s'occupe de la deuxième et ainsi de suite.

Le fonctionnement est identique à celui des piles. La seule différence est qu'on utilise front() pour accéder à ce qui se trouve à l'avant de la file au lieu de top().

Les priority_queue, la fin de l'égalité

Les priority_queue sont des queue qui ordonnent leurs éléments. Un peu comme si les clients avec les plus gros paquets de course passaient avant les gens avec seulement un ou deux articles.
Les méthodes sont exactement les mêmes que dans le cas des files simples.

Code : C++ - Utilisation d'une priority_queue

#include <queue> //Attention ! queue et priority_queue sont définies dans le même fichier
#include <iostream>
using namespace std;

int main()
{
    priority_queue<int> file;
    file.push(5);
    file.push(8);
    file.push(3);

    cout << file.top() << endl;  //Affiche le plus grand des éléments insérés (le nombre 8)

    return 0;
}

Les objets stockés dans une priority_queue doivent avoir un opérateur de comparaison (<) surchargé afin de pouvoir être classés !

On utilise par exemple ce genre de structure pour gérer des évènements selon leur priorité. Pensez aux signaux et slots de Qt. On pourrait leur affecter une valeur pour traiter les évènements dans un certain ordre.

Les list, à voir plus tard

Finalement, le dernier conteneur sous forme de séquence est la liste. Cependant, pour les utiliser de manière efficace il faut savoir manipuler les itérateurs, ce que nous apprendrons à faire dans le prochain chapitre. De toute façon, je crois que je vous ai assez parlé de séquences pour le moment. Il est temps de parler d'une tout autre manière de ranger des objets.

Retour en haut

Les tables associatives

Jusqu'à maintenant, vous êtes habitués à accéder aux éléments d'un conteneur en utilisant les crochets []. Dans un vector ou une deque, les éléments sont accessibles via leur index, un nombre entier positif. Ce n'est pas toujours très pratique. Imaginez un dictionnaire, vous n'avez pas besoin de savoir que "banane" est le 832^ème mot pour accéder à sa définition. Les tables associatives sont des structures de données qui autorisent l'emploi de n'importe quel type comme index.
En termes techniques, on dit qu'une map est une table associative permettant de stocker des paires clé-valeur.

Concrètement, cela veut dire que vous pouvez créer un conteneur où les indices sont des string par exemple. Comme le type des indices peut varier, il faut l'indiquer lors de la déclaration de l'objet :

Code : C++

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

map<string, int> a;

Ce code déclare une table associative qui stocke des entiers mais dont les indices sont des chaînes de caractères. On peut alors accéder à un élément via les crochets [] comme ceci :

Code : C++

1	a["salut"] = 3; //La case "salut" de la map vaut maintenant 3

Si la case n'existe pas, elle est automatiquement créée.
On peut utiliser ce que l'on veut comme clé. La seule condition est que l'objet utilisé possède un opérateur de comparaison "plus-petit-que" (<).

Avec ce nouvel outil, on peut très facilement compter le nombre d'occurrences d'un mot dans un fichier. Essayez par vous-même c'est un très bon exercice. Le principe est simple. On parcourt le fichier et pour chaque mot on incrémente la case correspondante dans la table associative. Voici ma solution :

Code : C++

#include <map>
#include <string>
#include <fstream>
using namespace std;

int main()
{
    ifstream fichier("texte.txt");
    string mot;
    map<string, int> occurrences;
    while(fichier >> mot)   //On lit le fichier mot par mot
    {
         ++occurrences[mot]; //On incrémente le compteur pour le mot lu
    }
    cout << "Le mot 'banane' est present " << occurrences["banane"] << " fois dans le fichier" << endl; 
    return 0;
}

On peut difficilement faire plus court ! Pour le moment en tout cas.

Les map ont un autre gros point fort : les éléments sont triés selon leur clé. Donc si l'on parcourt une map du début à la fin, on parcourt les clés de la plus petite à la plus grande. Le problème, c'est que pour parcourir une table associative du début à la fin, il faut utiliser les itérateurs et donc attendre le prochain chapitre.

Les autres tables associatives

Les autres tables sont des variations de la map. Le principe de fonctionnement de ces conteneurs est très similaire, mais à nouveau, il nous faut utiliser les itérateurs pour exploiter la pleine puissance de ces structures de données. Je sens que vous allez bientôt avoir envie d'en savoir plus sur ces drôles de bêtes...
En attendant, je vais quand même vous en dire quelques mots sur ces autres structures de données. :soleil:

Les set sont utilisés pour représenter les ensembles. On peut insérer des objets dans l'ensemble et y accéder via une méthode de recherche. Par contre, il n'est pas possible d'y accéder via les crochets. En fait, c'est comme si on avait une map où les clés et les éléments étaient confondus.
Les multiset et multimap sont des copies des set et map où chaque clé peut exister en plusieurs exemplaires.

On reparlera un peu de tout cela, mais ces trois derniers conteneurs sont quand même d'un usage plus rare.

Retour en haut

Choisir le bon conteneur

La principale difficulté avec la STL est de choisir le bon conteneur ! Comme dans l'exemple de la bibliothèque de livres, faire le mauvais choix peut avoir des conséquences désastreuses en terme de performances. Et puis, tous les conteneurs n'offrent pas les mêmes services. Avez-vous besoin d'accéder aux éléments directement ? Ou préférez-vous les trier et n'accéder qu'à l'élément avec la plus grande priorité ? C'est à ce genre de questions qu'il faut répondre pour faire le bon choix. Et ce n'est pas facile !

Heureusement, je vais vous aider via un schéma. En suivant les flèches et en répondant aux questions posées dans les losanges, on tombe sur le conteneur le plus approprié.

Avec ça, pas moyen de se tromper !

Il est évidemment inutile d'apprendre ce schéma par cœur. Sachez simplement qu'il existe et où le trouver.

Au final, on utilise souvent des vector. Cet outil de base permet de résoudre bien des problèmes sans trop se poser de questions. Et on sort une map quand on a besoin d'utiliser autre chose que des entiers pour indexer les éléments.
Utiliser ce schéma c'est le niveau supérieur, mais choisir le bon conteneur peut devenir essentiel quand on cherche à créer un programme vraiment optimisé.

Retour en haut

Bon, récapitulons. Vous savez maintenant choisir le conteneur adapté à vos besoins et vous savez le remplir. C'est bien, mais vous en conviendrez on ne va pas très loin avec juste ces notions.

La prochaine étape est bien sûr d'apprendre à parcourir ces conteneurs pour utiliser les objets qui y sont stockés. Ça vous tente ? Parfait ! Alors ne quittez pas votre clavier, c'est ce que je vais vous présenter dans le chapitre suivant.