Recherche
Recherche
En général, la plupart des opérations de recherche de séquence spécifique que les programmes sont susceptibles d’effectuer se font sur des chaînes de caractères ou sur les conteneurs associatifs. Cependant, il peut être nécessaire de rechercher un élément dans un conteneur selon un critère particulier ou de rechercher une séquence d’éléments reproduisant un schéma particulier à retrouver dans la suite des éléments d’un conteneur. Enfin, il est relativement courant d’avoir à rechercher les groupes d’éléments consécutifs disposant de la même valeur dans un conteneur. Toutes ces opérations peuvent être effectuées à l’aide des algorithmes de recherche.Recherche d’éléments
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 Predicat>
InputIterator find_if(InputIterator premier, InputIterator dernier, Predicat 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 argument 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 argument 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é de valeur, vous devrez utiliser l’algorithme find_if. Celui-ci prend un prédicat en argument à 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.
find_first_of
L’algorithme find_first_of prend deux paires d’itérateurs en argument. La première paire définit l’intervalle d’éléments dans lequel la recherche doit être effectuée et la seconde 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 la seconde paire 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 argument 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.Code 9.11 : algorithme de recherche d’éléments
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int tab[10] = {0, 5, 3, 4, 255, 7, 0, 5, 255, 9};
//On recherche les éléments de valeur 0 ou 255 :
int sep[2] = {0, 255};
int *debut = tab;
int *fin = tab+10;
int *courant;
cout << "Dans le tableau {0,5,3,4,255,7,0,5,255,9}" << endl;
while ((courant=find_first_of(debut, fin, sep, sep+2)) != fin)
{
//On affiche la position de l’élément trouvé :
cout << *courant << " en position " << courant-tab << endl;
debut = courant+1;
}
}
Recherche de séquences spécifiques
Les opérations de recherche de séquences spécifiques permettent de trouver les premières et les dernières occurrences d’un schéma donné dans une suite de valeurs. Ces opérations sont effectué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 les algorithmes de ce type prennent en argument deux paires d’itérateurs, la première permettant d’identifier la séquence des valeurs dans laquelle la recherche du motif doit être effectuée et la seconde 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 seconde permet d’effectuer cette comparaison à l’aide d’un prédicat binaire, que l’on fournit dans ce cas en dernier argument.
search et find_end
La valeur retournée par l’algorithme search est un itérateur sur la première occurrence de la séquence recherchée 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 schéma 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 schéma 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 la séquence n’a pas pu être trouvée.Code 9.12 : algorithmes de recherche de séquence spécifique
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int tab[10] = {1, 2, 4, 5, 3, 1, 2, 3, 5, 9};
//On recherche le schéma {1, 2, 3} dans le tableau :
int motif[3] = {1, 2, 3};
int *p = search(tab, tab+10, motif, motif+3);
cout << "Dans le tableau {1,2,4,5,3,1,2,3,5,9}" << endl;
cout << "{1,2,3} se trouve en position ";
cout << p - tab << endl;
//On recherche la dernière occurrence de {1, 2} :
p = find_end(tab, tab+10, motif, motif+2);
cout << "La derniere occurrence de {1, 2}";
cout << " se trouve en position " << p - tab << endl;
}
Quand la séquence recherchée est une suite d’éléments identiques, il est possible d’utiliser l’algorithme search_n.
adjacent_find
L’algorithme adjacent_find() recherche deux éléments adjacents de même valeur dans la séquence. La bibliothèque standard définit deux opérateurs adjacent_find() surchargés. La première version compare les éléments à l’aide de l’opérateur surchargé == :template<class ForwardIterator> ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last);
La seconde version de adjacent_find() compare les éléments à l’aide d’un prédicat binaire externe. Si le prédicat est vrai sur deux éléments adjacents, ces derniers sont considérés comme étant égaux :
template <class ForwardIterator , class...BinaryPredicate> ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred);
Les deux versions renvoient l’itérateur pointant sur le premier élément de la paire (si toutefois une paire d’éléments a bien été trouvée). Dans le cas contraire, l’itérateur last est renvoyé.
Code 9.13 : algorithme de recherche de doublons
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int tab[10] = {0, 1, 2, 2, 3, 4, 4, 5, 6, 2};
// Recherche les doublons dans le tableau :
int *debut = tab;
int *fin = tab+10;
int *p;
cout << "Dans le tableau {0, 1, 2, 2, 3, 4, 4, 5, 6, 2}" << endl;
while ((p = adjacent_find(debut, fin)) != fin)
{
cout << "Doublon en position " << p-tab << endl;
debut = p+1;
}
}
Le texte original de cette fiche pratique est extrait de
«Tout sur le C++» (Christine EBERHARDT, Collection
CommentCaMarche.net, Dunod, 2009)