std::ranges:: find_end

From 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)

1) Recherche la dernière occurrence de la séquence

first2

last2

dans la plage

first1

last1

, après projection avec proj1 et proj2 respectivement. Les éléments projetés sont comparés en utilisant le prédicat binaire pred .

2) Identique à (1) , mais utilise r1 comme première plage source et r2 comme seconde plage source, comme si on utilisait 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 algorithm function objects (informellement appelées niebloids ), c'est-à-dire :

Les listes d'arguments de modèle explicites ne peuvent pas être spécifiées lors de l'appel de l'une d'entre elles.
Aucune d'entre elles n'est visible pour la recherche dépendante des arguments .
Lorsque l'une d'entre elles est trouvée par la 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.

Table des matières

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 pour comparer les éléments
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

1) ranges:: subrange < I1 > { } valeur initialisée avec l'expression { i, i + ( i == last1 ? 0 : ranges:: distance ( first2, last2 ) ) } qui désigne la dernière occurrence de la séquence

first2

last2

dans la plage

first1

last1

(après projections avec proj1 et proj2 ). Si

first2

last2

est vide ou si aucune telle séquence n'est trouvée, la valeur de retour est effectivement initialisée avec { last1, last1 } .

2) Identique à (1) , sauf que le type de retour est ranges:: borrowed_subrange_t < R1 > .

Complexité

Au plus $S\cdot(N-S+1)$ applications du prédicat correspondant et de chaque projection, où $\scriptsize S$ $S$ est ranges:: distance ( first2, last2 ) et $\scriptsize N$ $N$ est ranges:: distance ( first1, last1 ) pour (1) , ou $\scriptsize S$ $S$ est ranges:: distance ( r2 ) et $\scriptsize N$ $N$ est ranges:: distance ( r1 ) pour (2) .

Notes

Une implémentation peut améliorer l'efficacité de la recherche si les itérateurs d'entrée modélisent std:: bidirectional_iterator en cherchant depuis la fin vers le début. Modéliser le std:: 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::end(r1),
                       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 << "Dans \"";
    for (const auto c : haystack)
        std::cout << c;
    std::cout << "\" trouvé \"";
    for (const auto c : needle)
        std::cout << c;
    std::cout << "\" à la position [" << pos << ".." << pos + needle.size() << ")\n"
        << std::string(4 + pos, ' ') << std::string(needle.size(), '^') << '\n';
}
int main()
{
    using namespace std::literals;
    constexpr auto secret{"password password word..."sv};
    constexpr auto wanted{"password"sv};
    constexpr auto found1 = std::ranges::find_end(
        secret.cbegin(), secret.cend(), wanted.cbegin(), wanted.cend());
    print(secret, found1);
    constexpr auto found2 = std::ranges::find_end(secret, "word"sv);
    print(secret, found2);
    const auto found3 = std::ranges::find_end(secret, "ORD"sv,
        [](const char x, const char y) { // utilise un prédicat binaire
            return std::tolower(x) == std::tolower(y);
        });
    print(secret, found3);
    const auto found4 = std::ranges::find_end(secret, "SWORD"sv, {}, {},
        [](char c) { return std::tolower(c); }); // projette la deuxième plage
    print(secret, found4);
    static_assert(std::ranges::find_end(secret, "PASS"sv).empty()); // => non trouvé
}

Sortie :

Dans "password password word..." trouvé "password" à la position [9..17)
             ^^^^^^^^
Dans "password password word..." trouvé "word" à la position [18..22)
                      ^^^^
Dans "password password word..." trouvé "ord" à la position [19..22)
                       ^^^
Dans "password password word..." trouvé "sword" à la position [12..17)
                ^^^^^

Voir aussi

ranges::find_last ranges::find_last_if ranges::find_last_if_not (C++23) (C++23) (C++23)	trouve le dernier élément satisfaisant des critères spécifiques (objet fonction algorithme)
ranges::find ranges::find_if ranges::find_if_not (C++20) (C++20) (C++20)	trouve le premier élément satisfaisant des critères spécifiques (objet fonction algorithme)
ranges::find_first_of (C++20)	recherche l'un quelconque d'un ensemble d'éléments (objet fonction algorithme)
ranges::adjacent_find (C++20)	trouve les deux premiers éléments adjacents qui sont égaux (ou satisfont un prédicat donné) (objet fonction algorithme)
ranges::search (C++20)	recherche la première occurrence d'une plage d'éléments (objet fonction algorithme)
ranges::search_n (C++20)	recherche la première occurrence d'un nombre de copies consécutives d'un élément dans une plage (objet fonction algorithme)
find_end	trouve la dernière séquence d'éléments dans une certaine plage (modèle de fonction)

Compiler support
Freestanding and hosted
Language
Standard library
Standard library headers
Named requirements
Feature test macros (C++20)
Language support library
Concepts library (C++20)
Diagnostics library
Memory management library
Metaprogramming library (C++11)
General utilities library
Containers library
Iterators library
Ranges library (C++20)
Algorithms library
Strings library
Text processing library
Numerics library
Date and time library
Input/output library
Filesystem library (C++17)
Concurrency support library (C++11)
Execution control library (C++26)
Technical specifications
Symbols index
External libraries

cppreference.net

Namespaces

Variants

std::ranges:: find_end

Table des matières

Paramètres

Valeur de retour

Complexité

Notes

Implémentation possible

Exemple

Voir aussi