std::ranges::find_end
Depuis fr.cppreference.net
| 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>
find_end( 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>
find_end( R1&& r1, R2&& r2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {} );
|
(2) | (depuis C++20) |
template< /*execution-policy*/ Ep,
std::random_access_iterator I1, std::sized_sentinel_for<I1> S1,
std::random_access_iterator I2, std::sized_sentinel_for<I2> S2,
class Pred = ranges::equal_to,
class Proj1 = identity, class Proj2 = identity>
requires std::indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
ranges::subrange<I1> find_end( Ep&& policy, I1 first1, S1 last1,
I2 first2, S2 last2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {} );
|
(3) | (depuis C++26) |
template< /*execution-policy*/ Ep,
/*sized-random-access-range*/ R1,
/*sized-random-access-range*/ R2,
class Pred = ranges::equal_to,
class Proj1 = identity, class Proj2 = identity>
requires std::indirectly_comparable<ranges::iterator_t<R1>,
ranges::iterator_t<R2>,
Pred, Proj1, Proj2>
ranges::borrowed_subrange_t<R1>
find_end( Ep&& policy, R1&& r1, R2&& r2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {} );
|
(4) | (depuis C++26) |
Pour la définition de /*execution-policy*/, voir cette page ; pour la définition de /*sized-random-access-range*/, voir cette page.
Recherche la dernière occurrence de la plage cible dans la plage source. Les éléments (projetés respectivement par proj1 et proj2) sont comparés à l'aide du prédicat binaire pred.
1) La plage source est
[first1, last1), et la plage cible est [first2, last2).2) La plage source est
r1, et la plage cible est r2.3,4) Identique à (1,2), mais exécuté selon
policy.Les entités de type fonction décrites sur cette page sont des objets fonction d'algorithme (informellement appelés niebloids), c'est-à-dire :
- Les listes explicites d'arguments de template ne peuvent pas être spécifiées lors de l'appel de l'une d'elles.
- Aucune d'elles n'est visible par la recherche dépendante des arguments.
- Lorsque l'une d'elles est trouvée par une recherche non qualifiée normale comme 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 source plage |
| first2, last2 | - | la paire itérateur-sentinelle définissant la cible plage |
| r1 | - | la plage source |
| r2 | - | la plage cible |
| pred | - | le prédicat à appliquer aux éléments (projetés) |
| proj1 | - | la projection à appliquer aux éléments de la plage source |
| proj2 | - | la projection à appliquer aux éléments de la plage cible |
| policy | - | la politique d'exécution à utiliser |
Valeur de retour
Une sous-plage correspondant à la dernière occurrence de la plage cible dans la plage source.
Si la plage cible est vide ou qu'elle n'apparaît pas dans la plage source, une plage vide est retournée.
Complexité
Étant donné N1 comme ranges::distance(first1, last1) ou ranges::distance(r1), et N2 comme ranges::distance(first2, last2) ou ranges::distance(r2) :
1,2) Au plus N2⋅(N1-N2+1) applications de
pred et proj.3,4) 𝓞(N2⋅(N1-N2+1)) applications de
pred et proj.Exceptions
3,4) Durant le processus d'exécution :
- Si les ressources mémoire temporaires nécessaires à la parallélisation ne sont pas disponibles, std::bad_alloc est levée.
- Si une exception non interceptée est levée lors de l'accès à des objets via un argument d'algorithme, le comportement est déterminé par la politique d'exécution (pour les politiques standard, std::terminate est invoqué).
Notes
Une implémentation peut améliorer l'efficacité de la recherche si les types d'itérateurs modélisent bidirectional_iterator en recherchant de la fin vers le début. La modélisation de random_access_iterator peut améliorer la vitesse de comparaison. Tout cela ne change cependant pas la complexité théorique du pire cas.
Implémentation possible
struct find_end_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
{
if (first2 == last2)
{
auto last_it = ranges::next(first1, last1);
return {last_it, last_it};
}
auto result = ranges::search(std::move(first1), last1,
first2, last2, pred, proj1, proj2);
if (result.empty())
return result;
for (;;)
{
auto new_result = ranges::search(std::next(result.begin()), last1,
first2, last2, pred, proj1, proj2);
if (new_result.empty())
return result;
else
result = std::move(new_result);
}
}
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::next(ranges::begin(r1), ranges::end(r1)),
ranges::begin(r2),
ranges::next(ranges::begin(r2), ranges::end(r2)),
std::move(pred), std::move(proj1), std::move(proj2));
}
};
inline constexpr find_end_fn find_end{};
|
Exemple
Exécuter ce code
#include <algorithm>
#include <array>
#include <cctype>
#include <iostream>
#include <ranges>
#include <string_view>
void print(const auto haystack, const auto needle)
{
const auto pos = std::distance(haystack.begin(), needle.begin());
std::cout << "In \"";
for (const auto c : haystack)
std::cout << c;
std::cout << "\" found \"";
for (const auto c : needle)
std::cout << c;
std::cout << "\" at position [" << pos << ".." << pos + needle.size() << ")\n"
<< std::string(4 + pos, ' ') << std::string(needle.size(), '^') << '\n';
}
int main()
{
using namespace std::literals;
using std::ranges::find_end;
constexpr auto secret{"password password word..."sv};
constexpr auto wanted{"password"sv};
constexpr auto found1 = find_end(secret.cbegin(), secret.cend(),
wanted.cbegin(), wanted.cend());
print(secret, found1);
constexpr auto found2 = find_end(secret, "word"sv);
print(secret, found2);
const auto found3 = find_end(secret, "ORD"sv,
[](const char x, const char y)
{ // uses a binary predicate
return std::tolower(x) == std::tolower(y);
});
print(secret, found3);
const auto found4 = find_end(secret, "SWORD"sv, {}, {},
[](char c) { return std::tolower(c); }); // projects the 2nd range
print(secret, found4);
static_assert(find_end(secret, "PASS"sv).empty()); // => not found
}
Sortie :
In "password password word..." found "password" at position [9..17)
^^^^^^^^
In "password password word..." found "word" at position [18..22)
^^^^
In "password password word..." found "ord" at position [19..22)
^^^
In "password password word..." found "sword" at position [12..17)
^^^^^
Voir aussi
| trouve la dernière séquence d'éléments dans une certaine plage (modèle de fonction) | |
(C++23)(C++23)(C++23) |
trouve le dernier élément satisfaisant des critères spécifiques (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) |
recherche n'importe lequel d'un ensemble d'éléments (objet fonction d'algorithme) |
(C++20) |
trouve les deux premiers éléments adjacents qui sont égaux (ou satisfont un prédicat donné) (objet fonction d'algorithme) |
(C++20) |
recherche la première occurrence d'une plage d'éléments (objet fonction d'algorithme) |
(C++20) |
recherche la première occurrence d'un nombre de copies consécutives d'un élément dans une plage (objet fonction d'algorithme) |