Embed Size (px)
Citation preview
Structures de donnéesIFT-2000
Abder AlikacemAbder Alikacem
Standard Template library
Édition Septembre 2009 Département d’informatique et de génie logiciel
Plan
Description généraleConteneurs
• Conteneurs séquentiels• Vector, list, deque
• Conteneurs associatifs• Set, map
• Adaptateurs• Stack, queue
ItérateursAlgorithmes
• Algorithmes• Foncteurs• Adaptateurs de fonctions
STL : Standard Template Library
La STL est une bibliothèque de C++ qui permet de mettre en œuvre d’autres structures de données plus complexes et de faciliter également l’écriture de programmes. En quelques sortes, cette bibliothèque propose des algorithmes clés en main pour beaucoup de problèmes de programmation. Étant donné la complexité des programmes écrits en C++, à chaque fois que cela est possible, il recommandé d’utiliser des STL.
Facteurs de qualité des logiciels :
• Fiabilité : écrite par des spécialistes (Andrew Koenig)• Réutilisabilité : portabilité• Compréhensabilité et facilité de maintenance
=> EFFICACITE
Exemple :Fusionner deux listes en les triant et placer le résultat dans un fichier se code en deux lignes.
Développer rapidement des applications en assemblant des briques des classes génériques.
STL : Standard Template Library
STL : Standard Template Library
• Il s’agit donc d’une bibliothèque générique qui fournit des solutions pour gérer un ensemble de données en utilisant des algorithmes efficaces.
• Du point de vue du programmeur, STL fournit un groupe de classes répondant à divers besoins.
• Tous les composants de STL sont des templates• Une STL est développée selon les axes suivants :
conteneurs – itérateurs - algorithmes
STL : Standard Template Library
Il existe deux grandes catégories de conteneurs :• Les séquences élémentaires (appelées aussi stockages élémentaires). Les dérivées des séquences élémentaires (appelées aussi types abstraits de données : TDA)• Les conteneurs associatifs (clé,valeur)
Pour comprendre les conteneurs proposés dans la STL, on doit donc appréhender à la fois les structures de données, les algorithmes associés et les itérateurs.
http://www.sgi.com/tech/stl/
STL : Standard Template Library
• Conteneurs: En C++, une classe contenant un ensemble d’éléments d'un certain type est appelée conteneur. Ce sont donc eux qui contiendront les informations que l’on veut stocker.
• Itérateurs: utilisés pour parcourir les items qui se retrouvent dans les conteneurs, ils jouent un peu le rôle de pointeurs sur des éléments d’un conteneur.
• Algorithmes: utilisés pour faire des traitements sur les éléments qui se retrouvent dans les conteneurs.
STL : Standard Template Library
Algorithmes
Conteneurs
Conteneurs Conteneurs
ItérateursItérateurs
Itér
ate
urs
Les algorithmes sont indépendants
du type de données stockées.
Il s’agit ainsi de connecter des
algorithmes à des structures
de données, par le biais de
connecteurs.
Les conteneurs
Les conteneurs contiennent les structures de données linéaires telles que les listes, piles, tables, etc, utilisées pour stocker des données. L’utilisation des templates dans une STL permet l’adaptation à tous les types de données. Les conteneurs les plus utilisés sont :
vector Tableaulist Liste doublement chaînée slist List simplement chaînéequeue File- FIFO (first-in, first-out) deque Tableau avec des opération efficaces d’insertion
et de suppression aux extrémitésset Ensemble avec des éléments distinctsstack Pile - LIFO (last in, first out) map Table de hachagemultiset Comme l’ensemble mais autorise des valeurs
répétéesmultimap Comme la table mais autorise des clefs
multiples
Les méthodes des conteneurs
push_front Insère un élément avant le premier (non disponible pour vector)
pop_front Supprime le premier élément (non disponible pour vector)
push_back Insère élément après le dernier
pop_back Supprime le dernier élément
empty Booléen indiquant si le conteneur est vide
size Retourne le nombre d’éléments du conteneur
insert Insère un élément à une position donnée
erase Supprime un élément à une position donnée
clear Supprime tous les éléments
resize Redonne une taille au conteneur
front Retourne l’adresse du premier élément
back Retourne l’adresse du dernier élément
remove Supprime le premier élément (non disponible pour vector)
sort Trier
reverse Ordre inverse
find Trouver un élément
swap échange deux éléments de deux vecteurs
Les conteneurs
Les conteneurs sont classés suivant deux types:
• séquentiels: les éléments sont ordonnés et leurs positions sont indépendantes des caractéristiques des éléments eux-mêmes
• associatifs: les éléments sont triés selon un certain critère; la position d’un élément est un endroit identifié par un « nom » et peut dépendre de la valeur de l’élément
Conteneurs séquentiels
• vector: tableau dynamique qui ne se remplit qu’à la fin • deque: tableau dynamique qui peut s’étendre par les deux
extrémités• list: liste doublement chaînée
on verra plus loin que les piles et les files sont définies en fonctiondes ces trois conteneurs
Une séquence est un conteneur dans lequel les éléments sont organisés linéairement (il y a un premier, un suivant … , un dernier). On distingue trois séquences:
Les vecteurs (vector)
Les conteneurs vector et deque fournissent l’accès aux éléments à travers l’indexation [ ]. Ceci permet un accès direct à un élément par le biais d’un indice.
Les vecteurs font référence aux tableaux dynamiques. Les éléments sont insérés à la fin du tableau. La déclaration vector<int> unEnsemble; crée un tableau d’entiers. Dans ce cas, le constructeur par défaut nous retourne un tableau vide. Les méthodes les plus importantes sont :
- size( ) ; empty( ) ; clear( ) ; resize( ) ;- front( ) ; back( ) ;- push_front(valeur); push_back(valeur);- pop_front( ); pop_back( );
Les opérateurs les plus utilisées sont : = , = = , < , [ ].
Avantages : ajout/suppression à la fin en O(1) ; accès direct aux éléments en O(1).
Inconvénients : l’ajout et la suppression est O(n) en général.
Les vecteurs (vector)
• Les vecteurs sont donc des listes implémentées à l'aide de tableaux. Ils remplacent avantageusement les tableaux standards du C car
leur taille est implicite et peut être redéfinie. De plus, on peut affecter un vecteur dans un autre à l'aide de l'opérateur d'affectation. On peut définir un vecteur d'entiers de la façon suivante:
vector<int> monvecteur(100);
• L’insertion d’un élément à la fin est très rapide (sauf dans certains cas que l’on verra plus loin)
• L’insertion au milieu est très lente parce qu’elle exige un déplacement de tous les éléments qui sont stockés après la position d’insertion
Les vecteurs (vector)
Exemple 1
vector<int> v(3); // Déclarstion d’un vector de 3 éléments.
v[0] = 7; v[1] = v[0] + 3; v[2] = v[0] + v[1]; // v[0] == 7, v[1] == 10, v[2] == 17
reverse(v.begin(), v.end()); // v[0] == 17, v[1] == 10, v[2] == 7
Les vecteurs (vector)
Exemple 2
int main(){ vector<int> unTableau;
for (int i = 1; i < 10; ++i) { unTableau.push_back(i); }
for (int j = 0; j < unTableau.size(); ++j) { cout << unTableau[j] << ' '; }
cout << endl; return 0;}
Les vecteurs (vector)
Exemple 3
#include <vector>#include <iostream>
using namespace std;
int main ( ) {
vector<int> vect1, vec2(3);
vec1.push_back(10) ; vec1.push_back(12) ; vec1.push_back(20) ; vec2[0] = 1; vec2[2] = 10; vec2[3] = 20; cout << “Les deux vecteurs ” cout << (vec1 != vec2 ? “ sont différents “ : “ sont identiques “) ;
return 0 ;}
Les vecteurs (vector)
Exemple 4 # include <vector.h># include <iostream.h>
using namespace std;
int main (void) {
vector<int> v;
V1.push_back(1); V1.push_back(2);V1.push_back(3);vector<int> v2(3); v2[0] = 1, v2[1] = 2; v2[2] =3;
if (v1==v2) cout << " OK " ;
else cout << " ???? (stupeur) ";
return 0;
}
Les vecteurs (vector)
Exemple 5 Un tableau à deux dimensions est un vecteur de vecteurs. Le constructeur de vecteurs peut initialiser la taille du tableau et aussi la valeur initiale.
#include <iostream>#include <vector>using namespace std;int main(){ // Déclarer un tableau à deux dimensions et initialiser à 0 vector< vector<int> > vI2Matrix(3, vector<int>(2,0)); vI2Matrix[0][0] = 0; vI2Matrix[0][1] = 1; vI2Matrix[1][0] = 10; vI2Matrix[1][1] = 11; vI2Matrix[2][0] = 20; vI2Matrix[2][1] = 21; cout << "Itérer par indice:" << endl; for(int ii=0; ii < 3; ii++) { for(int jj=0; jj < 2; jj++) { cout << vI2Matrix[ii][jj] << endl; } }return 0;}
Les vecteurs (vector)
Fonction Description
vector<T> v; Déclaration d’un Vector de type "T".
vector<T> v(size_type n);Déclaration d’un Vector de type "T" et de taille "n".
vector<T> v(size_type n,const T& t);Déclaration d’un Vector de type "T" et de taille "n" contenant la valeur "t".
Les vecteurs (vector)
Exemple 6 #include <iostream>#include <vector>using namespace std;
int main(){ // Vecteur de 3 éléments initialisé à 0 vector<int> vI1Matrix(3,0); // Vecteur de 4 éléments contenant chacun un autre vecteur // vecteur vI1Matrix qui a été initialisé à 0 vector< vector<int> > vI2Matrix(4, vI1Matrix); // Vecteur 5 éléments contenant chaucn un vecteur de dimension deux vector< vector< vector<int> > > vI3Matrix(5, vI2Matrix);//Ou alors si on veut en une seule déclaration : //vector< vector< vector<int> > > vI3Matrix(2, vector< vector<int> > (3, vector<int>(4,0)) ); for(int kk=0; kk<4; kk++) { for(int jj=0; jj<3; jj++) { for(int ii=0; ii<2; ii++) { cout << vI3Matrix[ii][jj][kk] << endl; } } return 0; }
Les vecteurs – Taille et capacité
Il est important de distinguer la taille et la capacité d’un vector car il maintient à l’interne un tableau qui n’est pas nécessairement rempli
• Taille: nombre d’éléments effectivement contenus dans le tableau interne
• Capacité: taille du tableau interne. Elle est augmentée lorsqu’on veut insérer un nouvel item et que le tableau est plein
Les vecteurs – Capacité
• Initialement la capacité est 0• Aussitôt qu’on ajoute un premier élément, on alloue un
tableau de taille 1 (capacité = 1)• Lorsque la capacité est réajustée, il faut allouer un nouveau
tableau et copier les éléments dans ce nouveau tableau• La réallocation est donc coûteuse• On peut fixer la capacité du vecteur:
vector<int> unTableau;unTableau.reserve(10);
• Il est important de noter que la réallocation invalide tout pointeur, référence ou itérateur sur des éléments du vector avant réallocation
Les vecteurs – Capacité
• Dans la plupart des implémentations, la capacité est doublée chaque fois qu’elle doit être augmentée
• Dans .NET on ajoute un nombre de cellules qui croît à chaque réallocation selon la suite de Fibonacci
• Dans tous les cas, le principe est le même: plus le tableau est grand, plus il sera agrandi lors d’un réallocation
• Pourquoi? Tout simplement parce plus il est grand, plus l’allocation coûte cher (beaucoup d’éléments à recopier). On veut donc diminuer le nombre de ces réallocations.
• Bien sûr, cela a pour effet de causer une éventuelle sur-utilisation de mémoire
Les vecteurs – Capacité
int main(){ vector<int> unTableau; cout << "capacite initiale: " << unTableau.capacity() << endl;
for (int i = 1; i < 10; ++i) { unTableau.push_back(i); cout << "capacite: " << unTableau.capacity() << endl; } for (int j = 0; j < unTableau.size(); ++j) { cout << unTableau[j] << ' '; } cout << endl; return 0;}
Exemple 7
Les vecteurs
Principales opérations (n est la dimension du vecteur)
•Ajout ou suppression d ’un élément en fin de vecteur sans redimensionnement 0(1) push_back
• Ajout ou suppression d ’un élément en fin de vecteur avec redimensionnement 0(n) push_back
• Ajout ou suppression d ’un élément au milieu du vecteur 0(n)
Les listes (list)
• Liste doublement chaînée• Un élément pointe sur son prédécesseur et son successeur
PRÉCÉDENT
SUIVANT
Objet T
PRÉCÉDENT
SUIVANT
Objet T
PRÉCÉDENT
SUIVANT
Objet T
Les listes sont des séquences ordonnées d‘éléments d'un certain type. Elles sont implémentées à l'aide de listes doublement chaînées:
On peut définir une liste de 100 entiers de la façon suivante:
list<int> maliste(100);
Les listes (list)
Les méthodes les plus importantes sont :
- size( ) ; empty( ) ; clear( ) ; resize( ) ;- front( ) ; back( ) ;- push_fron(valeur); push_back(valeur);-pop_front( ); pop_back( ); remove (valeur);
Avantages : ajout/suppression se font en O(1)Inconvénients : l’accès aux éléments se fait en O(n).
Les listes (list) - Caractéristiques
• Pas d’accès direct à un élément au milieu de la liste• On peut insérer ou retirer un élément n’importe où à un coût
constant• L’insertion ou le retrait d’élément n’invalidera jamais les pointeurs,
références et itérateurs sur d’autres éléments, comme c’est le cas lors de réallocation avec les vectors et les deques
Les listes (list) - Caractéristiques
Plusieurs fonctions pour déplacer, insérer ou retirer des éléments(efficaces parce qu’elle ne font que réaffecter des pointeurs)
Exemples
– unique() pour éliminer les duplications d’éléments consécutifs– reverse()
• beaucoup d’autres
Les listes (list)
Exemple 1#include <list>#include <stdio.h>
int main ( ) {
list<int> liste1 ; liste1.push_back(20) ; liste1.push_back(12) ; liste1.push_back(15) ;
liste1.sort( ) ; liste1.reverse() ;
cout << “le début de liste est “<< liste1.front cout << “ la fin de liste est “<<liste1.back ;
return 0 ;}
La liste utilisée ci-dessous est en fait doublement chaînée. Si on désire une liste simplement chaînée, remplacer list par slist.
Les listes (list)
Exemple 2
int main(){ list<char> uneListe; for (char c = 'a'; c <= 'z'; ++c){ uneListe.push_back(c); } while (!uneListe.empty()){ cout << uneListe.front() << ' '; uneListe.pop_front(); } cout << endl; return 0;}
Les listes (list)
Exemple 3
bool voyelle(char c){ return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u');}
Les listes (list)
Exemple 3 suite int main(){ list<char> uneListe;
for (char c='a'; c<='z'; ++c){ uneListe.push_back(c); } uneListe.remove_if(voyelle); uneListe.reverse(); while (!uneListe.empty()){ cout << uneListe.front() << ' '; uneListe.pop_front(); } cout << endl; return 0;}
Les listes (list) Exemple 4
#include <list>using namespace std; list<int> list1; // Ajoute des valeurs à la fin de la liste, initialement vide. // la fonction membre "push_back" ajoute un élément à la fin de la liste int value1 = 10; int value2 = -3; list1.push_back (value1); list1.push_back (value2); list1.push_back (5); list1.push_back (1); // Imprime les éléments de la liste Output cout << endl << "List values:" << endl; // Répéter aussi longtemps qu’il reste des éléments dans la liste while (list1.size() > 0) {
int value = list1.front(); // Output la valeur the value. cout << value << endl; // Supprime l’élément du début de la liste. list1.pop_front();
}
Les listes (list)
Exemple 5#include <list>#include <vector>using namespace std;
int main() {
list<int> l(4,0); // l vaut 0::0::0::0::[] vector<int> v(10,1); // v vaut
[1,1,1,1,1,1,1,1,1,1,1]
vector<int>::iterator i =copy(l.begin(),l.end(),v.begin());
copy(v.begin(),i, ostream_iterator<int>(cout," "));
copy(i,v.end(), ostream_iterator<int>(cout," ")); return 0;}
Liste (list) et vecteur (vector)
Fonctions communes à vector et list
void push back(const Object& x):Ajoute x à la fin du conteneur. Notons que si un objet est ajouté à la fin d'un vecteur alors sa taille est automatiquement augmentée.void pop back(): Enlève le dernier objet du conteneurconst Object& back() const: Retourne l'objet situé µa la fin du conteneurconst Object& front() const: Retourne l'objet situé au début du conteneur
Pour les conteneurs de type list seulement
void push front(const Object& x): Ajoute x au début du conteneurvoid pop front(): Enlève le premier objet du conteneur
Pour les conteneurs de type vector seulement
Object& operator[] (int i): Retourne l'objet situé µa la position i du conteneurObject& at (int i): Comme le précédent mais avec un contrôle de la plagedes valeurs. Déclenche une exception out of range lorsqu'un indice es tincorrect.void resize( int nouvelle taille): Redéfini la taille du conteneurint capacity() const: Retourne la capacité du conteneurvoid reserve(int nouvelle capacite): Redéfini la capacité du conteneu
Double end queue (deque)
• Tableau dynamique• Peut s’étendre dans les deux sens• La fonction push_back() pour ajouter à la fin• La fonction push_front() pour ajouter au début
Double end queue (deque)
Une deque se comporte comme un vecteur à la différence que l’ajout et la suppression d’une valeur au début de la structure se fait en O(1).
Cette structure est intéressante dans le cas où les insertions et suppressions se font aux extrémités et où on a besoin d’un accès efficace aux éléments. Les méthodes les plus importantes sont comme dans vector. Exemple:
#include <deque>#include <iostream> using namespace std;int main ( ) { deque<int> DD1, DD2(3); DD1.push_back(1); DD1.push_back(2); DD1.push_back(3); DD2[0] =1; DD2[1]=2; DD2[3]=3; cout << "Deque " ; (DD1 == DD2) ? cout << "identiques" : cout <<"différents"; cout << endl; return 0 ; }
Deque - Implémentation
• Le tableau est divisé en blocs• Le premier bloc s’étend dans un direction et le
dernier, dans l’autre direction• Lorsqu’un bloc est plein, on en crée un nouveau
Deque - Implémentation
Premierélément
Dernierélément
Deque - Caractéristiques
• L’accès est plus lent qu’avec un vecteur, parce qu’il faut d’abord identifier le bloc, et ensuite la position dans le bloc
• Pas de fonction pour accéder ou fixer la capacité• Un bloc peut être désalloué lorsque le deque diminue• Pas besoin de recopier le tableau lorsqu’il y a réallocation• Les itérateurs ne peuvent pas être des pointeurs ordinaires, puisqu’il
faut parfois passer d’un bloc à un autre• Tout comme avec les vectors, l’insertion ou la suppression
d’éléments au milieu est très lente
STL - Les containeurs séquentiels
Vector- extensible et relocalisable- accès aléatoire par index en O(1)- insertions et retraits à la fin en O(1)- insertions et retraits lents au milieu
List ( liste circulaire doublement chaînée )- insertions et retraits n’importe où en O(1)- accès au début et à la fin en O(1)- accès lent aux autres éléments
Deque ( Double Ended Queue = tampon circulaire dynamique )- exactement pareil que Vector pour la complexité- pas d’insertion au milieu- bon compromis vitesse d’accès / souplesse du remplissage
Synthèse
STL - Les containeurs séquentiels
Synthèse
Méthodes disponibles sur tout conteneur :
• Gestion de la taille du conteneur
- size_type size() const;
- size_type max_size() const;
- bool empty() const;
- void resize(size_type, T c=T());
• Accès aux éléments :
- const_reference front() const;
- const_reference back() const;
STL - Les containeurs séquentiels
Synthèse
Méthodes disponibles sur tout conteneur :
• Insertion des éléments
- void push_back(const T&);appel du constructeur par copie
- .. . insert (...); avec un itérateur
• Suppression d ’éléments :
- void pop_back();
- .. . erase (...); avec un itérateur
Echange d ’éléments :
- void swap(sequence<T>&);
STL - Les containeurs séquentiels
Synthèse
Méthodes disponibles sur tout conteneur :
Echange d ’éléments :
- void swap(sequence<T>&);
Sequence est à remplacer par vector, list ou deque.
Echange this avec les éléments du conteneur passé en argument.
Pour échanger des éléments de séquences différentes, il faut passer à une version avec itérateur
Les séquences : types abstraits
Les classes (conteneur) :
- pile : stack
- file d ’attente : queue
- file d ’attente prioritaire : priority_queue
A partir des séquences de base, on dérive trois types abstraits :
pile, file d ’attente et file d ’attente prioritaire.
La pile (stack)
L’attribut privé est un deque. Les méthodes les plus importantes sont :
push(valeur), pop( ), top( ), empty() et size()
#include <iostream>#include <stack>using namespace std;
int main(){ stack<int> EntStack; int Num; cout << "introduire un entier (ou CTRL z pour terminer): "; cin >> Num; while(!cin.fail()) { EntStack.push(Num); cout << "Introduire un entier (or CTRL z pour terminer): "; cin >> Num; } cout << endl << "Les nombres dans l’ordre inverse sont comme ci-dessous" << endl; while (!EntStack.empty()) { Num = EntStack.top(); EntStack.pop(); cout << Num << endl; } return 0; }
La file (queue)
Cette structure dérive de deque, avec en plus les méthodes push(valeur) et pop( ).
Adaptateurs
• Uitilisé lorsqu’on veut redéfinir une interface pour une classe déjà existante
• On définit les méthodes de la nouvelle classe en fonction de celles de la classe de base
• On peut implémenter un adaptateur par agrégation, en utilisant comme attribut une instance de la classe de référence
Exemple: la pile (stack) dans la bibliothèque STL
La Pile (stack) - Implémentation
Voici comment la classe pourrait être implémentée:
template <class T>class stack {
public:stack(const deque<T> & c = deque<T>());
bool empty() const { return cont.empty(); }size_type size() const { return cont.size(); }void push(const T & x) { cont.push_back(x); }void pop() { cont.pop_back(); }T & top() { return cont.back(); }const T & top() { return cont.back(); }
// ... autres méthodes protected:
deque< T > cont;};
La Pile (stack) - Extension
• Remarquez que le conteneur caché dans la pile est déclaré protected• On peut donc facilement étendre la classe• Voici comment on peut y ajouter une méthode pour vider la pile:
template <class T>class Pile : public stack< T > {
public:Pile() {}~Pile() {}
void vider(){ while (!empty())
pop();};
}
STL – L’adaptateur de conteneurs
Pour résumer :Adaptateur < Conteneur < Truc > >
Stack ( la pile )Peut être implémentée avec Vector, List, DequePrincipe LIFO : push et pop à la même extrémité
Queue ( la file )Peut être implémentée avec List, DequePrincipe FIFO
Priority_queue ( la file par priorité )Dépend d’une fonction de comparaison:priority_queue< Conteneur < Truc > , fcomp < Truc > >
Conteneurs associatifs
Contrairement aux séquences, les conteneurs associatifs peuvent identifier leurs éléments par la valeur d ’une clé. Cette clé a parfois pour valeur une partie de la valeur de l ’élément.
Ces conteneurs sont particulièrement adaptés dans des applications où l ’on doit rechercher des éléments connaissant leur clé.
Un conteneur associatif offre la possibilité de rechercher rapidement les éléments mémorisés par leur clé.
Conteneurs associatifs
Ces conteneurs sont « paramétrés » avec le type de la clé correspondant. .
Opérations sur les clés :
recherche : find (complexité logarithmique)
Comptage selon la clé : count
On doit avoir une relation d ’ordre total sur les clés
Conteneurs associatifs
• Les éléments sont toujours ajoutés en respectant un ordre établi selon un critère précis
• Nous nous intéresserons à deux types de conteneur associatif:
• set: les éléments sont triés et ne peuvent apparaître qu’une seule fois
• map: les éléments sont des paires clé/valeur et sont triés en fonction de la clé; chaque clé ne peut apparaître qu’une seule fois
• Il existe des versions (multiset et multimap) qui permettent les répétitions
Ensembles (set)
• À moins d’indication contraire, les éléments sont ordonnés en utilisant l’opérateur < par défaut
• Il faut donc que cet opérateur soit défini pour le type d’objet qui est stocké dans le set
• Normalement implémenté en un arbre équilibré, ce fournit donc un algorithme efficace pour la rercherche d’une valeur
• Nous savons que pour rechercher un élément dans un conteneur, il faut pouvoir tester l’égalité, or il n’est pas nécessaire de définir l’opérateur == pour l’utilisation d’un set
• La raison pour cela est que la comparaison d’un élément x recherché est comparé avec un élément y du set de la manière suivante:
if (! (x < y || y < x))
Ensembles (set)
On suppose que chaque valeur de l’ensemble est unique. Les méthodes les plus importantes sont :
- size ( ); empty ( ); - count(elem): retourne le nombre d’occurrences de l’élément dans le set (qui, évidemment, peut être supérieur à 1
seulement dans le cas d’un multiset)- find(elem): retourne la position de la première occurrence de l’élément dans le set (ou multiset)- insert(elem) : insère un nouvel élément et la valeur de retour dépend de si on a affaire à un set ou un multiset- erase(elem) : retire toutes les occurrences de l’élément et retourne le nombre d’éléments retirés- clear() : vide le conteneur
Les opérateurs les plus utilisés sont: = , = = , < , [ ]
Ensembles (set)
• La fonction insert(elem) retourne un objet du type suivant:pair< iterator, bool >
• Ceci représente une paire dont le premier item est un itérateur qui pointe à la position de l’élément ajouté
• Le second item est true si l’insertion a pû être effectuée (c’est-à-dire que l’élément n’existait pas déjà)
Ensembles (set)
• Contrainte importante: on ne peut pas modifier directement la valeur d’un élément parce que cela pourrait affecter l’ordre:
il faut d’abord le retirer et ensuite le remplacer par un nouvel élément avec la nouvelle valeur.
• Pas d’accès direct aux éléments, il faut utiliser des itérateurs.
• La complexité de toutes les opérations est en O(n) ; n étant le nombre d’éléments dans l’ensemble. Par ailleurs, en interne, les éléments sont tous rangés dans l’ordre croissant.
Ensembles (set)
Exemple 1
#include <set> #include <iostream> using namespace std;
int main( ) { set<int> Ens;
Ens.insert(10); Ens.insert(20); Ens.inser(14) ; Ens.erase(10) ;
cout << “le cardinal de l’ensemble Ens est “ << Ens.size() ;
return 0 ;}
Ensembles (set)
Exemple 2
#include <set>
set<int> unEnsemble;
unEnsemble.insert(3);
unEnsemble.insert(1);
unEnsemble.insert(5);
unEnsemble.insert(4);
unEnsemble.insert(1);
unEnsemble.insert(6);
unEnsemble.insert(2);
4
2 6
1 3 5
Dictionnaire (map)
• Les éléments sont une paire formée d’une clé jumelée à une valeur• Les éléments sont triés selon la clé• Chacune des clés ne peut exister qu’une seule fois (mais peut être
répétée dans un multimap)• Contrairement aux sets, on peut accéder directement aux éléments
#include <map>
map<string, float> coll;
coll["VAT"] = 0.15; // VAT est la clé
coll["Pi"] = 3.1416;
coll["an arbitrary number"] = 4983.223;
coll["Null"] = 0;
Map - Caractéristique
• L’indice utilisé pour identifier un élément est la clé• Le type d’un élément de map est une paire
pair < cont Key, T > où Key est le type de la clé, et T le type des items contenus
dans le map
• Tout comme le set, le map fournit les méthodes count(clé) et find(clé)
• Attention: Si on accède en utilisant une clé pour laquelle il n’y a aucun élément, un nouvel élément est automatiquement inséré avec cette clé, en utilisant le constructeur par défaut pour l’initialiser
Map - Caractéristique
• On ne peut pas modifier une clé contenue dans le map, mais on peut modifier l’item qui lui est associé
• Pour retirer un élément, il suffit d’appeler la méthode erase(cle), qui élimine toutes ses occurrences et retourne le nombre d’éléments retirés
• Il existe aussi une méthode insert(elem), mais qu’on n’a pas besoin d’utiliser en général (il est important de noter que elem dans ce cas est une paire qui contient une clé et son item associé)
• Ne pas oublier, lorsqu’on parcourt un map avec un itérateur, que celui-ci pointe sur une paire
Set et map
La classe set peut être vu comme un cas particulier de la classe map où les deux composantes d'une paire sont identiques. On utilise un set lorsque la clef est la seule information qui nous intéresse.
template<class Clef>class set{
public:typedef Clef value_type;typedef Clef key_type;iterator begin();iterator end();iterator find(const key_type_type& k);pair<iterator, bool> insert(const value_type& val);void erase(iterator pos);int erase(const key_type& k);void clear();// autres membres
};
On remarque que la définition des classe set et map sont similaires. Laprincipale différence est l'absence de l'opérateur d'indiçage dans la classe set.
template<class Clef, class Valeur>class map{
public:typedef Clef key_type;typedef Valeur mapped_type;typedef pair<const Clef,Valeur> value_type;iterator begin();iterator end();mapped_type& operator[] (const key_type& k);iterator find(const key_type& k);pair<iterator, bool> insert(const value_type& val);void erase(iterator pos);int erase(const key_type& k);void clear();// autres membres
};
Multimap et multiset
Les multimap et les multiset sont similaires aux classes map et set sauf que plusieurs éléments peuvent posséder la même clef.
Les fonctions membres suivantes sont aussi disponibles pour les classes set et map mais sont surtout utiles pour les multiset et les multimap.
iterator lower_bound(const key_type& k);iterator upper_bound(const key_type& k);pair<iterator,iterator> equal_range(const key_type& k);
La fonction lower(k) retourne un itérateur pointant sur le premier eléments possédant la clef k. La fonction upper(k) retourne un itérateur vers le premier élément dont la clef est supérieure à k.
Dans les deux cas, si l’élément recherché est inexistant, l'iterateur end() est retourné. Finalement, la fonction equal_range(const clef& k) retourne la paire d'itérateurs (lower(k), upper(k)).
Multimap et multiset
L'exemple suivant illustre comment afficher de façon ordonnée tousles éléments de m possédant la clef s.
void afficher(multimap<string,int>& m, string s){
typedef multimap<string,int>::iterator MI;pair<MI,MI> g=m.equal_range(s);for(MI p=g.first; p!=g.second; ++p)cout<<p->Elem<<endl;
}
STL - Les containers associatifs
Set ( liste triée )- Chaque élément doit être unique ( pas de doublons )- accès aléatoire par clé ( l’objet lui-même est la clé )
Multiset - Un ‘set’ qui permet les doublons
Map ( association clé / élément )- une clé pour un élément ( pas de doublons )- accès aléatoire par clé
Mulimap- Un ‘map’ ou les éléments peuvent être multiples pour une clé
Synthèse
Conteneurs - Requis
L’élément qui sera inclus dans un conteneur doit posséder:
• constructeur de recopie• opérateur =• destructeur• possiblement, un constructeur par défaut• possiblement, un test d’égalité (opérateur ==)• possiblement, un critère d’ordre (operateur < et autres)
Conteneurs – Remarques supplémentaires
• Tous les conteneurs ont un attribut size_type, qui est en fait un entier non signé pour représenter le nombre d’items dans le conteneur
• Tous les conteneurs ont aussi un attribut value_type, qui mémorise le type des entités qu’il contient
Les itérateurs
Ils servent de lien entre les conteneurs et les algorithmes car permettant d’accéder aux informations de la même manière.
Un itérateur peut être vu comme un pointeur sur un élément d’un conteneur. Par définition donc, un itérateur permet de récupérer une donnée pour la manipuler et de passer à la suivante pour mettre en place l’itération. Par ailleurs, chaque conteneur fourni un type d’itérateur.
Exemple
le type list<int> donne un itérateur de type :
list<int> :: iterator.
Tous les conteneurs offrent les mêmes fonctions de basepermettant aux itérateurs d’accéder aux éléments
begin() Retourne un itérateur pointant au premier élément du conteneur
end() Retourne un itérateur pointant après le dernier élément du conteneur
size() Retourne le nombre d’éléments présents dans le conteneur
Les itérateurs
Les itérateurs
• L'itérateur est donc une généralisation des pointeurs. Il permet de parcourir en séquence les éléments d'un conteneur.
• Hiérarchie des itérateurs:
EcritureLecture
Forward
Bidirectionnel
Accèsaléatoire It+n, It-n
It++, It--
It++
• Bidirectionnel• peut itérer en direction avant (++) et arrière (--)• type d’itérateur des conteneurs list, set, multiset, map et
multimap• Accès par index
• peut itérer en direction avant (++), arrière (--) et par index ([ ])• type d’itérateur des conteneurs vector et deque
Les itérateurs
Les catégories
Les itérateurs
Première version:• Une méthode hasNext() pour savoir si on est arrivé à la fin• Une méthode next() pour passer à l’élément suivant
• Ce type d’itérateur est utilisé en Java
Deuxième version:• L’itérateur est manipulé comme s’il s’agissait d’un pointeur• La manipulation se fait par la surcharge des opérateurs *, ++,
--, ==, != et =.• Ce type d’itérateur est utilisé en C++
Implémentation
Les itérateurs
Tous les conteneurs définissent deux types d’itérateur• container::iterator
permet de naviguer en mode lecture/écriture• container::const_iterator
permet de naviguer en mode lecture seulement
Utilisation
Les itérateurs
Exemple 1#include <list>#include <iostream> Using namespace std;
int main( ) { list <int> list1;
cin >> n; for (int i = 1; i<=n; i++) list1.push(i+i); list 1<int> :: iterator i; for (i = list1.begin( ); i!=list1.end( ); i++) cout <<*i << “ “ ; list <int> :: reverse_iterator inv; for (inv = list1.rbegin( ); i!=list1.rend( ); rev++) cout <<*rev << “ “ ;
return 0 ;}
Les itérateurs
Dans l’exemple précédent, on utilise également un itérateur inversé (reverse_iterator) qui permet le parcours dans le sens inverse. Les principaux opérateurs sont * donnant accès à la valeur, ++ et -- pour incrémenter et décrémenter une valeur.
-Opérateur * : Retourne l’élément de la position courante
-Opérateur ++ : Fait pointer l’itérateur à l’élément suivant
-Opérateur == : Indique si 2 itérateurs pointent sur le même élément
-Opérateur = : Assigne un itérateur
Les itérateurs
Exemple 2
#include <list>#include <iostream> using namespace std;................. list<int> nums; list<int>::iterator nums_iter; nums.push_back (0); nums.push_back (4); nums.push_front (7); cout << endl << "List 'nums' now becomes:" << endl; for (nums_iter=nums.begin(); nums_iter != nums.end(); nums_iter++) {
*nums_iter = *nums_iter + 3; // Modifier chaque élément. cout << (*nums_iter) << endl;
} cout << endl;
Les itérateurs
Après la création d’une liste d’entiers , l’itérateur num_iter est initialisé pour spécifier la position de la liste (nums.begin()). La boucle est exécutée jusqu’à atteindre la valeur de l’itérateur représentant la position derrière le dernier élément de la liste (nums.end()).
Chaque élément de la liste est accédé par l’opérateur "*" qui retourne une référence à cet élément. L’opérateur d’incrémentation (++) déplace l’itérateur à la position suivante dans la liste.
Souvent, les éléments stockés dans une STL sont des classes. Dans pareils cas, il se pourrait que nous voulions invoquer les fonctions membre de cet objet référencé par l’itérateur. Pour ce faire, nous devons faire attention à la précédence des opérateurs pour que le compilateur puisse comprendre ce que nous sommes en train de faire.
Les itérateurs
#include <list> #include <string> using namespace std;... list<string> words; list<string>::iterator words_iter;... unsigned int total_length = 0; for (words_iter=words.begin(); words_iter != words.end(); words_iter++) { total_length += (*words_iter).length(); // correct // total_length += *words_iter.length(); // faux !!
} cout << "Total length is " << total_length << endl;
Exemple 3
Les itérateurs
Les parenthèses entre "*words_iter" sont nécessaires quand nous invoquons la fonction "length( )". Sans elles, le compilateur va comprendre que la fonction "length( )" est membre de l’iterateur, et non de la classe string class, car le "." de l’operateur sera autrement évalué avant l’opérateur "*" .
Remarquez que les parenthèses vont aussi être nécessaires lors de l’accès aux données.
#include <list>
// création d’une liste de caractèreslist<char> coll;
for (char c = ‘a’; c<=‘z’; c++)coll.push_back(c);
// impression de la liste à l’aide d’un itérateurlist<char>::const_iterator pos;
for(pos = coll.begin(); pos != coll.end(); pos++)cout << *pos << ‘ ‘;
Exemple 4
Les itérateurs
Synthèse
Les itérateurs
Plusieurs fonctions requièrent la notion de position dans un conteneur. Dans la STL une position est représentée par un type imbriqué que l'on nomme itérateur.
Par exemple, on utilise le type vector<string>::iterator pour représenterune position dans un vector<string>. Pour plus de concision nous écrironssimplement iterator.
Synthèse
Les itérateurs
iterator begin() Retourne un iterateur pointant au début du conteneur
iterator end() Retourne un itérateur pointant à la fin du conteneur
iterator insert (iterator p, const Object& x) Ajoute x immédiatementavant la position p. Cette opération prend un temps constant pour les listes mais pas pour les vecteurs.
iterator erase (iterator p) Enlève l'objet à la position p. Retourne la position de l'objet suivant.
iterator erase(iterator debut, iterator fin) Enlève tous les objets àpartir de debut jusqu‘à fin.
Synthèse
Les itérateurs
Si v est une variable de type vector<int> alors on peut afficherses éléments de la façon suivante:
for (int i=0; i< v.size(); ++i) cout<<v[i]<<endl;
On peut aussi utiliser la méthode suivante:
for (vector<int>::iterator itr=v.begin(); itr!= v.end(); ++itr)cout<<*itr<<endl;
Itérateurs – Pour les arbres
• Chaque fois qu’on le fait avancer, l’itérateur pointe sur le noeud suivant dans un ordre pré-défini
• Pour un parcours pré-ordre, on peut faire une implémentation simple en utilisant une pile
• Les parcours en ordre et post-ordre sont un peu plus compliqués...
Arbres – Itérateur abstrait
template <class T>class IterateurArbre{public:
IterateurArbre(const Arbre< T > & unArbre): laRacine(unArbre.ptrRacine), actuel(NULL) {}
virtual ~IterateurArbre(){}
virtual void premier() = 0;bool estValide() const{
return (actuel != NULL);}
T extraire() const; // retourne la donnée à la position actuellevirtual void avancer() = 0;
protected:const NoeudArbre< T > *laRacine;const NoeudArbre< T > *actuel;
};
Arbres – Itérateur pré-ordre
template <class T>class IterateurPreOrdre : public IterateurArbre< T >{public:
IterateurPreOrdre(const Arbre< T > & unArbre);~IterateurPreOrdre() {}
virtual void premier();virtual void avancer();
protected: Pile< const NoeudArbre< T > *> pileNoeuds;};
Arbres – Itérateur pré-ordre
// Réinitialise l'itérateur en le faisant pointer// à la racine de l'arbre
template <class T>void IterateurPreOrdre< T >::premier(){
// Vider la pile pileNoeuds.vider();
if (laRacine != NULL){
pileNoeuds.push(laRacine);avancer();
}}
Arbres – Itérateur pré-ordre
template <class T>void IterateurPreOrdre< T >::avancer(){ NoeudArbre< T > *fils;
if (pileNoeuds.empty()){ if (actuel == NULL) cout << "Tentative d'avancer au dela de la fin"; actuel = NULL; return;}
actuel = pileNoeuds.top();pileNoeuds.pop();
fils = actuel->obtenirFilsDroit();if (fils != NULL)
pileNoeuds.push(fils); fils = actuel->obtenirFilsGauche();
if (fils != NULL)pileNoeuds.push(fils);
}
Les algorithmes
La STL fournit un nombre important d’algorithmes génériques les plus utilisés, tels que les algorithmes de parcours, de recherche et de tri. Ilss’appliquent sur les conteneurs.
Les algorithmes ne sont pas des fonctions membres des classes des conteneurs. Ce sont plutôt des fonctions globales qui opèrent avec des intérateurs.
Pour manipuler cette bibliothèque, il suffit d‘incorporer dans l’entête
#include <algorithtm>
On distingue deux types d’algorithmes: ceux qui modifient les conteneurs et ceux qui ne le modifient pas (remarquer que les algorithmes de tri font partie des algorithmes qui ne modifient pas les conteneurs).
Algorithmes de non modification (non mutating algorithms)
findTrouver la première occurrence d’une valeur donnée.
find_if Trouver la première apparition d’un prédicat.
find_first_ofTrouver la première occurrence d’une valeur d’une séquence dans une autre .
adjacent_findTrouver la première occurrence d’une paire de valeurs adjacente
countCompter l’apparition d’une valeur dans une séquence.
count_ifCompter le nombre de fois qu’un prédicat apparait dans une séquence.
equalComparaison élément à élément le contenu de deux conteneurs. Les conteneurs peuvent de types différents
max_elementTrouver le plus grand élément d’une séquence.
min_element Trouver le plus petit élément d’une séquence.
searchRecherche la première occurrence d’un sous ensemble d’éléments.
Algorithmes de non modification (non mutating algorithms)
Exemple – for_each()
void print(const int elem){ cout << elem << ' ';}
int main(){ vector< int > coll;
...
for_each(coll.begin(), coll.end(), print);}
Algorithmes de non modification (non mutating algorithms)
Exemple – count() et count_if()
bool estPair(const int elem){ return (elem % 2 == 0);}
int main(){ vector< int > coll; ... count(coll.begin(), coll.end(), 3); ... count_if(coll.begin(), coll.end(), estPair);
Algorithmes de non modification (non mutating algorithms)
Exemple – find()
... int tab[4] = {76,77,3,45}; vector< int >::const_iterator pos;
for (i=0; i<3; i++){ pos = find(coll.begin(), coll.end(), tab[i]); if (pos != coll.end()) cout << "Element trouve: " << *pos << endl; else cout << "Element non trouve: " << tab[i] << endl; }
les conteneurs associatifs ont une méthode find() qui fait la même chose, mais de manière plus efficace, en O(lg n)
Algorithmes de non modification (non mutating algorithms)
Exemple – find_if()
bool plusGrandQue10(const int elem){ return elem > 10;}
int main(){ ... pos = find_if(coll.begin(), coll.end(), plusGrandQue10); if (pos != coll.end()) cout << "Premier element trouve qui est > 10:" << *pos << endl; else cout << "Aucun element > 10: " << endl;
Algorithmes de non modification (non mutating algorithms)
Exemple – search()
vector< int > coll2; coll2.push_back(3); coll2.push_back(1); coll2.push_back(3); pos = search(coll.begin(), coll.end(), coll2.begin(), coll2.end());
if (pos != coll.end()){ cout << "A partir de la sous-séquence trouvee:“
<< endl; for_each(pos, coll.end(), print); cout << endl;
} else cout << "Sous-sequence pas trouvee" << endl;
reverse() inverse l'ordre des éléments du conteneurpartition() met au debut tous les éléments qui respectent
la condition passée en paramètresort() trie les élémentsstable_sort() trie les éléments de manière à ce que les
éléments égaux restent dans le même ordre
Algorithmes qui altèrent l’ordre des données
Les algorithmes
Exemple – partition()
// Partitionne le conteneur en mettant les// nombre pairs au début
partition(coll.begin(), coll.end(), estPair);
Les algorithmes
#include <vector>#include <algorithm> // inclusion des algorithmes
#include <iostream> using namespace std;……………………………vector<int> vec;vec.push_back (10);vec.push_back (3);vec.push_back (7);
sort(vec.begin(), vec.end()); // tri le vecteur // le vecteur contient maintenant : 3, 7, 10
Exemple – sort()
Algorithmes de modification (mutating algorithms)
transformfor_eachMerge
Modifie et copie les éléments d’un conteneurRéalise sur tous les éléments l’opération passée en paramètreFusionne deux conteneurs triés en un seul ensemble trié de valeurs
copy Copier une séquence
replace Remplacer les éléments d’une séquence par une valeur donnée.
replace_if Remplacer les éléments égaux à une prédicat
remove Supprimer toutes les occurences d’un élément donné dans le conteneur
remove_if Supprimer tous les éléments qui respectent à un prédicat passé en paramètre
reverse Inverser une séquence.
random_shuffle Aléatoirement réorganiser les éléments en utilisant une distribution uniforme.
fill Remplacer les éléments d’une séquence avec une valeur.
generate Remplacer les éléments d’une séquence avec le résultat d’une opération donnée.
accumulate Sommer les éléments d’une séquence.
unique Élimine tous les éléments qui sont égaux à leur prédécesseur
Les algorithmes
Remarques sur remove()
• les listes ont leur propre méthode remove(), plus efficace• Ne retire pas réellement les éléments du conteneur• Les éléments sont retiré de la position où ils se trouvent et les
reste est décalé en conséquence• Par contre, comme la taille du conteneur ne change pas, on se
retrouve à avoir à la fin des valeurs invalides• La fonction remove() retourne un itérateur pointant sur la
première position invalide• Pour “nettoyer le conteneur, on peut appeler erase à partir de
cette position
Les algorithmes
Exemple - remove()
// retrait des occurrences de la valeur 2vector< int >::iterator fin = remove(coll.begin(), coll.end(), 2);
// ajustement du conteneurcoll.erase(fin, coll.end());
Les algorithmes
Exemple – remove_if()
// Retrait des nombres pairsfin = remove_if(coll.begin(), coll.end(), estPair);coll.erase(fin,coll.end());cout << "Apres retrait des nombres pairs: " << endl;for_each(coll.begin(), coll.end(), print);cout << endl
Les algorithmes
#include <iostream>#include <list>#include <algorithm>
List<char> initC(char*c){ List<char> majax; while (*c != ‘\0’= majax.push_back(*c++); return majax;}
int main() { List<char> gerard = initC("le plus grand et le plus fort des magiciens"); gerard.sort(); gerard.unique(); for (List<char>::iterator i = gerard.begin() ; i != gerard.end() ; i++) cout << *i; return 0;}
Exemple 1 – unique()
Les algorithmes
Exemple 2 – unique()
// Elimination des répétitionsfin = unique(coll.begin(), coll.end());coll.erase(fin,coll.end());cout << "Apres elimination des repetitions: " << endl;for_each(coll.begin(), coll.end(), print);cout << endl;
• Pour encore plus de flexibilité, certains algorithmes permettent l’usage de fonctions définies par l’usager
• Les fonctions sont appelées à l’interne par l’algorithme et généralement appliquées à chaque élément du conteneur
• Un prédicat est une fonction qui retourne une valeur booléenne (vrai ou faux)
• Les prédicats peuvent être utilisés pour spécifier un critère de recherche ou de tri
Utilisation de prédicats dans les algorithmes
Différence entre for_each() et transform()
• for_each() requiert une fonction qui ne retourne aucune valeur, et qui modifiera directement chaque élément en le recevant par référence
• transform() requiert une fonction qui retourne la valeur modifiée, et qui sera copiée dans un second conteneur
• Remarque: le second conteneur peut être le même conteneur
Les algorithmes
Exemple - for_each()
void ajouter10(int & elem){ elem += 10;}...
// Utilisation de for_each() qui altère les donnéesfor_each(coll.begin(), coll.end(), ajouter10);cout << endl;
Les algorithmes
Exemple - transform()
// Utilisation de transform() qui altère les données// et les envoie dans un autre conteneurvector<int> coll2;coll2.resize(coll.size());transform(coll.begin(), coll.end(), coll2.begin(), ajouter10bis);cout << endl;
Les algorithmes
Exemple – fill_n()
// Mettre des 0 dans la première moitié et //des 1 dans la seconde
// On remplit la première moitiéfill_n(coll.begin(),5,0); // On utilise un itérateur inverse pour // ajouter à partir de la finfill_n(coll.rbegin(),5,1);
Les algorithmes
Exemple – generate()
int fibonacci(){
static int n1 = 0;static int n2 = 1;int temp = n1 + n2;
n1 = n2;n2 = temp;return n1;
}
Les algorithmes
Exemple – generate()
// Utilisation de generate pour créer la// suite de Fibonacci
generate(coll.begin(), coll.end(), fibonacci);
cout << "Suite de Fibonacci: " << endl;for_each(coll.begin(), coll.end(), print);cout << endl;
Algorithmes de manipulation d’ensembles
includesVérifie si les éléments d’un conteneur forment un sous-ensemble d’un autre conteneur
set_union Réalise l’union ensembliste de deux conteneurs
set-intersectionRéalise l’intersection ensembliste de deux conteneurs
binary_searchTrouver une valeur donnée en utilisant la recherche dichotomique
Les algorithmes
Exemple – includes()
if (includes(c1.begin(), c1.end(), c2.begin(), c2.end())) cout << "c2 inclus dans c1" << endl;
else cout << "c2 non inclus dans c1" << endl;
Les algorithmes
Problèmes d’utilisation
#include <list>
#include <vector>list<int> coll1;vector<int> coll2;
// insertion d’éléments dans la listefor (int i=1; i<=9; i++)
coll1.push_back(i);
// copie dans le vecteur (PROBLÈME À L’EXÉCUTION)copy(coll1.begin(), coll1.end(), // source
coll2.begin()); // destination
Les algorithmes
Problèmes d’utilisation
• L’algorithme copy écrase les éléments de la destination• Or, au moment de l’appel, le vecteur (coll2) est vide• Dans un tel cas, il faudrait créer les éléments lors de la copie
plutôt que d’écraser un élément qui n’existe pas!• Solution: adaptateur d’itérateur
Les algorithmes
Adaptateur d’itérateurs
• Il existe trois types d’itérateurs adaptateurs• insert: permet aux algorithmes d’opérer en mode
insertion plutôt qu’en mode écrasement
• Reprenons le cas de la copie…
list<int> coll1;
// insertion d’éléments dans la listefor (int i=1; i<=9; i++)
coll1.push_back(i);
Les algorithmes
Adaptateur d’itérateurs
// copie dans un vectorvector<int> coll2;copy(coll1.begin(), coll1.end(), // source
back_inserter(coll2)); // destination
// copie dans un dequedeque<int> coll3;copy(coll1.begin(), coll1.end(), // source
front_inserter(coll3)); // destination
// copie dans un setset<int> coll4;copy(coll1.begin(), coll1.end(), // source
inserter(coll4, coll4.begin()); // destination
Les algorithmes
Adaptateur d’itérateurs, autre exemple
int main(){
int t1[] = { 1, 3, 5, 7, 9};deque<int> dq1(t1,t1+5);int t2[] = { 2, 4, 6};deque<int> dq2(t2,t2+3);
copy(dq1.begin(), dq1.end(), back_inserter(dq2));for (int i=0 ; i<dq2.size() ; i++) cout << dq2[i] << ‘ ‘;
return 0;}
Les algorithmes
Adaptateur d’itérateurs - Ensemble
// intersection de deux ensembles
vector< int > c1,c3,c4;...set_intersection(c1.begin(), c1.end(),
c3.begin(), c3.end(), back_inserter(c4));
Les algorithmes
Adaptateur d’itérateurs
Les deux autre types d’adaptateurs sont• stream: permet de lire ou d’écrire des « stream » (accès
direct au clavier et à l’écran• reverse: opère en mode inverse (pour afficher un tableau
à l’envers, par exemple)
Les algorithmes
La STL fournit aussi des utilitaires qui augmentent les capacités desalgorithmes :
• Foncteurs (objets de fonction)• Adaptateurs de fonctions
Les foncteurs
• Un foncteur est un objet se comportant comme une fonction• Repose sur la surcharge de l’opérateur ()
class PrintInt { public: void operator() (int elem) { cout << elem << ‘ ‘; }};
int main() { vector<int> coll;
... for_each (coll.begin(), coll.end(), PrintInt()); cout << endl; return 0;}
Exemple
Les foncteurs
• Attention: l’expression PrintInt() crée un objet temporaire• On crée d’abord l’objet, qu’on utilise ensuite comme foncteur
Exemple 1
PrintInt unFoncteur;
unFoncteur(8); // imprime l’entier 8
Les foncteurs
• Permet de définir des fonctions « intelligentes », en utilisant d’autres fonctions et données membres
• Chaque instance de la fonction peut avoir un état différent• Avec une fonction ordinaire, on ne pourrait pas par exemple avoir
une variable statique avec plusieur valeurs initiales différentes, ce qui est possible avec un foncteur
Avantages
Les foncteurs
Exemple 2
• Supposons que l’on veuille une fonction qui incrémente d’une certaine valeur un élément
• Si la valeur est fixe et connue d’avance, on peut utiliser une fonction normale:
void ajouter10(int & elem){
elem += 10;}int main(){
vector<int> unTableau; ... transform(unTableau.begin(), unTableau.end(), unTableau.begin(), ajouter10); ...}
Les foncteurs
Exemple 2 suite
• Si la valeur est variable, mais connue lors de la compilation, on utilise un template:
template <int laValeur>void ajouter(int & elem){
elem += laValeur;}
int main(){
vector<int> unTableau; ... transform(unTableau.begin(), unTableau.end(), unTableau.begin(), ajouter<10>); ...}
Les foncteurs
Si la valeur est variable, mais connue seulement lors de l’exécution, on utilise un foncteur:
class Ajouter {public:
Ajouter(int v) : laValeur(v) {} void operator() (int & elem) const {
elem += laValeur; }private:
int laValeur;}
Utilisationint increment;cin >> increment;for_each(unTableau.begin(), unTableau.end(),Ajouter(increment));
Les foncteurs
Exemple 3
class FiltrerLettres{public: FiltrerLettres(const char* lesLettres = "") {strcpy(lettresFiltrees,lesLettres);}
bool operator () (char c) const { int i = 0; while (lettresFiltrees[i] != 0) { if (c == lettresFiltrees[i]) return true; ++i; } return false; }private: char lettresFiltrees[27];};
Les foncteurs
Exemple 3 suite
int main(){ list<char> uneListe; for (char c='a'; c<='z'; ++c){ uneListe.push_back(c); } remove_if(uneListe.begin(),uneListe.end(), FiltrerLettres("aeiou")); while (!uneListe.empty()){ cout << uneListe.front() << ' '; uneListe.pop_front(); } cout << endl; return 0;}
Les foncteurs prédéfinis
• STL offrent plusieurs foncteurs couvrant les opérations de base• Par exemple, le conteneur set trie ses éléments en ordre
croissant. Pour utiliser un autre critère de tri, on n’a qu’à utiliser un autre prédicat
• set<int> coll; // trie en ordre croissant (par défaut)
• set<int, greater<int> > coll; // trie en ordre décroissant
• greater<int> est un foncteur prédéfini
Les foncteurs prédéfinis
Exemple de traitement numérique
transform(coll.begin(),
coll.end(),
coll.begin(),
negate<int>());
• negate<int> est un foncteur qui multiplie la valeur par -1
Adaptateurs de fonctions
Il s’agit de foncteurs qui permettent de combiner des fonctions.
Exemple
• plus<int> le foncteur pré-défini qui effectue une addition sur des entiers
• bind2nd(op,valeur) est un foncteur pré-defini qui prend une fonction à deux arguments et la transforme en un nouvelle fonction où le second argument est la valeur spécifiée
• bind2nd(plus<int>(),10) est donc une fonction qui prend un seul argument et qui ajoute 10 à cet argument
Adaptateurs de fonctions
Exemple 1int main(){ vector<int> vect;
vect.push_back(2); vect.push_back(7); vect.push_back(10);
for_each(vect.begin(), vect.end(), PrintInt()); cout << endl; transform(vect.begin(), vect.end(), vect.begin(), bind2nd(plus<int>(),10) ); cout << endl;
for_each(vect.begin(), vect.end(), PrintInt()); cout << endl; return 0;}
Adaptateurs de fonctions
Exemple 2int main(){ vector< int > coll; int resultat; for (int i = 1; i < 5; i++) coll.push_back(i);
// Calculer le produit resultat = accumulate(coll.begin(), coll.end(), 1,
multiplies<int>()); return 0;}
STL : Standard Template Library
Pour plus d’informations sur les STL, consulter par exemple le lien suivant :
http://www.sgi.com/tech/stl/stl_introduction.html
