Introduction à la STL en C++ (standard template library)

Introduction

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é).

Complexité : insertion et accès en O(1)

#include <pair>
#include <iostream> 
#include <string> 

int main(){ 
  std::pair<int, std::string> p = std::make_pair(5, "pouet"); 
  std::cout << p.first << ' ' << p.second << std::endl; 
  return 0; 
}

std::list<T,...>

Une liste permet de stocker des éléments de même types, potentiellement en plusieurs exemplaires.

Complexité :

• Insertion (en début ou fin de liste) : O(1)
• Recherche : O(n) en général, O(1) pour le premier et le dernier maillon

Exemple :

Cet exemple montre comment insérer les valeurs 4, 5, 4, 1 dans une liste et comment afficher son contenu :

#include <list> 
#include <iostream> 

int main(){ 
  std::list<int> ma_liste; 
  ma_liste.push_back(4); 
  ma_liste.push_back(5); 
  ma_liste.push_back(4); 
  ma_liste.push_back(1); 
  std::list<int>::const_iterator 
    lit (ma_liste.begin()), 
    lend(ma_liste.end()); 
  for(;lit!=lend;++lit) std::cout << *lit << ' '; 
  std::cout << std::endl;  
  return 0; 
} 

std::vector<T,...>

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

  const std::map

  .

Exemple :

#include <map> 
#include <string> 
#include <iostream> 

int main(){ 
  std::map<std::string,unsigned> map_mois_idx; 
  map_mois_idx["janvier"] = 1; 
  map_mois_idx["février"] = 2; 
  //... 
  std::map<std::string,unsigned>::const_iterator 
    mit (map_mois_idx.begin()), 
    mend(map_mois_idx.end()); 
  for(;mit!=mend; ++mit) {
    std::cout << mit->first << '\t' << mit->second << std::endl; 
  }
  return 0; 
}

Les iterators

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 ;
• la méthode

  std:fill

  pour (ré)initialiser d'un

  std::vector

  ;
• des algorithmes de tri ;
• des algorithmes de recherche de min ou de max ;
• etc.