Cours de C/C++

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

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

template <class ForwarIterator, class T>
void fill(ForwardIterator premier, ForwardIterator dernier, const T &valeur);
 
template <class OutputIterator, class T>
void fill_n(OutputIterator premier, Size nombre, const T &valeur);
 
tempalte <class ForwardIterator, class T, class Generator>
void generate(ForwardIterator premier, ForwardIterator dernier, Generator g);
 
template <class OutputIterator, class T, class Generator>
void generate_n(OutputIterator premier, Size nombre, Generator g);

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

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

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

template <class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator premier, InputIterator dernier,
    OutputIterator destination);
 
template <class BidirectionalIterator1, class BidirectionalIterator2>
BidirectionalIterator2 copy_backward(
    BidirectionalIterator1 premier, BidirectionalIterator1 dernier,
    BidirectionalIterator2 fin_destination);

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

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

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.

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

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

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

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

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

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

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

template <class ForwardIterator, class T>
ForwardIterator remove(ForwardIterator premier, ForwardIterator second,
    const T &valeur);
 
template <class InputIterator, class OutputIterator, class T>
OutputIterator remove_copy(InputIterator premier, InputIterator second,
    OutputIterator destination, const T &valeur);
 
template <class ForwardIterator, class Predicate>
ForwardIterator remove_if(ForwardIterator premier, ForwardIterator second,
    Predicate p);
 
template <class InputIterator, class OutputIterator, class Predicate>
OutputIterator remove_copy_if(InputIterator premier, InputIterator second,
    OutputIterator destination, Predicate p);

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

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

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

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

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

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

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

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

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

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

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

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.

18.1.6.1. Opérations de rotation et de permutation▲

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

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

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

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

18.1.6.2. Opérations d'inversion▲

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

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

18.1.6.3. Opérations de mélange▲

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

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

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

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

template <class InputIterator, class Function>
Function for_each(InputIterator premier, InputIterator dernier, Function f);
 
template <class InputIterator, class OutputIterator,
    class UnaryOperation>
OutputIterator transform(InputIterator premier, InputIterator dernier,
    OutputIterator destination, UnaryOperation op);
 
template <class InputIterator1, class InputIterator2,
    class OutputIterator, class BinaryOperation>
OutputIterator transform(InputIterator1 premier1, InputIterator1 dernier1,
    InputIterator2 premier2, OutputIterator destination,
 
    BinaryOperation op);

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

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

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

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

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

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

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

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

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

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

template <class InputIterator, class T>
T accumulate(InputIterator premier, InputIterator dernier, T init);
 
template <class InputIterator, class T, class BinaryOperation>
T accumulate(InputIterator premier, InputIterator dernier,
    T init, BinaryOperation op);
 
template <class InputIterator1, class InputIterator2, class T>
T inner_product(InputIterator1 premier1, InputIterator1 dernier1,
    InputIterator2 premier2, T init);
 
template <class InputIterator1, class InputIterator2, class T,
    class BinaryOperation1, class BinaryOperation2>
T inner_product(InputIterator1 premier1, InputIterator1 dernier1,
    InputIterator2 premier2, T init,
    BinaryOperation1 op1, BinaryOperation op2);
 
template <class InputIterator, class OutputIterator>
OutputIterator partial_sum(InputIterator premier, InputIterator dernier,
    OutputIterator destination);
 
template <class InputIterator, class OutputIterator, class BinaryOperation>
OutputIterator partial_sum(InputIterator premier, InputIterator dernier,
    OutputIterator destination, BinaryOperation op);
 
template <class InputIterator, class OutputIterator>
OutputIterator adjacent_difference(InputIterator premier, InputIterator dernier,
    OutputIterator destination);
 
template <class InputIterator, class OutputIterator, class BinaryOperation>
OutputIterator adjacent_difference(InputIterator premier, InputIterator dernier,
    OutputIterator destination, BinaryOperation op);

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

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

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

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

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

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

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 :

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.

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

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 :

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

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

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 :

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.

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

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.

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 :

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.

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

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 :

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.

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

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.

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

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

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.

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

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 :

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 :

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.

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

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.

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.

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

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 :

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.

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

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 :

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.

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

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 :

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.

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

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.

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

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.

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

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.

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

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 :

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.

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

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