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

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 :

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

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 :

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.

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

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

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 :

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.

18.1.1. Opérations d'initialisation et de remplissage

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

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

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

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

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

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

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

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

using namespace std;

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

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

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

18.1.2. Opérations de copie

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

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

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

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

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

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

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

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

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

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

using namespace std;

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

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

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

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

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

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

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

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

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

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

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

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

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

18.1.5. Opérations de remplacement

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

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

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

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

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

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

#include <iostream>
#include <algorithm>

using namespace std;

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

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

18.1.6. Réorganisation de séquences

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

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

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

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

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

18.1.7. Algorithmes d'itération et de transformation

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

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

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

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

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

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

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

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

17.3.1. Généralités et propriétés de base des clefs

La contrainte fondamentale que les algorithmes des conteneurs associatifs imposent est qu'il existe une relation d'ordre pour le type de donnée utilisé pour les clefs des objets. Cette relation peut être définie soit implicitement par un opérateur d'infériorité, soit par un foncteur que l'on peut spécifier en tant que paramètre template des classes des conteneurs.

Alors que l'ordre de la suite des éléments stockés dans les séquences est très important, ce n'est pas le cas avec les conteneurs associatifs, car ceux-ci se basent exclusivement sur l'ordre des clefs des objets. En revanche, la bibliothèque standard C++ garantit que le sens de parcours utilisé par les itérateurs des conteneurs associatifs est non décroissant sur les clefs des objets itérés. Cela signifie que le test d'infériorité strict entre la clef de l'élément suivant et la clef de l'élément courant est toujours faux, ou, autrement dit, l'élément suivant n'est pas plus petit que l'élément courant.

Comme pour tous les conteneurs, le type des éléments stockés par les conteneurs associatifs est le type value_type. Cependant, contrairement aux séquences, ce type n'est pas toujours le type template par lequel le conteneur est paramétré. En effet, ce type est une paire contenant le couple de valeurs formé par la clef et par l'objet lui-même pour toutes les associations (c'est-à-dire pour les map et les multimap). Dans ce cas, les méthodes du conteneur qui doivent effectuer des comparaisons sur les objets se basent uniquement sur le champ first de la paire encapsulant le couple (clef, valeur) de chaque objet. Autrement dit, les comparaisons d'objets sont toujours définies sur les clefs, et jamais sur les objets eux-mêmes. Bien entendu, pour les ensembles, le type value_type est strictement équivalent au type template par lequel ils sont paramétrés.

Pour simplifier l'utilisation de leurs clefs, les conteneurs associatifs définissent quelques types complémentaires de ceux que l'on a déjà présentés dans la section 17.1.12. Le plus important de ces types est sans doute le type key_type qui, comme son nom l'indique, représente le type des clefs utilisées par ce conteneur. Ce type constitue donc, avec le type value_type, l'essentiel des informations de typage des conteneurs associatifs. Enfin, les conteneurs définissent également des types de prédicats permettant d'effectuer des comparaisons entre deux clefs et entre deux objets de type value_type. Il s'agit des types key_compare et value_compare.

17.3.2. Construction et initialisation

Les conteneurs associatifs disposent de plusieurs surcharges de leurs constructeurs qui permettent de les créer et de les initialiser directement. De manière générale, ces constructeurs prennent tous deux paramètres afin de laisser au programmeur la possibilité de définir la valeur du foncteur qu'ils doivent utiliser pour comparer les clefs, ainsi qu'une instance de l'allocateur à utiliser pour les opérations mémoire. Comme pour les séquences, ces paramètres disposent de valeurs par défaut, si bien qu'en général il n'est pas nécessaire de les préciser.

Hormis le constructeur de copie et le constructeur par défaut, les conteneurs associatifs fournissent un troisième constructeur permettant de les initialiser à partir d'une série d'objets. Ces objets sont spécifiés par deux itérateurs, le premier indiquant le premier objet à insérer dans le conteneur et le deuxième l'itérateur référençant l'élément suivant le dernier élément à insérer. L'utilisation de ce constructeur est semblable au constructeur du même type défini pour les séquences et ne devrait donc pas poser de problème particulier.

#include <iostream>
#include <map>
#include <list>

using namespace std;

int main(void)
{
    typedef map<int, char *> Int2String;
    // Remplit une liste d'éléments pour ces maps :
    typedef list<pair<int, char *> > lv;
    lv l;
    l.push_back(lv::value_type(1, "Un"));
    l.push_back(lv::value_type(2, "Deux"));
    l.push_back(lv::value_type(5, "Trois"));
    l.push_back(lv::value_type(6, "Quatre"));
    // Construit une map et l'initialise avec la liste :
    Int2String i2s(l.begin(), l.end());
    // Affiche le contenu de la map :
    Int2String::iterator i = i2s.begin();
    while (i != i2s.end())
    {
        cout << i->second << endl;
        ++i;
    }
    return 0;
}

17.3.3. Ajout et suppression d'éléments

Du fait de l'existence des clefs, les méthodes d'insertion et de suppression des conteneurs associatifs sont légèrement différentes de celles des séquences. De plus, elles n'ont pas tout à fait la même signification. En effet, les méthodes d'insertion des conteneurs associatifs ne permettent pas, contrairement à celles des séquences, de spécifier l'emplacement où un élément doit être inséré puisque l'ordre des éléments est imposé par la valeur de leur clef. Les méthodes d'insertion des conteneurs associatifs sont présentées ci-dessous :

Comme pour les séquences, la suppression des éléments des conteneurs associatifs se fait à l'aide des surcharges de la méthode erase. Les différentes versions de cette méthode sont indiquées ci-dessous :

#include <iostream>
#include <map>

using namespace std;

typedef map<int, char *> Int2String;

void print(Int2String &m)
{
    Int2String::iterator i = m.begin();
    while (i != m.end())
    {
        cout << i->second << endl;
        ++i;
    }
    return ;
}

int main(void)
{
    // Construit une association Entier -> Chaîne :
    Int2String m;
    // Ajoute quelques éléments :
    m.insert(Int2String::value_type(2, "Deux"));
    pair<Int2String::iterator, bool> res =
        m.insert(Int2String::value_type(3, "Trois"));
    // On peut aussi spécifier un indice sur
    // l'emplacement où l'insertion aura lieu :
    m.insert(res.first,
        Int2String::value_type(5, "Cinq"));
    // Affiche le contenu de l'association :
    print(m);
    // Supprime l'élément de clef 2 :
    m.erase(2);
    // Supprime l'élément "Trois" par son itérateur :
    m.erase(res.first);
    print(m);
    return 0;
}

17.3.4. Fonctions de recherche

Les fonctions de recherche des conteneurs associatifs sont puissantes et nombreuses. Ces méthodes sont décrites ci-dessous :

#include <iostream>
#include <map>

using namespace std;

int main(void)
{
    // Déclare une map à clefs multiples :
    typedef multimap<int, char *> Int2String;
    Int2String m;
    // Remplit la map :
    m.insert(Int2String::value_type(2, "Deux"));
    m.insert(Int2String::value_type(3, "Drei"));
    m.insert(Int2String::value_type(1, "Un"));
    m.insert(Int2String::value_type(3, "Three"));
    m.insert(Int2String::value_type(4, "Quatre"));
    m.insert(Int2String::value_type(3, "Trois"));
    // Recherche un élément de clef 4 et l'affiche :
    Int2String::iterator i = m.find(4);
    cout << i->first << " : " << i->second << endl;
    // Recherche le premier élément de clef 3 :
    i = m.lower_bound(3);
    // Affiche tous les éléments dont la clef vaut 3 :
    while (i != m.upper_bound(3))
    {
        cout << i->first << " : " << i->second << endl;
        ++i;
    }
    // Effectue la même opération, mais de manière plus efficace
    // (upper_bound n'est pas appelée à chaque itération) :
    pair<Int2String::iterator, Int2String::iterator> p =
        m.equal_range(3);
    for (i = p.first; i != p.second; ++i)
    {
        cout << i->first << " : " << i->second << endl;
    }
    return 0;
}

Les recherches dans les conteneurs associatifs s'appuient sur le fait que les objets disposent d'une relation d'ordre induite par le foncteur less appliqué sur le type des données qu'ils manipulent. Ce comportement est généralement celui qui est souhaité, mais il existe des situations où ce foncteur ne convient pas. Par exemple, on peut désirer que le classement des objets se fasse sur une de leur donnée membre seulement, ou que la fonction de comparaison utilisée pour classer les objets soit différente de celle induite par le foncteur less. La bibliothèque standard fournit donc la possibilité de spécifier un foncteur de comparaison pour chaque conteneur associatif, en tant que paramètre template complémentaire au type de données des objets contenus. Ce foncteur doit, s'il est spécifié, être précisé avant le type de l'allocateur mémoire à utiliser. Il pourra être construit à partir des facilités fournies par la bibliothèque standard pour la création et la manipulation des foncteurs.

#include <iostream>
#include <map>
#include <string>
#include <functional>
#include <cstring>

using namespace std;

// Fonction de comparaison de chaînes de caractères
// non sensible à la casse des lettres :
bool stringless_nocase(const string &s1, const string &s2)
{
    return (strcasecmp(s1.c_str(), s2.c_str()) < 0);
}

int main(void)
{
    // Définit le type des associations chaînes -> entiers
    // dont la clef est indexée sans tenir compte
    // de la casse des lettres :
    typedef map<string, int,
        pointer_to_binary_function<const string &,
            const string &, bool> > String2Int;
    String2Int m(ptr_fun(stringless_nocase));
    // Insère quelques éléments dans la map :
    m.insert(String2Int::value_type("a. Un", 1));
    m.insert(String2Int::value_type("B. Deux", 2));
    m.insert(String2Int::value_type("c. Trois", 3));
    // Affiche le contenu de la map :
    String2Int::iterator i = m.begin();
    while (i != m.end())
    {
        cout << i->first << " : " << i->second << endl;
        ++i;
    }
    return 0;
}

Dans cet exemple, le type du foncteur est spécifié en troisième paramètre de la classe template map. Ce type est une instance de la classe template pointer_to_binary_function pour les types string et bool. Comme on l'a vu dans la section 13.5, cette classe permet d'encapsuler toute fonction binaire dans un foncteur binaire. Il ne reste donc qu'à spécifier l'instance du foncteur que la classe template map doit utiliser, en la lui fournissant dans son constructeur. L'exemple précédent utilise la fonction utilitaire ptr_fun de la bibliothèque standard pour construire ce foncteur à partir de la fonction stringless_nocase.

En fait, il est possible de passer des foncteurs beaucoup plus évolués à la classe map, qui peuvent éventuellement être paramétrés par d'autres paramètres que la fonction de comparaison à utiliser pour comparer deux clefs. Cependant, il est rare d'avoir à écrire de tels foncteurs et même, en général, il est courant que la fonction binaire utilisée soit toujours la même. Dans ce cas, il est plus simple de définir directement le foncteur et de laisser le constructeur de la classe map prendre sa valeur par défaut. Ainsi, seul le paramètre template donnant le type du foncteur doit être spécifié, et l'utilisation des conteneurs associatif en est d'autant facilitée. L'exemple suivant montre comment la comparaison de chaînes de caractères non sensible à la casse peut être implémentée de manière simplifiée.

#include <iostream>
#include <string>
#include <map>
#include <functional>
#include <cstring>

using namespace std;

// Classe de comparaison de chaînes de caractères :
class StringLessNoCase : public binary_function<string, string, bool>
{
public:
    bool operator()(const string &s1, const string &s2)
    {
        return (strcasecmp(s1.c_str(), s2.c_str()) < 0);
    }
};

int main(void)
{
    // Définition du type des associations chaînes -> entiers
    // en spécifiant directement le type de foncteur à utiliser
    // pour les comparaisons de clefs :
    typedef map<string, int, StringLessNoCase> String2Int;
    // Instanciation d'une association en utilisant
    // la valeur par défaut du foncteur de comparaison :
    String2Int m;
    // Utilisation de la map :
    m.insert(String2Int::value_type("a. Un", 1));
    m.insert(String2Int::value_type("B. Deux", 2));
    m.insert(String2Int::value_type("c. Trois", 3));
    String2Int::iterator i = m.begin();
    while (i != m.end())
    {
        cout << i->first << " : " << i->second << endl;
        ++i;
    }
    return 0;
}

Pour finir, sachez que les conteneurs associatifs disposent d'une méthode count qui renvoie le nombre d'éléments du conteneur dont la clef est égale à la valeur passée en premier paramètre. Cette méthode retourne donc une valeur du type size_type du conteneur, valeur qui peut valoir 0 ou 1 pour les conteneurs à clefs uniques et n'importe quelle valeur pour les conteneurs à clefs multiples. La complexité de cette méthode est ln(N)+n, où N est le nombre d'éléments stockés dans le conteneur et n est le nombre d'éléments dont la clef est égale à la valeur passée en paramètre. Le premier terme provient en effet de la recherche du premier élément disposant de cette propriété, et le deuxième des comparaisons qui suivent pour compter les éléments désignés par la clef.

17.2.1. Fonctionnalités communes

Il existe un grand nombre de classes template de séquences dans la bibliothèque standard qui permettent de couvrir la majorité des besoins des programmeurs. Ces classes sont relativement variées tant dans leurs implémentations que dans leurs interfaces. Cependant, un certain nombre de fonctionnalités communes sont gérées par la plupart des séquences. Ce sont ces fonctionnalités que cette section se propose de vous décrire. Les fonctionnalités spécifiques à chaque classe de séquence seront détaillées séparément dans la section 17.2.2.1.

Les exemples fournis dans cette section se baseront sur le conteneur list, qui est le type de séquence le plus simple de la bibliothèque standard. Cependant, ils sont parfaitement utilisables avec les autres types de séquences de la bibliothèque standard, avec des niveaux de performances éventuellement différents en fonction des séquences choisies bien entendu.

#include <iostream>
#include <list>

using namespace std;

typedef list<int> li;

void print(li &l)
{
    li::iterator i = l.begin();
    while (i != l.end())
    {
        cout << *i << " " ;
        ++i;
    }
    cout << endl;
}

int main(void)
{
    // Initialise une liste avec trois éléments valant 5 :
    li l1(3, 5);
    print(l1);
    // Initialise une autre liste à partir de la première
    // (en fait on devrait appeler le constructeur de copie) :
    li l2(l1.begin(), l1.end());
    print(l2);
    // Affecte 4 éléments valant 2 à l1 :
    l1.assign(4, 2);
    print(l1);
    // Affecte l1 à l2 (de même, on devrait normalement
    // utiliser l'opérateur d'affectation) :
    l2.assign(l1.begin(), l1.end());
    print(l2);
    return 0;
}

#include <iostream>
#include <list>

using namespace std;

typedef list<int> li;

void print(li &l)
{
    li::iterator i = l.begin();
    while (i != l.end())
    {
        cout << *i << " " ;
        ++i;
    }
    cout << endl;
    return ;
}

int main(void)
{
    li l1;
    // Ajoute 5 à la liste :
    li::iterator i = l1.insert(l1.begin(), 5);
    print(l1);
    // Ajoute deux 3 à la liste :
    l1.insert(i, 2, 3);
    print(l1);
    // Insère le contenu de l1 dans une autre liste :
    li l2;
    l2.insert(l2.begin(), l1.begin(), l1.end());
    print(l2);
    return 0;
}

// Récupère un itérateur sur le premier
// élément de la liste :
list<int>::iterator i = instance.begin();
while (i != instance.end())
{
    i = instance.erase(i);
}

17.2.2. Les différents types de séquences

La bibliothèque standard fournit trois classes fondamentales de séquence. Ces trois classes sont respectivement la classe list, la classe vector et la classe deque. Chacune de ces classes possède ses spécificités en fonction desquelles le choix du programmeur devra se faire. De plus, la bibliothèque standard fournit également des classes adaptatrices permettant de construire des conteneurs équivalents, mais disposant d'une interface plus standard et plus habituelle aux notions couramment utilisées en informatique. Toutes ces classes sont décrites dans cette section, les adaptateurs étant abordés en dernière partie.

#include <iostream>
#include <list>

using namespace std;

typedef list<int> li;

int main(void)
{
    li l1;
    l1.push_back(2);
    l1.push_back(5);
    cout << "Tête : " << l1.front() << endl;
    cout << "Queue : " << l1.back() << endl;
    l1.push_front(7);
    cout << "Tête : " << l1.front() << endl;
    cout << "Queue : " << l1.back() << endl;
    l1.pop_back();
    cout << "Tête : " << l1.front() << endl;
    cout << "Queue : " << l1.back() << endl;
    return 0;
}

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

using namespace std;

typedef list<int> li;

void print(li &l)
{
    li::iterator i = l.begin();
    while (i != l.end())
    {
        cout << *i << " ";
        ++i;
    }
    cout << endl;
    return ;
}

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

int main(void)
{
    // Construit une liste exemple :
    li l;
    l.push_back(2);
    l.push_back(5);
    l.push_back(7);
    l.push_back(7);
    l.push_back(3);
    l.push_back(3);
    l.push_back(2);
    l.push_back(6);
    l.push_back(6);
    l.push_back(6);
    l.push_back(3);
    l.push_back(4);
    cout << "Liste de départ :" << endl;
    print(l);
    li l1;
    // Liste en ordre inverse :
    l1 = l;
    l1.reverse();
    cout << "Liste inverse :" << endl;
    print(l1);
    // Trie la liste :
    l1 = l;
    l1.sort();
    cout << "Liste triée : " << endl;
    print(l1);
    // Supprime tous les 3 :
    l1 = l;
    l1.remove(3);
    cout << "Liste sans 3 :" << endl;
    print(l1);
    // Supprime les doublons :
    l1 = l;
    l1.unique();
    cout << "Liste sans doublon :" << endl;
    print(l1);
    // Retire tous les nombres pairs :
    l1 = l;
    l1.remove_if(ptr_fun(&parity_even));
    cout << "Liste sans nombre pair :" << endl;
    print(l1);
    // Injecte une autre liste entre les 7 :
    l1 = l;
    li::iterator i = l1.begin();
    ++i; ++i; ++i;
    li l2;
    l2.push_back(35);
    l2.push_back(36);
    l2.push_back(37);
    l1.splice(i, l2, l2.begin(), l2.end());
    cout << "Fusion des deux listes :" << endl;
    print(l1);
    if (l2.size() == 0)
        cout << "l2 est vide" << endl;
    return 0;
}

#include <iostream>
#include <vector>

using namespace std;

int main(void)
{
    typedef vector<int> vi;
    // Crée un vecteur de 10 éléments :
    vi v(10);
    // Modifie quelques éléments :
    v.at(2) = 2;
    v.at(5) = 7;
    // Redimensionne le vecteur :
    v.resize(11);
    v.at(10) = 5;
    // Ajoute un élément à la fin du vecteur :
    v.push_back(13);
    // Affiche le vecteur en utilisant l'opérateur [] :
    for (int i=0; i<v.size(); ++i)
    {
        cout << v[i] << endl;
    }
    return 0;
}

#include <iostream>
#include <stack>

using namespace std;

int main(void)
{
    typedef stack<int> si;
    // Crée une pile :
    si s;
    // Empile quelques éléments :
    s.push(2);
    s.push(5);
    s.push(8);
    // Affiche les éléments en ordre inverse :
    while (!s.empty())
    {
        cout << s.top() << endl;
        s.pop();
    }
    return 0;
}

#include <iostream>
#include <queue>

using namespace std;

int main(void)
{
    typedef queue<int> qi;
    // Crée une file :
    qi q;
    // Ajoute quelques éléments :
    q.push(2);
    q.push(5);
    q.push(8);
    // Affiche récupère et affiche les éléments :
    while (!q.empty())
    {
        cout << q.front() << endl;
        q.pop();
    }
    return 0;
}

#include <iostream>
#include <queue>

using namespace std;

// Type des données stockées dans la file :
struct A
{
    int k;         // Priorité
    const char *t; // Valeur
    A() : k(0), t(0) {}
    A(int k, const char *t) : k(k), t(t) {}
};

// Foncteur de comparaison selon les priorités :
class C
{
public:
    bool operator()(const A &a1, const A &a2)
    {
        return a1.k < a2.k ;
    }
};

int main(void)
{
    // Construit quelques objets :
    A a1(1, "Priorité faible");
    A a2(2, "Priorité moyenne 1");
    A a3(2, "Priorité moyenne 2");
    A a4(3, "Priorité haute 1");
    A a5(3, "Priorité haute 2");
    // Construit une file de priorité :
    priority_queue<A, vector<A>, C> pq;
    // Ajoute les éléments :
    pq.push(a5);
    pq.push(a3);
    pq.push(a1);
    pq.push(a2);
    pq.push(a4);
    // Récupère les éléments par ordre de priorité :
    while (!pq.empty())
    {
        cout << pq.top().t << endl;
        pq.pop();
    }
    return 0;
}