Containers ✱

Your native language: with Chrome, right-click on the page and select « Translate into … »
English version:

Ce chapitre présente les principaux containers de données disponibles en C++. Ils enterrent définitivement l’utilisation des tableaux du C. A partir de maintenant, vous devez les utiliser à chaque fois dans tous nos exercices. Les tableaux du C sont INTERDITS. Nous rappelons qu’ils ont été conçus pour optimiser performance et sûreté. Effectivement, des années de tests et développement permettent de garantir leur robustesse.

Nous étudions dans la suite :

Les array - container à taille fixe avec mémoire contiguë

Les vector - dimension dynamique, contiguïté)

Les map - association par clé–valeur ordonnée et opérations garanties en O(log n)) amortie.

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
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.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.
La syntaxe at(i) ou [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, 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
        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

Les itérateurs

Note

Un effort de simplification a été fait dans ce cours relativement aux syntaxes présentées pour les itérateurs. Cependant, lorsque vous trouverez des informations sur internet, certains auteurs pourront fournir un code beaucoup plus difficile à lire, il faut le savoir.

Présentation

Avertissement

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

La norme de la Standard Template Library (STL) n’impose aucune implémentation particulière. Elle se limite à spécifier les signatures des fonctions membres ainsi que, le cas échéant, les complexités algorithmiques de certaines fonctions : temps constant, logarithmique ou linéaire amorti. Par conséquent, les conteneurs définis par la STL peuvent, en interne, recourir à des mécanismes variés, par exemple l’utilisation d’entiers ou de pointeurs pour l’indexation des données. Il convient également de rappeler que plusieurs implémentations de la STL coexistent :

libstdc++ :distribuée avec GCC et appréciée pour sa large compatibilité avec différentes architectures

LLVM libc++ : associée à Clang, caractérisée par sa légèreté et sa conception modulaire

Microsoft STL : intégrée à Visual Studio et optimisée pour les environnements Windows ;

Des implémentations internes ou adaptées : développées par certaines entreprises afin de répondre à des besoins spécifiques, notamment dans le domaine des consoles de jeu ou du développement embarqué.

Quelle que soit la structure de données ou l’implémentation retenue, la nécessité d’une abstraction pour l’accès et l’indexation des éléments s’est imposée : on parle des itérateurs iterator. Cependant, la syntaxe des itérateurs peut surprendre. On l’aime, on ne l’aime pas, mais dans tous les cas, il faut savoir les utiliser.

Les itérateurs remplacent ainsi les indices :

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

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

*it : si it est un itérateur ; *it est une référence vers l’élément désigné par cet itérateur.

Avertissement

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

#include <iostream>
#include <array>

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

        std::cout << *arr.begin() << std::endl;   // prints the first element
        *arr.begin() = 9;                         // modifies the first element
        for(int v : arr) std::cout << v << " ";   // prints the list
}

>> 1
>> 9 2 3 4 5

Note

Un itérateur permet un accès en lecture/écriture. Pour un accès en mode read-only, le langage fournit des const iterator ainsi que les méthodes cbegin() et cend().

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 un itérateur associé à l’élément suivant. Voici quelques exemples :

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

int main()
{
        vector<int> L = {2,3,4};
        for (int v : L) cout << v << endl;

        L.erase(L.begin()+1);   // removes the 2nd element
        for (int v : L) cout << v << endl;

        L.insert(L.begin()+1, 8); // inserts 8 at the 2nd position
        for (int v : L) cout << v << endl;
}
>> 2 3 4
>> 2 4          // L.erase(L.begin()+1);
>> 2 8 4        // L.insert(L.begin()+1,8);

Travail à rendre sur Github Classroom

Exercice 1

Créez un fichier nommé 6_STL_basic.cpp

A partir de l’exemple ci-dessous, effectuez les actions demandées.

Uploadez le fichier sur votre github

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;
template <typename Container>
void print(const Container& c,string t="") { for (const auto& x : c) cout << x << " "; cout << t << "\n"; }

int main()
{
        vector<int> v = { 1, 3, 5, 7, 9, 4, 3, 3, 3, 3, 9, 5, 9};
        vector<int> t = { 9, 4, 3 };
        vector<int> z = { 1, 3, 5 };
}

Opération	Description
int count(first, last, value)	Comptez le nombre d’apparitions du chiffre 9 dans le vector
iterator min_element(first,last)	Affichez la plus petite valeur du vector
T accumulate(first,last,T initvalue)	Calculez la somme des éléments de v
iterator find(first, last, value)	Recherchez la valeur 4 et remplacez la par 8 - find returns an iterator
bool equal(first1,last1,first2)	Vérifiez si les 3 premiers éléments de v sont identiques à ceux de z

Exercice 2

Créez un fichier nommé 6_STL_arrangement.cpp

A partir de l’exemple ci-dessous, ajoutez les fonctions documentées ci-dessous pour obtenir la sortie suivante :

Uploadez le fichier sur votre github

Opération	Description
fill(first,last,value)	Assigne la valeur value à chaque élément de l’intervalle [first, last).
fill_n(first,n,value)	Assigne la valeur value aux n éléments à partir de la position first.
iota(first,last,startvalue)	Remplit l’intervalle [first, last) avec des valeurs croissantes en commençant par startvalue.
shuffle(first,last,rng)	Réorganise aléatoirement les éléments dans l’intervalle [first, last) en utilisant le générateur de nombres aléatoires rng.
rotate(first,middle,last)	Effectue une rotation à gauche des éléments dans l’intervalle [first, last), de sorte que l’élément pointé par middle devienne le premier de la séquence.
reverse(first,last)	Inverse l’ordre des éléments dans l’intervalle [first, last).

Exercice 3

Nous allons présenter plusieurs algorithmes de la STL fonctionnant uniquement sur des listes triées.

Avertissement

Si l’on prend l’exemple de la fusion de deux vectors triés, l’algorithme merge a pour objectif de construire un nouveau vector résultat. Dans ce genre de cas, la STL souhaite que l’on initialise la taille du vector cible à sa taille finale, ceci AVANT l’appel du merge, ce qui est contraignant. Cependant, il est possible d’effectuer la fusion vers vector vide en utilisant la syntaxe back_inserter(vector_destination).

Créez un fichier nommé 6_STL_sorted.cpp

A partir de l’exemple ci-dessous, effectuez les actions demandées.

Uploadez le fichier sur votre github

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <numeric>

using namespace std;
template <typename Container>
void print(const Container& c,string t="") { for (const auto& x : c) cout << x << " "; cout << t << "\n"; }

int main()
{
        vector<int> v = { 1, 3, 5, 9, 11  };
        vector<int> w = { 0, 1 , 2, 7, 8, 13 };
        const int N = 1000000;
        vector<int> z(N);
}

Opération	Description
merge(first1,last1,first2,last2,back_inserter(first3))	Fusionnez le contenu des deux vectors dans un nouveau vector, les doublons seront préservés
bool is_sorted(first,last)	Vérifiez si le nouveau vector est bien trié
size()	Affichez le nombre d’éléments du nouveau vector
set_union(start1,end1,start2,end2,back_inserter(out1))	Créez un vector qui correspond à l’union ensembliste de v et w
set_intersection(start1,end1,start2,end2,back_inserter(out1))	Créez un vector qui correspond à l’intersection ensembliste de v et w
iota(start,end,val)	Initialisez les valeurs de la liste z de 1 à 1000000
iterator lower_bound(first,last,val)	Grâce à une boucle, recherchez la position des valeurs 1 à N dans le vector. A votre avis, quelle est la complexité de l’algorithme de recherche ?