Recherche dans une séquence et méthodes associées en C++ - Bibliothèque STL

La recherche est une technique principale utilisée avec des collections ou des séquences pour y rechercher des éléments. Dans ce cours, nous allons découvrir autant de fonctions définies dans la bibliothèque STL pour rechercher dans une séquence (vecteur, deque...)

Nous utilisons le mot algorithme dans ce cours pour faire référence à ce que fait la fonction.

Fonctions find, find_if, et find_if_not

Les algorithmes find, find_if , et find_if_not trouvent le premier élément d'une séquence correspondant à certains critères définis par l'utilisateur.

Ces algorithmes renvoient un InputIterator pointant sur la valeur val de correspondance du premier élément de la séquence cible (find), donnant un résultat true lorsqu'il est invoqué avec pred (find_if), ou donnant un résultat false lorsqu'il est invoqué avec pred (find_if_not).

Si l'algorithme ne trouve aucune correspondance, il renvoie it_end.

Syntaxe

InputIterator find([ep], it_debut, it_fin, val);
InputIterator find_if([ep], it_debut, it_fin, pred);
InputIterator find_if_not([ep], it_debut, it_fin, pred);

Arguments

Une politique d'exécution std::execution facultative, ep (par défaut : std::execution ::seq)
Une paire d'objets InputIterator, it_debut et it_fin, représentant la séquence cible
La valeur recherchée val (find) ou un prédicat pred qui accepte un seul argument avec le type sous-jacent de la séquence cible (find_if et find_if_not)

L'algorithme effectue au maximum distance(it_debut, it_fin) comparaisons (find) ou invocations de pred (find_if et find_if_not). La complexité est donc linéaire.

Exemple 1

#include<iostream>
#include<algorithm>
#include<deque>
using namespace std;

bool estpair (int i) {return ((i%2)==0);}
bool estimpair (int i) {return ((i%2)==1);}

int main () {

    int vals[] = {1,15,3,2,4,4,5,13,8,9,6};
    int * p;

    p = find (vals, vals+11, 4);

    if(p!=vals+11) cout<< "L'élément avec la valeur 4 se trouve dans Vals";
    else cout<< "L'élément avec la valeur 4 n'est pas trouvé dans Vals";
    cout<<'\n';


    deque<int> d1(vals,vals+11);   
    deque<int>::iterator it;

    it=find(d1.begin(),d1.end(),17);
    if(it==d1.end()) cout << "L'élément avec la valeur 17 n'est pas trouvé dans d1";
    else cout<< "L'élément avec la valeur 17 se trouve dans d1";
    cout<<'\n';

    it = find_if (d1.begin(), d1.end(), estpair);
    if(it!=d1.end()){
        cout << "La première valeur paire est " << *it;
    }

    cout<<'\n';

    it = find_if_not (d1.begin(), d1.end(), estimpair);
    if(it!=d1.end()){
        cout << "La première valeur paire est " << *it;
    }

    cout<<'\n';

    return 0;
}

Résultat

L'élément avec la valeur 4 se trouve dans Vals
L'élément avec la valeur 17 n'est pas trouvé dans d1
La première valeur paire est 2
La première valeur paire est 2

Fonction find_end

Recherche dans l'intervalle [fwd_deb1, fwd_fin1) la dernière occurrence de la séquence définie par [fwd_deb2, fwd_fin2), et renvoie un itérateur vers son premier élément, ou fwd_fin1 si aucune occurrence n'est trouvée.

Syntaxe

InputIterator find_end([ep], fwd_deb1, fwd_fin1,fwd_deb2, fwd_fin2, [pred]);

Arguments

Une politique d'exécution std::execution facultative, ep (par défaut : std::execution ::seq)
Deux paires de ForwardIterators, fwd_deb1/fwd_fin1 et fwd_deb2 / fwd _fin2, représentant les séquences cibles 1 et 2
Un prédicat binaire optionnel pred pour comparer si deux éléments sont égaux.

L'algorithme effectue au maximum le nombre suivant de comparaisons ou d'invocations de pred

$$distance(fwd\_deb2, fwd\_fin2) * (distance(fwd\_deb1, fwd\_fin1) - distance(fwd\_deb2, fwd\_fin2) + 1)$$

Exemple 2

#include<iostream>
#include<algorithm>
#include<deque>
using namespace std;

bool compare (int i, int j) {return (i==j);}

int main () {

    int vals[] = {1,15,3,2,4,4,1,15,3,9,6};
    int objectif1[] = {1,15,3};

    deque<int> d1(vals,vals+11);   
    deque<int>::iterator it;

    it=find_end(d1.begin(),d1.end(),objectif1,objectif1+3);

    if(it!=d1.end()) 
        cout << "La dernière position de la sous-séquence {1, 15, 3} dans d1 est " << (it-d1.begin());
    else 
        cout<< "La sous-séquence {1, 15, 3} n'est pas trouvée";

    cout<<'\n';

    int objectif2[] = {3,9};
    it=find_end(d1.begin(),d1.end(),objectif2,objectif2+2, compare);

    if(it!=d1.end()) 
        cout << "La dernière position de la sous-séquence {3,9} dans d1 est " << (it-d1.begin());
    else 
        cout<< "La sous-séquence {3,9} n'est pas trouvée";

    cout<<'\n';

    return 0;
}

Résultat

La dernière position de la sous-séquence {1, 15, 3} dans d1 est à 6
La dernière position de la sous-séquence {3,9} dans d1 est à 8

Fonction find_first_of

Renvoie un itérateur vers le premier élément de la plage [fwd_deb1, fwd_fin1) qui correspond à l'un des éléments de [fwd_deb2, fwd_fin2). Si aucun élément de ce type n'est trouvé, la fonction renvoie fwd_fin1.

Les éléments de [fwd_deb1, fwd_fin1) sont comparés séquentiellement à chacune des valeurs de [fwd_deb2, fwd_fin2) en utilisant l'opérateur== (ou pred), jusqu'à ce qu'une paire corresponde.

Syntaxe

InputIterator find_first_of([ep], it_deb1, it_fin1,fwd_deb2, fwd_fin2, [pred]);

Arguments

Une politique d'exécution std::execution facultative, ep (par défaut : std::execution ::seq)
Une paire d'objets InputIterator, it_deb1 / it_fin1, représentant la séquence cible 1
Une paire d'objets ForwardIterator, fwd_deb2 / fwd_fin2, représentant la séquence cible 2.
Un prédicat binaire optionnel pred pour comparer si deux éléments sont égaux.

L'algorithme effectue au maximum le nombre suivant de comparaisons ou d'invocations de pred :

$$distance(it\_deb1, it\_fin1) * distance(fwd\_deb2, fwd\_fin2)$$

Exemple 3

#include<iostream>
#include<algorithm>
#include<deque>
using namespace std;

bool compare (int i, int j) {return (i==j);}

int main () {

    int vals[] = {1,15,3,2,4,4,1,15,3,9,6};
    int objectif1[] = {1,15,3};

    deque<int> d1(vals,vals+11);   
    deque<int>::iterator it;

    it=find_first_of(d1.begin(),d1.end(),objectif1,objectif1+3);

    if(it!=d1.end()) 
        cout << "La position du premier élément qui correspond à l'un des éléments de {1, 15, 3} est " << (it-d1.begin());
    else 
        cout<< "Aucun élément de {1, 15, 3} n'est trouvé";

    cout<<'\n';

    int objectif2[] = {51,10};
    it=find_first_of(d1.begin(),d1.end(),objectif2,objectif2+2, compare);

    if(it!=d1.end()) 
        cout << "La position du premier élément qui correspond à l'un des éléments de {51, 10} est " << (it-d1.begin());
    else 
        cout<< "Aucun élément de {51, 10} n'est trouvé";

    cout<<'\n';

    return 0;
}

Résultat

La position du premier élément qui correspond à l'un des éléments de {1, 15, 3} est 0
Aucun élément de {51, 10} n'est trouvé

Fonction adjacent_find

L'algorithme adjacent_find trouve la première répétition dans une séquence. L'algorithme trouve la première occurrence dans la séquence cible où deux éléments adjacents sont égaux ou, si vous fournissez pred, l'algorithme trouve la première occurrence de l'élément i dans la séquence où pred (i, i+1) est true.

Si adjacent_find ne trouve pas un tel élément, il renvoie fwd_end. Si adjacent_find trouve un tel élément, il renvoie un ForwardIterator pointant vers lui.

Syntaxe

ForwardIterator adjacent_find([ep], fwd_debut, fwd_fin, [pred]);

Arguments

Une politique d'exécution std::execution facultative, ep (par défaut : std::execution ::seq)
Une paire de ForwardIterators, fwd_debut / fwd_fin, représentant la séquence cible
Un prédicat binaire optionnel pred pour comparer si deux éléments sont égaux.

L'algorithme effectue au maximum le nombre suivant de comparaisons ou d'invocations de pred : $$min(distance(fwd\_debut, i)+1, distance(fwd\_debut, fwd\_fin)-1)$$ où i est l'indice de la valeur de retour.

Exemple 4

#include<iostream>
#include<algorithm>
#include<deque>
using namespace std;

void afficher(int a){ cout << a << " "; }
bool compare (int i, int j) {return (i<j);}

int main () {

    int vals[] = {16,15,3,4,4,1,15,9,9,6};

    deque<int> d1(vals,vals+10);   
    deque<int>::iterator it;

    for_each(d1.begin(),d1.end(), afficher);
    cout<<'\n';

    it=adjacent_find(d1.begin(),d1.end());

    if(it!=d1.end()) 
        cout << "La position des premiers éléments consécutifs égaux est : " << (it-d1.begin());
    else 
        cout<< "Il n'y a pas d'éléments consécutifs égaux";

    cout<<'\n';

    it=adjacent_find(d1.begin(),d1.end(),compare);

    if(it!=d1.end()) 
        cout << "La position de la première sous-séquence strictement croissante est " << (it-d1.begin());
    else 
        cout<< "Il n'y a pas de sous-séquence strictement croissante";

    cout<<'\n';

    return 0;
}

Résultat

16 15 3 4 4 1 15 9 9 6 
La position des premiers éléments consécutifs égaux est : 3
La position de la première sous-séquence strictement croissante est 2

Fonction count

L'algorithme count compte les éléments d'une séquence correspondant à certains critères définis par l'utilisateur.

L'algorithme renvoie le nombre d'éléments i dans la séquence cible où pred(i) est true ou où val==i.

Vous utilisez count quand vous voulez compter les occurrences d'une valeur particulière, et vous utilisez count_if quand vous avez un prédicat plus compliqué que vous voulez utiliser pour la comparaison.

Syntaxe

DifferenceType count([ep], it_debut, it_fin, val);
DifferenceType count_if([ep], it_debut, it_fin, pred);

Arguments

Une politique d'exécution std::execution facultative, ep (par défaut : std::execution ::seq)
DifferenceType est un type entier signé. représent le nombre d'occurences
Une paire d'objets InputIterator, it_debut / it_fin, représentant la séquence cible
Soit une valeur val, soit un prédicat unaire pred pour évaluer si un élément x de la séquence cible doit être compté.

La complexité de cette fonction est linéaire dans la distance entre it_debut et it_fin : compare une fois chaque élément.

Exemple 5

#include<iostream>
#include<algorithm>
#include<deque>
using namespace std;

void afficher(int a){ cout << a << " "; }
bool compare (int i) {return (i<0);}

int main () {

    int vals[] = {16,-15,9,4,4,1,15,9,9,-6};

    deque<int> d1(vals,vals+10);   

    for_each(d1.begin(),d1.end(), afficher);
    cout<<'\n';

    int cpt=count(d1.begin(),d1.end(),9);
    cout<< "La valeur 9 apparaît "<< cpt << " fois dans la séquence";
    cout<<'\n';

    cpt=count_if(d1.begin(),d1.end(),compare);
    cout<< "Le nombre de valeurs négatives est "<< cpt;

    cout<<'\n';

    return 0;
}

Résultat

16 -15 9 4 4 1 15 9 9 -6 
La valeur 9 apparaît 3 fois dans la séquence
Le nombre de valeurs négatives est 2

Fonction mismatch

L'algorithme mismatch trouve la première discordance dans deux séquences. L'algorithme trouve la première paire d'éléments incompatibles i, j de la séquence 1 et de la séquence 2. Plus précisément, il trouve le premier indice n tel que i = (it_deb1 + n); j = (it_deb2 + n); et i!= j ou pred(i, j) == false.

Les types des itérateurs dans la paire retournée sont égaux aux types de it_deb1 et it_deb2.

Syntaxe

pair<Itr, Itr> mismatch([ep], it_deb1, it_fin1,  it_deb2, [it_fin2], [pred]);

Arguments

Une politique d'exécution std::execution facultative, ep (par défaut : std::execution ::seq)
Deux paires d'InputIterators, it_deb1 / it_fin1 et it_deb2 / it _fin2, représentant les séquences cibles 1 et 2. Si vous ne fournissez pas it_fin2, la longueur de la séquence 1 implique la longueur de la séquence 2.
Un prédicat binaire optionnel pred pour comparer si deux éléments sont égaux.

La complexité est linéaire par rapport à la distance entre it_deb1 et it_fin1 : Compare les éléments jusqu'à ce qu'une non-concordance soit trouvée. $$min(distance(it\_deb1, it\_fin1), distance(it\_deb2, it\_fin2))$$

Exemple 6

#include<iostream>
#include<algorithm>
#include<deque>
using namespace std;

void afficher(int a){ cout << a << " "; }
bool compare (int i, int j) {return (i<=j);}

int main () {

    int t1[] = {13, 15, 17, 2, 5, 9};
    int t2[] = {13, 15, 17, 3, 2, 9};

    deque<int> d1(t1,t1+6);   
    deque<int> d2(t2,t2+6);  

    pair<deque<int>::iterator,deque<int>::iterator> it;

    for_each(d1.begin(),d1.end(), afficher);
    cout<<'\n';
    for_each(d2.begin(),d2.end(), afficher);
    cout<<'\n';

    it=mismatch(d1.begin(),d1.end(),d2.begin());
    cout<< "La première discordance est aux positions i=" << (it.first-d1.begin()) << ", j=" << (it.second-d2.begin());
    cout<<'\n';

    it=mismatch(d1.begin(),d1.end(),d2.begin(),compare);
    cout<< "La première position où i est supérieur à j est i=" << (it.first-d1.begin()) << ", j=" << (it.second-d2.begin());

    cout<<'\n';

    return 0;
}

Résultat

13 15 17 2 5 9 
13 15 17 3 2 9 
La première discordance est aux positions i=3, j=3
La première position où i est supérieur à j est i=4, j=4

Fonction equal

L'algorithme equal détermine si deux séquences sont égales. L'algorithme détermine si les éléments de la séquence 1 sont égaux à ceux de la séquence 2.

Syntaxe

bool equal([ep], it_deb1, it_fin1, it_deb2, [it_fin2], [pred]);

Arguments

Une politique d'exécution std::execution facultative, ep (par défaut : std::execution ::seq)
Deux paires d'InputIterators, it_deb1 / it_fin1 et it_deb2 / it_fin2, représentant les séquences cibles 1 et 2. Si vous ne fournissez pas it_fin2, la longueur de la séquence 1 implique la longueur de la séquence 2.
Un prédicat binaire optionnel pred pour comparer si deux éléments sont égaux.

La complexité est linéaire dans la distance entre it_deb1 et it_fin1. Compare les éléments jusqu'à ce qu'une non-concordance soit trouvée.

Exemple 7

#include<iostream>
#include<algorithm>
#include<deque>
using namespace std;

void afficher(int a){ cout << a << " "; }
bool compare (int i, int j) {return (i==j);}

int main () {

    int t1[] = {13, 15, 17, 2, 5, 9};
    deque<int> d1(t1,t1+6);   
    for_each(d1.begin(),d1.end(), afficher);
    cout<<'\n';

    if(equal(d1.begin(),d1.end(),t1))
        cout << "Le contenu des deux séquences est égal.\n";
    else
        cout << "Le contenu des deux séquences diffère.\n";
    
    t1[2]=5;
    if(equal(d1.begin(),d1.end(),t1, compare))
        cout << "Le contenu des deux séquences est égal.\n";
    else
        cout << "Le contenu des deux séquences diffère.\n";


    return 0;
}

Résultat

13 15 17 2 5 9 
Le contenu des deux séquences est égal.
Le contenu des deux séquences diffère.

Fonction is_permutation

L'algorithme is_permutation détermine si deux séquences sont des permutations, c'est-à-dire qu'elles contiennent les mêmes éléments mais potentiellement dans un ordre différent.

Syntaxe

bool is_permutation([ep], fwd_deb1, fwd_fin1, fwd_deb2, [fwd_fin2], [pred]);

Arguments

Une politique d'exécution std::execution facultative, ep (par défaut : std::execution ::seq)
Deux paires de ForwardIterators, fwd_deb1 / fwd_fin1 et fwd_deb2 / fwd_fin2, représentant les séquences cibles 1 et 2. Si l'on ne prévoit pas fwd_fin2, la longueur de la séquence 1 implique la longueur de la séquence 2.
Un prédicat binaire optionnel pred pour comparer si deux éléments sont égaux.

Si les deux séquences sont égales (avec les éléments dans le même ordre), la complexité est linéaire dans la distance entre it_deb1 et it_fin1. Sinon, jusqu'au quadratique $N^2$ : Effectue au plus $N^2$ comparaisons d'éléments jusqu'à ce que le résultat soit déterminé (où N est la distance entre it_deb1 et it_fin1).

Exemple 8

#include<iostream>
#include<algorithm>
#include<deque>
using namespace std;

void afficher(int a){ cout << a << " "; }

int main () {

    int t1[] = {13, 15, 17, 2, 5, 9};
    int t2[] = {9, 2, 17, 15, 5, 13};

    for_each(t1,t1+6, afficher);
    cout<<'\n';
    for_each(t2,t2+6, afficher);
    cout<<'\n';
    
    if(is_permutation(t1,t1+6,t2))
        cout << "t1 et t2 contiennent les mêmes éléments.\n";


    return 0;
}

Résultat

13 15 17 2 5 9 
9 2 17 15 5 13 
t1 et t2 contiennent les mêmes éléments.

Fonction search

L'algorithme search localise la séquence 2 dans la séquence 1. En d'autres termes, il renvoie le premier itérateur i de la séquence 1 tel que pour chaque entier non négatif n, *(i + n) est égal à *(fwd_deb2 + n), ou si vous fournissez un prédicat pred(*(i + n), *(fwd_deb2 + n)) est true.

L'algorithme search renvoie it_deb1 si la séquence 2 est vide ou fwd_deb2 si aucune sous-séquence n'est trouvée. Cette méthode est différente de find car elle localise une sous-séquence plutôt qu'un seul élément.

Syntaxe

ForwardIterator search([ep], fwd_deb1, fwd_fin1, fwd_deb2, fwd_fin2, [pred]);

Arguments

Une politique d'exécution std::execution facultative, ep (par défaut : std::execution ::seq)
Deux paires de ForwardIterators, fwd_deb1 / fwd_fin1 et fwd_deb2 / fwd_fin2, représentant les séquences cibles 1 et 2
Un prédicat binaire optionnel pred pour comparer si deux éléments sont égaux.

L'algorithme effectue le nombre suivant de comparaisons ou d'invocations de pred : $$distance(fwd\_deb1, fwd\_fin1) * distance(fwd\_deb2, fwd\_fin2)$$

Exemple 9

#include<iostream>
#include<algorithm>
#include<deque>
using namespace std;

bool compare (int i, int j) {return (i==j);}

int main () {

    int vals[] = {1,15,3,2,4,4,1,15,3,9,6};
    int objectif1[] = {3,2,4};

    deque<int> d1(vals,vals+11);   
    deque<int>::iterator it;

    it=search(d1.begin(),d1.end(),objectif1,objectif1+3);

    if(it!=d1.end()) 
        cout << "La position de la séquence {3,2,4} est " << (it-d1.begin());
    else 
        cout<< "La séquence {3,2,4} est introuvable";

    cout<<'\n';

    return 0;
}

Résultat

La position de la séquence {3,2,4} est 2

Fonction search_n

L'algorithme search_n localise une sous-séquence contenant des valeurs identiques et consécutives.

L'algorithme recherche le nombre de valeurs consécutives dans la séquence et renvoie un itérateur pointant sur la première valeur, ou renvoie fwd_end si une telle sous-séquence n'est pas trouvée. Cet algorithme est différent de adjacent_find car il localise une sous-séquence plutôt qu'un seul élément.

Syntaxe

ForwardIterator search_n([ep], fwd_debut, fwd_fin, count, val, [pred]);

Arguments

Une politique d'exécution std::execution facultative, ep (par défaut : std::execution ::seq)
Une paire de ForwardIterators, fwd_debut / fwd_fin, représentant la séquence cible
Une valeur entière count représentant le nombre de correspondances consécutives que vous voulez trouver
Une valeur représentant l'élément que vous voulez trouver (val).
Un prédicat binaire optionnel pred pour comparer si deux éléments sont égaux.

La complexité de cet algorithme est linéaire dans la distance entre fwd_debut et fwd_fin : Compare les éléments jusqu'à ce qu'une sous-séquence correspondante soit trouvée.

Exemple 10

#include<iostream>
#include<algorithm>
#include<deque>
using namespace std;

bool compare (int i, int j) {return (i==j);}

int main () {

    int vals[] = {1,15,3,2,4,4,1,15,4,4,4,5};

    deque<int> d1(vals,vals+12);   
    deque<int>::iterator it;

    it=search_n(d1.begin(),d1.end(),3, 4);

    if(it!=d1.end()) 
        cout << "La position des trois premiers 4 consécutifs est " << (it-d1.begin());

    cout<<'\n';

    return 0;
}

Résultat

La position des trois premiers 4 consécutifs est 8

Recherche dans une séquence et méthodes associées en C++ - Bibliothèque STL

Sommaire