STL containers

To translate this course in your native langage:

In Chrome: right-click anywhere on the page and select “Translate to…”
Or use this language selector:

Les mots colorés en anglais représentent des mots-clés de la norme du langage C++. Ils sont conservés à l’identique lors de l’utilisation d’une traduction automatique avec Google Translate. Exemple : l’héritage (inheritance) est un principe fondamental de C++.

Ce chapitre présente les principaux conteneurs de données disponibles en C++. Ils remplacent avantageusement les tableaux hérités du langage C.

À partir de maintenant, vous devez les utiliser dans tous nos exercices. Les tableaux sont désormais INTERDITS.

Jusqu’à présent, nous avons développé nous-mêmes les fonctionnalités nécessaires à la classe V10 dans les chapitres précédents. La bibliothèque standard fournit des conteneurs qui prennent déjà en charge une grande partie de ce travail. Ainsi maintenant vous pourrez/devrez simplement écrire :

using V10 = std::array<int, 10>;
V10 v;
cout << v.size();
cout << v[3];

Ainsi les conteneurs ont été conçus pour offrir de bonnes performances tout en améliorant la sûreté et la lisibilité du code. Leur conception, leur standardisation et leurs nombreuses années d’utilisation permettent aujourd’hui de s’appuyer sur des composants robustes et largement éprouvés. Nous étudions dans la suite :

Les array : container de taille fixe, accès aux éléments en O(1), taille en mémoire optimale

Les vector : dimension dynamique, accès aux éléments en O(1)

Les map : association par clé–valeur ordonnée et accès aux éléments en O(log n))

La présentation est synthétique et convient à des étudiants de master expérimentés.

Array

Rôle

Un std::array contient un nombre fixe d’éléments de même type.

Pourquoi utiliser un std::array plutôt qu’un tableau int T[10] ?

Les arrays sont des objets, ils peuvent donc être passés par copie ou par référence.

La fonction membre at(i) permet de vérifier la validité de l’indice avant d’accéder au i-ème élément.

Les algorithmes de la STL peuvent être appliqués sur ces objets : tri, recherche…

Pour instancier un array, vous devez :

Ecrire une directive #include <array> en début de programme

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

Présentation rapide

Opérations sur les arrays
Type	Exemple	Remarque
Initialisation	array<int, 3> a = {1, 2, 3};
Initialisation	array<int, 3> a {1, 2, 3
Initialisation	array<int, 3> a({1, 2, 3});
Initialisation	array<int, 3> a = {};	Avec initialisation des valeurs : les numériques sont mis à zéro !
Initialisation	array<int, 3> a;	Sans initialisation
Méthode	a.fill(value)	Initialise tous les éléments à la valeur donnée
Méthode	a.at(i)	Retourne une référence vers le i-ème élément AVEC bound-checking
Méthode	a[i]	Retourne une référence vers le i-ème élément SANS bound-checking
Méthode	a.size()	Retourne le nombre d’éléments
Méthode	a.swap(b)	Permute les éléments des deux arrays

Quizzz

La fonction length retourne le nombre d’éléments.
La syntaxe at(i) ou [i] sont identiques en tout point.
La syntaxe : array<int, 3> a {1, 2, 3}; est valide.
Il est possible d’instancier un array sans initialiser ses valeurs.
Quel est le nom de la fonction initialisant l’ensemble des éléments à une valeur donnée.

Vector

Rôle

Un std::vector représente une liste de taille dynamique d’éléments de même type.

Pourquoi utiliser un std::vector :

Classe modèle pouvant s’adapter à tout type.

Les vectors sont des objets, ils peuvent donc être passés par copie ou par référence.

Pas de limite de taille.

Les algorithmes de la STL peuvent être appliqués sur ces objets : tri, recherche…

La fonction membre at(i) permet de vérifier la validité de l’indice avant d’accéder au i-ème élément

Gestion automatisée de la mémoire : allocation, libération.

Présentation rapide

Pour instancier un objet vector, vous devez :

Mettre une directive #include <vector> en début de programme

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

Opérations sur les vectors
Type	Exemple
Initialisation	vector<int> L;	Vector vide ; pas d’éléments dans la liste
Initialisation	vector<int> L = {};	Idem
Initialisation	vector<int> L = {1,2,3,4};
Initialisation	vector<int> L( {1,2,3,4} );
Initialisation	vector<int> L( );	Confusion => Déclaration d’une fonction retournant un vector
Initialisation	vector<int> v1(10);	Taille fixée à 10 éléments + INITIALISATION à zéro
Initialisation	vector<int> v1(10,5);	Taille fixée à 10 éléments initialisés à la valeur 5
Initialisation	vector<int> v2(v1);	Initialisation par copie
Méthode,	L.fill(value)	Initialise tous les éléments à la valeur donnée
Méthode,	L.at(i)	Retourne une référence vers le i-ème élément AVEC bound-checking
Méthode,	L[i]	Retourne une référence vers le i-ème élément SANS bound-checking
Méthode,	L.size()	Retourne le nombre d’éléments
Méthode,	L.empty()	Indique si la liste est vide
Méthode,	L.clear()	Retire et détruit tous les éléments de la liste
Méthode,	L.resize(n)	Force le nombre d’éléments à n
Méthode,	L.push_back(v)	Insère une copie de l’élément v en fin de liste en O(1)
Méthode,	L.pop_back()	Retire et détruit le dernier élément de la liste en O(1)
Méthode,	L.back()	Retourne une référence vers le dernier élément de la liste
Méthode,	L.erase(iter)	Supprime l’élément désigné par l’itérateur iter
Méthode,	L.insert(iter,v)	Insère une copie de l’élément v à la position désignée par l’itérateur iter

Avertissement

Tous les éléments dans une liste de type vector sont de même type. Ainsi, si vous stockez un double dans une liste de type vector<int>, alors il sera implicitement converti en entier.

La fonction resize(n) fixe le nombre d’éléments :

Si n < size() alors les derniers éléments sont détruits.

Si n = size() aucun effet.

Si n > size() il y a création de nouveaux éléments par appel au constructeur par défaut.

Note

Certaines méthodes des vectors portent des noms similaires ce qui prête à confusion. On pense ici aux fonctions membres resize() et reserve() ainsi que size() et capacity(). Une clarification s’impose ! Un objet vector alloue une zone mémoire servant de buffer. La mécanique interne du vector fait en sorte que la taille de ce buffer soit supérieure au nombre d’éléments stockés. La méthode reserve() permet de fixer la taille de ce buffer et capacity() retourne sa taille. Par exemple, si vous savez que 10 000 000 d’éléments vont être stockés, alors, il peut être utile de fixer directement la taille du buffer à cette grandeur ce qui évite de multiples redimensionnements et permet de gagner en efficacité. Ainsi, ces deux fonctions permettent une optimisation fine des objets vector.

Quizzz

La fonction pop_back() insère un élément en fin.
Les syntaxe at(i) et [i] sont identiques en tout point.
La fonction size() retourne le nombre d’éléments.
La syntaxe : vector<int> v(10) crée une liste et initialise ses éléments à la valeur 10.
Quel est le nom de la fonction initialisant l’ensemble des éléments à une valeur donnée ?
Quel est le nom de la fonction retirant tous les éléments ?
Quel est le nom de la fonction indiquant si la liste est vide ?
Quel est le nom de la fonction permettant de fixer le nombre d’éléments dans la liste ?

Map

Un std::map représente un dictionnaire permettant d’associer une valeur (value) à une clé (key) pouvant être un entier comme un string !

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 un vector : O(log n) versus O(1). Il y a donc un surcoût à cette souplesse.

Présentation rapide

Opérations sur les maps
Type	Exemple
Initialisation	map<string,int> m = { {"one",1}, {"two",2} };
Affectation	m["trois"] = 3;	Associe la valeur 3 à la clé "trois"
Opérateur[]	cout << m["deux"]	Retourne la valeur associée à la clé "deux"
Méthode	m.count(key) > 0	Teste si la clé existe dans ce dictionnaire
Méthode,	m.erase("trois")	Supprime la paire clé/valeur correspondant à la clé "trois"
Méthode,	m.size()	Nombre de paires clé/valeur dans le dictionnaire

Parcours

Avertissement

Les présentations ci-dessous sont valables pour un array comme pour un vector

En mode read-only

#include <iostream>
#include <array>

int main()
{
        std::array<int, 3> a = {1, 2, 3};
        for (int v : a)  std::cout << v << " ";
        for (int v : a)  v = 4;   // warning: v is a local copy - no update of a
        for (int v : a)  std::cout << v << " ";
}

>> 1 2 3
>> 1 2 3

En mode read-write

#include <iostream>
#include <array>

int main()
{
        std::array<int, 3> a = {1, 2, 3};
        for (int v  : a)  std::cout << v << " ";
        for (int &v : a)  v = 4;   // this time v is a reference
        for (int v  : a)  std::cout << v << " ";
}

>> 1 2 3
>> 4 4 4

Avertissement

Un vector ne peut gérer le retrait ou l’ajout d’élément durant un parcours.

Map

Pour les dictionnaires, il y a une légère différence car la boucle for retourne un objet dont :

La variable first correspond à la clé

La variable second correspond à la valeur

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

int main()
{
        map<string,int> myMap = {{"one",1}, {"two",2}, {"three",3}};

        for (auto pair : myMap)
                cout << pair.first << " => " << pair.second << endl;
}

>> one => 1
>> three => 3
>> two => 2

Rule of Zero

Pour gérer des données, il est recommandé d’utiliser les conteneurs de la STL. Plusieurs raisons justifient ce choix :

Les opérations de copie sont déjà implémentées.

Le conteneur vector adapte dynamiquement sa taille en fonction des besoins.

La libération de la mémoire est gérée automatiquement.

Il ne faut pas sous-estimer la complexité de la gestion des ressources mémoire. Prenons l’exemple de deux objets M1 et M2 de type Matrix :

M1 = M2;        // copy a matrix object into an existing matrix object

Cette opération, qui paraît simple, soulève en réalité plusieurs difficultés :

Rien ne garantit que les deux matrices possèdent les mêmes dimensions.

Il faut penser à libérer correctement les données précédemment contenues dans M1.

Il ne faut pas simplement faire pointer M1 vers les données de M2. Dans ce cas, la destruction de M2 pourrait rendre les données de M1 invalides.

Pour copier les données de M2 vers M1, la bibliothèque standard utilise des fonctions de transfert mémoire par bloc pour optimiser les performances.

Il existe des cas particuliers, comme par exemple celui où M1 est une référence vers M2. On doit gérer un self-assignment.

L’utilisation des conteneurs de la STL constitue donc un choix sûr, efficace et robuste. Les principaux cas complexes liés à la gestion de la mémoire, à la copie et à la destruction des objets ont déjà été pris en charge et optimisés par la bibliothèque standard. Il est donc préférable de s’appuyer sur ces mécanismes plutôt que de les réimplémenter soi-même. Cette idée est notamment exprimée dans les C++ Core Guidelines à travers la règle RC-0, également appelée Rule of Zero. Cette règle peut être résumée ainsi :

Règle RC-0 : Si vous pouvez éviter de gérer des ressources ou des situations complexes, faites-le et laissez les containers de la STL s’en charger.

En conclusion de ce chapitre :

Tous les containers de vos exercices et projets seront choisis parmis les containers de la STL : vector, array…

Les itérateurs

Dans ce cours, la syntaxe des itérateurs a été volontairement simplifiée pour en faciliter la lecture. Vous verrez cependant, en consultant d’autres sources, que certains exemples sur Internet peuvent sembler plus complexes — c’est normal.

Les itérateurs sont apparus dans les années 2000 avec une syntaxe reposant sur deux fonctions, begin() et end(). Depuis C++20, a fait son apparition la notion de range/view, similaire aux ranges de Python. Cependant, pour rester concis, nous nous limiterons aux itérateurs begin/end.

Présentation

Les présentations ci-dessous sont valables pour un array comme pour un vector.

La STL introduit le concept d’itérateur, qui généralise et unifie les mécanismes d’accès aux éléments : l’indice pour les tableaux et le pointeur pour les listes chaînées. Chaque container fournit ainsi ses propres itérateurs (~une sorte d’index) permettant d’accéder à ses éléments. La convention de la STL impose à un itérateur d’assurer les opérations suivantes :

Se copier/assigner, se comparer : ==, !=, <, >, <=, >=

Passer à l’élément suivant/précédent : ++it, –it

Avancer/reculer de n : it + n, it - n, it += n, it -= n

Accéder en O(1) à l’élément : *it

Itérateurs begin/end

Chaque container fournit deux fonctions spécifiques :

begin() : retourne un itérateur positionné sur le premier élément.

end() : retourne un itérateur positionné a la fin du container : un élément fictif placé après le dernier élément.

#include <iostream>
#include <array>

int main()
{
        std::array<int, 5> arr = {1, 2, 3, 4, 7};

        std::cout << *arr.begin() << std::endl;    // prints the first element

        std::cout << *(arr.end()-1) << std::endl;  // prints the last element
}

>> 1
>> 7

Les itérateurs begin/end permettent un accès en lecture/écriture. Pour un accès en mode read-only, le langage fournit des const iterator cbegin() et cend() !

Avertissement

On n’utilise plus la valeur 0 ou le paramètre size() pour parcourir une liste à partir de maintenant !

A noter qu’il n’y a pas de #include particulier à effectuer en début de programme. L’insertion d’un #include <vector> est suffisante pour pouvoir utiliser les itérateurs venant d’un vector.

Généricité

La généricité des containers opèrent à travers l’utilisation des templates.

Ainsi, si on vous demandait d’écrire une fonction qui recopie les valeurs d’un container vers un autre, vous pourriez coder la fonction suivante :

template <typename InputIt, typename OutputIt>
OutputIt my_copy(InputIt first, InputIt last, OutputIt dest)
{
        while (first != last)
        {
                *dest = *first;   // copy in O(1)
                ++first;          // go forward in the source
                ++dest;           // go forward in the destination
        }
        return dest;
}

Grâce au mécanisme des templates et des itérateurs, même si les containers sont de type différent, du moment qu’ils fournissent des itérateurs, la méthode fonctionne.

Le mot-clef auto

Le type des itérateurs est assez long à écrire : array<T, N>::iterator. Ainsi, on préfère utiliser le mot-clef auto qui laisse au langage le soin de déduire automatiquement le type :

#include <iostream>
#include <array>

int main()
{
        std::array<int, 5> arr = {1, 2, 3, 4, 5};
        auto it = arr.begin();   // iterator pointing to the first element
}

Arithmétique des itérateurs

L’expression :

begin()+1 désigne l’élément placé après le premier élément

begin()+2 désigne le suivant du suivant !

L.end() - L.begin() correspond aux nombres d’éléments dans L

Voici quelques exemples :

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

int main()
{
        vector<int> L = {2,3,4,5,6};    // 2 3 4 5 6

        L.erase(L.begin()+2);         // Removes the element at index 2 (the 3rd one, which is 4)
                                      // L becomes [2, 3, 5, 6]

        L.insert(L.begin()+3, 8);     // Inserts 8 *before* the element at index 3 (the 4th one, which is 6)
                                      // L becomes [2, 3, 5, 8, 6]

        cout << L.end() - L.begin();  // returns the number of elements !!!
}

Travail à rendre sur l’espace partagé

Exercice 1 : relevés de température

Créez un fichier nommé STL_vector.cpp.

On stocke une série de mesures expérimentales dans un vector<double> :

vector<double> values = {  12.5, 8.2, 15.7, 9.1, 18.4, 7.8, 11.3, 21.6, 14.2, 10.0  };

Réalisez les opérations suivantes :
- Affichez toutes les valeurs à l’aide d’une boucle for moderne.
- Ajoutez les valeurs 13.7 et 16.1 à la fin du vecteur.
- Affichez le nombre de valeurs contenues dans le vecteur.
- À l’aide d’un itérateur, faites une boucle qui recherche la première valeur strictement supérieure à 18.0.
- Affichez cette valeur ainsi que sa position dans le vecteur - vous ne devez pas utiliser un parcours avec indice.
- Insérez la valeur 20.0 juste avant cette valeur.
- Supprimez la troisième valeur du vecteur en utilisant la fonction erase().
- Multipliez toutes les valeurs par 2 en utilisant un parcours par référence.
- Affichez le vecteur final.
Contraintes :
- Aucun tableau C ne doit être utilisé.
- Pour les étapes nécessitant une position dans le conteneur, utilisez begin() et end().
- Utilisez le mot-clef auto pour déclarer les itérateurs.
- N’utilisez pas directement un indice pour les opérations d’insertion ou de suppression.
Vérification - Le vecteur final est :
- 25 16.4 18.2 40 36.8 15.6 22.6 43.2 28.4 20 27.4 32.2
Déposez votre fichier dans l’espace partagé.

Exercice 2 : analyse des résultats d’étudiants

Créez un fichier nommé STL_map.cpp
Utilisez la structure suivante pour représenter les notes de plusieurs étudiants :
map<string, vector<double>> students =
{
    {"Alice", {12.0, 15.0, 14.0}},
    {"Bob",   {8.0,  11.0, 10.0}},
    {"Chloe", {17.0, 16.0, 18.0}},
    {"David", {10.0, 13.0, 12.0}}
};
Réalisez les opérations suivantes :

Affichez le nom de chaque étudiant ainsi que toutes ses notes.

Ajoutez la note 16.0 à Alice.

Ajoutez une nouvelle étudiante : Emma -> {14.0, 13.0, 15.0}

Vérifiez si Paul est présent dans le dictionnaire.

Pour chaque étudiant, calculez sa moyenne - une fonction serait bienvenue.
Affichez les résultats sous la forme suivante :
Alice : 14.25
Bob   : 9.67
...
Recherchez l’étudiant possédant la meilleure moyenne.

Affichez son nom ainsi que sa moyenne.

Supprimez de la map tous les étudiants dont la moyenne est strictement inférieure à 10.

Vous ne pouvez pas faire un parcours standard type for(each) car des suppressions ont lieu durant le parcours

Préférez un itérateur courant qui avance tant qu’il reste des éléments à parcourir

Affichez le contenu final du dictionnaire.

Déposez votre fichier dans l’espace partagé.

Avertissement

IA or not IA, that is the question. Ces exercices sont au programme de l’examen.