std::ranges::search
| Défini dans l'en-tête <algorithm>
|
||
| Signature d'appel |
||
template< std::forward_iterator I1, std::sentinel_for<I1> S1,
std::forward_iterator I2, std::sentinel_for<I2> S2,
class Pred = ranges::equal_to,
class Proj1 = std::identity,
class Proj2 = std::identity >
requires std::indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
constexpr ranges::subrange<I1>
search( I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {} );
|
(1) | (depuis C++20) |
template< ranges::forward_range R1, ranges::forward_range R2,
class Pred = ranges::equal_to,
class Proj1 = std::identity,
class Proj2 = std::identity>
requires std::indirectly_comparable<ranges::iterator_t<R1>,
ranges::iterator_t<R2>, Pred, Proj1, Proj2>
constexpr ranges::borrowed_subrange_t<R1>
search( R1&& r1, R2&& r2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );
|
(2) | (depuis C++20) |
[first2, last2) dans l'intervalle [first1, last1). Les éléments sont comparés à l'aide du prédicat binaire pred après avoir été projetés avec proj2 et proj1, respectivement.r1 comme premier intervalle source et r2 comme second intervalle source, comme si en utilisant ranges::begin(r1) comme first1, ranges::end(r1) comme last1, ranges::begin(r2) comme first2, et ranges::end(r2) comme last2.Les entités de type fonction décrites sur cette page sont des objets fonctions d'algorithme (informellement appelés niebloids), c'est-à-dire :
- Les listes explicites d'arguments de modèle ne peuvent pas être spécifiées lors de l'appel de l'une d'elles.
- Aucune d'entre elles n'est visible par la recherche dépendante des arguments.
- Lorsque l'une d'elles est trouvée par la recherche non qualifiée normale comme le nom à gauche de l'opérateur d'appel de fonction, la recherche dépendante des arguments est inhibée.
Paramètres
| first1, last1 | - | la paire itérateur-sentinelle définissant la plage d'éléments à examiner (appelée haystack ) |
| first2, last2 | - | la paire itérateur-sentinelle définissant la plage d'éléments à rechercher (appelée needle ) |
| r1 | - | la plage d'éléments à examiner (appelée haystack ) |
| r2 | - | la plage d'éléments à rechercher (appelée needle ) |
| pred | - | prédicat binaire à appliquer aux éléments projetés |
| proj1 | - | projection à appliquer aux éléments de la première plage |
| proj2 | - | projection à appliquer aux éléments de la deuxième plage |
Valeur de retour
[
first2
,
last2
)
(appelée
needle
) dans la plage
[
first1
,
last1
)
(appelée
haystack
), après application des projections
proj1
et
proj2
aux éléments des deux séquences respectivement, suivie de l'application du prédicat binaire
pred
pour comparer les éléments projetés.
Si aucune occurrence n'est trouvée, ranges:: subrange { last1, last1 } est retourné.
Si la plage à rechercher (appelée needle ) est vide, c'est-à-dire first2 == last2 , alors ranges:: subrange { first1, first1 } est retourné.Complexité
Au plus
S * N
applications du prédicat correspondant et de chaque projection, où
(1)
S
=
ranges::
distance
(
first2, last2
)
et
N
=
ranges::
distance
(
first1, last1
)
;
(2)
S
=
ranges::
distance
(
r2
)
et
N
=
ranges::
distance
(
r1
)
.
Implémentation possible
struct search_fn { template<std::forward_iterator I1, std::sentinel_for<I1> S1, std::forward_iterator I2, std::sentinel_for<I2> S2, class Pred = ranges::equal_to, class Proj1 = std::identity, class Proj2 = std::identity> requires std::indirectly_comparable<I1, I2, Pred, Proj1, Proj2> constexpr ranges::subrange<I1> operator()(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) const { for (;; ++first1) { I1 it1 = first1; for (I2 it2 = first2;; ++it1, ++it2) { if (it2 == last2) return {first1, it1}; if (it1 == last1) return {it1, it1}; if (!std::invoke(pred, std::invoke(proj1, *it1), std::invoke(proj2, *it2))) break; } } } template<ranges::forward_range R1, ranges::forward_range R2, class Pred = ranges::equal_to, class Proj1 = std::identity, class Proj2 = std::identity> requires std::indirectly_comparable<ranges::iterator_t<R1>, ranges::iterator_t<R2>, Pred, Proj1, Proj2> constexpr ranges::borrowed_subrange_t<R1> operator()(R1&& r1, R2&& r2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) const { return (*this)(ranges::begin(r1), ranges::end(r1), ranges::begin(r2), ranges::end(r2), std::move(pred), std::move(proj1), std::move(proj2)); } }; inline constexpr search_fn search {}; |
Exemple
#include <algorithm> #include <cctype> #include <iostream> #include <iterator> #include <string_view> using namespace std::literals; void print(int id, const auto& haystack, const auto& needle, const auto& found) { std::cout << id << ") search(\"" << haystack << "\", \"" << needle << "\"); "; const auto first = std::distance(haystack.begin(), found.begin()); const auto last = std::distance(haystack.begin(), found.end()); if (found.empty()) std::cout << "not found;"; else { std::cout << "found: \""; for (const auto x : found) std::cout << x; std::cout << "\";"; } std::cout << " subrange: {" << first << ", " << last << "}\n"; } int main() { constexpr auto haystack {"abcd abcd"sv}; constexpr auto needle {"bcd"sv}; // la recherche utilise des paires d'itérateurs begin()/end() : constexpr auto found1 = std::ranges::search( haystack.begin(), haystack.end(), needle.begin(), needle.end()); print(1, haystack, needle, found1); // la recherche utilise les plages r1, r2 : constexpr auto found2 = std::ranges::search(haystack, needle); print(2, haystack, needle, found2); // la plage 'needle' est vide : constexpr auto none {""sv}; constexpr auto found3 = std::ranges::search(haystack, none); print(3, haystack, none, found3); // 'needle' ne sera pas trouvé : constexpr auto awl {"efg"sv}; constexpr auto found4 = std::ranges::search(haystack, awl); print(4, haystack, awl, found4); // la recherche utilise un comparateur personnalisé et des projections : constexpr auto bodkin {"234"sv}; auto found5 = std::ranges::search(haystack, bodkin, [](const int x, const int y) { return x == y; }, // pred [](const int x) { return std::toupper(x); }, // proj1 [](const int y) { return y + 'A' - '1'; }); // proj2 print(5, haystack, bodkin, found5); }
Sortie :
1) search("abcd abcd", "bcd"); found: "bcd"; subrange: {1, 4}
2) search("abcd abcd", "bcd"); found: "bcd"; subrange: {1, 4}
3) search("abcd abcd", ""); not found; subrange: {0, 0}
4) search("abcd abcd", "efg"); not found; subrange: {9, 9}
5) search("abcd abcd", "234"); found: "bcd"; subrange: {1, 4}
Voir aussi
(C++20) |
trouve les deux premiers éléments adjacents qui sont égaux (ou satisfont un prédicat donné) (objet fonction d'algorithme) |
(C++20)(C++20)(C++20) |
trouve le premier élément satisfaisant des critères spécifiques (objet fonction d'algorithme) |
(C++20) |
trouve la dernière séquence d'éléments dans un certain intervalle (objet fonction d'algorithme) |
(C++20) |
recherche l'un quelconque d'un ensemble d'éléments (objet fonction d'algorithme) |
(C++23)(C++23) |
vérifie si l'intervalle contient l'élément ou le sous-intervalle donné (objet fonction d'algorithme) |
(C++20) |
détermine si une séquence est une sous-séquence d'une autre (objet fonction d'algorithme) |
(C++20) |
trouve la première position où deux intervalles diffèrent (objet fonction d'algorithme) |
(C++20) |
recherche la première occurrence d'un nombre de copies consécutives d'un élément dans un intervalle (objet fonction d'algorithme) |
| recherche la première occurrence d'un intervalle d'éléments (fonction template) |