Algorithmes de recherche dans la 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, etc.).
Nous utilisons le mot algorithme dans ce cours pour faire référence à ce que fait la fonction.
1. Algorithmes 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 correspondante :
- find : recherche une valeur spécifique
val - find_if : recherche un élément vérifiant un prédicat
pred(retourne true) - find_if_not : recherche un élément ne vérifiant pas un prédicat
pred(retourne false)
Si l'algorithme ne trouve aucune correspondance, il renvoie it_fin.
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
- ep (optionnel) : politique d'exécution (std::execution::seq par défaut)
- it_debut, it_fin : une paire d'InputIterator représentant la séquence cible
- val : la valeur recherchée (pour find)
- pred : un prédicat unaire (pour 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 : Utilisation de find, find_if et find_if_not
#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;
// find : recherche de la valeur 4
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';
// Utilisation avec un deque
deque<int> d1(vals, vals + 11);
deque<int>::iterator it;
// find : recherche de la valeur 17 (inexistante)
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';
// find_if : recherche de la première valeur paire
it = find_if(d1.begin(), d1.end(), estpair);
if (it != d1.end())
cout << "La première valeur paire est " << *it;
cout << '\n';
// find_if_not : recherche de la première valeur non impaire = paire
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;
}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
2. Algorithme find_end
L'algorithme 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).
Il renvoie un itérateur vers le premier élément de cette dernière occurrence, 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
- ep (optionnel) : politique d'exécution
- fwd_deb1, fwd_fin1 : première séquence (où chercher)
- fwd_deb2, fwd_fin2 : deuxième séquence (ce qu'on cherche)
- pred (optionnel) : prédicat binaire pour comparer deux éléments
L'algorithme effectue au maximum :
distance(fwd_deb2, fwd_fin2) * (distance(fwd_deb1, fwd_fin1) - distance(fwd_deb2, fwd_fin2) + 1)
comparaisons ou invocations de pred.
Exemple 2 : Recherche de la dernière occurrence d'une sous-séquence
#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;
// Recherche de la dernière occurrence de {1,15,3}
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};
// Avec prédicat explicite
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;
}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 83. Algorithme find_first_of
L'algorithme 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.
Syntaxe
InputIterator find_first_of([ep], it_deb1, it_fin1, fwd_deb2, fwd_fin2, [pred]);L'algorithme effectue au maximum :
distance(it_deb1, it_fin1) * distance(fwd_deb2, fwd_fin2)
comparaisons ou invocations de pred.
Exemple 3 : Recherche du premier élément correspondant à une liste
#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;
// Premier élément de d1 qui est dans {1,15,3}
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;
}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é4. Algorithme adjacent_find
L'algorithme adjacent_find trouve la première répétition dans une séquence, c'est-à-dire la première occurrence où deux éléments adjacents sont égaux (ou vérifient un prédicat).
Si l'algorithme ne trouve pas un tel élément, il renvoie fwd_fin. Sinon, il renvoie un ForwardIterator pointant vers le premier élément de la paire.
Syntaxe
ForwardIterator adjacent_find([ep], fwd_debut, fwd_fin, [pred]);Exemple 4 : Recherche d'éléments adjacents
#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;
// Affichage du conteneur
for_each(d1.begin(), d1.end(), afficher);
cout << '\n';
// Recherche de deux éléments égaux consécutifs
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';
// Recherche de deux éléments où le premier est strictement inférieur au second
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;
}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
5. Algorithmes count et count_if
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.
- count : compte les occurrences d'une valeur spécifique
- count_if : compte les éléments vérifiant un prédicat
Syntaxe
DifferenceType count([ep], it_debut, it_fin, val);
DifferenceType count_if([ep], it_debut, it_fin, pred);DifferenceType est un type entier signé représentant le nombre d'occurrences.
Exemple 5 : Comptage d'éléments
#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);
// Affichage du conteneur
for_each(d1.begin(), d1.end(), afficher);
cout << '\n';
// Comptage de la valeur 9
int cpt = count(d1.begin(), d1.end(), 9);
cout << "La valeur 9 apparaît " << cpt << " fois dans la séquence";
cout << '\n';
// Comptage des valeurs négatives
cpt = count_if(d1.begin(), d1.end(), compare);
cout << "Le nombre de valeurs négatives est " << cpt;
cout << '\n';
return 0;
}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
6. Algorithme mismatch
L'algorithme mismatch trouve la première discordance dans deux séquences. Il retourne une paire d'itérateurs pointant vers les premiers éléments qui diffèrent.
Syntaxe
pair<Itr, Itr> mismatch([ep], it_deb1, it_fin1, it_deb2, [it_fin2], [pred]);Exemple 6 : Trouver la première différence entre deux séquences
#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);
// Affichage des deux séquences
for_each(d1.begin(), d1.end(), afficher);
cout << '\n';
for_each(d2.begin(), d2.end(), afficher);
cout << '\n';
// Recherche de la première différence
pair<deque<int>::iterator, deque<int>::iterator> it;
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';
// Recherche de la première position où l'élément de d1 est supérieur à celui de d2
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;
}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
7. Algorithme equal
L'algorithme equal détermine si deux séquences sont égales (mêmes éléments dans le même ordre).
Syntaxe
bool equal([ep], it_deb1, it_fin1, it_deb2, [it_fin2], [pred]);Exemple 7 : Tester l'égalité de deux séquences
#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);
// Affichage
for_each(d1.begin(), d1.end(), afficher);
cout << '\n';
// Test d'égalité avec t1 (identique)
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";
// Modification de t1
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;
}13 15 17 2 5 9 Le contenu des deux séquences est égal. Le contenu des deux séquences diffère.
8. Algorithme 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]);Si les deux séquences sont égales (même ordre), la complexité est linéaire. Sinon, jusqu'au quadratique O(N²) (au plus N² comparaisons).
Exemple 8 : Tester si deux séquences sont des permutations
#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};
// Affichage
for_each(t1, t1 + 6, afficher);
cout << '\n';
for_each(t2, t2 + 6, afficher);
cout << '\n';
// Test de permutation
if (is_permutation(t1, t1 + 6, t2))
cout << "t1 et t2 contiennent les mêmes éléments.\n";
return 0;
}13 15 17 2 5 9 9 2 17 15 5 13 t1 et t2 contiennent les mêmes éléments.
9. Algorithme search
L'algorithme search localise la première occurrence d'une sous-séquence (séquence 2) dans une séquence principale (séquence 1).
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]);Exemple 9 : Recherche d'une sous-séquence
#include <iostream>
#include <algorithm>
#include <deque>
using namespace std;
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;
// Recherche de la sous-séquence {3,2,4}
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;
}La position de la séquence {3,2,4} est 210. Algorithme search_n
L'algorithme search_n localise une sous-séquence contenant count valeurs identiques et consécutives.
Cet algorithme est différent de adjacent_find car il recherche une sous-séquence de longueur spécifiée plutôt qu'une simple paire.
Syntaxe
ForwardIterator search_n([ep], fwd_debut, fwd_fin, count, val, [pred]);Exemple 10 : Recherche d'une séquence de 3 valeurs identiques
#include <iostream>
#include <algorithm>
#include <deque>
using namespace std;
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;
// Recherche de 3 valeurs 4 consécutives
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;
}
13 15 17 2 5 9 9 2 17 15 5 13 t1 et t2 contiennent les mêmes éléments.
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.