• 50 heures
  • Difficile

Ce cours est visible gratuitement en ligne.

Ce cours existe en livre papier.

course.header.alt.is_certifying

Vous pouvez être accompagné et mentoré par un professeur particulier par visioconférence sur ce cours.

J'ai tout compris !

Mis à jour le 02/08/2019

Décrouvrez la puissance des algorithmes

Connectez-vous ou inscrivez-vous gratuitement pour bénéficier de toutes les fonctionnalités de ce cours !

Nous avons découvert les itérateurs qui nous permettent de parcourir des conteneurs, comme lesvector. Dans ce chapitre, nous allons découvrir les algorithmes de la STL, des fonctions qui nous permettent d'effectuer des modifications sur les conteneurs.

Cela fait un moment que je vous parle de modifications mais qu'est-ce que cela veut dire ? Eh bien, par exemple on peut trier un tableau, supprimer les doublons, inverser une sélection, chercher, remplacer ou supprimer des éléments, etc.

Certains de ces algorithmes sont simples à écrire et vous ne voyez peut-être pas l'intérêt d'utiliser des fonctions toutes faites. L'avantage d'utiliser les algorithmes de la STL est qu'il n'y a pas besoin de réfléchir pour écrire ces fonctions. Il n'y a qu'à utiliser ce qui existe déjà. De plus, ces fonctions sont extrêmement optimisées. En bref, ne réinventez pas la roue et utilisez les algorithmes !

Un premier exemple

Je vous préviens tout de suite, nous n'allons pas étudier tous les algorithmes proposés par la STL. Il y en a une soixantaine et ils ne sont pas tous très utiles. Et puis, quand vous aurez compris le principe, vous saurez vous débrouiller seuls.

La première chose à faire est, comme toujours, l'inclusion du bon en-tête. Dans notre cas, il s'agit du fichier algorithm. Et croyez-moi, vous allez souvent en avoir besoin à partir de maintenant.

Un début en douceur

Au chapitre précédent, nous avions créé un foncteur nommé Rempliret nous l'avons appliqué à tous les éléments d'un vector. Nous utilisions pour cela une boucle forqui parcourait les éléments du tableau de la position begin()à la position end().

Le plus simple des algorithmes s'appelle generateet il fait exactement la même chose, mais de façon plus optimisée. Il appelle un foncteur sur tous les éléments situés entre deux itérateurs. Grâce à cet algorithme, notre code de remplissage de tableau devient beaucoup plus court :

#include <algorithm>
#include <vector>
using namespace std;

//Définition de Remplir…

int main()
{ 
    vector<int> tab(100,0); //Un tableau de 100 cases valant toutes 0

    Remplir f(0);       

    generate(tab.begin(), tab.end(), f);
    //On applique f à tout ce qui se trouve entre begin() et end()
    
    return 0;
}

Ce code a l'avantage d'être en plus très simple à comprendre. 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 entretab.begin()ettab.end(). On peut difficilement faire plus clair !

Mais pourquoi doit-on utiliser des itérateurs ? Pourquoi la fonction generate()ne prend-elle pas comme premier argument le vector?

Excellente question ! Je vois que vous suivez. Il serait bien plus simple de pouvoir écrire quelque chose comme generate(tab, f)à la place des itérateurs. On s'éviterait toute la théorie sur les itérateurs !
En fait, c'est une fausse bonne idée de procéder ainsi. Imaginez que vous ne vouliez appliquer votre foncteur qu'aux dix premiers éléments du tableau et pas au tableau entier. Comment feriez-vous avec votre technique ? Ce ne serait tout simplement pas possible. L'avantage des itérateurs est clair dans ce cas : on peut se restreindre à une portion d'un conteneur. Tenez, pour remplir seulement les 10 premières cases, on ferait ceci :

int main()
{ 
    vector<int> tab(100,0); //Un tableau de 100 cases valant toutes 0

    Remplir f(0);       

    generate(tab.begin(), tab.begin()+10, f); //On applique f aux 10 premières cases
    generate(tab.end()-5, tab.end(), f);      //Et aux 5 dernières
    
    return 0;
}

Plutôt sympa non ?

En fait, c'est une propriété importante des algorithmes, ils s'utilisent toujours sur une plage d'éléments situés entre deux itérateurs.

Application aux autres conteneurs

Autre avantage de l'utilisation des itérateurs : ils existent pour tous les conteneurs. On peut donc utiliser les algorithmes sur tous les types de conteneurs ou presque. Il existe quand même quelques restrictions selon que les itérateurs sont aléatoires, bidirectionnels ou constants comme on l'a vu au chapitre précédent.

Par exemple, nous pouvons tout à fait utiliser notre foncteur sur une list<int>.

int main()
{ 
    list<int> tab; //Une liste d'entiers

    //Quelques manipulations pour créer des éléments…

    Remplir f(0);       

    generate(tab.begin(), tab.end(), f); //On applique f aux éléments de la liste
    
    return 0;
}

La syntaxe est strictement identique ! Il suffit donc de comprendre une fois le fonctionnement de tout ceci pour pouvoir effectuer des manipulations complexes sur n'importe quel type de conteneur !

Comptez, cherchez, triez

Bon, plongeons-nous un peu plus en avant dans la documentation de l'en-tête algorithm. Commençons par quelques fonctions de comptage.

Comptez 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 :

int nombre = count(tab.begin(), tab.end(), 2);

Et bien sûr, tabest 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 ! À vos claviers !

Vous avez réussi ? Voici une solution possible :

#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 au 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.

Au 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 !

#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 voyelle 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 TestVoyelless'active sur chacun des éléments du tableau et count_ifindique 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.

Cherchez

Chercher un élément dans un tableau est aussi très facile. On utilise l'algorithme find()oufind_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 dequede char, on fera quelque chose comme :

#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.

Triez !

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 trie dans l'ordre croissant tout ce qui se trouve entre ces deux éléments. Trions donc le tableau de nombres aléatoires utilisé précédemment.

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;
}

À nouveau, rien de bien sorcier.

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 au 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 :

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 ?

Encore plus d'algos

Ne nous arrêtons pas en si bon chemin. On est encore loin d'avoir fait le tour de tout ce qui existe.

Dans l'exemple du tri, j'affichais le contenu du vectorvia une boucle for. Employer pour cela un algorithme serait plus élégant. Concrètement, afficher les éléments revient à les passer en argument à une fonction (ou un foncteur) qui les affiche. Écrire un foncteur qui affiche l'argument reçu ne devrait pas vous poser de problèmes à ce stade du cours.

class Afficher
{
public:
    void operator()(int a) const
    {
        cout << a << endl;
    }
};

Il ne nous reste plus qu'à appliquer ce foncteur sur tous les éléments. L'algorithme permettant cela s'appelle for_each(), ce qui signifie « pour tout ».

int main()
{
    srand(time(0));
    vector<int> tab(100, -1);
    generate(tab.begin(), tab.end(), Generer());  //On génère des nombres aléatoires
    sort(tab.begin(), tab.end());

    for_each(tab.begin(), tab.end(), Afficher());   //Et on affiche les éléments
    
    return 0;
}

Le code a encore été raccourci. Il existe une autre manière d'envoyer des valeurs dans un flux mais il faudra attendre encore un peu. C'est le sujet du prochain chapitre.

À partir de cet algorithme, on peut faire énormément de choses. Un des premiers cas qui me vient à l'esprit est le calcul de la somme des éléments d'un conteneur. Vous voyez comment ? Comme for_each()appelle le foncteur sur tous les éléments de la plage spécifiée, on peut demander au foncteur d'additionner les éléments dans un de ses attributs.

class Sommer
{
public:
    Sommer()
        :m_somme(0)
    {}

    void operator()(int n)
    { 
        m_somme += n; 
    }

    int resultat() const
    {
        return m_somme;
    }

private:
    int m_somme;

};

L'opérateur()ajoute simplement la valeur de l'élément courant à l'attribut m_somme. Après l'appel à l'algorithme, on peut consulter la valeur de m_sommeen utilisant la méthode resultat(). Il faut cependant faire attention. La fonction for_eachreçoit une copie du foncteur en argument et pas une référence. Cela veut dire que l'objet dont l'attribut m_sommeest incrémenté n'est pas celui déclaré dans le main, mais une copie de celui-ci. Heureusement pour nous, les concepteurs de la STL ont pensé à tout et la fonction for_each()renvoie le foncteur qu'elle a utilisé une fois qu'elle a terminé. On peut donc utiliser l'objet retourné pour connaître la somme.

int main()
{
    srand(time(0));
    vector<int> tab(100, -1);
    generate(tab.begin(), tab.end(), Generer());  //On génère des nombres aléatoires

    Sommer somme;

    //On somme les éléments et on récupère le foncteur utilisé
    somme = for_each(tab.begin(), tab.end(), somme);   
 
    cout << "La somme des elements generes est : " << somme.resultat() << endl;
   
    return 0;
}

Si vous voulez un exercice, je peux vous proposer de réécrire la fonction qui calculait la moyenne d'un tableau de notes. Nous avions vu ce problème au tout début de ce cours (chapitre 8). Un petit foncteur pour le calcul de la moyenne, un for_each()et le tour est joué.

Utilisez deux séries à la fois

Terminons cette courte présentation par un dernier algorithme bien pratique pour traiter deux conteneurs à la fois. Imaginons que nous voulions calculer la somme des éléments de deux tableaux et stocker le résultat dans un troisième vector. Pour cela, il va nous falloir un foncteur qui effectue l'addition. Mais cela, on l'a déjà vu, existe dans l'en-tête functional. Pour le reste, il nous faut parcourir en parallèle deux tableaux et écrire les résultats dans un troisième. C'est ce que fait la fonction transform(). Elle prend cinq arguments : le début et la fin du premier tableau, le début du deuxième, le début de celui où seront stockés les résultats et bien sûr le foncteur.

#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

int main()
{
    vector<double> a(50, 0.);    //Trois tableaux de 50 nombres à virgule
    vector<double> b(50, 0.);
    vector<double> c(50, 0.);
   
    //Remplissage des vectors 'a' et 'b'….

    transform(a.begin(), a.end(), b.begin(), c.begin(), plus<double>());

    //À partir d'ici les cases de 'c' contiennent la somme des cases de 'a' et 'b'

    return 0;
}

Arrêtons-nous là pour ce chapitre. Je vous ai parlé des algorithmes les plus utilisés et je pense que vous avez compris comment tout cela fonctionnait. Vous commencez à avoir une bonne expérience du langage.

En résumé

  • Les algorithmes de la STL permettent d'effectuer des traitements sur des données.

  • On les utilise en spécifiant les éléments à modifier grâce à deux itérateurs.

  • Certains algorithmes utilisent des foncteurs, par exemple pour les appliquer à tous les éléments du conteneur ou pour chercher un élément correspondant à un critère donné.

Exemple de certificat de réussite
Exemple de certificat de réussite