Chapitre 6 : Bibliothèque STL

Le C++ possède une bibliothèque standard (SL pour Standard Library) qui est composée, entre
autre, d’une bibliothèque de flux, de la bibliothèque standard du C, de la gestion des exceptions,
..., et de la STL (Standard Template Library : bibliothèque de modèles standard).
La STL fournit un certain nombre de conteneurs pour gérer des collections d’objets : les
tableaux (vector), les listes (list), les ensembles (set), les piles (stack), et beaucoup
d’autres ...
On distingue différents types de conteneurs :
 Les conteneurs de séquence :
 vector : accès direct à n’importe quel élément
 list : accès séquentiel avant arrière.
 deque : associe les 2 précédents.
 Les conteneurs associatifs :
 set : recherche rapide, aucun doublon autorisé.
 multiset : recherche rapide, doublons autorisés.
 map : recherche rapide par clé
 Les adaptateurs de conteneur :
 stack : pile ou LIFO : dernier entré, premier sorti.
 queue : file ou FIFO : premier entré, premier sorti.
 priority_queue : l’élément de priorité la plus grande est toujours le premier
élément sorti.
Les conteneurs de la STL ont été conçus de façon à fournir des fonctionnalités similaires, c’est
pourquoi, ils contiennent un certain nombre de méthodes et d’opérateurs communs :
Constructeur par size Retourne le nombre actuel
défaut d’éléments dans le conteneur
Constructeur de Constructeur qui initialise max_size Retourne le nombre
copie le conteneur comme une maximum d’éléments d’un
copie d’un conteneur conteneur
existant de même type
destructeur Les 7 operator Retourne true ou false selon la
= < <= > >= == comparaison du premier

63
 != conteneur avec le second.
empty Retourne true s’il n’y a pas swap Effectue l’échange de 2
d’élément dans le conteneurs
conteneur

Un conteneur (container) est un objet qui contient d’autres objets. Il fournit un moyen de gérer
les objets contenus (au minimum ajout, suppression, parfois insertion, tri, recherche, ...) ainsi
qu’un accès à ces objets qui dans le cas de la STL consiste très souvent en un itérateur.
Pour utiliser ces classes conteneurs, il faut les en têtes suivantes ; elles sont totalement intégrées
à l’espace de noms std (namespace std).
<vector> <queue> contient à la fois des queue et les
<list> priority_queue
<dequeue> <map> contient à la fois les map et les
<stack> multimap
<bitset> <set> contient à la fois les set et les multiset

1. Tableau dynamique (vector) :

Un vector est un tableau dynamique où il est particulièrement aisé d’accéder directement
aux divers éléments par un index, et d’en ajouter ou en retirer à la fin.
A la manière des tableaux de type C, l’espace mémoire alloué pour un objet de type vector est
toujours continu, ce qui permet des algorithmes rapides d’accès aux divers éléments.

Aux méthodes communes des classes conteneurs s’ajoute ces méthodes spécifiques :

64
push_back, pop_back, front, back, at, capacity.

Exemple :
#include <iostream>
#include <vector>
using namespace std;
int main()
{
cout << "test Vector " << endl;
vector<int> monVect;
int fibo1=0, fibo2=1;
monVect.push_back (fibo1);
for (int i =0 ; i < 10; i++)
{
int fibo = fibo2 + fibo1;
monVect.push_back (fibo);
fibo1 = fibo2;
fibo2 = fibo;
}
cout << "Premier element " << monVect.front() << endl;
for (int i=0; i < monVect.size(); i++){
cout << "Element no " << i << " " << monVect.at(i) << endl;
}
cout << "Dernier element " << monVect.back() << endl;
cout << "copie de vector " << endl;
vector<int> monVect2(monVect);
cout << "Capacite " << monVect2.capacity() << " Nombre elements
" <<
monVect2.size() << endl;
monVect.clear();
cout << " Apres clear : Capacite " << monVect.capacity() << "
Nombreelts " << monVect.size() << endl;
int i= monVect2.size() -1;
while (!monVect2.empty()) {
cout << "retire element " << i << " " << monVect2[i] <<
endl; //ou monVect2.at(i)
i--;
monVect2.pop_back();
}
}
Résultat :

65
Les itérateurs (iterator) sont une généralisation des pointeurs : ce sont des objets qui
pointent sur d’autres objets.
Comme son nom l’indique, les itérateurs sont utilisés pour parcourir une série d’objets de
telle façon que si on incrémente l’itérateur, il désignera l’objet suivant de la série.
Exemple :
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> v2(4, 100); // un vecteur de 4 entiers initialisés avec la valeur 100
cout << "Le vecteur v2 contient " << v2.size() << "entiers : ";
// utilisation d’un itérateur pour parcourir le vecteur v2
for (vector<int>::iterator it = v2.begin(); it != v2.end(); ++it)
cout << " " << *it;
cout << "\n";
return 0;
}

2. Les listes chainées (list) :

La classe list fournit une structure générique de listes doublement chaînées (c’est-à-dire que
l’on peut parcourir dans les deux sens) pouvant éventuellement contenir des doublons.

Exemple :
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<int> lst; // une liste vide
lst.push_back( 5 );
lst.push_back( 6 );
lst.push_back( 1 );
lst.push_back( 10 );
lst.push_back( 7 );
lst.push_back( 8 );

66
 lst.push_back( 4 );
lst.push_back( 5 );
lst.pop_back(); // enleve le dernier élément et supprime l’entier 5
cout << "La liste lst contient " << lst.size() << " entiers : \n";
// utilisation d’un itérateur pour parcourir la liste lst
for (list<int>::iterator it = lst.begin(); it != lst.end(); ++it)
cout << " " << *it;
cout << "\n";
// afficher le premier élément
cout << "Premier element : " << lst.front() << "\n";
// afficher le dernier élément
cout << "Dernier element : " << lst.back() << "\n";
// parcours avec un itérateur en inverse
for ( list<int>::reverse_iterator rit = lst.rbegin(); rit !=
lst.rend(); ++rit )
{
cout << " " << *rit;
}
cout << "\n";
return 0;
}

Résultat :
La liste lst contient 7 entiers :
5 6 1 10 7 8 4
Premier element : 5
Dernier element : 4
4 8 7 10 1 6 5

3. La table associative (map)

Une table associative map permet d’associer une clé à une donnée.
La map prend au moins deux paramètres :
– le type de la clé (dans l’exemple ci-dessous, une chaîne de caractères string)
– le type de la donnée (dans l’exemple ci-dessous, un entier non signé unsigned int)

Exemple :
#include <iostream>
#include <iomanip>
#include <map>
#include <string>
using namespace std;
int main()
{
map<string,unsigned int> nbJoursMois;
nbJoursMois["janvier"] = 31;

67
 nbJoursMois["février"] = 28;
nbJoursMois["mars"] = 31;
nbJoursMois["avril"] = 30;
//...
cout << "La map contient " << nbJoursMois.size() << "elements : \n";
for (map<string,unsigned int>::iterator it=nbJoursMois.begin();
it!=nbJoursMois.end(); ++it)
{
cout << it->first << " -> \t" << it->second << endl;
}
cout << "Nombre de jours du mois de janvier : " <<
nbJoursMois.find("janvier")->second <<"\n";
// affichage du mois de janvier
cout << "Janvier : \n" ;
for (int i=1; i <= nbJoursMois["janvier"]; i++)
{
cout << setw(3) << i;
if(i%7 == 0)
cout << endl;
}
cout << endl;
return 0;
}
Résultat :
La map contient 4 elements :
avril -> 30
février -> 28
janvier -> 31
mars -> 31
Nombre de jours du mois de janvier : 31
Janvier :
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31

4. Les Set :
Un set<T> contient des éléments de type T triées automatiquement. T doit définir un ordre, par
défaut on utilise l’opérateur < mais une autre fonction peut être utilisée.
Set possède quelques opérations spécifiques à la recherche dans le conteneur :
 count(elem) retourne le nombre d’éléments avec valeur égale à elem.
 find(elem) retourne le premier élément avec valeur elem

 lower_bound(elem), upper_bound(elem) retournene la position du premier élément >=

68
 elem, resp. <= elem.
Dans un set il n’y a pas de duplication.
Exemple :
#include <set>
#include <iostream>

int main() {
std::set<int> s; // équivaut à std::set<int, std::less<int> >
s.insert(2); // s contient 2
s.insert(5); // s contient 2 5
s.insert(2); // le doublon n'est pas inséré
s.insert(1); // s contient 1 2 5
std::set<int>::const_iterator sit (s.begin()), send(s.end());
for(;sit!=send;++sit)
std::cout << *sit << ' ';
std::cout << std::endl;
return 0;
}

5. Les piles et les files :

A la différence avec les conteneurs vector, les piles & les files n’offrent pas d’accès direct aux
éléments mais uniquement par les iterator.
Les priority_queue ont le même fonctionnement que les queues mais l’élément retiré le premier
est celui de plus haute priorité.
Exemple :
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
int main() {
cout << "test des classes stack, queue " << endl;
stack <int> pile;
queue <double>file;
cout << "remplissage de la pile " << endl;
for (int i=0; i < 5; i++)
{
pile.push(i);
cout << "sommet " << pile.top() << endl;
}
cout << "Vidage de la pile " << endl;
while (pile.empty() == false)
{
cout << "tete " << pile.top() << endl;
pile.pop();
}
cout << "remplissage de la file par l'arriere " << endl;
for (int i=0; i < 5; i++)
{
file.push(i);

69
 cout << "avant " << file.front() << " arriere " <<
file.back() << endl;
}
cout << "Sauvegarde de la file " << endl;
queue <double> file2(file);
cout << "Vidage de la file par l'avant " << endl;
while (file.empty() == false)
{
cout << "avant " << file.front() << " arriere " <<
file.back() << endl;
file.pop();
}
return 0;
}
Résultat :
test des classes tete 3 avant 0 arriere 4
stack, queue tete 2 Sauvegarde de la
remplissage de la tete 1 file
pile tete 0 Vidage de la file
sommet 0 remplissage de la par l'avant
sommet 1 file par l'arriere avant 0 arriere 4
sommet 2 avantavant 0 avant 1 arriere 4
sommet 3 arriere 0 avant 2 arriere 4
sommet 4 avant 0 arriere 1 avant 3 arriere 4
Vidage de la pile avant 0 arriere 2 avant 4 arriere 4
tete 4 avant 0 arriere 3

6. Les algorithmes :
La STL fournit environs 70 algorithmes destinés à manipuler des conteneurs. Les algorithmes
opèrent sur les conteneurs uniquement via les itérateurs.
Il est également possible de créer ses propres algorithmes qui opèrent d’une manière semblable
à ceux de la STL.
Un algorithme tel que find (), par exemple, localise un élément et retourne un itérateur vers
cet élement. Si l ‘élement n’est pas trouvé, find () retourne l’iterateur end() qui est le
dernier élément du conteneur.
L’algorithme find () est disponible avec tous les conteneurs de la STL.
On distingue les algorithmes mutables, c’est à dire qui modifient les éléments du conteneur.
copy () partition() replace_copy() stable_partition()
copy_backward() random_suffle() replace_copy_if() swap()

fill() remove() replace_if() swap_ranges()

70
 fill_n() remove-copy() reverse() transform()

generate() remove_copy_if() reverse_copy() unique()

generate_n() remove_if() rotate() unique_copy()

iter_swap() replace() rotate_copy()

Les algorithmes non mutables

adjacent-find () equal() find_end() mismatch()

count() find() find_first_of() search()

count_if() find_each() find_if() search_n()

et les algorithmes numériques (fichier d’en-tête <numeric>)

accumulate () inner_product() partial_sum() adjacent_difference()

71