std::ranges:: find_end

From cppreference.net

Definido en el encabezado `<algorithm>`
Firma de llamada
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)	(desde 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)	(desde C++20)

1) Busca la última ocurrencia de la secuencia

first2

last2

en el rango

first1

last1

, después de la proyección con proj1 y proj2 respectivamente. Los elementos proyectados se comparan usando el predicado binario pred .

2) Igual que (1) , pero utiliza r1 como el primer rango fuente y r2 como el segundo rango fuente, como si se usara ranges:: begin ( r1 ) como first1 , ranges:: end ( r1 ) como last1 , ranges:: begin ( r2 ) como first2 , y ranges:: end ( r2 ) como last2 .

Las entidades similares a funciones descritas en esta página son algorithm function objects (conocidas informalmente como niebloids ), es decir:

No se pueden especificar listas de argumentos de plantilla explícitas al llamar a cualquiera de ellos.
Ninguno de ellos es visible para la búsqueda dependiente de argumento .
Cuando cualquiera de ellos es encontrado mediante la búsqueda no calificada normal como el nombre a la izquierda del operador de llamada a función, la búsqueda dependiente de argumento queda inhibida.

Contenidos

Parámetros

first1, last1	-	el par iterador-centinela que define el rango de elementos a examinar (también conocido como haystack )
first2, last2	-	el par iterador-centinela que define el rango de elementos a buscar (también conocido como needle )
r1	-	el rango de elementos a examinar (también conocido como haystack )
r2	-	el rango de elementos a buscar (también conocido como needle )
pred	-	predicado binario para comparar los elementos
proj1	-	proyección a aplicar a los elementos en el primer rango
proj2	-	proyección a aplicar a los elementos en el segundo rango

Valor de retorno

1) ranges:: subrange < I1 > { } valor inicializado con la expresión { i, i + ( i == last1 ? 0 : ranges:: distance ( first2, last2 ) ) } que denota la última ocurrencia de la secuencia

first2

last2

en el rango

first1

last1

(después de las proyecciones con proj1 y proj2 ). Si

first2

last2

está vacío o si no se encuentra dicha secuencia, el valor de retorno se inicializa efectivamente con { last1, last1 } .

2) Igual que (1) , excepto que el tipo de retorno es ranges:: borrowed_subrange_t < R1 > .

Complejidad

Como máximo $S\cdot(N-S+1)$ aplicaciones del predicado correspondiente y cada proyección, donde $\scriptsize S$ $S$ es ranges:: distance ( first2, last2 ) y $\scriptsize N$ $N$ es ranges:: distance ( first1, last1 ) para (1) , o $\scriptsize S$ $S$ es ranges:: distance ( r2 ) y $\scriptsize N$ $N$ es ranges:: distance ( r1 ) para (2) .

Notas

Una implementación puede mejorar la eficiencia de la búsqueda si los iteradores de entrada modelan std:: bidirectional_iterator buscando desde el final hacia el principio. Modelar el std:: random_access_iterator puede mejorar la velocidad de comparación. Sin embargo, todo esto no cambia la complejidad teórica del peor caso.

Implementación posible

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 {};

Ejemplo

Ejecutar este código

#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 << "En \"";
    for (const auto c : haystack)
        std::cout << c;
    std::cout << "\" se encontró \"";
    for (const auto c : needle)
        std::cout << c;
    std::cout << "\" en la posición [" << 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) { // utiliza un predicado binario
            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); }); // proyecta el segundo rango
    print(secret, found4);
    static_assert(std::ranges::find_end(secret, "PASS"sv).empty()); // => no encontrado
}

Salida:

En "password password word..." se encontró "password" en la posición [9..17)
             ^^^^^^^^
En "password password word..." se encontró "word" en la posición [18..22)
                      ^^^^
En "password password word..." se encontró "ord" en la posición [19..22)
                       ^^^
En "password password word..." se encontró "sword" en la posición [12..17)
                ^^^^^

Véase también

ranges::find_last ranges::find_last_if ranges::find_last_if_not (C++23) (C++23) (C++23)	encuentra el último elemento que satisface criterios específicos (objeto función de algoritmo)
ranges::find ranges::find_if ranges::find_if_not (C++20) (C++20) (C++20)	encuentra el primer elemento que satisface criterios específicos (objeto función de algoritmo)
ranges::find_first_of (C++20)	busca cualquiera de un conjunto de elementos (objeto función de algoritmo)
ranges::adjacent_find (C++20)	encuentra los dos primeros elementos adyacentes que son iguales (o satisfacen un predicado dado) (objeto función de algoritmo)
ranges::search (C++20)	busca la primera ocurrencia de un rango de elementos (objeto función de algoritmo)
ranges::search_n (C++20)	busca la primera ocurrencia de un número de copias consecutivas de un elemento en un rango (objeto función de algoritmo)
find_end	encuentra la última secuencia de elementos en un rango determinado (plantilla de función)

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

Contenidos

Parámetros

Valor de retorno

Complejidad

Notas

Implementación posible

Ejemplo

Véase también