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
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
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.
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
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
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 : ==, !=, <, >, <=, >=
S’incrémenter et se décrémenter : ++it, –it
Avancer/reculer de n : it + n, it - n, it += n, it -= n
Accéder en O(1) à l’élément *it
Les différents itérateurs respectent cette interface décrite plus préciséement par le concept std::random_access_iterator. Introduit avec C++20, un concept permet de lister les contraintes qu’un type doit respecter : présence d’une fonction, constante associée … (hors programme). Ainsi, les différents itérateurs ne sont pas reliés par une hiérarchie de classes mais par une interface définie à travers cette notion de concept. Les concepts étant vérifiés durant la compilation, ils ne génèrent aucun coût supplémentaire durant l’exécution, contrairement aux polymorphisme d’héritage.
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, 5};
std::cout << *arr.begin() << std::endl; // prints the first element
std::cout << *(arr.end()-1) << std::endl; // prints the last element
}
>> 1
>> 5
Les itérateurs being/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. De même begin()+2 désigne le suivant du suivant ! 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]
}
Générateurs de nombres alétoires
Introduction
Vous êtes sans doute familier avec le C et sa célèbre fonction rand(), cependant la STL a choisi de mettre à disposition des développeurs toute une panoplie de générateurs de nombres aléatoires. Pourquoi une telle offre ? Tout simplement, pour répondre à différents besoins techniques. Par défaut, ils fournissent tous des nombres entiers positifs. A titre indicatif, voici quelques exemples :
Générateur |
Vitesse |
Qualité / Usage typique |
|---|---|---|
mt19937 |
Rapide |
Le plus utilisé. Bon compromis entre qualité et performance. |
minstd_rand |
Très rapide |
Basique, faible qualité |
ranlux24 |
Lent |
Très bon aléatoire, utile pour la physique, les statistiques… |
random_device |
Très lent |
Générateur entropique |
Pour la petite histoire : un générateur entropique utilise une source physique présente dans votre processeur, censée fournir une information réellement aléatoire, comme le bruit électronique ou thermique capté par un composant adapté.
Exemple
#include <iostream>
#include <random>
int main()
{
std::mt19937 gen;
for (int i = 0; i < 3; ++i) std::cout << gen() << " ";
}
>>> 3499211612 581869302 3890346734
Loi de probabilité
A titre indicatif, on peut utiliser différentes lois de probabilité :
Uniforme discrète : chaque entier dans l’intervalle a la même probabilité d’apparaître
Uniforme continue : même principe pour les réels
Normale (gaussienne) : définie à partir d’une moyenne et d’un écart type
#include <iostream>
#include <random>
using namespace std;
int main()
{
mt19937 gen;
uniform_int_distribution<int> unifInt(10, 30);
for (int i = 0; i < 10; ++i) cout << unifInt(gen) << " ";
normal_distribution<double> normale(20.0, 3.0); // mean 20, std 3
for (int i = 0; i < 10; ++i) cout << normale(gen) << " ";
}
>> 12 29 27 12 30 29 14 23 16
>> 15.9701 20.6107 18.0698 22.8348 22.6076 20.9631 24.3167 20.0531 16.3851 18.2595
Les algorithmes
Il existe une différence philosophique fondamentale entre la STL et la conception orientée objet classique. En effet, si l’on veut trier un vector T, dans une approche POO, il semble naturel d’écrire :
T.sort(); // KO
Mais cette approche pose problème :
Il n’existe pas une hiérarchie de classes entre les différents containers
Il faut donc écrire une fonction sort() pour chaque container, alors que basiquement, c’est toujours la même
L’approche retenue consiste à utiliser une fonction sort(…) et de lui passer en arguments des itérateurs :
sort(T.begin(), T.end() ); // OK
C’est donc le mécanisme de template (le T de STL) qui garantit la généricité de cette approche.
Les fonctions de la STL opèrant sur les containers s’appelent algorithms et sont, pour l’essentiel, disponibles à travers le package <algorithm>. Très rapidement, on peut essayer de les regrouper par thématique :
Parcours : for_each, count, find, search…
Transformation : copy, move, fill, generate, replace, transform…
Organisation : reverse, rotate, shuffle…
Liste triée : sort, lower_bound, binary_search…
Ensembliste : merge, set_intersection, set_difference…
Calcul : accumulate - package <numeric>
Comme les fonctions ne sont pas disponibles à travers un objet, elles n’apparaissent pas dans la documentation des containers. Il faut donc connaître leur existence pour pouvoir les retrouver si besoin, ou parcourir la documentation du package algorithm. Nous avons choisi de les introduire à travers différents exercices.
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> z = { 1, 3, 5 };
}
Opération |
Description |
|---|---|
int count(first, last, value) |
Comptez le nombre d’apparitions du chiffre 9 dans le vector v |
iterator min_element(first,last) |
Affichez la plus petite valeur du vector v |
T accumulate(first,last,T initvalue) |
Calculez la somme des éléments de v |
iterator find(first, last, value) |
Dans le vector v, recherchez la valeur 4 et remplacez la par 8 |
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 un 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 v et w dans un nouveau vector x, les doublons seront préservés |
bool is_sorted(first,last) |
Vérifiez si le nouveau vector x est bien trié |
size() |
Affichez le nombre d’éléments du nouveau vector x |
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) |
Recherchez la position de la valeur N/2 dans le vector z. Affichez la pour vérification. |