STL

(Standard Template Library)

Enseignement Informatique

LAL

Introduction

STL est une bibliothèque standard du C++

Fait partie du langage
Tout le code est contenu dans les fichiers 'header', pas de 'libraries' à linker
Entièrement définie dans l'espace de nommage std
Repose sur le concept de généricité (template) permettant de paramétrer le type d'élément utilisé
Particulièrement efficace

Organisation

La librarie STL est organisée en plusieurs parties. Il existe principalement 3 types d'éléments

Les conteneurs
Permettent de contenir des données
Les itérateurs
Permettent aux algorithmes de manipuler les conteneurs : récupérer une donnée et passer à la suivante
Les algorithmes
Permettent de manipuler les données d'un conteneur en accédant aux données via les itérateurs

On ajoute

Les strings
Qui définissent les chaines de caractères comme type normal (copie, assignation, comparaison,...)

Conteneurs

Il s'agit de structures algorithmiques permettant :
- d'organiser un ensemble de données de même type en séquence,
- puis de parcourir ces données
Exemples :
- les listes (std::list)
- les tableaux (std::vector)
- les listes triées (std::set)
- les listes d'associations (std::map)
La définition d'un conteneur est indépendante du type des objets contenus
On spécifie ce qu'il contient lors de la déclaration de la variable
Allocation dynamique et automatique de la mémoire

Conteneurs ...

Ordonnés (position indépendante de la valeur)

List : liste doublement chaînée
Vector : tableau à 1 dimension

Triés (position dépendante de la valeur)

Set/Multiset : ensemble
Map/Multimap : tableau associatif

List

Utilisation des listes

 #include <iostream>
 #include <list>

 int main()
 {
   std::list<int> l;
 
   l.push_front(3);
   l.push_front(2);
   l.push_back(4);
 
   l.pop_front();
   l.pop_back();
 
   std::cout << l.front() << std::endl;
   std::cout << l.back()  << std::endl;
 
   return 0;
 }

List

Comme pour tous les composants STL, il faut toujours se placer dans l'espace de nommage std::

 #include <iostream>
 #include <list>

 int main()
 {
   std::list<int> l;
 
   l.push_front(3);
   l.push_front(2);
   l.push_back(4);
 
   l.pop_front();
   l.pop_back();
 
   std::cout << l.front() << std::endl;
   std::cout << l.back()  << std::endl;
 
   return 0;
 }

List

Insère un élément dans la liste

 #include <iostream>
 #include <list>

 int main()
 {
   std::list<int> l;
 
   l.push_front(3);
   l.push_front(2);
   l.push_back(4);
 
   l.pop_front();
   l.pop_back();
 
   std::cout << l.front() << std::endl;
   std::cout << l.back()  << std::endl;
 
   return 0;
 }

List

Retire un élément de la liste

 #include <iostream>
 #include <list>

 int main()
 {
   std::list<int> l;
 
   l.push_front(3);
   l.push_front(2);
   l.push_back(4);
 
   l.pop_front();
   l.pop_back();
 
   std::cout << l.front() << std::endl;
   std::cout << l.back()  << std::endl;
 
   return 0;
 }

List

Accède à un élément de la liste

 #include <iostream>
 #include <list>

 int main()
 {
   std::list<int> l;
 
   l.push_front(3);
   l.push_front(2);
   l.push_back(4);
 
   l.pop_front();
   l.pop_back();
 
   std::cout << l.front() << std::endl;
   std::cout << l.back()  << std::endl;
 
   return 0;
 }

Vector

Utilisation des vecteurs

 #include <iostream>
 #include <vector>
 
 int main()
 {
   std::vector<int> v;
 
   v.push_back(3);
   v.push_back(4);
 
   std::cout << v[0] << std::endl;
 
   v.at( 1 ) = 5;
   std::cout << v.back() << std::endl;
  
   v.clear();
   return 0;
 }

Vector

Insère un élément dans le vecteur

 #include <iostream>
 #include <vector>
 
 int main()
 {
   std::vector<int> v;
 
   v.push_back(3);
   v.push_back(4);
 
   std::cout << v[0] << std::endl;
 
   v.at( 1 ) = 5;
   std::cout << v.back() << std::endl;
  
   v.clear();
   return 0;
 }

Vector

Accède au 1er élément

 #include <iostream>
 #include <vector>
 
 int main()
 {
   std::vector<int> v;
 
   v.push_back(3);
   v.push_back(4);
 
   std::cout << v[0] << std::endl;
 
   v.at( 1 ) = 5;
   std::cout << v.back() << std::endl;
  
   v.clear();
   return 0;
 }

Vector

Modifie le 2è élément

 #include <iostream>
 #include <vector>
 
 int main()
 {
   std::vector<int> v;
 
   v.push_back(3);
   v.push_back(4);
 
   std::cout << v[0] << std::endl;
 
   v.at( 1 ) = 5;
   std::cout << v.back() << std::endl;
  
   v.clear();
   return 0;
 }

Vector

Accède au dernier élément du vecteur

 #include <iostream>
 #include <vector>
 
 int main()
 {
   std::vector<int> v;
 
   v.push_back(3);
   v.push_back(4);
 
   std::cout << v[0] << std::endl;
 
   v.at( 1 ) = 5;
   std::cout << v.back() << std::endl;
  
   v.clear();
   return 0;
 }

Vector

Supprime tous les éléments

 #include <iostream>
 #include <vector>
 
 int main()
 {
   std::vector<int> v;
 
   v.push_back(3);
   v.push_back(4);
 
   std::cout << v[0] << std::endl;
 
   v.at( 1 ) = 5;
   std::cout << v.back() << std::endl;
  
   v.clear();
   return 0;
 }

Quelques méthodes communes

Vider le conteneur :
- void clear();
  appelle le destructeur pour chaque objet dans le conteneur
  désalloue la mémoire utilisée
Retourner le nombre d'éléments :
- int size();
Tester si le conteneur est vide :
- bool empty();

Itérateurs

C'est une généralisation de la notion de pointeur.
Il permet de parcourir en séquence les éléments d'un conteneur sans avoir à se préoccuper du type du conteneur.

 #include <vector>
 {
   std::vector<int> v;
   // 
  std::vector<int>::iterator it1 = v.begin();
  std::vector<int>::iterator it2 = v.end();
 }

Itérateurs

 #include <iostream>
 #include <list>
 
 int main()
 {
   std::list<int> liste;
 
   for (unsigned int i = 0; i < 10; i++) {
     liste.push_back(i);    
   }  
 
   std::list<int>::iterator it;  
   for (it = liste.begin(); it != liste.end(); ++it) {
    int i = *it;      
    std::cout << "i = " << i << std::endl;    
   }
   return (0);
 }

Itérateurs

Déclaration

 #include <iostream>
 #include <list>
 
 int main()
 {
   std::list<int> liste;
 
   for (unsigned int i = 0; i < 10; i++) {
     liste.push_back(i);
   }
 
   std::list<int>::iterator it;
   for (it = liste.begin(); it != liste.end(); ++it) {
    int i = *it;
    std::cout << "i = " << i << std::endl;
   }
   return (0);
 }

Itérateurs

1er élément

 #include <iostream>
 #include <list>
 
 int main()
 {
   std::list<int> liste;
 
   for (unsigned int i = 0; i < 10; i++) {
     liste.push_back(i);    
   }  
 
   std::list<int>::iterator it;  
   for (it = liste.begin(); it != liste.end(); ++it) {
    int i = *it;      
    std::cout << "i = " << i << std::endl;    
   }
   return (0);
 }

Itérateurs

Pointe après le dernier élément

 #include <iostream>
 #include <list>
 
 int main()
 {
   std::list<int> liste;
 
   for (unsigned int i = 0; i < 10; i++) {
     liste.push_back(i);    
   }  
 
   std::list<int>::iterator it;  
   for (it = liste.begin(); it != liste.end(); ++it) {
    int i = *it;      
    std::cout << "i = " << i << std::endl;    
   }
   return (0);
 }

Itérateurs

On incrémente l'itérateur

 #include <iostream>
 #include <list>
 
 int main()
 {
   std::list<int> liste;
 
   for (unsigned int i = 0; i < 10; i++) {
     liste.push_back(i);    
   }  
 
   std::list<int>::iterator it;  
   for (it = liste.begin(); it != liste.end(); ++it) {
    int i = *it;      
    std::cout << "i = " << i << std::endl;    
   }
   return (0);
 }

Itérateurs

On accède à l'élément par déréférencement

 #include <iostream>
 #include <list>
 
 int main()
 {
   std::list<int> liste;
 
   for (unsigned int i = 0; i < 10; i++) {
     liste.push_back(i);    
   }  
 
   std::list<int>::iterator it;  
   for (it = liste.begin(); it != liste.end(); ++it) {
    int i = *it;      
    std::cout << "i = " << i << std::endl;    
   }
   return (0);
 }

Choisir un conteneur

List :
- si on a besoin d'insérer ou de supprimer au milieu
- insertion en temps constant
- accès au n-ième élément en itérant depuis le 1er
Vector :
- si on a besoin d'accéder au n-ième élément
- insertion et suppression peuvent être coûteuses
- très efficace lorsqu'on a à parcourir le conteneur
Map :
- listes associatives
- listes maintenues triées lors de l'insertion de nouveaux éléments

Questions ?