STL
STL(Standard Template Library)
• Partie importante de la bibliothèque standard basée
sur les template
• Développée par HP puis Silicon Graphics
• Propose un grand nombre :
– de structures de données évoluées (tableaux, listes
chaînées, vecteurs, piles, …)
– d’algorithmes efficaces sur ces structures de données
(ajout, recherche, parcours, suppression, …)
STL(Standard Template Library)
• La STL propose trois types d’éléments :
– Les conteneurs (containers) de base ou évolués
(adaptators) permettent de stocker les données (
vecteurs, listes, piles, …)
– Les itérateurs permettent de parcourir les conteneurs
– Les algorithmes travaillent sur les conteneurs via les
itérateurs
STL(Standard Template Library
• Fichiers de la bibliothèque de STL
#include <vector> // vecteurs
#include <string> // chaînes de caractères
#include <list> // listes doublement chaînées
#include <set> // ensembles
#include <stack> // piles
#include <queue> // files
#include <map> // maps et multimaps
#include <iterator> // itérateurs, fonctions, adaptateurs
#include <algorithm> // algorithmes utiles (tri,…)
…
Conteneurs
• Un conteneur est un objet qui contient d’autres objets, d’où le
nom
• Il fournit un moyen de gérer les objets contenus (ajout,
suppression, parfois insertion, tri, recherche,…) ainsi qu’un
accès à ces objets
• Paramétré par le type des éléments qu’il contient ( à l’image
des patrons)
• Permet de représenter les structures de données les plus
répandues telles que les tableaux, les listes, les ensembles, les
piles,…
Conteneurs
• Différents types de conteneurs
– Conteneur simple
– Conteneur séquentiel stocke les éléments de manière
séquentielle et y accède de manière séquentielle ou
directement (selon le conteneur)
– Conteneur associatif associe une clé à chaque objet
stocké, la clé servant ensuite à accéder efficacement aux
objets
– Adaptateurs de conteneurs spécialisation de conteneur
Conteneurs
• Principaux conteneurs de la STL
– Les paires pair conteneur simple
– Les vecteurs (tableaux) vector conteneur séquentiel
– Les listes doublement chaînées list conteneur séquentiel
– Les tableaux dynamiques deque conteneur séquentiel
– Les ensembles ordonnés set conteneur associatif
– Les tables associatives ordonnées (tableaux
pouvant être indexés par autre chose que des
entiers, des chaînes de caractères, par exple) map conteneur assoc
– Les piles stack adaptateur de conteneur
– les files queue adaptateur de conteneur
Eléments de complexité
• Important de choisir la classe une classe fournie par la STL
cohérente avec son besoin
• Important de connaître la complexité des algorithmes : accès
(recherche) à une donnée, insertion d’une donnée, …
• Complexité
soit n – la taille d’un conteneur
– Un algorithme est dit linéaire ( en O(n) ) si son temps de calcul est
proportionnel à n
– Algorithme instantané ( O(1) )
– Algorithme logarithmique ( O log(n) )
– Algorithme polynomial ( O(n^k) )
– Algorithme exponentiel ( O(e(n) )
– …
Les vecteurs (vector)
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> v(5);
v[0]=1; // Accès direct à l’indice 0 pour affecter la valeur 1
v[1]=2; // Accès direct à l’indice 1 pour affecter la valeur 2
// augmente et diminue la taille
v.push_back(15); // ajoute 15 à la fin
v.push_back(16); // ajoute 16 à la fin
v.push_back(18); // ajoute 18 à la fin A l’exécution
v.pop_back(); // enlève le dernier élément et supprime 18 v[0] = 1
cout << “le vecteur contient “ << [Link]() << ”entiers \n“; v[1] = 2
for (int =0; i < [Link](); i++) v[2] = 0
cout << ”v[“ << i << ”] = “ << v[i] << endl; v[3] = 0
return(0); v[4] = 0
} v[5] = 15
v[6] = 16
Les vecteurs (vector)
• Observations
– Une case n’est accessible par l’opérateur “[]” que si elle a été allouée
au préalable (sinon erreur de segmentation)
– Ne pas perdre de vue qu’une réallocation mémoire est coûteuse en
terme de performance. Si la taille du vecteur est connue d’avance, le
créer avec cette taille
• Complexité
– Accès : O(1)
– Insertion ou suppression: O(n) sauf (en fin )
Les listes doublement chaînées (list)
#include <iostream>
#include <list>
using namespace std;
int main() {
list< int > L; // declaration similaire a celle d’un vecteur
// mais utilisation différente
L.push_back(5); // L={5}
L.push_back(4); // L={5,4}
L.push_front(3); // L = {3,5,4}
cout << "Tete de L : " << [Link]() << endl; // Tete de L : 3
cout << "Queue de L : " << [Link]() << endl; // Queue de L : 4
for(int i = 0 ; i < [Link]() ; i++){
cout << "[Link](" << i << ") : " << [Link](i); // Erreur
cout << "L[" << i << "] : " << L[i] << endl; // Erreur
}
return 0;
}
Les listes doublement chaînées (list)
• Complexité :
– Insertion en début ou fin : 0(1)
– Recherche : O(n) en général, O(1) pour le premier et le dernier maillon
Table associative (map)
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {
map <string, unsigned int> nbjoursMois;
nbjoursMois[”janvier”] = 31;
nbjoursMois[”fevrier”] = 28;
nbjoursMois[”mars”] = 31;
nbjours[”avril”] = 30;
cout << ” Janvier : ” << nbjoursMois[”janvier”] << endl;
cout << ” Fevrier : ” << nbjoursMois[”fevrier”] << endl;
return 0; Janvier : 31
} Fevrier : 28
Table associative (map)
• Complexité :
– Insertion : O(log(n))
– Recherche : 0(log(n))
Les itérateurs
• Un itérateur permet :
– de parcourir un conteneur
– d’accéder aux données contenues dans le conteneur
– et (éventuellement) de modifier les données
• Un itérateur peut être vu comme un pointeur sur un
élément du conteneur
• Deux types d’itérateurs :
– iterator ou const iterator parcours d’un conteneur du
début à la fin
– reverse_iterator ou const reverse iterator parcours dans
le sens inverse
Les itérateurs
• Utilisation générale d’un itérateur
– Déclaration d’un itérateur associé à un conteneur C
(vecteur, liste, …)
C::iterator it1;
C::reverse_iterator it2;
– Un itérateur iterator peut être initialisé grâce aux
méthodes :
• begin() retourne un itérateur pointant sur le premier élément
du conteneur
• end() retourne un itérateur pointant sur l’élément juste après le
dernier élément du conteneur
ou toutes autres méthodes retournant un itérateur sur le conteneur :
find(), …
Les itérateurs
– De la même manière, un itérateur reverse_iterator peut
être initialisé grâce aux méthodes :
• rbegin()
• rend()
• …
• Accéder à l’élément pointé par un itérateur it se fait de la
même manière que pour accéder à l’élément pointé par un
pointeur *it
Parcours d’un vecteur
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> v(5);
vector< int >::iterator it1;
vector< int >::reverse_iterator it2;
int i = 0;
// --> initialisation du début a la fin du vecteur
for(it1 = [Link]() ; it1 != [Link]() ; it1++)
(*it1) = (i++); // affectation de (i++) a l’element pointe par it1,
// c’est-a-dire, a v1[i]
// --> parcours dans le sens inverse
for(it2 = [Link]() ; it2 != [Link](); it2++)
cout << "v1[" << i-- << "] = " << (*it2) << endl;
return 0.
}
Les listes doublement chaînées (list)
#include <iostream>
#include <list>
using namespace std;
int main() {
list< int > L; // declaration similaire a celle d’un vecteur
// mais utilisation différente
L.push_back(5); // L={5}
L.push_back(4); // L={5,4}
L.push_front(3); // L = {3,5,4}
cout << "Tete de L : " << [Link]() << endl; // Tete de L : 3
cout << "Queue de L : " << [Link]() << endl; // Queue de L : 4
for(int i = 0 ; i < [Link]() ; i++){
cout << "[Link](" << i << ") : " << [Link](i); // Erreur
cout << "L[" << i << "] : " << L[i] << endl; // Erreur
}
return 0;
}
Parcours de la liste
#include <iostream>
#include <list>
using namespace std;
int main() {
list< int > L; // declaration similaire a celle d’un vecteur
// mais utilisation différente
L.push_back(5); // L={5}
L.push_back(4); // L={5,4}
L.push_front(3); // L = {3,5,4}
cout << "Tete de L : " << [Link]() << endl; // Tete de L : 3
cout << "Queue de L : " << [Link]() << endl; // Queue de L : 4
int i =0;
list <int>::iterator it1;
list <int>::reverse_iterator it2;
for(it1 = [Link]() ; it1 != [Link]() ; it1++)
cout << ”L(" << i++ << “) : " << *it1 << endl; // 3 5 4
Parcours de la liste
for(it2 = [Link]() ; it2 != [Link]() ; it2++)
cout << ”L(" << i++ << “) : " << *it2 << endl; // 4 5 3
return 0;
}
Parcours de la table associative (map)
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {
map <string, unsigned int> nbjoursMois;
map <string, unsigned int>::iterator it;
nbjoursMois[”janvier”] = 31;
nbjoursMois[”fevrier”] = 28;
nbjoursMois[”mars”] = 31;
//…
cout << ”La table contient ” << [Link]() << ”elements ” << endl;
for (it=[Link](); it != [Link](); it++)
cout << it->first << ” \t” << it->second;
cout << ”Nombre de jours du mois de janvier : ” << [Link](”janvier”) ->
second << endl;
return 0;
}
Les algorithmes de la stl
• La STL offre un ensemble d’algorithmes utilisables sur les
conteneurs, via les itérateurs.
• Les principaux algorithmes sont :
– les algorithmes numériques minimum, maximum, sommes
partielles, accumulations, produits, ...)
– les algorithmes de tri quick-sort
– les algorithmes modifiant les conteneurs remplissage, copie,
échanges, union
– les algorithmes ne modifiant pas les conteneurs recherche,
applications de fonctions, inclusion, ...
Exemples d’algorithmes sur un vecteur
#include <iostream>
#include <vector>
#include <numeric> // Utilisation des algorithmes numériques
#include <algorithm> // Utilisation des algorithmes de tri
using namespace std;
int main() {
vector<int> v(8);
vector< int >::iterator it1;
int i=1;
for(it1 = [Link]() ; it1 != [Link]() ; it1++)
(*it1) = (i++);
int sum = accumulate([Link](), [Link](), 0); // calcul de la somme des éléments
sort([Link](), [Link]()); // tri des éléments
for(it1 = [Link]() ; it1 != [Link]() ; it1++)
cout << (*it1) << ” ” ;
return 0;
}
