L'une des difficultés du langage C consiste à implémenter des containers (vecteurs, listes chaînées, ensembles ordonnés) génériques, simple d'utilisation et efficaces. Une structure générique (par exemple une liste d'objets génériques) nécessite de passer par pointeurs génériques (void *) et aux opérateurs de cast qui en découlent. Si ces containers sont imbriqués les uns dans les autres (par exemple un vecteur de vecteur d'entiers) le code devient rapidement complexe à manipuler.
Afin de répondre à ce problème, la STL (standard template library) propose des classe template décrivant des containers génériques pour le langage C++. La STL fournit en plus des algorithmes permettent de manipuler aisément ces containers (pour les initialiser, rechercher des valeurs, ...). Enfin, la STL introduit également le concept d'itérateur, qui permet de parcourir très facilement un container sans se préoccuper de la manière dont il est implémenté.
L'objectif de cette introduction n'est pas de faire un inventaire exhaustif des possibilités offertes par la STL, mais de donner des exemples courants d'utilisation.
Une fois ce tutoriel compris, il faut voir les classes de la STL comme des briques que l'on emboîte les unes dans les autres. On peut ainsi facilement déclarer un vector d'ensemble de liste d'entiers (
std::vector<std::set<std::list<int> > >)
.
Principaux containers de la STL
Le container doit être choisi en fonction de ses besoins. Certaines structures sont plus ou moins efficaces en temps d'accès, en coût mémoire, et en termes de fonctionnalités (gestion des doublons, etc).
Il est au préalable nécessaire d'avoir quelques notions de complexité. Soit n la taille d'un container. Un algorithme est dit linéaire (en O(n)) si son temps de calcul est proportionnel à n. Voici quelques exemples de complexités, de la moins coûteuse à la plus coûteuse.
O(1)
O(log(n))
O(n)
O(n^k)
O(e(n))
Dans ce qui suit, on s'intéresse principalement à la complexité pour l'accès (recherche) à une donnée stockée dans un container et à la complexité pour insérer une donnée.
Important : Tous les types templates (notés T1, T2, ou T dans ce qui suit) doivent exposer un constructeur vide public pour être utilisable dans un container STL.
std::pair<T1, T2>
Une paire est une structure contenant deux éléments de types éventuellement différents. Certains algorithmes de la STL (find par exemple) retournent des paires (position de l'élément trouvé et un booléen indiquant s'il a été trouvé).
La classe vecteur est proche du tableau du C. Tous les éléments contenus dans le vector sont adjacents en mémoire, ce qui permet d'accéder immédiatement (en O(1)) à n'importe quel élément. Comparé au tableau du C, un vecteur se réalloue facilement (lors d'un
push_back
ou d'un
resize
).
Cependant, une case n'est accessible par l'opérateur [ ] que si elle a été allouée au préalable (sinon une erreur de segmentation se déclenche).
Complexité :
Accès O(1)
Insertion : O(n) en début de vector (pop_back), O(1) en fin de vector (push_back). Dans les deux cas des réallocations peuvent survenir.
ll ne faut pas perdre de vue qu'une réallocation mémoire est coûteuse en terme de performances. Ainsi si la taille d'un vecteur est connue par avance, il vaut mieux le créer directement à la bonne taille (voir méthodes
resize
et
reserve
).
Exemple :
#include <vector>
#include <iostream>
int main(){
std::vector<int> mon_vecteur;
mon_vecteur.push_back(4);
mon_vecteur.push_back(2);
mon_vecteur.push_back(5);
// Pour parcourir un vector (même const) on peut utiliser les iterators ou les index
for(std::size_t i=0;i<mon_vecteur.size();++i) {
std::cout << mon_vecteur[i] << ' ';
}
std::cout << std::endl;
std::vector<int> mon_vecteur(5, 69); // crée le vecteur 69, 69, 69, 69, 69
v[0] = 5;
v[1] = 3;
v[2] = 7;
v[3] = 4;
v[4] = 8;
return 0;
}
std::set<T,...>
Cette classe implémente un ensemble ordonné et sans doublon. On peut préciser la relation d'ordre en paramètre template (à l'aide d'un foncteur). Par défaut, cette relation d'ordre est le foncteur
std::less<T>
(qui enveloppe l'opérateur
<
), ce qui revient à considérer un ensemble d'éléments trié par ordre croissant. À moins d'avoir une relation d'ordre dédiée, cela impose que l'opérateur < soit bien défini pour comparer deux instances de type
T
.
Complexité :
O(log(n)) pour la recherche et l'insertion. En effet, la structure std::set tire partie de l'ordre sur T pour construire une structure d'arbre rouge noir, ce qui permet une recherche logarithmique d'un élément.
#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;
}
Attention : Le fait de supprimer ou ajouter un élément dans un
std::set
invalide ses iterators. Il ne faut donc pas modifier un
std::set
dans une boucle
for
en train d'itérer sur cet ensemble.
std::map<K, V,...>
Une map associe une clé (identifiant) à une donnée (table associative) et prend au moins deux paramètres templates :
le type de la clé K ;
le type de la valeur V.
À l'image de
std::set
, les maps reposent sur la notion d'arbre rouge noir et nécessite donc une relation d'ordre (par défaut
std::less<K>
). À moins de préciser cette relation d'ordre, l'opérateur
<
doit donc être défini pour le type
K
.
Complexité :
O(log(n)) pour la recherche et l'insertion.
Attention :
À l'image de
std::set
, le fait de supprimer ou ajouter un élément dans un
std::map
remet invalide ses iterators. Il ne faut pas modifier un std::map dans une boucle for basée sur ses iterators.
Contrairement à
std::vector
, le fait d'accéder à une clé via l'opérateur [ ] ajoute la clé à la map et lui associe la donnée
V()
. Ainsi l'opérateur [ ] n'est pas adapté pour vérifier si une clé est déjà présente dans la map, il faut utiliser la méthode
find
. Enfin, comme cet opérateur peut insérer une clé, il ne garantit pas la constance de la mapet ne peut donc pas être utilisé sur des
Nous avons vu dans la section précédente que les itérateurs permettaient de parcourir aisément une structure de la STL d'un bout à l'autre. Bien qu'un itérateur s'utilise comme un pointeur, ce n'est pas une adresse. Nous allons à présent voir quatre iterators classiques de la STL.
Ils sont définis pour toutes les classes de la STL évoquées ci-dessus, hormis std::pair.
iterator et const_iterator
Un
iterator
(et un
const_iterator
) permet de parcourir un container du début à la fin.
Un
const_iterator
fournit un accès en lecture seule sur l'élément "pointé".
Un
iterator
fournit un accès en lecture / écriture sur l'élément "pointé" (on peut donc modifier l'élément "pointé" par l'iterator, ou le supprimer du container en le passant à la méthode adéquate).
C'est pourquoi un container
const
ne peut être parcouru que par des
const_iterator
s et pas par des
iterator
s. Quand on a le choix entre ces deux types d'itérateurs, il faut privilégier les
const_iterator
, car le code est applicable aussi aux containers qu'ils soient
const
ou non.
begin()
: retourne un (const) iterator qui pointe sur le premier élément ;
end()
: retourne un (const) iterator qui pointe juste "après" le dernier élément ;
++
: permet d'incrémenter l'iterator en le faisant passer à l'élément suivant.
Exemple :
#include <list>
#include <iostream>
const std::list<int> creer_liste(){
std::list<int> l;
l.push_back(3);
l.push_back(4);
return l;
}
int main(){
<bold>const</bold> std::list<int> ma_liste(creer_liste());
/*
// ne compile pas car l est const
std::list<int>::iterator
lit1 (l.begin()),
lend1(l.end());
for(;lit1!=lend1;++lit1) std::cout << *lit1 << ' ';
std::cout << std::endl; */
std::list<int>::const_iterator
lit2 (l.begin()),
lend2(l.end());
for(;lit2!=lend2;++lit2) std::cout << *lit2 << ' ';
std::cout << std::endl;
return 0;
}
reverse_iterator et const_reverse_iterator
Le principe des
reverse_iterators
et
const_reverse_iterator
est similaire, à ceci près que le parcours se fait de la fin vers le début du container.
On utilise alors :
rbegin()
: retourne un (const) reverse_iterator qui pointe sur le dernier élément ;
rend()
: retourne un (const) reverse_iterator qui pointe juste "avant" le premier élément ;
++
: permet de incrémenter le reverse_iterator en le faisant passer à l'élément précédent.
Exemple :
#include <set>
#include <iostream>
int main(){
std::set<unsigned> s;
s.insert(1); // s = {1}
s.insert(4); // s = {1, 4}
s.insert(3); // s = {1, 3, 4}
std::set<unsigned>::const_reverse_iterator
sit (s.rbegin()),
send(s.rend());
for(;sit!=send;++sit) std::cout << *sit << std::endl;
return 0;
}
... affiche :
4 3 1
Les algorithmes
Cette page liste les algorithmes disponibles dans la STL. Parmi eux, ont retiendra quelques méthodes bien pratiques comme :
la méthode
find
(pour les
std::set
et
std::map
) pour chercher un élément ou tester son existence ;
