Bon, plongeons-nous un peu plus en avant dans la documentation de l'en-tête
algorithm. Commençons par quelques fonctions de comptage.
Compter des éléments
Compter des éléments est une opération très facile à réaliser. Utiliser la STL peut à nouveau vous sembler superflu, moi je trouve que cela rend le code plus clair et peut-être même plus optimisé dans certains cas.
Pour compter le nombre d'éléments égaux à une valeur donnée, on utilise l'algorithme
count. Oui, être anglophone aide beaucoup en programmation. Mais je crois que vous l'avez compris.
Pour compter le nombre d'éléments égaux au nombre 2, c'est très simple :
Code : C++ | int nombre = count(tab.begin(), tab.end(), 2);
|
Et bien sûr
tab est le conteneur de votre choix. Et voilà, vous savez tout !
En tout cas pour cet algorithme...
Avant d'aller plus loin, faisons un petit exercice pour récapituler tout ce que nous savons sur les foncteurs,
generate() et
count(). Essayez d'écrire un programme qui génère un tableau de 100 nombres aléatoires entre 0 et 9 puis qui compte le nombre de 5 générés. Tout ceci en utilisant au maximum la STL bien sûr ! A vos claviers !
Vous avez réussi ? Voici une solution possible :
Code : C++ 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 | #include <iostream>
#include <cstdlib> //pour rand()
#include <ctime> //pour time()
#include <vector>
#include <algorithm>
using namespace std;
class Generer
{
public:
int operator()() const
{
return rand() % 10; //On renvoie un nombre entre 0 et 9
}
};
int main()
{
srand(time(0));
vector<int> tab(100,-1); //Un tableau de 100 cases
generate(tab.begin(), tab.end(), Generer()); //On génère les nombres aléatoires
int const compteur = count(tab.begin(), tab.end(), 5); //Et on compte les occurrences du 5
cout << "Il y a " << compteur << " elements valant 5." << endl;
return 0;
}
|
Personnellement, je trouve ce code très clair. On voit rapidement ce qui se passe. Toutes les boucles nécessaires sont cachées dans les fonctions de la STL. Pas besoin de s'ennuyer à devoir tout écrire soi-même.
Le retour des prédicats
Si vous pensiez que vous pourriez vous en sortir sans ces drôles de foncteurs, vous vous trompiez !
Je vous avais dit dans le chapitre précédent que l'on utilisait des prédicats pour tester une propriété des éléments. On pourrait donc utiliser un prédicat pour ne compter que les éléments qui passent un certain test. Et si je vous en parle, c'est qu'un tel algorithme existe. Il s'appelle
count_if(). La différence avec
count() est que le troisième argument n'est pas une valeur mais un prédicat.
Dans le chapitre précédent, nous avions écrit un prédicat qui testait si une chaîne de caractères contenait des voyelles ou non. Essayons-le !
Code : C++ 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41 | #include <algorithm>
#include <string>
#include <vector>
using namespace std;
class TestVoyelles
{
public:
bool operator()(string const& chaine) const
{
for(int i(0); i<chaine.size(); ++i)
{
switch (chaine[i]) //On teste les lettres une-à-une
{
case 'a': //Si c'est une voyelle
case 'e':
case 'i':
case 'o':
case 'u':
case 'y':
return true; //On renvoie 'true'
default:
break; //Sinon, on continue
}
}
return false; //Si on arrive là, c'est qu'il n'y avait pas de voyelles du tout
}
};
int main()
{
vector<string> tableau;
//... On remplit le tableau en lisant un fichier par exemple.
int const compteur = count_if(tableau.begin(), tableau.end(), TestVoyelles());
//... Et on fait quelque chose avec 'compteur'
return 0;
}
|
Voilà qui est vraiment puissant ! Le prédicat
TestVoyelles s'active sur chacun des éléments du tableau et
count_if indique combien de fois le prédicat a renvoyé "vrai". On sait ainsi combien il y a de chaînes contenant des voyelles dans le tableau.
Chercher
Chercher un élément dans un tableau est aussi très facile. On utilise l'algorithme
find() ou
find_if(). Ils s'utilisent exactement comme les algorithmes de comptage, la seule différence est leur type de retour : ils renvoient un itérateur sur l'élément trouvé ou sur
end() si l'objet cherché n'a pas été trouvé.
Pour chercher la lettre
a dans une
deque de
char, on fera quelque chose comme :
Code : C++ 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | #include <deque>
#include <algorithm>
#include <iostream>
using namespace std;
int main()
{
deque<char> lettres;
//On remplit la deque... avec generate() par exemple !
deque<char>::iterator trouve = find(lettres.begin(), lettres.end(), 'a');
if(trouve == lettres.end())
cout << "La lettre 'a' n'a pas ete trouvee" << endl;
else
cout << "La lettre 'a' a ete trouvee" << endl;
return 0;
}
|
Et je ne vous fais pas l'affront de vous montrer la version qui utilise un prédicat.
Je suis convaincu que vous saurez vous débrouiller.
Puisque l'on parle de recherche d'éléments, je vous signale juste l'existence des fonctions
min_element() et
max_element() qui cherchent l'élément le plus petit ou le plus grand.
Trier !
Il arrive souvent que l'on doive trier une série d'éléments. Et ce n'est pas une mince affaire. En tout cas, c'est un problème avancé d'algorithmique (la science des algorithmes
). Je vous assure qu'écrire une fonction de tri optimisée est une tâche qui n'est pas à la portée de beaucoup de monde.
Heureusement, la STL propose une fonction pour cela, et je peux vous assurer qu'elle est très efficace et bien codée. Son nom est simplement
sort(), ce qui signifie
trier en anglais (au cas où je devrais le préciser).
On lui fournit deux itérateurs et la fonction va trier tout ce qui se trouve entre ces deux éléments dans l'ordre croissant. Trions donc le tableau de nombres aléatoires utilisé précédemment.
Code : C++ 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | int main()
{
srand(time(0));
vector<int> tab(100,-1); //Un tableau de 100 cases
generate(tab.begin(), tab.end(), Generer()); //On génère les nombres aléatoires
sort(tab.begin(), tab.end()); //On trie le tableau
for(vector<int>::iterator it=tab.begin(); it!=tab.end(); ++it)
cout << *it << endl; //On affiche le tableau trié
return 0;
}
|
A nouveau, rien de bien sorcier.
La fonction
sort() ne peut être utilisée qu'avec des conteneurs proposant des
random access iterators, c'est-à-dire les
vector et les
deque uniquement. De toute façon, trier une
map a peu de sens puisque ces conteneurs stockent directement leurs éléments dans le bon ordre.
Par défaut, la fonction
sort() utilise l'opérateur
< pour comparer les éléments avant de les trier. Mais il existe également une autre version de cette fonction qui prend un troisième argument : un foncteur comparant deux éléments. Nous avons déjà rencontré un tel foncteur dans le chapitre précédent pour changer le comportement d'une table associative. C'est exactement le même principe ici. Si l'on souhaite créer un tri spécifique, on doit fournir un foncteur expliquant à
sort() comment trier.
Pour trier des chaînes de caractères selon leur longueur, nous pouvons ré-utiliser notre foncteur :
Code : C++ 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | class ComparaisonLongueur
{
public:
bool operator()(const string& a, const string& b)
{
return a.length() < b.length();
}
};
int main()
{
vector<string> tableau;
//... On remplit le tableau en lisant un fichier par exemple.
sort(tableau.begin(), tableau.end(), ComparaisonLongueur());
//Le tableau est maintenant trié par longueur de chaîne
return 0;
}
|
Puissant, simple et efficace. Que demander de mieux ?
La puissance des algorithmes
Durée d'étude :
1
jour
Si vous parlez la langue de Shakespeare, vous aurez compris que "to generate" signifie "générer". La ligne mise en évidence se lit donc de la manière suivante : Génère grâce au foncteur f tous les éléments situés entre tab.begin() et tab.end(). On peut difficilement faire plus clair !
*Nat
Nanoc
Trouvez une formation
Suggestions
Flux RSS News
Twitter
Facebook
Google+