Programmez en orienté objet avec C++

Dans ce chapitre, nous allons découvrir certains algorithmes de la STL, des fonctions qui nous permettent d'effectuer des modifications sur les conteneurs, comme :

• trier un tableau ;

• supprimer les doublons ;

• inverser une sélection ;

• chercher, remplacer ou supprimer des éléments, etc.

L'avantage d'utiliser les algorithmes de la STL ? Ces fonctions sont extrêmement optimisées.

Remplissez un tableau avec l'algorithme  generate

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.

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

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

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 !

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

Revoyons rapidement dans ce screencast comment remplir l’ensemble du tableau à l’aide de la fonction  generate()  et d'un foncteur que nous allons créer.

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.

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 comment ça marche pour effectuer des manipulations complexes sur n'importe quel type de conteneur !

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 avec les algorithmes  count  et  count_if

Comptez des éléments avec  count

Pour compter le nombre d'éléments égaux à une valeur donnée, comme 2 par exemple, c'est très simple, on utilise l'algorithme count :

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

Et bien sûr, tab est le conteneur de votre choix.

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

Comptez des éléments sur un critère donné avec  count_if

On peut aussi ne compter que les éléments qui passent un certain test. Et si je vous en parle, c'est qu'un tel algorithme existe pour faire cela. 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 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.

Cherchez des éléments avec  find  ou  find_if

Pour chercher un élément dans un tableau, on utilise l'algorithme find ou find_if  .

Pour chercher la lettre "a" dans une deque de 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.

Triez des éléments avec  sort

On doit souvent trier une série d'éléments. Cela dit, écrire une fonction de tri optimisée n'est pas une mince affaire. Heureusement, la STL propose une fonction pour cela : sort  .

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

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 ?

Affichez le contenu d'un  vector

Ne nous arrêtons pas en si bon chemin.

Dans l'exemple du tri, j'affichais le contenu du vector via 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 :

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, comme calculer la somme des éléments d'un conteneur, par exemple. 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_somme en utilisant la méthode resultat()  .

Heureusement pour nous, 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.

Un petit foncteur pour le calcul de la moyenne, un for_each() et le tour est joué !

Traitez deux conteneurs à la fois avec  transform()

Terminons par un dernier algorithme bien pratique pour traiter deux conteneurs à la fois.

Imaginons : on veut 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 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.

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

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

Vous venez de découvrir la puissance des itérateurs, il faut donc les exploiter dès que c’est nécessaire, sans modération. Je propose de continuer notre aventure avec les itérateurs dans le prochain chapitre, et voir comment les utiliser sur les flux.