18.2. Opérations de recherche

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.