• Les algorithmes

    Chapitre 18. Les algorithmes


    La plupart des opérations qui peuvent être appliquées aux structures de données ne sont pas spécifiques à ces structures. Par exemple, il est possible de trier quasiment toutes les séquences, que ce soient des listes, des vecteurs ou des deques. Les classes template des conteneurs de la bibliothèque standard ne fournissent donc que des méthodes de base permettant de les manipuler, et rares sont les conteneurs qui définissent des opérations dont le rôle dépasse le simple cadre de l'ajout, de la suppression ou de la recherche d'éléments. Au lieu de cela, la bibliothèque standard définit tout un jeu de fonctions template extérieures aux conteneurs et dont le but est de réaliser ces opérations de haut niveau. Ces fonctions sont appelées algorithmes en raison du fait qu'elles effectuent les traitements des algorithmes les plus connus et les plus utilisés en informatique.

    Les algorithmes ne dérogent pas à la règle de généricité que la bibliothèque standard C++ s'impose. Autrement dit, ils sont capables de travailler en faisant le moins d'hypothèses possibles sur la structure de données contenant les objets sur lesquels ils s'appliquent. Ainsi, tous les algorithmes sont des fonctions template et ils travaillent sur les objets exclusivement par l'intermédiaire d'itérateurs et de foncteurs. Cela signifie que les algorithmes peuvent, en pratique, être utilisés sur n'importe quelle structure de données ou n'importe quel conteneur, pourvu que les préconditions imposées sur les itérateurs et le type des données manipulées soient respectées.

    Comme pour les méthodes permettant de manipuler les conteneurs, les algorithmes sont décrits par leur sémantique et par leur complexité. Cela signifie que les implémentations de la bibliothèque standard sont libres quant à la manière de réaliser ces algorithmes, mais qu'elles doivent impérativement respecter les contraintes de performances imposées par la norme de la bibliothèque standard. En pratique cependant, tout comme pour les structures de données des conteneurs, ces contraintes imposent souvent l'algorithme sous-jacent pour l'implémentation de ces fonctionnalités et l'algorithme utilisé est le meilleur algorithme connu à ce jour. Autrement dit, les algorithmes de la bibliothèque standard sont forcément les plus efficaces qui soient.

    La plupart des algorithmes de la bibliothèque standard sont déclarés dans l'en-tête algorithm. Certains algorithmes ont été toutefois définis initialement pour les valarray et n'apparaissent donc pas dans cet en-tête. Au lieu de cela, ils sont déclarés dans l'en-tête numeric. Ces algorithmes sont peu nombreux et cette particularité sera signalée dans leur description.

    Le nombre des algorithmes définis par la bibliothèque standard est impressionnant et couvre sans doute tous les besoins courants des programmeurs. Il est donc difficile, en raison de cette grande diversité, de présenter les algorithmes de manière structurée. Cependant, les sections suivantes regroupent ces algorithmes en fonction de la nature des opérations qu'ils sont supposés effectuer. Ces opérations comprennent les opérations de manipulation générales des données, les recherches d'éléments selon des critères particuliers, les opérations de tri et de comparaison, et enfin les opérations de manipulation ensemblistes.

    18.1. Opérations générales de manipulation des données

    Les algorithmes généraux de manipulation des données permettent de réaliser toutes les opérations classiques de type création, copie, suppression et remplacement, mais également de modifier l'ordre des séquences d'éléments ainsi que d'appliquer un traitement sur chacun des éléments des conteneurs.

    Certains algorithmes peuvent modifier soit les données contenues par les conteneurs sur lesquels ils travaillent, soit les conteneurs eux-mêmes. En général ces algorithmes travaillent sur place, c'est à dire qu'ils modifient les données du conteneur directement. Cependant, pour certains algorithmes, il est possible de stocker les données modifiées dans un autre conteneur. Le conteneur source n'est donc pas modifié et les données, modifiées ou non, sont copiées dans le conteneur destination. En général, les versions des algorithmes capables de faire cette copie à la volée ne sont fournies que pour les algorithmes peu complexes car le coût de la copie peut dans ce cas être aussi grand ou plus grand que le coût du traitement des algorithmes eux-mêmes. Il est donc justifié pour ces algorithmes de donner la possibilité de réaliser la copie pendant leur traitement afin de permettre aux programmes d'optimiser les programmes selon les cas d'utilisation. Le nom des algorithmes qui réalisent une copie à la volée est le même nom que leur algorithme de base, mais suffixé par le mot « _copy ».

    18.1.1. Opérations d'initialisation et de remplissage

    Il existe deux méthodes permettant d'initialiser un conteneur ou de générer une série d'objets pour initialiser un conteneur. La première méthode ne permet que de générer plusieurs copies d'un même objet, que l'on spécifie par valeur, alors que la deuxième permet d'appeler une fonction de génération pour chaque objet à créer.

    Les algorithmes de génération et d'initialisation sont déclarés de la manière suivante dans l'en-tête algorithm :

    template <class ForwarIterator, class T>
    void fill(ForwardIterator premier, ForwardIterator dernier, const T &valeur);

    template <class OutputIterator, class T>
    void fill_n(OutputIterator premier, Size nombre, const T &valeur);

    tempalte <class ForwardIterator, class T, class Generator>
    void generate(ForwardIterator premier, ForwardIterator dernier, Generator g);

    template <class OutputIterator, class T, class Generator>
    void generate_n(OutputIterator premier, Size nombre, Generator g);

    Chaque algorithme est disponible sous deux formes différentes. La première utilise un couple d'itérateurs référençant le premier et le dernier élément à initialiser, et la deuxième n'utilise qu'un itérateur sur le premier élément et le nombre d'éléments à générer. Le dernier paramètre permet de préciser la valeur à affecter aux éléments du conteneur cible pour les algorithmes fill et fill_n, ou un foncteur permettant d'obtenir une nouvelle valeur à chaque invocation. Ce foncteur ne prend aucun paramètre et renvoie la nouvelle valeur de l'objet.

    Exemple 18-1. Algorithme de génération d'objets et de remplissage d'un conteneur

    #include <iostream>
    #include <list>
    #include <iterator>
    #include <algorithm>

    using namespace std;

    int compte()
    {
    static int i = 0;
    return i++;
    }

    int main(void)
    {
    // Crée une liste de 20 entiers consécutifs :
    typedef list<int> li;
    li l;
    generate_n(back_inserter(l), 20, compte);
    // Affiche la liste :
    li::iterator i = l.begin();
    while (i != l.end())
    {
    cout << *i << endl;
    ++i;
    }
    return 0;
    }

    Ces algorithmes effectuent exactement autant d'affectations qu'il y a d'éléments à créer ou à initialiser. Leur complexité est donc linéaire en fonction du nombre de ces éléments.

    18.1.2. Opérations de copie

    La bibliothèque standard définit deux algorithmes fondamentaux pour réaliser la copie des données des conteneurs. Ces algorithmes sont déclarés comme suit dans l'en-tête algorithm :

    template <class InputIterator, class OutputIterator>
    OutputIterator copy(InputIterator premier, InputIterator dernier,
    OutputIterator destination);

    template <class BidirectionalIterator1, class BidirectionalIterator2>
    BidirectionalIterator2 copy_backward(
    BidirectionalIterator1 premier, BidirectionalIterator1 dernier,
    BidirectionalIterator2 fin_destination);

    Alors que copy réalise la copie des objets référencés par les itérateurs premier et dernier du premier vers le dernier, l'algorithme backward_copy travaille dans le sens contraire. On utilisera donc typiquement backward_copy à chaque fois que la zone mémoire destination empiète sur la fin des données sources. Notez que dans ce cas, l'itérateur spécifiant la destination référence le dernier emplacement utilisé après la copie et non le premier élément. Autrement dit, l'itérateur fin_destination est utilisé de manière descendante, alors que l'itérateur destination fourni à l'algorithme copy est utilisé de manière ascendante.

    Exemple 18-2. Algorithme de copie inverse

    #include <iostream>
    #include <algorithm>
    #include <cstring>

    using namespace std;

    int main(void)
    {
    char sBuffer[] = "abcdefg123";
    // Détermine l'itérateur de fin :
    char *pFin = sBuffer + strlen(sBuffer);
    // Écrase la chaîne par elle-même à partir du 'd' :
    copy_backward(sBuffer, pFin-3, pFin);
    // Affiche le résultat :
    cout << sBuffer << endl;
    return 0;
    }

    Note : La fonction strlen utilisée dans cet exemple est une des fonctions de la bibliothèque C standard, qui est déclarée dans l'en-tête cstring. Elle permet de calculer la longueur d'une chaîne de caractères C (sans compter le caratère nul terminal).

    Ces algorithmes effectuent exactement autant d'affectation qu'il y a d'éléments à copier. Leur complexité est donc linéaire en fonction du nombre de ces éléments.

    Note : Il existe également des algorithmes capables de réaliser une copie de leur résultat à la volée. Le nom de ces algorithmes est généralement le nom de leur algorithme de base suffixé par la chaîne _copy. Ces algorithmes seront décrits avec leurs algorithmes de base.

    18.1.3. Opérations d'échange d'éléments

    Il est possible d'échanger le contenu de deux séquences d'éléments grâce à un algorithme dédié à cette tâche, l'algorithme swap_ranges. Cet algorithme est déclaré comme suit dans l'en-tête algorithm :

    template <class ForwardIterator, class ForwardIterator2>
    ForwardIterator2 swap_ranges(ForwardIterator premier, ForwardIterator dernier,
    ForwardIterator2 destination);

    Cet algorithme prend en paramètre les deux itérateurs définissant la première séquence et un itérateur destination permettant d'indiquer le premier élément de la deuxième séquence avec les éléments de laquelle l'échange doit être fait. La valeur retournée est l'itérateur de fin de cette séquence, une fois l'opération terminée.

    Exemple 18-3. Algorithme d'échange

    #include <iostream>
    #include <list>
    #include <algorithm>

    using namespace std;

    int main(void)
    {
    // Définit une liste d'entiers :
    typedef list<int> li;
    li l;
    l.push_back(2);
    l.push_back(5);
    l.push_back(3);
    l.push_back(7);
    // Définit un tableau de quatre éléments :
    int t[4] = {10, 11, 12, 13};
    // Échange le contenu du tableau et de la liste :
    swap_ranges(t, t+4, l.begin());
    // Affiche le tableau :
    int i;
    for (i=0; i<4; ++i)
    cout << t[i] << " ";
    cout << endl;
    // Affiche la liste :
    li::iterator it = l.begin();
    while (it != l.end())
    {
    cout << *it << " ";
    ++it;
    }
    cout << endl;
    return 0;
    }

    Cet algorithme n'échange pas plus d'éléments que nécessaire, autrement dit, il a une complexité linéaire en fonction de la taille de la séquence initiale.

    18.1.4. Opérations de suppression d'éléments

    Les conteneurs de la bibliothèque standard disposent tous de méthodes puissantes permettant d'effectuer des suppressions d'éléments selon différents critères. Toutefois, la bibliothèque standard définit également des algorithmes de suppression d'éléments dans des séquences. En fait, ces algorithmes n'effectuent pas à proprement parler de suppression, mais une réécriture des séquences au cours de laquelle les éléments à supprimer sont tout simplement ignorés. Ces algorithmes renvoient donc l'itérateur du dernier élément copié, au-delà duquel la séquence initiale est inchangée.

    La bibliothèque standard fournit également des versions de ces algorithmes capables de réaliser une copie à la volée des éléments de la séquence résultat. Ces algorithmes peuvent donc typiquement être utilisés pour effectuer un filtre sur des éléments dont le but serait de supprimer les éléments indésirables.

    Les fonctions de suppression des éléments sont déclarées comme suit dans l'en-tête algorithm :

    template <class ForwardIterator, class T>
    ForwardIterator remove(ForwardIterator premier, ForwardIterator second,
    const T &valeur);

    template <class InputIterator, class OutputIterator, class T>
    OutputIterator remove_copy(InputIterator premier, InputIterator second,
    OutputIterator destination, const T &valeur);

    template <class ForwardIterator, class Predicate>
    ForwardIterator remove_if(ForwardIterator premier, ForwardIterator second,
    Predicate p);

    template <class InputIterator, class OutputIterator, class Predicate>
    OutputIterator remove_copy_if(InputIterator premier, InputIterator second,
    OutputIterator destination, Predicate p);

    Toutes ces fonctions prennent en premier et en deuxième paramètre les itérateurs définissant l'intervalle d'éléments sur lequel elles doivent travailler. Pour les fonctions de suppression d'un élément particulier, la valeur de cet élément doit également être fournie. Si vous préférez utiliser les versions basées sur un prédicat, il vous faut spécifier un foncteur unaire prenant en paramètre un élément et renvoyant un booléen indiquant si cet élément doit être supprimé ou non. Enfin, les versions de ces algorithmes permettant de réaliser une copie à la volée nécessitent bien entendu un itérateur supplémentaire indiquant l'emplacement destination où les éléments non supprimés devront être stockés.

    Comme vous pouvez le constater d'après leurs déclarations, ces algorithmes renvoient tous un itérateur référençant l'élément suivant le dernier élément de la séquence résultat. Cet itérateur permet de déterminer la fin de la séquence d'éléments résultat, que cette séquence ait été modifiée sur place ou qu'une copie ait été réalisée. Si l'algorithme utilisé n'effectue pas de copie, les éléments suivant cet itérateur sont les éléments de la séquence initiale. C'est à ce niveau que la différence entre les algorithmes de suppression et les méthodes erase des conteneurs (et les méthodes remove des listes) apparaît : les algorithmes écrasent les éléments supprimés par les éléments qui les suivent, mais ne suppriment pas les éléments source du conteneur situés au-delà de l'itérateur renvoyé, alors que les méthodes erase des conteneurs suppriment effectivement des conteneurs les éléments à éliminer.

    Exemple 18-4. Algorithme de suppression

    #include <iostream>
    #include <algorithm>

    using namespace std;

    int main(void)
    {
    // Construit un tableau de 10 entiers :
    int t[10] = { 1, 2, 2, 3, 5, 2, 4, 3, 6, 7 };
    // Supprime les entiers valant 2 :
    int *fin = remove(t, t+10, 2);
    // Affiche le tableau résultat :
    int *p = t;
    while (p != fin)
    {
    cout << *p << endl;
    ++p;
    }
    return 0;
    }

    De manière similaire, la bibliothèque standard définit également des algorithmes permettant de supprimer les doublons dans des séquences d'éléments. Ces algorithmes sont déclarés comme suit dans l'en-tête algorithm :

    template<class ForwardIterator>
    ForwardIterator unique(ForwardIterator premier, ForwardIterator dernier);

    template<class ForwardIterator, class OutputIterator>
    OutputIterator unique_copy(ForwardIterator premier, ForwardIterator dernier);

    template <class ForwardIterator, class BinaryPredicate>
    ForwardIterator unique(ForwardIterator premier, ForwardIterator dernier,
    BinaryPredicate p);

    template <class ForwardIterator, class OutputIterator, class BinaryPredicate>
    OutputIterator unique_copy(ForwardIterator premier, ForwardIterator dernier,
    BinaryPredicate p);

    Ces algorithmes fonctionnent de la même manière que les algorithmes remove à ceci près qu'ils n'éliminent que les doublons dans la séquence source. Cela signifie qu'il n'est pas nécessaire de préciser la valeur des éléments à éliminer d'une part et, d'autre part, que les prédicats utilisés sont des prédicats binaires puisqu'ils doivent être appliqués aux couples d'éléments successifs.

    Note : Il n'existe pas d'algorithmes unique_if et unique_copy_if. La bibliothèque standard utilise les possibilités de surcharge du C++ pour distinguer les versions avec et sans prédicat des algorithmes de suppression des doublons.

    Exemple 18-5. Algorithme de suppression des doublons

    #include <iostream>
    #include <algorithm>

    using namespace std;

    int main(void)
    {
    // Construit un tableau de 10 entiers :
    int t[10] = { 1, 2, 2, 3, 5, 2, 4, 3, 6, 7 };
    // Supprime les doublons :
    int *fin = unique(t, t+10);
    // Affiche le tableau résultat :
    int *p = t;
    while (p != fin)
    {
    cout << *p << endl;
    ++p;
    }
    return 0;
    }

    Le test de suppression est appliqué par ces algorithmes autant de fois qu'il y a d'éléments dans la séquence initiale, c'est-à-dire que leur complexité est linéaire en fonction du nombre d'éléments de cette séquence.

    18.1.5. Opérations de remplacement

    Les algorithmes de remplacement permettent de remplacer tous les éléments d'un conteneur vérifiant une propriété particulière par un autre élément dont la valeur doit être fournie en paramètre. Les éléments devant être remplacés peuvent être identifiés soit par leur valeur, soit par un prédicat unaire prenant en paramètre un élément et renvoyant un booléen indiquant si cet élément doit être remplacé ou non. Les algorithmes de remplacement sont déclarés comme suit dans l'en-tête algorithm :

    template <class ForwardIterator, class T>
    void replace(ForwardIterator premier, ForwardIterator dernier,
    const T &ancienne_valeur, const T &nouvelle_valeur);

    template <class InputIterator, class OutputIterator, class T>
    void replace_copy(InputIterator premier, InputIterator dernier,
    OutputIterator destination,
    const T &ancienne_valeur, const T &nouvelle_valeur);

    template <class ForwardIterator, class Predicate, class T>
    void replace_if(ForwardIterator premier, ForwardIterator dernier,
    Predicate p, const T &nouvelle_valeur);

    template <class InputIterator, class OutputIterator,
    class Predicate, class T>
    void replace_copy_if(InputIterator premier, InputIterator dernier,
    OutputIterator destination,
    Predicate p, const T &nouvelle_valeur);

    Les algorithmes de remplacement peuvent travailler sur place ou effectuer une copie à la volée des éléments sur lesquels ils travaillent. Les versions capables de réaliser ces copies sont identifiées par le suffixe _copy de leur nom. Ces algorithmes prennent un paramètre supplémentaire permettant de spécifier l'emplacement destination où les éléments copiés devront être stockés. Ce paramètre est un itérateur, tout comme les paramètres qui indiquent l'intervalle d'éléments dans lequel la recherche et le remplacement doivent être réalisés.

    Exemple 18-6. Algorithme de recherche et de remplacement

    #include <iostream>
    #include <algorithm>

    using namespace std;

    int main(void)
    {
    int t[10] = {1, 2, 5, 3, 2, 7, 6, 4, 2, 1};
    // Remplace tous les 2 par des 9 :
    replace(t, t+10, 2, 9);
    // Affiche le résultat :
    int i;
    for (i=0; i<10; ++i)
    cout << t[i] << endl;
    return 0;
    }

    Le test de remplacement est appliqué par ces algorithmes autant de fois qu'il y a des éléments dans la séquence initiale, c'est-à-dire que leur complexité est linéaire en fonction du nombre d'éléments de cette séquence.

    18.1.6. Réorganisation de séquences

    Comme il l'a été expliqué dans la section 17.12, l'ordre des éléments d'une séquence est important. La plupart des séquences conservent les éléments dans l'ordre dans lequel ils ont été insérés, d'autre se réorganisent automatiquement lorsque l'on travaille dessus pour assurer un ordre bien défini.

    La bibliothèque standard fournit plusieurs algorithmes permettant de réorganiser la séquence des éléments dans un conteneur qui ne prend pas en charge lui-même l'ordre de ses éléments. Ces algorithmes permettent de réaliser des rotations et des permutations des éléments, des symétries et des inversions, ainsi que de les mélanger de manière aléatoire.

    Note : Il existe également des algorithmes de tri extrêmement efficaces, mais ces algorithmes seront décrits plus loin dans une section qui leur est consacrée.

    18.1.6.1. Opérations de rotation et de permutation

    Les algorithmes de rotation permettent de faire tourner les différents éléments d'une séquence dans un sens ou dans l'autre. Par exemple, dans une rotation vers la gauche d'une place, le deuxième élément peut prendre la place du premier, le troisième celle du deuxième, etc., le premier élément revenant à la place du dernier. Ces algorithmes sont déclarés de la manière suivante dans l'en-tête algorithm :

    template <class ForwardIterator>
    void rotate(ForwardIterator premier, ForwardIterator pivot,
    ForwardIterator dernier);

    template <class ForwardIterator, class OutputIterator>
    void rotate_copy(ForwardIterator premier, ForwardIterator pivot,
    ForwardIterator dernier, OutputIterator destination);

    Les algorithmes de rotation prennent en paramètre un itérateur indiquant le premier élément de la séquence devant subir la rotation, un itérateur référençant l'élément qui se trouvera en première position après la rotation, et un itérateur référençant l'élément suivant le dernier élément de la séquence. Ainsi, pour effectuer une rotation d'une position vers la gauche, il suffit d'utiliser pour l'itérateur pivot la valeur de l'itérateur suivant l'itérateur premier et, pour effectuer une rotation d'une position vers la droite, il faut prendre pour l'itérateur pivot la valeur précédant celle de l'itérateur dernier.

    Exemple 18-7. Algorithme de rotation

    #include <iostream>
    #include <algorithm>

    using namespace std;

    int main(void)
    {
    int t[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    // Effectue une rotation pour amener le quatrième
    // élément en première position :
    rotate(t, t+3, t+10);
    // Affiche le résultat :
    int i;
    for (i=0; i<10; ++i)
    cout << t[i] << endl;
    return 0;
    }

    La bibliothèque fournit également des algorithmes permettant d'obtenir l'ensemble des permutations d'une séquence d'éléments. Rappelons qu'une permutation est une des combinaisons possibles des valeurs des différents éléments d'un ensemble, en considérant les éléments d'égale valeur comme identiques. Par exemple, si un ensemble contient deux éléments de même valeur, il n'y a qu'une seule permutation possible : les deux valeurs. Si en revanche ces deux éléments ont deux valeurs distinctes, on peut réaliser deux permutations selon la valeur que l'on place en premier.

    Les algorithmes de permutation de la bibliothèque ne permettent pas d'obtenir les permutations directement. Au lieu de cela, ils permettent de passer d'une permutation à la permutation suivante ou à la précédente. Cela suppose qu'une relation d'ordre soit définie sur l'ensemble des permutations de la séquence. La bibliothèque standard utilise l'ordre lexicographique pour classer ces permutations. Autrement dit, les premières permutations sont celles pour lesquelles les premiers éléments ont les valeurs les plus faibles.

    Les algorithmes de calcul des permutations suivante et précédente sont déclarés comme suit dans l'en-tête algorithm :

    template <class BidirectionalIterator>
    bool next_permutation(BidirectionalIterator premier, BidirectionalIterator dernier);

    template <class BidirectionalIterator>
    bool prev_permutation(BidirectionalIterator premier, BidirectionalIterator dernier);

    Ces algorithmes prennent tous les deux deux itérateurs indiquant les éléments devant subir la permutation et renvoient un booléen indiquant si la permutation suivante ou précédente existe ou non. Si ces permutations n'existent pas, les algorithmes next_permutation et prev_permutation bouclent et calculent respectivement la plus petite et la plus grande permutation de l'ensemble des permutations.

    Exemple 18-8. Algorithme de permutation

    #include <iostream>
    #include <algorithm>

    using namespace std;

    int main(void)
    {
    int t[3] = {1, 1, 2};
    // Affiche l'ensemble des permutations de (1, 1, 2) :
    do
    {
    int i;
    for (i=0; i<3; ++i)
    cout << t[i] << " ";
    cout << endl;
    }
    while (next_permutation(t, t+3));
    return 0;
    }

    Les algorithmes de rotation effectuent autant d'échange qu'il y a d'éléments dans la séquence initiale, et les algorithmes de calcul de permutation en font exactement la moitié. La complexité de ces algorithmes est donc linéaire en fonction du nombre d'éléments de l'intervalle qui doit subir l'opération.

    18.1.6.2. Opérations d'inversion

    Il est possible d'inverser l'ordre des éléments d'une séquence à l'aide des algorithmes reverse et reverse_copy. Ces algorithmes sont déclarés de la manière suivante dans l'en-tête algorithm :

    template <class BidirectionalIterator>
    void reverse(BidirectionalIterator premier, BidirectionalIterator dernier);

    template <class BidirectionalIterator, class OutputIterator>
    OutputIterator reverse_copy(BidirectionalIterator premier,
    BidirectionalIterator dernier, OutputIterator destination);

    Ces algorithmes prennent en paramètre les itérateurs permettant de spécifier l'intervalle des éléments qui doit être inversé. La version de cet algorithme qui permet de réaliser une copie prend un paramètre supplémentaire qui doit recevoir l'itérateur référençant l'emplacement destination dans lequel le résultat de l'inversion doit être stocké. Cet itérateur retourne la valeur de l'itérateur destination passé le dernier élément écrit.

    Exemple 18-9. Algorithme d'inversion

    #include <iostream>
    #include <algorithm>

    using namespace std;

    int main(void)
    {
    int t[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    // Inverse le tableau :
    reverse(t, t+10);
    // Affiche le résultat :
    int i;
    for (i=0; i<10; ++i)
    cout << t[i] << endl;
    return 0;
    }

    Les algorithmes d'inversion effectuent autant d'échange d'éléments qu'il y en a dans la séquence initiale. Autrement dit, leur complexité est linéaire en fonction de la taille de cette séquence.

    18.1.6.3. Opérations de mélange

    Il est possible de redistribuer aléatoirement les éléments d'une séquence à l'aide de l'algorithme random_shuffle. Cet algorithme est fourni sous la forme de deux surcharges déclarées comme suit dans l'en-tête algorithm :

    template <class RandomAccessIterator>
    void random_shuffle(RandomAccessIterator premier, RandomAccessIterator dernier);

    template <class RandomAccessIterator, class RandomNumberGenerator>
    void random_shuffle(RandomAccessIterator premier, RandomAccessIterator dernier,
    RandomNumberGenerator g);

    Ces algorithmes prennent en paramètre les itérateurs de début et de fin de la séquence dont les éléments doivent être mélangés. La deuxième version de cet algorithme peut prendre en dernier paramètre un foncteur qui sera utilisé pour calculer les positions des éléments pendant le mélange. Ainsi, cette surcharge permet de spécifier soi-même la fonction de distribution à utiliser pour effectuer cette nouvelle répartition. Ce foncteur doit prendre en paramètre une valeur du type difference_type des itérateurs utilisés pour référencer les éléments de la séquence, et renvoyer une valeur comprise entre 0 et la valeur reçue en paramètre. Il doit donc se comporter comme la fonction rand de la bibliothèque standard C (déclarée dans le fichier d'en-tête cstdlib).

    Exemple 18-10. Algorithme de mélange

    #include <iostream>
    #include <algorithm>

    using namespace std;

    int main(void)
    {
    int t[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    // Mélange le tableau t :
    random_shuffle(t, t+10);
    // Affiche le résultat :
    int i;
    for (i=0; i<10; ++i)
    cout << t[i] << endl;
    return 0;
    }

    Ces algorithmes effectuent exactement le nombre d'éléments de la séquence à mélanger moins un échanges de valeurs. Leur complexité est donc linéaire en fonction du nombre d'éléments de ces séquences.

    18.1.7. Algorithmes d'itération et de transformation

    Les algorithmes de transformation et d'itération de la bibliothèque standard font partie des plus utiles puisqu'ils permettent d'effectuer un traitement sur l'ensemble des éléments d'un conteneur. Ces traitements peuvent modifier ou non ces éléments ou tout simplement calculer une valeur à partir de ces éléments.

    Les deux principaux algorithmes fournis par la bibliothèque standard sont sans doute les algorithmes for_each et transform, qui permettent d'effectuer une action sur chaque élément d'un conteneur. Ces algorithmes sont déclarés comme suit dans l'en-tête algorithm :

    template <class InputIterator, class Function>
    Function for_each(InputIterator premier, InputIterator dernier, Function f);

    template <class InputIterator, class OutputIterator,
    class UnaryOperation>
    OutputIterator transform(InputIterator premier, InputIterator dernier,
    OutputIterator destination, UnaryOperation op);

    template <class InputIterator1, class InputIterator2,
    class OutputIterator, class BinaryOperation>
    OutputIterator transform(InputIterator1 premier1, InputIterator1 dernier1,
    InputIterator2 premier2, OutputIterator destination,
    BinaryOperation op);

    L'algorithme for_each permet d'itérer les éléments d'un conteneur et d'appeler une fonction pour chacun de ces éléments. Il prend donc en paramètre deux itérateurs permettant de spécifier les éléments à itérer et un foncteur qui sera appelé à chaque itération. Pendant l'itération, ce foncteur reçoit en paramètre la valeur de l'élément de l'itération courante de la part de for_each. Cette valeur ne doit en aucun cas être modifiée et la valeur retournée par ce foncteur est ignorée. La valeur retournée par l'algorithme for_each est le foncteur qui lui a été communiqué en paramètre.

    Contrairement à for_each, qui ne permet pas de modifier les éléments qu'il itère, l'algorithme transform autorise la modification des éléments du conteneur sur lequel il travaille. Il est fourni sous deux versions, la première permettant d'appliquer un foncteur unaire sur chaque élément d'un conteneur et la deuxième un foncteur binaire sur deux éléments de deux conteneurs sur lesquels l'algorithme itère simultanément. Les deux versions prennent en premiers paramètres les itérateurs permettant de spécifier les éléments à itérer du premier conteneur. Ils prennent également en paramètre un foncteur permettant de calculer une nouvelle valeur à partir des éléments itérés et un itérateur dans lequel les résultats de ce foncteur seront stockés. La version permettant de travailler avec un foncteur binaire prend un paramètre complémentaire, qui doit recevoir la valeur de l'itérateur de début du conteneur devant fournir les éléments utilisés en tant que second opérande du foncteur. La valeur retournée par les algorithmes transform est la valeur de fin de l'itérateur destination.

    Exemple 18-11. Algorithmes d'itération

    #include <iostream>
    #include <functional>
    #include <algorithm>

    using namespace std;

    void aff_entier(int i)
    {
    cout << i << endl;
    }

    int main(void)
    {
    int t[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    // Inverse tous les éléments du tableau :
    transform(t, t+10, t, negate<int>());
    // Affiche le résultat :
    for_each(t, t+10, ptr_fun(&aff_entier));
    return 0;
    }

    Comme vous pouvez le constater d'après cet exemple, il est tout à fait possible d'utiliser la même valeur pour l'itérateur premier et l'itérateur destination. Cela signifie que les éléments itérés peuvent être remplacés par les nouvelles valeurs calculées par le foncteur fourni à l'algorithme transform.

    Un cas particulier des algorithmes d'itération est celui des algorithmes count et count_if puisque le traitement effectué est alors simplement le décompte des éléments vérifiant une certaine condition. Ces deux algorithmes permettent en effet de compter le nombre d'éléments d'un conteneur dont la valeur est égale à une valeur donnée ou vérifiant un critère spécifié par l'intermédiaire d'un prédicat unaire. Ces deux algorithmes sont déclarés de la manière suivante dans l'en-tête algorithm :

    template <class InputIterator, class T>
    iterator_traits<InputIterator>::difference_type
    count(InputIterator premier, InputIterator dernier, const T &valeur);

    template <class InputIterator, class Predicate>
    iterator_traits<InputIterator>::difference_type
    count_if(InputIterator premier, InputIterator dernier, Predicate p);

    Comme vous pouvez le constater, ces algorithmes prennent en paramètre deux itérateurs spécifiant l'intervalle des éléments sur lesquels le test doit être effectué, et la valeur avec laquelle ces éléments doivent être comparés ou un prédicat unaire. Dans ce cas, le résultat de ce prédicat indique si l'élément qu'il reçoit en paramètre doit être compté ou non.

    Exemple 18-12. Algorithme de décompte d'éléments

    #include <iostream>
    #include <functional>
    #include <algorithm>

    using namespace std;

    bool parity_even(int i)
    {
    return (i & 1) == 0;
    }

    int main(void)
    {
    int t[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    // Compte le nombre d'éléments pairs :
    cout << count_if(t, t+10, ptr_fun(&parity_even)) << endl;
    return 0;
    }

    Tous les algorithmes d'itération ne font qu'un seul passage sur chaque élément itéré. Autrement dit, la complexité de ces algorithmes est linéaire en fonction du nombre d'éléments compris entre les deux itérateurs spécifiant l'intervalle d'éléments sur lequel ils sont appliqués.

    Enfin, la bibliothèque standard fournit des algorithmes de calcul plus évolués, capables de travailler sur les éléments des conteneurs. Ces algorithmes sont généralement utilisés en calcul numérique et ont été conçus spécialement pour les tableaux de valeurs. Cependant, ils restent tout à fait utilisables sur d'autres conteneurs que les valarray, la seule distinction qu'ils ont avec les autres algorithmes de la bibliothèque standard est qu'ils sont déclarés dans l'en-tête numeric au lieu de l'en-tête algorithm. Ces algorithmes sont les suivants :

    template <class InputIterator, class T>
    T accumulate(InputIterator premier, InputIterator dernier, T init);

    template <class InputIterator, class T, class BinaryOperation>
    T accumulate(InputIterator premier, InputIterator dernier,
    T init, BinaryOperation op);

    template <class InputIterator1, class InputIterator2, class T>
    T inner_product(InputIterator1 premier1, InputIterator1 dernier1,
    InputIterator2 premier2, T init);

    template <class InputIterator1, class InputIterator2, class T,
    class BinaryOperation1, class BinaryOperation2>
    T inner_product(InputIterator1 premier1, InputIterator1 dernier1,
    InputIterator2 premier2, T init,
    BinaryOperation1 op1, BinaryOperation op2);

    template <class InputIterator, class OutputIterator>
    OutputIterator partial_sum(InputIterator premier, InputIterator dernier,
    OutputIterator destination);

    template <class InputIterator, class OutputIterator, class BinaryOperation>
    OutputIterator partial_sum(InputIterator premier, InputIterator dernier,
    OutputIterator destination, BinaryOperation op);

    template <class InputIterator, class OutputIterator>
    OutputIterator adjacent_difference(InputIterator premier, InputIterator dernier,
    OutputIterator destination);

    template <class InputIterator, class OutputIterator, class BinaryOperation>
    OutputIterator adjacent_difference(InputIterator premier, InputIterator dernier,
    OutputIterator destination, BinaryOperation op);

    Ces algorithmes correspondent à des opérations courantes, que l'on fait généralement sur les tableaux de nombres de type valarray. L'algorithme accumulate permet généralement de réaliser la somme des valeurs qui sont stockées dans un conteneur. L'algorithme inner_product est utilisé quant à lui pour réaliser le produit scalaire de deux séquences de nombres, opération mathématique généralement effectuée dans le calcul vectoriel. Enfin, les algorithmes partial_sum et adjacent_difference réalisent respectivement le calcul des sommes partielles et des différences deux à deux des éléments d'un conteneur.

    Pout tous ces algorithmes, il est possible d'utiliser d'autres opérations que les opérations généralement utilisées. Par exemple, accumulate peut utiliser une autre opération que l'addition pour « accumuler » les valeurs des éléments. Pour cela, la bibliothèque standard fournit des surcharges de ces algorithmes capables de travailler avec des foncteurs binaires. Ces foncteurs doivent accepter deux paramètres du type des éléments du conteneur sur lequel les algorithmes sont appliqués et renvoyer une valeur du même type, calculée à partir de ces paramètres.

    L'algorithme accumulate prend donc en premiers paramètres les itérateurs définissant l'intervalle des valeurs qui doivent être accumulées. Il initialise la valeur d'une variable accumulateur avec la valeur fournie en troisième paramètre, et parcours l'ensemble des éléments. Pour chaque élément traité, accumulate remplace la valeur courante de l'accumulateur par le résultat de l'opération d'accumulation appliquée à l'accumulateur lui-même et à la valeur de l'élément courant. Par défaut, l'opération d'accumulation utilisée est l'addition, mais il est possible de changer ce comportement en fournissant un foncteur binaire en dernier paramètre. Lorsque l'ensemble des éléments a été parcouru, la valeur de l'accumulateur est retournée.

    Exemple 18-13. Algorithme d'accumulation

    #include <list>
    #include <numeric>
    #include <functional>
    #include <iostream>

    using namespace std;

    int main(void)
    {
    // Construit une liste d'entiers :
    typedef list<int> li;
    li l;
    l.push_back(5);
    l.push_back(2);
    l.push_back(9);
    l.push_back(1);
    // Calcule le produit de ces entiers :
    int res = accumulate(l.begin(), l.end(),
    1, multiplies<int>());
    cout << res << endl;
    return 0;
    }

    L'algorithme inner_product travaille sur deux conteneurs simultanément et réalise leur produit scalaire. Le produit scalaire est l'opération qui consiste à multiplier les éléments de deux séries de nombres deux à deux, et de faire la somme des résultats. L'algorithme inner_product prend donc en paramètre les itérateurs de début et de fin spécifiant la première série de nombres, l'itérateur de début de la deuxième série de nombres, et la valeur initiale de l'accumulateur utilisé pour réaliser la somme des produits des éléments de ces deux conteneurs. Bien entendu, tout comme pour l'algorithme accumulate, il est possible de remplacer les opérations de multiplication et d'addition de l'algorithme standard par deux foncteurs en fournissant ceux-ci en derniers paramètres.

    Exemple 18-14. Algorithme de produit scalaire

    #include <iostream>
    #include <numeric>

    using namespace std;

    int main(void)
    {
    // Définit deux vecteurs orthogonaux :
    int t1[3] = {0, 1, 0};
    int t2[3] = {0, 0, 1};
    // Calcule leur produit scalaire :
    int res = inner_product(t1, t1+3, t2, 0);
    // Le produit scalaire de deux vecteurs orthogonaux
    // est toujours nul :
    cout << res << endl;
    return 0;
    }

    L'algorithme partial_sum permet de calculer la série des sommes partielles de la suite de valeurs spécifiée par les deux itérateurs fournis en premiers paramètres. Cette série de sommes contiendra d'abord la valeur du premier élément, puis la valeur de la somme des deux premiers éléments, puis la valeur de la somme des trois premiers éléments, etc., et enfin la somme de l'ensemble des éléments de la suite de valeurs sur laquelle l'algorithme travaille. Toutes ces valeurs sont stockées successivement aux emplacements indiqués par l'itérateur destination. Comme pour les autres algorithmes, il est possible de spécifier une autre opération que l'addition à l'aide d'un foncteur binaire que l'on passera en dernier paramètre.

    Enfin, l'algorithme adjacent_difference est l'algorithme inverse de l'algorithme parial_sum. En effet, il permet de calculer la série des différences des valeurs des éléments successifs d'une suite de valeurs, pris deux à deux. Cet algorithme prend en paramètre les itérateurs décrivant la suite de valeurs sur laquelle il doit travailler, l'itérateur de l'emplacement destination où les résultats devront être stockés et éventuellement le foncteur à appliquer aux couples d'éléments successifs traités par l'algorithme. La première différence est calculée en supposant que l'élément précédent le premier élément a pour valeur la valeur nulle. Ainsi, le premier élément de l'emplacement destination est toujours égal au premier élément de la suite de valeurs sur laquelle l'algorithme travaille.

    Exemple 18-15. Algorithmes de sommes partielles et de différences adjacentes

    #include <iostream>
    #include <numeric>

    using namespace std;

    int main(void)
    {
    int t[4] = {1, 1, 1, 1};
    // Calcule les sommes partielles des éléments
    // du tableau :
    partial_sum(t, t+4, t);
    // Affiche le résultat :
    int i;
    for (i=0; i<4; ++i)
    cout << t[i] << " ";
    cout << endl;
    // Calcule les différences adjacentes :
    adjacent_difference(t, t+4, t);
    // C'est le tableau initial :
    for (i=0; i<4; ++i)
    cout << t[i] << " ";
    cout << endl;
    return 0;
    }

    Tous ces algorithmes travaillent en une seule passe sur les éléments des conteneurs sur lesquels ils s'appliquent. Leur complexité est donc linéaire en fonction du nombre d'éléments spécifiés par les itérateurs fournis en premier paramètre.



  • Commentaires

    Aucun commentaire pour le moment

    Suivre le flux RSS des commentaires


    Ajouter un commentaire

    Nom / Pseudo :

    E-mail (facultatif) :

    Site Web (facultatif) :

    Commentaire :