• 50 heures
  • Difficile

Ce cours est visible gratuitement en ligne.

Ce cours existe en livre papier.

course.header.alt.is_certifying

Vous pouvez être accompagné et mentoré par un professeur particulier par visioconférence sur ce cours.

J'ai tout compris !

Mis à jour le 30/09/2019

Utilisez les conteneurs

Connectez-vous ou inscrivez-vous gratuitement pour bénéficier de toutes les fonctionnalités de ce cours !

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, ce 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 de toute la STL est le conteneur. Un conteneur est un objet 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 conteneurs 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.

Stockez 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. En jargon informatique, ces moyens de stockage s'appellent des conteneurs. 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.
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.

#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 connaître le nombre d'éléments dans le vector
        cout << tab[i] << endl;      //On utilise les crochets [] pour accéder  aux éléments

    return 0;
}

Les vectorsont 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 cela 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 troisième ou au huitième livre en tendant simplement le bras.

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, 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 prendra du temps. De même, ôter un livre au milieu de l'étagère sera coûteux, il va falloir à nouveau 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.

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 non. On parle dans un cas de séquences et dans l'autre de conteneurs associatifs. Les vectorsont bien évidemment des séquences puisque, comme je vous l'ai dit, toutes les cases sont rangées de manière contiguë dans la mémoire.
Nous allons voir tous ces conteneurs en détail. Pour l'instant, voici une liste de tous les conteneurs de la STL triés suivant leur catégorie.

  • Séquences :

    • vector

    • deque

    • list

    • stack

    • queue

    • priority_queue

  • Conteneurs associatifs :

    • 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.

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é les mêmes noms aux méthodes communes de tous les conteneurs.

Par exemple, la méthodesize()renvoie la taille d'unvector, d'unelistou d'unemap. Magique !

Quelques méthodes communes

Connaître la taille, c'est bien mais on a parfois simplement besoin de savoir si le conteneur est vide ou pas. Pour cela, il existe la méthodeempty()qui renvoietruesi le conteneur est vide etfalsesinon.

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 declear(). Cela ne devrait pas surprendre les anglophones parmi vous !

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

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

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

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 une taille de 5.

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

Les séquences et leurs adaptateurs

Commençons avec notre vieil ami, levector.

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 !
Les vectorne 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 en changer… Vous allez donc devoir vous habituer à ce faux-ami.

Comme vous l'avez vu depuis longtemps, les vectorsont 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 va de même pour pop_back().

Il existe en plus de cela deux méthodes plus rarement utilisées permettant d'accéder au premier et au dernier élément d'un vectorou de toute autre séquence. Il s'agit des méthodes front()et back(). Mais comme il n'est que rarement utile d'accéder seulement au premier ou au dernier élément, ces méthodes ne présentent guère 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 cela dans un tableau.

Méthode

Description

push_back()

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

pop_back()

Suppression de la dernière case du tableau.

front()

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

back()

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

assign()

Modification du contenu d'un tableau.

En plus des crochets, il est possible d'accéder aux éléments d'unvectoren utilisant des itérateurs. C'est ce que nous allons découvrir dans le prochain chapitre.
Pour l'instant, tournons-nous vers les autres types de séquences.

Les deque, ces drôles de tableaux

dequeest 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 vectorproposent 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 dequelè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.

#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 :

Fonctionnement d'une deque
Fonctionnement d'une deque

Bon, je crois que vous avez compris. Si vous avez survécu aux premiers chapitres de ce cours, tout cela doit vous sembler bien facile.

Les stack, une histoire de pile

La classe stackest la première structure de données un peu spéciale que vous rencontrez. C'est un conteneur qui n'autorise l'accès qu'au dernier élément ajouté.
En fait, il n'y a que 3 opérations autorisées :

  1. Ajouter un élément ;

  2. Consulter le dernier élément ajouté ;

  3. Supprimer le dernier élément ajouté.

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

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

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

Une pile d'éléments (stack)

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 à la pile le nombre d'articles vendus chaque mois et, pour créer le bilan trimestriel, on consulte les trois derniers ajouts sans s'occuper du reste.

#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 aurez-vous besoin de ce genre de structures un jour. 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 (First In First Out). 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 (figure suivante).

Une file (queue)
Une file (queue)

Le fonctionnement est analogue à 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_queuesont des queuequi ordonnent leurs éléments. Un peu comme si les clients avec les plus gros paquets de courses 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.

#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;
}

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 au 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.

Les tables associatives

Jusqu'à maintenant, vous êtes habitués à accéder aux éléments d'un conteneur en utilisant les crochets[]. Dans un vectorou 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 mapest une table associative permettant de stocker des paires clé-valeur.

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

#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 :

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 :

#include <map>
#include <string>
#include <fstream>
#include <iostream>
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' existe " << occurrences["banane"] << " fois dans le fichier" << endl; 
    return 0;
}

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

Lesmapont un autre gros point fort : les éléments sont triés selon leur clé. Donc si l'on parcourt unemapdu 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.

  • Les setsont 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 unemapoù les clés et les éléments étaient confondus.

  • Les multisetet multimapsont des copies des setet mapoù 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.

Choisissez 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 termes 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é.

Choisir le bon conteneur
Choisir le bon conteneur

Avec cela, 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 se poser trop de questions. Et on sort une mapquand 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é.

En résumé

  • La STL propose de nombreux conteneurs. Ils sont tous optimisés pour des usages différents.

  • Les dequeet vectorpermettent de stocker des objets côte-à-côte dans la mémoire.

  • Les mapet setsont à utiliser si l'on souhaite indexer les éléments contenus avec autre chose que des entiers.

  • Choisir le bon conteneur est une tâche difficile. Sachez que vectorest le plus fréquemment utilisé. Vous pourrez toujours revenir sur votre décision par la suite si vous avez besoin d'un conteneur plus adapté.

Exemple de certificat de réussite
Exemple de certificat de réussite