Cours de C/C++


précédentsommairesuivant

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 :

 
Sélectionnez

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
Sélectionnez

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

 
Sélectionnez

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
Sélectionnez

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

 
Sélectionnez

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
Sélectionnez

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

 
Sélectionnez

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
Sélectionnez

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

 
Sélectionnez

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
Sélectionnez

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

 
Sélectionnez

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
Sélectionnez

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

XXI-A-6. 18.1.6. Réorganisation de séquences

Comme il l'a été expliqué dans la Section 17.2, 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 :

 
Sélectionnez

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
Sélectionnez

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

 
Sélectionnez

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
Sélectionnez

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

 
Sélectionnez

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
Sélectionnez

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

 
Sélectionnez

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
Sélectionnez

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

 
Sélectionnez

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
Sélectionnez

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

 
Sélectionnez

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
Sélectionnez

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

 
Sélectionnez

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
Sélectionnez

#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
Sélectionnez

#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
Sélectionnez

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

18.2. Opérations de recherche

En général, la plupart des opérations de recherche de motifs que les programmes sont susceptibles d'effectuer se font sur des chaînes de caractères ou sur les conteneurs associatifs. Cependant, il peut être nécessaire de rechercher un élément dans un conteneur selon un critère particulier ou de rechercher une séquence d'éléments constituant un motif à retrouver dans la suite des éléments d'un conteneur. Enfin, il est relativement courant d'avoir à rechercher les groupes d'éléments consécutifs disposant de la même valeur dans un conteneur. Toutes ces opérations peuvent être réalisées à l'aide des algorithmes de recherche que la bibliothèque standard met à la disposition des programmeurs.

18.2.1. Opération de recherche d'éléments

Le premier groupe d'opérations de recherche contient tous les algorithmes permettant de retrouver un élément dans un conteneur, en l'identifiant soit par sa valeur, soit par une propriété particulière. Toutefois, cet élément peut ne pas être le seul élément vérifiant ce critère. La bibliothèque standard définit donc plusieurs algorithmes permettant de rechercher ces éléments de différentes manières, facilitant ainsi les opérations de recherche dans différents contextes.

Les algorithmes de recherche d'éléments sont les algorithmes find et find_if, qui permettent de retrouver le premier élément d'un conteneur vérifiant une propriété particulière, et l'algorithme find_first_of, qui permet de retrouver le premier élément vérifiant une relation avec une valeur parmi un ensemble de valeurs données. Tous ces algorithmes sont déclarés dans l'en-tête algorithm :

 
Sélectionnez

template <class InputIterator, class T>
InputIterator find(InputIterator premier, InputIterator dernier, const T &valeur);
 
template <class InputIterator, class Predicate>
InputIterator find_if(InputIterator premier, InputIterator dernier, Predicate p);
 
template <class InputIterator, class ForwardIterator>
InputIterator find_first_of(InputIterator premier1, InputIterator dernier1,
    ForwardIterator premier2, ForwardIterator dernier2);
 
template <class InputIterator, class ForwardIterator, class BinaryPredicate>
InputIterator find_first_of(InputIterator premier1, InputIterator dernier1,
    ForwardIterator premier2, ForwardIterator dernier2,
    BinaryPredicate p);
 

L'algorithme find prend en paramètre les deux itérateurs classiques définissant la séquence d'éléments dans laquelle la recherche doit être effectuée. Il prend également en paramètre la valeur de l'élément recherché, et renvoie un itérateur sur le premier élément qui dispose de cette valeur. Si vous désirez effectuer une recherche sur un autre critère que l'égalité des valeurs, vous devez utiliser l'algorithme find_if. Celui-ci prend un prédicat en paramètre à la place de la valeur. C'est la valeur de ce prédicat, appliqué à l'élément courant dans le parcours des éléments de la séquence définie par les itérateurs premier et dernier, qui permettra de déterminer si cet élément est celui recherché ou non. La valeur retournée est l'itérateur dernier si aucun élément ne correspond au critère de recherche. La complexité de cet algorithme est linéaire en fonction du nombre d'éléments de la séquence d'éléments dans laquelle la recherche se fait.

L'algorithme find_first_of prend deux couples d'itérateurs en paramètre. Le premier définit l'intervalle d'éléments dans lequel la recherche doit être effectuée et le deuxième un ensemble de valeur dont les éléments doivent être recherchés. L'algorithme renvoie un itérateur sur le premier élément qui est égal à l'une des valeurs de l'ensemble de valeurs spécifié par le deuxième couple d'itérateurs, ou l'itérateur dernier1 si cet élément n'existe pas. Il est également possible d'utiliser un autre critère que l'égalité avec l'un des éléments de cet ensemble en utilisant un prédicat binaire dont la valeur indiquera si l'élément courant vérifie le critère de recherche. Lorsqu'il est appelé par l'algorithme, ce prédicat reçoit en paramètre l'élément courant de la recherche et l'une des valeurs de l'ensemble de valeurs spécifié par les itérateurs premier2 et dernier2. La complexité de cet algorithme est n×m, où n est le nombre d'éléments de la séquence dans laquelle la recherche est effectuée et m est le nombre de valeurs avec lesquelles ces éléments doivent être comparés.

Exemple 18-16. Algorithme de recherche d'éléments
Sélectionnez

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main(void)
{
    int t[10] = {0, 5, 3, 4, 255, 7, 0, 5, 255, 9};
    // Recherche les éléments valant 0 ou 255 :
    int sep[2] = {0, 255};
    int *debut = t;
    int *fin = t+10;
    int *courant;
    while ((courant=find_first_of(debut, fin,
        sep, sep+2)) != fin)
    {
        // Affiche la position de l'élément trouvé :
        cout << *courant << " en position " <<
            courant-t << endl;
        debut = courant+1;
    }
    return 0;
}
 

18.2.2. Opérations de recherche de motifs

Les opérations de recherche de motifs permettent de trouver les premières et les dernières occurrences d'un motif donné dans une suite de valeurs. Ces opérations sont réalisées respectivement par les algorithmes search et find_end, dont la déclaration dans l'en-tête algorithm est la suivante :

 
Sélectionnez

template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 search(ForwardIterator1 premier1, ForwardIterator1 dernier1,
    ForwardIterator2 premier2, ForwardIterator2 dernier2);
 
template <class ForwardIterator1, class ForwardIterator2,
    class BinaryPredicate>
ForwardIterator1 search(ForwardIterator1 premier1, ForwardIterator1 dernier1,
    ForwardIterator2 premier2, ForwardIterator2 dernier2,
    BinaryPredicate p);
 
template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 find_end(ForwardIterator1 premier1, ForwardIterator1 dernier1,
    ForwardIterator2 premier2, ForwardIterator2 dernier2);
 
template <class ForwardIterator1, class ForwardIterator2,
    class BinaryPredicate>
ForwardIterator1 find_end(ForwardIterator1 premier1, ForwardIterator1 dernier1,
    ForwardIterator2 premier2, ForwardIterator2 dernier2,
    BinaryPredicate p);
 

Tous ces algorithmes prennent en paramètre deux couples d'itérateurs, le premier permettant d'identifier la séquence des valeurs dans laquelle la recherche du motif doit être effectuée et le deuxième permettant d'identifier le motif lui-même. Chaque algorithme est fourni sous la forme de deux surcharges. La première recherche le motif en comparant les éléments à l'aide de l'opérateur d'égalité du type des éléments comparés. La deuxième permet d'effectuer cette comparaison à l'aide d'un prédicat binaire, que l'on fournit dans ce cas en dernier paramètre.

La valeur retournée par l'algorithme search est un itérateur sur la première occurrence du motif dans la séquence de valeurs spécifiées par les itérateurs premier1 et dernier1 ou l'itérateur dernier1 lui-même si ce motif n'y apparaît pas. De même, la valeur retournée par l'algorithme find_end est un itérateur référençant la dernière occurrence du motif dans la séquence des valeurs spécifiée par les itérateurs premier1 et dernier1, ou l'itérateur dernier1 lui-même si le motif n'a pas pu être trouvé.

Exemple 18-17. Algorithmes de recherche de motif
Sélectionnez

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main(void)
{
    int t[10] = {1, 2, 4, 5, 3, 1, 2, 3, 5, 9};
    // Recherche le motif {1, 2, 3} dans le tableau :
    int motif[3] = {1, 2, 3};
    int *p = search(t, t+10, motif, motif+3);
    cout << "{1, 2, 3} en position " <<
        p - t << endl;
    // Recherche la dernière occurrence de {1, 2} :
    p = find_end(t, t+10, motif, motif+2);
    cout << "Dernier {1, 2} en position " <<
        p - t << endl;
    return 0;
}
 

La complexité de l'algorithme search est n×m, où n est le nombre d'éléments de la séquence spécifiée par le premier couple d'itérateurs et m est la longueur du motif à rechercher. La complexité de l'algorithme find_end est n×(n-m).

Lorsque tous les éléments du motif sont égaux, il est possible d'utiliser l'algorithme search_n. Cet algorithme permet en effet de rechercher une série de valeurs identiques dans une séquence. Il est déclaré comme suit dans l'en-tête algorithm :

 
Sélectionnez

template <class ForwardIterator, class Size, class T>
ForwardIterator search_n(ForwardIterator premier, ForwardIterator dernier,
    Size nombre, const T &valeur);
 
template <class ForwardIterator, class Size, class T,
    class BinaryPredicate>
ForwardIterator search_n(ForwardIterator premier, ForwardIterator dernier,
    Size nombre, const T &valeur, BinaryPredicate p);
 

Les deux surcharges de cet algorithme prennent en paramètre les itérateurs définissant la séquence de valeurs dans laquelle la recherche doit être effectuée, la longueur du motif à rechercher, et la valeur des éléments de ce motif. La deuxième version de cet algorithme accepte également un prédicat binaire, qui sera utilisé pour effectuer la comparaison des éléments de la séquence dans laquelle la recherche se fait avec la valeur passée en paramètre. La valeur retournée est un itérateur référençant la première occurrence du motif recherché ou l'itérateur dernier si ce motif n'existe pas dans la séquence de valeurs analysée. La complexité de l'algorithme search_n est n×m, où n est la taille de la séquence dans laquelle la recherche est effectuée et m est la longueur du motif recherché.

Un cas particulier de la recherche de valeurs successives est l'identification de doublons de valeurs. Cette identification peut être réalisée grâce à l'algorithme adjacent_find. Contrairement à l'algorithme search_n, adjacent_find localise tous les couples de valeurs d'une série de valeurs, quelle que soit la valeur des éléments de ces couples. Il est donc inutile de préciser cette valeur, et les surcharges de cet algorithme sont déclarées comme suit dans l'en-tête algorithm :

 
Sélectionnez

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

Les itérateurs fournis en paramètre permettent comme à l'accoutumée de définir la séquence d'éléments dans laquelle la recherche s'effectue. La deuxième surcharge prend également en paramètre un prédicat binaire définissant la relation de comparaison utilisée par l'algorithme. La valeur retournée par ces algorithmes est l'itérateur référençant le premier doublon dans la séquence de valeurs analysée, ou l'itérateur dernier si aucun doublon n'existe.

Exemple 18-18. Algorithme de recherche de doublons
Sélectionnez

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main(void)
{
    int t[10] = {0, 1, 2, 2, 3, 4, 4, 5, 6, 2};
    // Recherche les doublons dans le tableau :
    int *debut = t;
    int *fin = t+10;
    int *p;
    while ((p = adjacent_find(debut, fin)) != fin)
    {
        cout << "Doublon en position " << p-t << endl;
        debut = p+1;
    }
    return 0;
}
 

La complexité de cet algorithme est linéaire en fonction de la taille de la séquence de valeurs dans laquelle la recherche se fait.

18.3. Opérations d'ordonnancement

La bibliothèque standard fournit plusieurs algorithmes relatifs à l'ordonnancement des éléments dans les conteneurs. Grâce à ces algorithmes, il est possible de réorganiser la séquence de ces éléments de manière à obtenir certaines propriétés basées sur la relation d'ordre. Ces réorganisations ont généralement pour but soit de trier complètement ces séquences, soit d'effectuer des tris partiels à partir desquels il est possible d'obtenir des informations relatives à l'ordre des éléments de manière très efficace.

La plupart des algorithmes de tri et d'ordonnancement se basent sur une structure de données très performante : les « tas ». Les algorithmes de manipulation de ces structures de données seront donc décrits en premier. Les sections qui suivront traiteront ensuite des algorithmes de tri et de recherches binaires dans un ensemble d'éléments déjà trié.

18.3.1. Opérations de gestion des tas

Un tas (« heap » en anglais) est une structure de données récursive dans laquelle le premier élément est toujours le plus grand élément et qui dispose d'une opération de suppression du premier élément ainsi que d'une opération d'ajout d'un nouvel élément extrêmement performantes.

Plus précisément, les propriétés fondamentales des tas sont les suivantes :
  • le premier élément du tas est toujours le plus grand de tous les éléments contenus ;
  • il est possible de supprimer ce premier élément et cette opération de suppression a une complexité logarithmique en fonction du nombre d'éléments dans le tas ;
  • il est possible d'ajouter un nouvel élément dans le tas avec une complexité également logarithmique en fonction du nombre d'éléments déjà présents.

Les tas sont donc particulièrement adaptés pour réaliser les files de priorité puisque la détermination du plus grand élément est immédiate et que la suppression de cet élément se fait avec une complexité logarithmique. Les tas sont également très utiles dans l'implémentation des algorithmes de tri car ils permettent d'atteindre une complexité algorithmique en n×ln(n), ce qui est l'optimum.

Note : En pratique, un tas est une forme d'arbre binaire équilibré dont la propriété récursive est que la racine de l'arbre est l'élément de plus grande valeur et que les deux branches de l'arbre sont eux-même des tas. La suppression de la racine, ainsi que l'ajout d'un nouvel élément, nécessite une réorganisation de l'arbre binaire, ce qui ne peut dépasser ln(n) opérations en raison de son aspect équilibré.

Notez que les tas ne garantissent pas, contrairement aux B-arbres et aux arbres rouges et noirs, que tous les éléments situés à la gauche d'un noeud sont plus grands que le noeud lui-même et que tous les éléments situés à la droite sont plus petits. C'est pour cette raison qu'un tas n'est justement pas complètement trié, et que les algorithmes de gestion des tas ne font que conserver cet ordre partiel.
La représentation des tas en mémoire peut être relativement difficile à comprendre. En général, il est d'usage de les stocker dans des tableaux, car les opérations de gestion des tas requièrent des itérateurs à accès aléatoires sur le conteneur sur lequel elles travaillent. Dans ce cas, les premiers éléments du tableau stockent les noeuds de l'arbre binaire du tas, et les feuilles sont placées dans la seconde moitié du tableau. Ainsi, un élément d'indice i a comme feuilles les éléments d'indice 2×i et 2×i+1 (pour tout i < n/2). Reportez-vous à la bibliographie pour plus de renseignements sur les structures de données et les notions algorithmiques associées.

Les algorithmes de manipulation des tas sont déclarés comme suit dans l'en-tête algorithm :

 
Sélectionnez

template <class RandomAccessIterator>
void make_heap(RandomAccessIterator premier, RandomAccessIterator dernier);
 
template <class RandomAccessIterator, class Compare>
void make_heap(RandomAccessIterator premier, RandomAccessIterator dernier,
    Compare c);
 
template <class RandomAccessIterator>
void pop_heap(RandomAccessIterator premier, RandomAccessIterator dernier);
 
template <class RandomAccessIterator, class Compare>
void pop_heap(RandomAccessIterator premier, RandomAccessIterator dernier,
    Compare c);
 
template <class RandomAccessIterator>
void push_heap(RandomAccessIterator premier, RandomAccessIterator dernier);
 
template <class RandomAccessIterator, class Compare>
void push_heap(RandomAccessIterator premier, RandomAccessIterator dernier,
    Compare c);
 
template <class RandomAccessIterator>
void sort_heap(RandomAccessIterator premier, RandomAccessIterator dernier);
 
template <class RandomAccessIterator, class Compare>
void sort_heap(RandomAccessIterator premier, RandomAccessIterator dernier,
    Compare c);
 

L'algorithme make_heap permet de construire un nouveau tas à partir d'une séquence d'éléments quelconque. Il prend simplement en paramètre les itérateurs de début et de fin de cette séquence, et ne retourne rien. Sa complexité est une fonction linéaire du nombre d'éléments référencés par ces deux itérateurs.

Les algorithmes pop_heap et push_heap permettent respectivement de supprimer la tête d'un tas existant et d'ajouter un nouvel élément dans un tas. pop_heap prend en paramètre deux itérateurs référençant le premier et le dernier élément du tas. Il place le premier élément du tas en dernière position et réorganise les éléments restants de telle sorte que les dernier-premier-1 éléments constituent un nouveau tas. L'algorithme push_heap en revanche effectue le travaille inverse : il prend en paramètre deux itérateurs référençant une séquence dont les premiers éléments sauf le dernier constituent un tas et y ajoute l'élément référencé par l'itérateur dernier-1. Ces deux opérations effectuent leur travail avec une complexité logarithmique.

Enfin, l'algorithme sort_heap permet simplement de trier une séquence ayant la structure de tas. Sa complexité est n×ln(n), où n est le nombre d'éléments de la séquence.

Exemple 18-19. Algorithmes de manipulation des tas
Sélectionnez

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main(void)
{
    int t[10] = {5, 8, 1, 6, 7, 9, 4, 3, 0, 2};
    // Construit un tas à partir de ce tableau :
    make_heap(t, t+10);
    // Affiche le tas :
    int i;
    for (i=0; i<10; ++i)
        cout << t[i] << " ";
    cout << endl;
    // Supprime l'élément de tête :
    pop_heap(t, t+10);
    // L'élément de tête est en position 9 :
    cout << "Max = " << t[9] << endl;
    // Affiche le nouveau tas :
    for (i=0; i<9; ++i)
        cout << t[i] << " ";
    cout << endl;
    // Ajoute un élément :
    t[9] = 6;
    push_heap(t, t+10);
    // Affiche le nouveau tas :
    for (i=0; i<10; ++i)
        cout << t[i] << " ";
    cout << endl;
    // Tri le tas :
    sort_heap(t, t+10);
    // Affiche le tableau ainsi trié :
    for (i=0; i<10; ++i)
        cout << t[i] << " ";
    cout << endl;
    return 0;
}
 

18.3.2. Opérations de tri

Les opérations de tri de la bibliothèque standard s'appuient sur les algorithmes de manipulation des tas que l'on vient de voir. Ces méthodes permettent d'effectuer un tri total des éléments d'une séquence, un tri stable, légèrement moins performant que le précédent mais permettant de conserver l'ordre relatif des éléments équivalents, et un tri partiel.

Les algorithmes de tri sont déclarés comme suit dans l'en-tête algorithm :

 
Sélectionnez

template <class RandomAccessIterator>
void sort(RandomAccessIterator premier, RandomAccessIterator dernier);
 
template <class RandomAccessIterator, class Compare>
void sort(RandomAccessIterator premier, RandomAccessIterator dernier,
    Compare c);
 
template <class RandomAccessIterator>
void stable_sort(RandomAccessIterator premier, RandomAccessIterator dernier);
 
template <class RandomAccessIterator, class Compare>
void stable_sort(RandomAccessIterator premier, RandomAccessIterator dernier,
    Compare c);

Les algorithmes sort et stable_sort s'utilisent de la même manière et permettent de trier complètement la séquence qui leur est spécifiée à l'aide des deux itérateurs premier et dernier. Ces deux algorithmes effectuent un tri par ordre croissant en utilisant l'opérateur d'infériorité du type des éléments de la séquence à trier. Cependant, il est également possible d'utiliser un autre critère, en spécifiant un foncteur binaire en troisième paramètre. Ce foncteur doit être capable de comparer deux éléments de la séquence à trier et d'indiquer si le premier est ou non le plus petit au sens de la relation d'ordre qu'il utilise.

Exemple 18-20. Algorithme de tri
Sélectionnez

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main(void)
{
    int t[10] = {2, 3, 7, 5, 4, 1, 8, 0, 9, 6};
    // Trie le tableau :
    sort(t, t+10);
    // Affiche le résultat :
    int i;
    for (i=0; i<10; ++i)
        cout << t[i] << " ";
    cout << endl;
    return 0;
}
 

Il se peut que plusieurs éléments de la séquence soient considérés comme équivalents par la relation d'ordre utilisée. Par exemple, il est possible de trier des structures selon l'un de leurs champs, et plusieurs éléments peuvent avoir la même valeur dans ce champ sans pour autant être strictement égaux. Dans ce cas, il peut être nécessaire de conserver l'ordre relatif initial de ces éléments dans la séquence à trier. L'algorithme sort ne permet pas de le faire, cependant, l'algorithme stable_sort garantit la conservation de cet ordre relatif, au prix d'une complexité algorithmique légèrement supérieure. En effet, la complexité de stable_sort est n×ln²(n) (où n est le nombre d'éléments à trier), alors que celle de l'algorithme sort n'est que de n×ln(n). Hormis cette petite différence, les deux algorithmes sont strictement équivalents.

Dans certaines situations, il n'est pas nécessaire d'effectuer un tri total des éléments. En effet, le tri des premiers éléments d'une séquence seulement ou bien seule la détermination du nième élément d'un ensemble peuvent être désirés. À cet effet, la bibliothèque standard fournit les algorithmes suivants :

 
Sélectionnez

template <class RandomAccessIterator>
void partial_sort(RandomAccessIterator premier,
    RandomAccessIterator pivot, RandomAccessIterator dernier);
 
template <class InputIterator, class RandomAccessIterator>
RandomAccessIterator partial_sort_copy(
    InputIterator premier, InputIterator dernier,
    RandomAccessIterator debut_resultat, RandomAccessIterator fin_resultat);
 
template <class RandomAccessIterator, class Compare>
void partial_sort(
    RandomAccessIterator premier, RandomAccessIterator fin_tri,
    RandomAccessIterator dernier, Compare c);
 
template <class InputIterator, class RandomAccessIterator,
    class Compare>
RandomAccessIterator partial_sort_copy(
    InputIterator premier, InputIterator dernier,
    RandomAccessIterator debut_resultat, RandomAccessIterator fin_resultat,
    Compare c);
 
template <class RandomAccessIterator>
void nth_element(RandomAccessIterator premier, RandomAccessIterator position,
    RandomAccessIterator dernier);
 
template <class RandomAccessIterator, class Compare>
void nth_element(RandomAccessIterator premier, RandomAccessIterator position,
    RandomAccessIterator dernier,  Compare c);
 

L'algorithme partial_sort permet de n'effectuer qu'un tri partiel d'une séquence. Cet algorithme peut être utilisé lorsqu'on désire n'obtenir que les premiers éléments de la séquence triée. Cet algorithme existe en deux versions. La première version prend en paramètre l'itérateur de début de la séquence, l'itérateur de la position du dernier élément de la séquence qui sera triée à la fin de l'exécution de l'algorithme, et l'itérateur de fin de la séquence. La deuxième version, nommée partial_sort_copy, permet de copier le résultat du tri partiel à un autre emplacement que celui de la séquence initiale. Cette version de l'algorithme de tri partiel prend alors deux couples d'itérateurs en paramètre, le premier spécifiant la séquence sur laquelle l'algorithme doit travailler et le deuxième l'emplacement destination dans lequel le résultat doit être stocké. Enfin, comme pour tous les autres algorithmes, il est possible de spécifier un autre opérateur de comparaison que l'opérateur d'infériorité utilisé par défaut en fournissant un foncteur binaire en dernier paramètre.

Exemple 18-21. Algorithme de tri partiel
Sélectionnez

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main(void)
{
    int t[10] = {2, 3, 7, 5, 4, 1, 8, 0, 9, 6};
    // Trie les 5 premiers éléments du tableau :
    partial_sort(t, t+5, t+10);
    // Affiche le résultat :
    int i;
    for (i=0; i<10; ++i)
        cout << t[i] << " ";
    cout << endl;
    return 0;
}
 

La complexité de l'algorithme partial_sort est n×ln(m), où n est la taille de la séquence sur laquelle l'algorithme travaille et m est le nombre d'éléments triés à obtenir.

L'algorithme nth_element permet quant à lui de calculer la valeur d'un élément de rang donné dans le conteneur si celui-ci était complètement trié. Cet algorithme prend en paramètre l'itérateur de début de la séquence à traiter, l'itérateur référençant l'emplacement qui recevra l'élément qui sera placé à sa position à la fin de l'opération de tri partiel et l'itérateur de fin de la séquence. Il est également possible, comme pour les autres algorithmes, de spécifier un foncteur à utiliser pour tester l'infériorité des éléments de la séquence. À l'issue de l'appel, le n-ième élément de la séquence sera le même élément que celui qui se trouverait à cette position si la séquence était complètement triée selon la relation d'ordre induite par l'opérateur d'infériorité ou par le foncteur fourni en paramètre. La complexité de l'algorithme nth_element est linéaire en fonction du nombre d'éléments de la séquence à traiter.

Exemple 18-22. Algorithme de positionnement du nième élément
Sélectionnez

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main(void)
{
    int t[10] = {2, 3, 9, 6, 7, 5, 4, 0, 1, 8};
    // Trie tous les éléments un à un :
    int i;
    for (i=0; i<10; ++i)
    {
        nth_element(t, t+i, t+10);
        cout << "L'élément " << i <<
            " a pour valeur " << t[i] << endl;
    }
    return 0;
}
 

Enfin, et bien que ces algorithmes ne fassent pas à proprement parler des opérations de tri, la bibliothèque standard fournit deux algorithmes permettant d'obtenir le plus petit et le plus grand des éléments d'une séquence. Ces algorithmes sont déclarés de la manière suivante dans l'en-tête algorithm :

 
Sélectionnez

template <class ForwardIterator>
ForwardIterator min_element(ForwardIterator premier, ForwardIterator dernier);
 
template <class ForwardIterator, class Compare>
ForwardIterator min_element(ForwardIterator premier, ForwardIterator dernier,
    Compare c);
 
template <class ForwardIterator>
ForwardIterator max_element(ForwardIterator premier, ForwardIterator dernier);
 
template <class ForwardIterator, class Compare>
ForwardIterator max_element(ForwardIterator premier, ForwardIterator dernier,
    Compare c);
 

Ces deux algorithmes prennent en paramètre deux itérateurs permettant de définir la séquence des éléments dont le minimum et le maximum doivent être déterminés. Ils retournent un itérateur référençant respectivement le plus petit et le plus grand des éléments de cette séquence. La complexité de ces algorithmes est proportionnelle à la taille de la séquence fournie en paramètre.

Exemple 18-23. Algorithmes de détermination du maximum et du minimum
Sélectionnez

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main(void)
{
    int t[10] = {5, 2, 4, 6, 3, 7, 9, 1, 0, 8};
    // Affiche le minimum et le maximum :
    cout << *min_element(t, t+10) << endl;
    cout << *max_element(t, t+10) << endl;
    return 0;
}
 

18.3.3. Opérations de recherche binaire

Les opérations de recherche binaire de la bibliothèque standard sont des opérations qui permettent de manipuler des séquences d'éléments déjà triées en se basant sur cet ordre. Les principales fonctionnalités de ces algorithmes sont de rechercher les positions des éléments dans ces séquences en fonction de leur valeur.

Les principaux algorithmes de recherche binaire sont les algorithmes lower_bound et upper_bound. Ces algorithmes sont déclarés comme suit dans l'en-tête algorithm :

 
Sélectionnez

template <class ForwardIterator, class T>
ForwardIterator lower_bound(ForwardIterator premier, ForwardIterator dernier,
    const T &valeur);
 
template <class ForwardIterator, class T, class Compare>
ForwardIterator lower_bound(ForwardIterator premier, ForwardIterator dernier,
    const T &valeur, Compare c);
 
template <class ForwardIterator, class T>
ForwardIterator upper_bound(ForwardIterator premier, ForwardIterator dernier,
    const T &valeur);
 
template <class ForwardIterator, class T, class Compare>
ForwardIterator upper_bound(ForwardIterator premier, ForwardIterator dernier,
    const T &valeur, Compare c);
 

L'algorithme lower_bound détermine la première position à laquelle la valeur valeur peut être insérée dans la séquence ordonnée spécifiée par les itérateurs premier et dernier sans en briser l'ordre. De même, l'algorithme upper_bound détermine la dernière position à laquelle la valeur valeur peut être insérée sans casser l'ordre de la séquence sur laquelle il travaille. Il est supposé ici que l'insertion se ferait avant les éléments indiqués par ces itérateurs, comme c'est généralement le cas pour tous les conteneurs.

Si le programmeur veut déterminer simultanément les deux itérateurs renvoyés par les algorithmes lower_bound et upper_bound, il peut utiliser l'algorithme equal_range suivant :

 
Sélectionnez

template <class ForwardIterator, class T>
pair<ForwardIterator, ForwardIterator>
    equal_range(ForwardIterator premier, ForwardIterator dernier,
        const T &valeur);
 
template <class ForwardIterator, class T, class Compare>
pair<ForwardIterator, ForwardIterator>
    equal_range(ForwardIterator premier, ForwardIterator dernier,
        const T &valeur, Compare comp);
 

Cet algorithme renvoie une paire d'itérateurs contenant respectivement la première et la dernière des positions auxquelles la valeur valeur peut être insérée sans perturber l'ordre de la séquence identifiée par les itérateurs premier et dernier.

Exemple 18-24. Algorithmes de détermination des bornes inférieures et supérieures
Sélectionnez

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main(void)
{
    int t[10] = {1, 2, 4, 4, 4, 5, 8, 9, 15, 20};
    // Détermine les positions possibles d'insertion
    // d'un 4 :
    cout << "4 peut être inséré de " <<
        lower_bound(t, t+10, 4) - t <<
        " à " <<
        upper_bound(t, t+10, 4) - t << endl;
    // Récupère ces positions directement
    // avec equal_range :
    pair<int *, int *> p = equal_range(t, t+10, 4);
    cout << "Equal range donne l'intervalle [" <<
        p.first-t << ", " << p.second-t << "]";
    cout << endl;
    return 0;
}
 

Comme pour la plupart des algorithmes de la bibliothèque standard, il est possible de spécifier un foncteur qui devra être utilisé par les algorithmes de recherche binaire dans les comparaisons d'infériorité des éléments de la séquence.

Enfin, l'algorithme binary_search permet de déterminer si un élément d'un conteneur au moins est équivalent à une valeur donnée au sens de l'opérateur d'infériorité ou au sens d'un foncteur fourni en paramètre. Cet algorithme est déclaré de la manière suivante dans l'en-tête algorithm :

 
Sélectionnez

template <class ForwardIterator, class T>
bool binary_search(ForwardIterator premier, ForwardIterator dernier,
    const T &valeur);
 
template <class ForwardIterator, class T, class Compare>
bool binary_search(ForwardIterator premier, ForwardIterator dernier,
    const T &valeur, Compare c);
 

Cet algorithme prend en paramètre les deux itérateurs définissant la séquence d'éléments à tester, la valeur avec laquelle ses éléments doivent être testés, et éventuellement un foncteur permettant de réaliser une opération de comparaison autre que celle de l'opérateur d'infériorité. Il renvoie un booléen indiquant si un des éléments au moins du conteneur est équivalent à la valeur fournie en paramètre.

Note : La relation d'équivalence utilisée par cet algorithme n'est pas celle induite par l'opérateur d'égalité des éléments. En réalité, deux éléments x et y sont considérés comme équivalents si et seulement si les deux inéquations x<y et y<x sont fausses. C'est la raison pour laquelle le foncteur fourni en paramètre ne doit pas définir la relation d'égalité, mais la relation d'infériorité.

Cette distinction a son importance si certains éléments de la séquence ne sont pas comparables ou si l'opérateur d'égalité définit une autre relation que l'opérateur d'infériorité. Bien entendu, en pratique, ces deux inéquations signifie souvent que les valeurs x et y sont égales.
Exemple 18-25. Algorithme de recherche binaire
Sélectionnez

#include <iostream>
#include <string>
#include <algorithm>
 
using namespace std;
 
struct A
{
    int numero;   // Numéro unique de l'élément
    string nom;   // Nom de l'élément
 
    A(const char *s) :
        nom(s)
    {
        // Affecte un nouveau numéro :
        static int i=0;
        numero = ++i;
    }
 
    // Opérateur de classement :
    bool operator<(const A &a) const
    {
        return (numero < a.numero);
    }
 
    // Opérateur d'égalité (jamais utilisé) :
    bool operator==(const A &a) const
    {
        return (nom == a.nom);
    }
};
 
int main(void)
{
    // Construit un tableau d'éléments triés
    // (par construction, puisque le numéro est incrémenté
    // à chaque nouvel objet) :
    A t[5] = {"Jean", "Marc", "Alain", "Ariane", "Sophie"};
    // Cette instance a le même nom que t[1]
    // mais ne sera pas trouvé car son numéro est différent :
    A test("Marc");
    // Effectue la recherche de test dans le tableau :
    if (binary_search(t, t+5, test))
    {
        cout << "(" << test.numero << ", " <<
            test.nom << ") a été trouvé" << endl;
    }
    else
    {
        cout << "(" << test.numero << ", " <<
            test.nom << ") n'a pas été trouvé" << endl;
    }
    return 0;
}
 

La complexité algorithmique de tous ces algorithmes est logarithmique en fonction du nombre d'éléments de la séquence sur laquelle ils travaillent. Ils s'appuient sur le fait que cette séquence est déjà triée pour atteindre cet objectif.

18.4. Opérations de comparaison

Afin de faciliter la comparaison de conteneurs de natures différentes pour lesquels, de surcroît, il n'existe pas forcément d'opérateurs de comparaison, la bibliothèque standard fournit plusieurs algorithmes de comparaison. Ces algorithmes sont capables d'effectuer une comparaison élément à élément des différents conteneurs pour vérifier leur égalité en terme d'éléments contenus, ou de déterminer une relation d'ordre au sens lexicographique. Enfin, il est possible de déterminer les éléments par lesquels deux conteneurs se différencient.

L'algorithme général de comparaison des conteneurs est l'algorithme equal. Cet algorithme est déclaré comme suit dans l'en-tête algorithm :

 
Sélectionnez

template <class InputIterator1, class InputIterator2>
bool equal(InputIterator1 premier1, InputIterator1 dernier1,
    InputIterator2 premier2);
 
template <class InputIterator1, class InputIterator2, class BinaryPredicate>
bool equal(InputIterator1 premier1, InputIterator1 dernier1,
    InputIterator2 premier2, BinaryPredicate p);
 

Comme vous pouvez le constater d'après cette déclaration, l'algorithme equal prend en paramètre un couple d'itérateurs décrivant la séquence d'éléments qui doivent être pris en compte dans la comparaison ainsi qu'un itérateur sur le premier élément du deuxième conteneur. Les éléments référencés successivement par les itérateurs premier1 et premier2 sont ainsi comparés, jusqu'à ce qu'une différence soit détectée ou que l'itérateur dernier1 du premier conteneur soit atteint. La valeur retournée est true si les deux séquences d'éléments des deux conteneurs sont égales élément à élément, et false sinon. Bien entendu, il est possible de spécifier un foncteur binaire que l'algorithme devra utiliser pour réaliser les comparaisons entre les éléments des deux conteneurs. S'il est spécifié, ce foncteur est utilisé pour déterminer si les éléments comparés sont égaux ou non.

Note : Notez bien ici que le foncteur fourni permet de tester l'égalité de deux éléments et non l'infériorité, comme c'est le cas avec la plupart des autres algorithmes.

S'il s'avère que les deux conteneurs ne sont pas égaux membre à membre, il peut être utile de déterminer les itérateurs des deux éléments qui ont fait échouer le test d'égalité. Cela peut être réalisé à l'aide de l'algorithme mismatch dont on trouvera la déclaration dans l'en-tête algorithm :

 
Sélectionnez

template <class InputIterator1, class InputIterator2>
pair<InputIterator1, InputIterator2>
    mismatch(InputIterator1 premier1, InputIterator1 dernier1,
        InputIterator2 premier2);
 
template <class InputIterator1, class InputIterator2, class BinaryPredicate>
pair<InputIterator1, InputIterator2>
    mismatch(InputIterator1 premier1, InputIterator1 dernier1,
        InputIterator2 premier2, BinaryPredicate p);
 

Cet algorithme fonctionne exactement de la même manière que l'algorithme equal. Cependant, contrairement à ce dernier, sa valeur de retour est une paire d'itérateurs des deux conteneurs référençant les éléments respectifs qui ne sont pas égaux au sens de l'opération de comparaison utilisée par l'algorithme (que ce soit l'opérateur d'égalité ou le foncteur fourni en paramètre). Si les deux conteneurs sont effectivement égaux, la valeur retournée est la paire contenant l'itérateur dernier1 et l'itérateur correspondant dans le deuxième conteneur.

Exemple 18-26. Algorithme de comparaison de conteneurs
Sélectionnez

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main(void)
{
    int t1[10] = {5, 6, 4, 7, 8, 9, 2, 1, 3, 0};
    int t2[10] = {5, 6, 4, 7, 9, 2, 1, 8, 3, 0};
    // Compare les deux tableaux :
    if (!equal(t1, t1+10, t2))
    {
        // Détermine les éléments différents :
        pair<int *, int *> p =
            mismatch(t1, t1+10, t2);
        cout << *p.first << " est différent de " <<
            *p.second << endl;
    }
    return 0;
}
 

Enfin, la bibliothèque standard fournit un algorithme de comparaison général permettant de déterminer si un conteneur est inférieur à un autre conteneur selon la relation d'ordre lexicographique induite par l'opérateur d'infériorité du type de leurs éléments. Rappelons que l'ordre lexicographique est celui utilisé par le dictionnaire : les éléments sont examinés un à un et dans leur ordre d'apparition et la comparaison s'arrête dès que deux éléments différents sont trouvés. En cas d'égalité totale, le plus petit des conteneurs est celui qui contient le moins d'éléments.

L'algorithme de comparaison lexicographique est l'algorithme lexicographical_compare. Il est déclaré comme suit dans l'en-tête algorithm :

 
Sélectionnez

template <class InputIterator1, class InputIterator2>
bool lexicographical_compare(InputIterator1 premier1, InputIterator1 dernier1,
    InputIterator2 premier2, InputIterator2 dernier2);
 
template <class InputIterator1, class InputIterator2, class Compare>
bool lexicographical_compare(InputIterator1 premier1, InputIterator1 dernier1,
    InputIterator2 premier2, InputIterator2 dernier2,
    Compare c);
 

Cet algorithme prend en paramètre deux couples d'itérateurs grâce auxquels le programmeur peut spécifier les deux séquences d'éléments à comparer selon l'ordre lexicographique. Comme à l'accoutumée, il est également possible de fournir un foncteur à utiliser pour les tests d'infériorité entre les éléments des deux conteneurs. La valeur retournée par l'algorithme lexicographical_compare est true si le premier conteneur est strictement plus petit que le deuxième et false sinon.

Exemple 18-27. Algorithme de comparaison lexicographique
Sélectionnez

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main(void)
{
    int t1[10] = {5, 6, 4, 7, 8, 9, 2, 1, 3, 0};
    int t2[10] = {5, 6, 4, 7, 9, 2, 1, 8, 3, 0};
    // Compare les deux tableaux :
    if (lexicographical_compare(t1, t1+10, t2, t2+10))
    {
        cout << "t1 est plus petit que t2" << endl;
    }
    return 0;
}
 

Tous ces algorithmes de comparaison s'exécutent avec une complexité linéaire en fonction du nombre d'éléments à comparer.

18.5. Opérations ensemblistes

En mathématiques, il est possible d'effectuer différents types d'opérations sur les ensembles. Ces opérations comprennent la détermination de l'inclusion d'un ensemble dans un autre, leur union (c'est-à-dire le regroupement de tous leurs éléments), leur intersection (la sélection de leurs éléments communs), leur différence (la suppression des éléments d'un ensemble qui appartiennent aussi à un autre ensemble) et leur partitionnement (le découpage d'un ensemble en sous-ensemble dont les éléments vérifient une propriété discriminante).

La bibliothèque standard fournit tout un ensemble d'algorithmes qui permettent d'effectuer les opérations ensemblistes classiques sur les conteneurs triés. Tous ces algorithmes sont décrits ci-dessous et sont classés selon la nature des opérations qu'ils réalisent.

Note : Remarquez ici que la notion de tri est importante : les algorithmes s'appuient sur cette propriété des conteneurs pour effectuer leur travail. En contrepartie de cette contrainte, les performances de ces algorithmes sont excellentes.

18.5.1. Opérations d'inclusion

L'inclusion d'un ensemble dans un autre peut être réalisée à l'aide de l'algorithme includes. Cet algorithme est déclaré comme suit dans l'en-tête algorithm :

 
Sélectionnez

template <class InputIterator1, class InputIterator2>
bool includes(InputIterator1 premier1, InputIterator1 dernier1,
    InputIterator2 premier2, InputIterator2 dernier2);
 
template <class InputIterator1, class InputIterator2, class Compare>
bool includes(InputIterator1 premier1, InputIterator1 dernier1,
    InputIterator2 premier2, InputIterator2 dernier2, Compare c);
 

L'algorithme includes prend en paramètre deux couples d'itérateurs permettant de définir les séquences d'éléments des deux ensembles sur lesquels il doit travailler. La valeur retournée par cet algorithme est true si tous les éléments de la séquence identifiée par les itérateurs premier2 et dernier2 sont également présents dans la séquence identifiée par les itérateurs premier1 et dernier1. L'algorithme considère qu'un élément est présent dans un ensemble s'il existe au moins un élément de cet ensemble qui lui est identique. Chaque élément utilisé de l'ensemble ne l'est qu'une seule fois, ainsi, si l'ensemble dont on teste l'inclusion dispose de plusieurs copies du même élément, il faut qu'il y en ait autant dans l'ensemble conteneur pour que le test d'inclusion soit valide.

Bien entendu, il est possible d'utiliser une autre relation que l'égalité pour déterminer l'appartenance d'un élément à un ensemble, pour cela, il suffit de fournir un foncteur binaire en dernier paramètre. Ce prédicat doit prendre deux éléments en paramètre et renvoyer true si le premier élément est inférieur au second, et false dans le cas contraire.

Note : Il est important que le foncteur d'infériorité spécifié soit compatible avec la relation d'ordre utilisée pour le tri des éléments des conteneurs. Si ce n'est pas le cas, l'algorithme peut ne pas fonctionner correctement.

Exemple 18-28. Algorithme de détermination d'inclusion
Sélectionnez

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main(void)
{
    int t1[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    int t2[3] = {4, 5, 6};
    if (includes(t1, t1+10, t2, t2+3))
        cout << "t1 contient t2" << endl;
    return 0;
}

La complexité de l'algorithme includes est n+m, où n et m sont respectivement les tailles des deux conteneurs qui lui sont fournis en paramètre.

18.5.2. Opérations d'intersection

L'intersection de deux ensembles peut être réalisée à l'aide de l'algorithme set_intersection. Cet algorithme est déclaré de la manière suivante dans l'en-tête algorithm :

 
Sélectionnez

template <class InputIterator1, class InputIterator2,
    class OutputIterator>
OutputIterator set_intersection(InputIterator1 premier1, InputIterator1 dernier1,
    InputIterator2 premier2, InputIterator2 dernier2,
    OutputIterator destination);
 
template <class InputIterator1, class InputIterator2,
    class OutputIterator, class Compare>
OutputIterator set_intersection(InputIterator1 premier1, InputIterator1 dernier1,
    InputIterator2 premier2, InputIterator2 dernier2,
    OutputIterator destination, Compare c);
 

Cet algorithme prend en paramètre les itérateurs de début et de fin des deux conteneurs dont l'intersection doit être déterminée, ainsi qu'un itérateur référençant l'emplacement destination où les éléments de l'intersection doivent être stockés. Pour ceux qui le désirent, il est également possible de spécifier un foncteur que l'algorithme utilisera pour effectuer les comparaisons d'infériorité entre les éléments des deux conteneurs fournis en paramètre. Ce foncteur devra bien entendu être compatible avec la relation d'ordre selon laquelle les conteneurs passés en paramètre sont triés.

L'algorithme copie à l'emplacement destination tous les éléments du premier conteneur qui font également partie du deuxième. Le critère d'appartenance à un ensemble est, comme pour l'algorithme includes, le fait qu'il existe au moins un élément dans le deuxième ensemble égal à l'élément considéré. De même, si plusieurs copies d'un même élément se trouvent dans chaque ensemble, le nombre de copies de l'intersection sera le plus petit nombre de copies de l'élément dans les deux ensembles sources.

Exemple 18-29. Algorithme d'intersection d'ensembles
Sélectionnez

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main(void)
{
    int t1[10] = {2, 4, 6, 8, 9, 10, 15, 15, 15, 17};
    int t2[10] = {1, 4, 5, 8, 11, 15, 15, 16, 18, 19};
    int t[10];
    // Effectue l'intersection de t1 et de t2 :
    int *fin = set_intersection(t1, t1+10, t2, t2+10, t);
    // Affiche le résultat :
    int *p = t;
    while (p != fin)
    {
        cout << *p << " ";
        ++p;
    }
    cout << endl;
    return 0;
}
 

La complexité de l'algorithme est n+m, où n et m sont respectivement les tailles des deux conteneurs qui lui sont fournis en paramètre.

18.5.3. Opérations d'union et de fusion

La bibliothèque standard fournit plusieurs algorithmes permettant de réaliser l'union de deux ensembles. Ces variantes se distinguent par la manière qu'elles ont de traiter le cas des éléments en multiples exemplaires.

L'algorithme set_union considère que les éléments équivalents des deux ensembles sont les mêmes entités et ne les place qu'une seule fois dans l'ensemble résultat de l'union. Toutefois, si ces éléments sont en plusieurs exemplaires dans un des ensembles source, ils apparaîtront également en plusieurs exemplaires dans le résultat. Autrement dit, le nombre d'éléments présents dans l'ensemble destination est le nombre maximum du compte de ses occurrences dans chacun des deux ensembles source.

Inversement, l'algorithme merge effectue une union au sens large et ajoute les éléments de chaque ensemble dans l'ensemble résultat sans considérer leurs valeurs. Ainsi, le nombre d'éléments du résultat est strictement égal à la somme des nombres des éléments de chaque conteneur source.

Afin de distinguer ces deux comportements, on peut dire que l'algorithme set_union réalise l'union des deux ensembles, alors que l'algorithme merge réalise leur fusion.

Tous ces algorithmes sont déclarés comme suit dans l'en-tête algorithm :

 
Sélectionnez

template <class InputIterator1, class InputIterator2,
    class OutputIterator>
OutputIterator set_union(InputIterator1 premier1, InputIterator1 dernier1,
    InputIterator2 premier2, InputIterator2 dernier2,
    OutputIterator destination);
 
template <class InputIterator1, class InputIterator2,
    class OutputIterator, class Compare>
OutputIterator set_union(InputIterator1 premier1, InputIterator1 dernier1,
    InputIterator2 premier2, InputIterator2 dernier2,
    OutputIterator destination, Compare c);
 
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator merge(InputIterator1 premier1, InputIterator1 dernier1,
    InputIterator2 premier2, InputIterator2 dernier2,
    OutputIterator destination);
 
template <class InputIterator1, class InputIterator2,
    class OutputIterator, class Compare>
OutputIterator merge(InputIterator1 premier1, InputIterator1 dernier1,
    InputIterator2 dernier2, InputIterator2 premier2,
    OutputIterator destination, Compare c);
 

Comme vous pouvez le constater, ils prennent tous en paramètre les itérateurs permettant de spécifier les deux ensembles ainsi qu'un itérateur destination indiquant l'emplacement où les éléments de l'union ou de la fusion doivent être stockés. Enfin, si le programmeur le désire, il peut également donner le foncteur définissant la relation d'ordre selon laquelle les ensembles sont triés.

Exemple 18-30. Algorithmes d'union et de fusion d'ensembles
Sélectionnez

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main(void)
{
    int t1[4] = {1, 2, 5, 5};
    int t2[6] = {3, 4, 5, 5, 5, 7};
    int t[10];
    // Effectue l'union de t1 et de t2 :
    int *fin = set_union(t1, t1+4, t2, t2+6, t);
    // Affiche le résultat :
    int *p = t;
    while (p != fin)
    {
        cout << *p << " ";
        ++p;
    }
    cout << endl;
    // Effectue la fusion de t1 et de t2 :
    fin = merge(t1, t1+4, t2, t2+6, t);
    // Affiche le résultat :
    p = t;
    while (p != fin)
    {
        cout << *p << " ";
        ++p;
    }
    cout << endl;
    return 0;
}
 

La bibliothèque standard fournit également une version modifiée de l'algorithme merge dont le but est de fusionner deux parties d'une même séquence d'éléments triées indépendamment l'une de l'autre. Cet algorithme permet d'effectuer la fusion sur place, et ne travaille donc que sur un seul conteneur. Il s'agit de l'algorithme inplace_merge, qui est déclaré comme suit :

 
Sélectionnez

template <class BidirectionalIterator>
void inplace_merge(BidirectionalIterator premier,
    BidirectionalIterator separation,
    BidirectionalIterator dernier);
 
template <class BidirectionalIterator, class Compare>
void inplace_merge(BidirectionalIterator premier,
    BidirectionalIterator separation,
    BidirectionalIterator dernier, Compare c);
 

Cet algorithme effectue la fusion des deux ensembles identifiés respectivement par les itérateurs premier et separation d'une part, et par les itérateurs separation et dernier d'autre part. Enfin, si besoin est, il est possible de spécifier le foncteur selon lequel ces deux ensembles sont triés.

Exemple 18-31. Algorithme de réunification de deux sous-ensembles
Sélectionnez

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main(void)
{
    int t[10] = {1, 5, 9, 0, 2, 3, 4, 6, 7, 8};
    // Fusionne les deux sous-ensembles de t
    // (la séparation est au troisième élément) :
    inplace_merge(t, t+3, t+10);
    // Affiche le résultat :
    int i;
    for (i=0; i<10; ++i)
    {
        cout << t[i] << " ";
    }
    cout << endl;
    return 0;
}
 

Tous les algorithmes d'union et de fusion ont une complexité n+m, où n et m sont les tailles des deux ensembles à fusionner ou à réunir.

18.5.4. Opérations de différence

La différence entre deux ensembles peut être réalisée avec l'algorithme set_difference. Cet algorithme supprime du premier ensemble tous les éléments du second, si nécessaire. Chaque élément n'est supprimé qu'une seule fois, ainsi, si le premier ensemble contient plusieurs éléments identiques et que le deuxième ensemble en contient moins, les éléments résiduels après suppression seront présents dans la différence.

La bibliothèque standard fournit également un algorithme de suppression symétrique, l'algorithme set_symmetric_difference, qui construit un nouvel ensemble contenant tous les éléments des deux ensembles qui ne se trouvent pas dans l'autre. Il s'agit en fait de l'union des deux différences des deux ensembles.

Note : Remarquez que le mot « symmetric » s'écrit avec deux 'm' en anglais. Ne vous étonnez donc pas d'obtenir des erreurs de compilation si vous écrivez set_symmetric_difference à la française !

Les algorithmes set_difference et set_symmetric_difference sont déclarés comme suit dans l'en-tête algorithm :

 
Sélectionnez

template <class InputIterator1, class InputIterator2,
    class OutputIterator>
OutputIterator set_difference(
    InputIterator1 premier1, InputIterator1 dernier1,
    InputIterator2 premier2, InputIterator2 dernier2,
    OutputIterator destination);
 
template <class InputIterator1, class InputIterator2,
    class OutputIterator, class Compare>
OutputIterator set_difference(
    InputIterator1 premier1, InputIterator1 dernier1,
    InputIterator2 premier2, InputIterator2 dernier2,
    OutputIterator destination, Compare c);
 
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_symmetric_difference(
    InputIterator1 premier, InputIterator1 dernier,
    InputIterator2 premier, InputIterator2 dernier2,
    OutputIterator destination);
 
template <class InputIterator1, class InputIterator2,
    class OutputIterator, class Compare>
OutputIterator set_symmetric_difference(
    InputIterator1 premier1, InputIterator1 dernier1,
    InputIterator2 premier2, InputIterator2 dernier2,
    OutputIterator destination, Compare c);
 

Ils prennent tous deux paires d'itérateurs identifiant les deux ensembles dont la différence doit être calculée ainsi qu'un itérateur référençant l'emplacement destination dans lequel le résultat doit être placé. Comme à l'accoutumée, il est possible d'indiquer le foncteur permettant à l'algorithme de réaliser les tests d'infériorité entre deux éléments et selon lequel les ensembles sont triés. La complexité de ces algorithmes est n+m, où n et m sont les nombres d'éléments des deux ensembles sur lesquels les algorithmes opèrent.

Exemple 18-32. Algorithmes de différence d'ensembles
Sélectionnez

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main(void)
{
    int t1[10] = {0, 1, 5, 7, 7, 7, 8, 8, 9, 10};
    int t2[10] = {0, 2, 3, 7, 9, 11, 12, 12, 13, 14};
    int t[20];
    // Calcule la différence de t1 et de t2 :
    int *fin = set_difference(t1, t1+10, t2, t2+10, t);
    // Affiche le résultat :
    int *p = t;
    while (p != fin)
    {
        cout << *p << " ";
        ++p;
    }
    cout << endl;
    // Calcule la différence symétrique de t1 et t2 :
    fin = set_symmetric_difference(t1, t1+10, t2, t2+10, t);
    // Affiche le résultat :
    int *p = t;
    while (p != fin)
    {
        cout << *p << " ";
        ++p;
    }
    cout << endl;
    // Calcule la différence symétrique de t1 et t2 :
    fin = set_symmetric_difference(t1, t1+10, t2, t2+10, t);
    // Affiche le résultat :
    p = t;
    while (p != fin)
    {
        cout << *p << " ";
        ++p;
    }
    cout << endl;
    return 0;
}				
 

18.5.5. Opérations de partitionnement

L'algorithme partition de la bibliothèque standard permet de séparer les éléments d'un ensemble en deux sous-ensembles selon un critère donné. Les éléments vérifiant ce critère sont placés en tête de l'ensemble, et les éléments qui ne le vérifient pas sont placés à la fin. Cet algorithme est déclaré comme suit dans l'en-tête algorithm :

 
Sélectionnez

template <class ForwardIterator, class Predicate>
ForwardIterator partition(ForwardIterator premier,
    ForwardIterator dernier, Predicate p);
 

Les paramètres qui doivent être fournis à cet algorithme sont les itérateurs référençant le premier et le dernier élément de l'ensemble à partitionner, ainsi qu'un foncteur unaire permettant de déterminer si un élément vérifie le critère de partitionnement ou non. La valeur retournée est la position de la séparation entre les deux sous-ensembles générés par l'opération de partition.

Exemple 18-33. Algorithme de partitionnement
Sélectionnez

#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};
    // Partitionne le tableau en nombre pairs
    // et nombre impairs :
    partition(t, t+10, ptr_fun(&parity_even));
    // Affiche le résultat :
    int i;
    for (i=0; i<10; ++i)
        cout << t[i] << " ";
    cout << endl;
    return 0;
}
 

La complexité de l'algorithme partition est linéaire en fonction du nombre d'éléments de l'ensemble à partitionner. Cependant, l'opération de partitionnement n'est pas stable, c'est-à-dire que l'ordre relatif des éléments de même valeur et sur lesquels le prédicat du critère de partitionnement donne le même résultat n'est pas conservé. La bibliothèque standard fournit donc un autre algorithme, stable celui-là, mais qui s'exécute avec une complexité légèrement supérieure. Il s'agit de l'algorithme stable_partition, qui est déclaré comme suit dans l'en-tête algorithm :

 
Sélectionnez

template <class ForwardIterator, class Predicate>
ForwardIterator stable_partition(ForwardIterator premier,
    ForwardIterator dernier, Predicate p);
 

Comme vous pouvez le constater, cet algorithme s'utilise exactement de la même manière que l'algorithme partition. Toutefois, il garantit l'ordre relatif des éléments au sein des sous-ensembles générés par l'opération de partitionnement. La complexité de cet algorithme est n s'il dispose de suffisamment de mémoire, et n×ln(n) dans le cas contraire (n étant la taille de l'ensemble à partitionner).


précédentsommairesuivant

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+   

  

Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright © 2012 developpez.com Developpez LLC. Tous droits réservés Developpez LLC. Aucune reproduction, même partielle, ne peut être faite de ce site ni de l'ensemble de son contenu : textes, documents et images sans l'autorisation expresse de Developpez LLC. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.