Page principale | Pages associées

Les Algorithmes

La STL contient une grande quantité d'algorithmes permettant de manipuler un conteneur (au sens large, un simple array[] suffit) sur lequel on a des itérateurs (souvent les fameux begin() et end()) Les algorithmes sont classés en plusieurs catégorie : non-modifieurs, modifieurs, tris.... Je vais donc vous en présenter quelques uns et la manière dont on les utilises.

Les algorithmes fonctionnent grâce aux itérateurs qui permettent de définir l'ensemble des éléments à traiter sans connaître la manière dont ils sont stockés (le conteneur). On a vu dans les tutoriaux précédents que les conteneurs mettent à disposition des itérateurs grâce notamment aux méthodes begin() et end(). Les itérateurs sont hiérarchisés dans 5 catégories selon les opérations qu'ils autorisent. La catégorie des itérateurs dépend de la nature du conteneur. Les détails ne sont pas utiles pour le moment à mon avis pour un simple tutorial. Pour le moment, il suffit de savoir que les itérateurs sur conteneurs que nous avons déjà vu ( vector, list, set, map ) permettent d'avancer (++) ou de reculer(--) dans le conteneur, et seul le vector (pour le moment) permet d'utiliser l'opérateur [] pour l'accès à ces éléments.

#include <iostream> #include <vector> #include <algorithm> #include <iterator> using namespace std; // Fonction permettant d'afficher un entier void afficher( int i ) { cout << i << ' '; } // ----- programme principal ----- int main() { const int aInt_size = 10; int aInt[aInt_size] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
A partir de maintenant on a un simple tableau de 10 entiers. Un pointeur classique répond aux mêmes exigences qu'un itérateur sur les vecteurs.

// Affichage du tableau for_each( aInt, aInt + aInt_size, afficher );
for_each permet d'appeler une fonction (ici afficher) sur tous les éléments du tableau. aInt est converti un pointeur sur l'élément 0 du tableau aInt + aInt_size pointe après le dernier élément du tableau.
cout << endl; // on passe à la ligne // Recherche d'un élément du tableau int* found = find( aInt, aInt + aInt_size, 4 ); afficher( *found ); cout << endl; int* notFound = find( aInt, aInt + aInt_size, 12 ); if ( notFound == (aInt + aInt_size) ) cout << "12 n'est pas présent dans le tableau" << endl;
find permet de rechercher un élément dans un conteneur. S'il le trouve il renvoi un pointeur sur cet élément (cf ligne 64) sinon renvoie un pointeur de fin ( aInt + aInt_size ) comme c'est la cas pour la recherche sur le 12

// Création d'un vecteur à partir du tableau vector<int> vInt( aInt, aInt + aInt_size );
Nous n'avions pas vu ce constructeur pour le vecteur. Le vecteur vInt sera construit à partir à partir des éléments contenus dans le tableau aInt, de l'élément aInt[0] et aInt[ aInt_size - 1 ] inclus.

// On secoue le vecteur pour le mélanger random_shuffle( vInt.begin(), vInt.end() );
ne sert pas vraiment mais permet de mélanger des tableaux. Permet de permuter de manière aléatoire des éléments du vecteur.

// Affichage du vecteur for_each( vInt.begin(), vInt.end(), afficher ); cout << endl; // Affichage du plus petit élément cout << "Min = "; afficher( *min_element( vInt.begin(), vInt.end() ) ); cout << endl;
min_element permet de trouver le plus petit élément du vecteur et renvoie un itérateur sur sa position. le * permet donc d'accéder à cet élément.

// Affichage du plus grand élément cout << "Max = "; afficher( *max_element( vInt.begin(), vInt.end() ) ); cout << endl;
max_element permet de récupérer la maximum des éléments contenu dans le vecteur.

// On trie le vecteur sort( vInt.begin(), vInt.end() );
un algorithme bien pratique qui permet de trier un conteneur à accès indexé (donc pas les listes par exemple)

// Suppression des éléments valant 7 vector<int>::iterator remove7 = remove( vInt.begin(), vInt.end(), 7 );
Attention, remove ne supprime pas vraiment l'élément du vecteur mais renvoi une position à partir de laquelle il faudra effectivement supprimer les éléments gràce à la méthode du conteneur après avoir déplacé l'élément à supprimer. Ici, on avait après le tri 1 2 3 4 5 6 7 8 9 10 après le remove on a 1 2 3 4 5 6 8 9 10 _ (il se peut que _ soit 10 )

vInt.erase( remove7, vInt.end() );
La suppression d'un élément se fait effectivement avec la méthode erase du conteneur

// Affichage du vecteur for_each( vInt.begin(), vInt.end(), afficher ); cout << endl;
Juste pour vérifier que le vecteur est bien trié

// inverser les éléments du vecteur reverse( vInt.begin(), vInt.end() );
permet d'inverser les éléments d'un conteneur

// Affichage du vecteur for_each( vInt.begin(), vInt.end(), afficher ); cout << endl; // Recherche d'un élément dans le vecteur vector<int>::iterator vFound = find( vInt.begin(), vInt.end(), 3 ); if ( vFound != vInt.end() ) cout << "Le 3 a été trouvé à la position " << distance( vInt.begin(), vFound ) << endl; }

Voilà pour le petit tour sur les algorithmes. Il y en a une cinquantaine présent dans la STL. Ils sont plus ou moins utiles en pratique, il faut juste les connaître pour ne pas avoir à les refaire si on a en besoin. L'utilisation de ces algorithmes revient à définir le début et la fin, une valeur éventuelle ou une function. On a vu ici:

De ceux là on peut dériver : find --> find_if, find_end (find_first_of est un peu différent) remove --> remove_if 1. ca doit suffir pour un simple tutorial. 2. le plus dur n'est souvent pas de les utiliser mais de trouver un exemple intéressant pour les utiliser. Les idées sont les bienvenues évidement...

Il est temps maintenant temps de regarder d'avantage du côté des itérateurs. Notamment les itérateurs d'insertion et les itérateurs de flux...

La suite...


Le source complet :
#include <iostream> #include <vector> #include <algorithm> #include <iterator> using namespace std; // Fonction permettant d'afficher un entier void afficher( int i ) { cout << i << ' '; } // ----- programme principal ----- int main() { const int aInt_size = 10; int aInt[aInt_size] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; // Affichage du tableau for_each( aInt, aInt + aInt_size, afficher ); cout << endl; // on passe à la ligne // Recherche d'un élément du tableau int* found = find( aInt, aInt + aInt_size, 4 ); afficher( *found ); cout << endl; int* notFound = find( aInt, aInt + aInt_size, 12 ); if ( notFound == (aInt + aInt_size) ) cout << "12 n'est pas présent dans le tableau" << endl; // Création d'un vecteur à partir du tableau vector<int> vInt( aInt, aInt + aInt_size ); // On secoue le vecteur pour le mélanger random_shuffle( vInt.begin(), vInt.end() ); // Affichage du vecteur for_each( vInt.begin(), vInt.end(), afficher ); cout << endl; // Affichage du plus petit élément cout << "Min = "; afficher( *min_element( vInt.begin(), vInt.end() ) ); cout << endl; // Affichage du plus grand élément cout << "Max = "; afficher( *max_element( vInt.begin(), vInt.end() ) ); cout << endl; // On trie le vecteur sort( vInt.begin(), vInt.end() ); // Suppression des éléments valant 7 vector<int>::iterator remove7 = remove( vInt.begin(), vInt.end(), 7 ); vInt.erase( remove7, vInt.end() ); // Affichage du vecteur for_each( vInt.begin(), vInt.end(), afficher ); cout << endl; // inverser les éléments du vecteur reverse( vInt.begin(), vInt.end() ); // Affichage du vecteur for_each( vInt.begin(), vInt.end(), afficher ); cout << endl; // Recherche d'un élément dans le vecteur vector<int>::iterator vFound = find( vInt.begin(), vInt.end(), 3 ); if ( vFound != vInt.end() ) cout << "Le 3 a été trouvé à la position " << distance( vInt.begin(), vFound ) << endl; }
00001 #include <iostream> 00002 #include <vector> 00003 #include <algorithm> 00004 #include <iterator> 00005 using namespace std; 00006 // Fonction permettant d'afficher un entier 00007 void afficher( int i ) 00008 { 00009 cout << i << ' '; 00010 } 00011 00012 // ----- programme principal ----- 00013 int main() 00014 { 00015 const int aInt_size = 10; 00016 int aInt[aInt_size] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 00017 // Affichage du tableau 00018 for_each( aInt, aInt + aInt_size, afficher ); 00019 cout << endl; // on passe à la ligne 00020 00021 // Recherche d'un élément du tableau 00022 int* found = find( aInt, aInt + aInt_size, 4 ); 00023 afficher( *found ); 00024 cout << endl; 00025 00026 int* notFound = find( aInt, aInt + aInt_size, 12 ); 00027 if ( notFound == (aInt + aInt_size) ) 00028 cout << "12 n'est pas présent dans le tableau" << endl; 00029 // Création d'un vecteur à partir du tableau 00030 vector<int> vInt( aInt, aInt + aInt_size ); 00031 // On secoue le vecteur pour le mélanger 00032 random_shuffle( vInt.begin(), vInt.end() ); 00033 // Affichage du vecteur 00034 for_each( vInt.begin(), vInt.end(), afficher ); 00035 cout << endl; 00036 00037 // Affichage du plus petit élément 00038 cout << "Min = "; 00039 afficher( *min_element( vInt.begin(), vInt.end() ) ); 00040 cout << endl; 00041 // Affichage du plus grand élément 00042 cout << "Max = "; 00043 afficher( *max_element( vInt.begin(), vInt.end() ) ); 00044 cout << endl; 00045 // On trie le vecteur 00046 sort( vInt.begin(), vInt.end() ); 00047 // Suppression des éléments valant 7 00048 vector<int>::iterator remove7 = remove( vInt.begin(), vInt.end(), 7 ); 00049 vInt.erase( remove7, vInt.end() ); 00050 // Affichage du vecteur 00051 for_each( vInt.begin(), vInt.end(), afficher ); 00052 cout << endl; 00053 // inverser les éléments du vecteur 00054 reverse( vInt.begin(), vInt.end() ); 00055 // Affichage du vecteur 00056 for_each( vInt.begin(), vInt.end(), afficher ); 00057 cout << endl; 00058 00059 // Recherche d'un élément dans le vecteur 00060 vector<int>::iterator vFound = find( vInt.begin(), vInt.end(), 3 ); 00061 if ( vFound != vInt.end() ) 00062 cout << "Le 3 a été trouvé à la position " 00063 << distance( vInt.begin(), vFound ) << endl; 00064 }

Dernière modification : Sun Jul 4 20:19:13 2004