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. Afin d'être générique on est souvent contraint de faire appel à des pointeurs génériques (void *) et aux opérateurs de cast. De plus, quand ces containers sont imbriqués les uns dans les autres (par exemple un ensemble de vecteurs) le code devient rapidement complexe à utiliser.

Afin de répondre à ce besoin, la STL (standard template library) implémente un grand nombre de 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, ...). La STL introduit également le concept d'iterator qui permet de parcourir très facilement un container en s'affranchissant complètement de la manière dont il est implémenté.

Les concepts développés dans la STL sont aujourd'hui étendus par la librairie boost qui permet de manipuler des structures de graphe générique.

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. On pourra trouver un aperçu très détaillé des classes de la STL ici :
http://www.sgi.com/tech/stl/table_of_contents.html

Par la suite, on présentera les classes de la STL avec des paramètres templates "simples". En pratique il faut voir les classes de la STL comme des legos (ou des duplos pour ne pas faire de jaloux) pouvant être imbriqués les uns dans les autres. Ainsi, on pourra tout à fait manipuler un vector d'ensemble de liste d'entier (std::vector<std::set<std::list<int> > >).

Principales classes de la STL

Il est particulièrement important de choisir une classe fournie par la STL cohérente avec son besoin. Certaines structures sont effectivement plus ou moins efficaces pour accéder à une mémoire ou en terme de réallocation mémoire lorsqu'elles deviennent importantes. L'enjeu de cette partie consiste à présenter les avantages et les inconvénients de chacune d'elle.

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. De la même façon, un algorithme peut être instantané (O(1)), logarithmique O(log(n)), polynomial O(n^k), exponentiel O(e(n)), etc...

Pour résumer, voici la liste des complexités dans l'ordre croissant des proportions de temps de calcul (plus on descend, plus c'est violent):

• O(1)
• O(log(n))
• O(n)
• O(n^k)
• O(e(n))

Ici on s'intéressera 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.

std::pair<T1,T2>

Une paire est une structure contenant deux éléments éventuellement de types 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> // en pratique cet include est sous-entendu car implicitement fait lorsqu'on utilise <vector>, <set> ...
#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,...>

La classe list fournit une structure générique de listes chaînées pouvant éventuellement contenir des doublons.

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

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 vector 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 à n'importe quel élément. L'avantage du vector comparé au tableau du C est sa faculté à se réallouer automatiquement en cas de besoin lors d'un push_back par exemple. Cependant comme un tableau classique 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 temps de calcul. Ainsi si la taille d'un vecteur est connue par avance, il faut autant que possible le créer directement à cette taille.

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,...>

La classe set permet de décrire un ensemble ordonné et sans doublons d'éléments. Il faut a priori passer cet ordre en paramètre template (plus précisément d'un foncteur). Par défaut, le foncteur std::less (basé sur l'opérateur <) est utilisé, ce qui revient à avoir un ensemble d'éléments classés du plus petit au plus grand. Concrètement il suffit donc d'implémenter l'opérateur < d'une classe ou d'une structure de type T pour pouvoir définir un std::set<T>. De plus, le type T doit disposer d'un constructeur vide 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 remet invalide ses iterators. Il ne faut pas modifier un std::set dans une boucle for basée sur ses iterators

std::map<K,T,...>

Une map permet d'associer une clé (identifiant) à une donnée (table associative).

La map prend au moins deux paramètres templates :

• le type de la clé K
• le type de la donnée T

À l'image du std::set, le type K doit être ordonné (cet ordre peut être passé en 3e paramètre template, std::less<K> par défaut) et . Le type T impose juste d'avoir un constructeur vide.

Complexité :

• O(log(n)) pour la recherche et l'insertion. En effet, la structure std::map 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.

Attention : 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

Attention : le fait d'accéder à une clé via l'opérateur [ ] insère cette clé (avec la donnée T()) dans la map. Ainsi l'opérateur [ ] n'est pas adapté pour vérifier si une clé est présente dans la map, il faut utiliser la méthode find. De plus, il ne garantit pas la constance de la map (à cause des insertions potentielles) et 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 iterators permettaient de parcourir aisément une structure de la STL d'un bout à l'autre. Un iterator rappelle un peu la notion de pointeur, mais 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 bien sûr 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, contrairement à un iterator, donne un accès uniquement en lecture à l'élément "pointé". Ainsi, un parcours avec des const_iterator maintient la constance du container. C'est pourquoi un container "const" peut être parcouru par des const_iterators mais pas des iterators.

De manière générale, quand on a le choix entre des iterators ou des const_iterator, il faut toujours privilégier les const_iterator car ils rendent la section de code à laquelle ils servent plus générique (applicable aux containers const ou non const).

• begin() : retourne un iterator qui pointe sur le premier élément
• end() : retourne un 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(){
  const std::list<int> ma_liste(creer_liste());
  // ne compile pas car l est const
  // std::list<int>::iterator
  //  lit1 (l.begin()),
  //  lend(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 aux iterators et const_iterator à ceci prês que le parcours se fait dans le sens opposé.

On utilise alors :

• rbegin() : retourne un iterator qui pointe sur le dernier élément
• rend() : retourne un iterator qui pointe juste "avant" le premier élément
• -- : permet de décrémenter le reverse_iterator en le faisant passer à l'élément précédent.

Les algorithmes

Si le concept d'iterator est maîtrisé, il suffit de se référer à
http://www.sgi.com/tech/stl/table_of_contents.html

On retiendra quelques méthodes bien pratiques comme find (pour les std::set et std::map) pour chercher un élément, std:fill pour (ré)initialiser un std::vector, des algorithmes de tri, de recherche de min ou de max.