std::ranges:: search_n

From cppreference.net

Definido en el encabezado `<algorithm>`
Firma de llamada
	(1)
template < std:: forward_iterator I, std:: sentinel_for < I > S, class T, class Pred = ranges:: equal_to , class Proj = std:: identity > requires std:: indirectly_comparable < I, const T * , Pred, Proj > constexpr ranges:: subrange < I > search_n ( I first, S last, std:: iter_difference_t < I > count, const T & value, Pred pred = { } , Proj proj = { } ) ;			(desde C++20) (hasta C++26)
template < std:: forward_iterator I, std:: sentinel_for < I > S, class Pred = ranges:: equal_to , class Proj = std:: identity , class T = std :: projected_value_t < I, Proj > > requires std:: indirectly_comparable < I, const T * , Pred, Proj > constexpr ranges:: subrange < I > search_n ( I first, S last, std:: iter_difference_t < I > count, const T & value, Pred pred = { } , Proj proj = { } ) ;			(desde C++26)
		(2)
template < ranges:: forward_range R, class T, class Pred = ranges:: equal_to , class Proj = std:: identity > requires std:: indirectly_comparable < ranges:: iterator_t < R > , const T * , Pred, Proj > constexpr ranges:: borrowed_subrange_t < R > search_n ( R && r, ranges:: range_difference_t < R > count, const T & value, Pred pred = { } , Proj proj = { } ) ;				(desde C++20) (hasta C++26)
template < ranges:: forward_range R, class Pred = ranges:: equal_to , class Proj = std:: identity , class T = std :: projected_value_t < ranges:: iterator_t < R > , Proj > > requires std:: indirectly_comparable < ranges:: iterator_t < R > , const T * , Pred, Proj > constexpr ranges:: borrowed_subrange_t < R > search_n ( R && r, ranges:: range_difference_t < R > count, const T & value, Pred pred = { } , Proj proj = { } ) ;				(desde C++26)

1) Busca en el rango

first

last

la primera secuencia de count elementos cuyos valores proyectados son iguales al value dado según el predicado binario pred .

2) Igual que (1) , pero utiliza r como el rango fuente, como si se usara ranges:: begin ( r ) como first y ranges:: end ( r ) como last .

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

first, last	-	el par iterador-centinela que define el rango de elementos a examinar (también conocido como haystack )
r	-	el rango de elementos a examinar (también conocido como haystack )
count	-	la longitud de la secuencia a buscar
value	-	el valor a buscar (también conocido como needle )
pred	-	el predicado binario que compara los elementos proyectados con value
proj	-	la proyección a aplicar a los elementos del rango a examinar

Valor de retorno

1) Devuelve un objeto std :: ranges:: subrange que contiene un par de iteradores en el rango

first

last

que designan la subsecuencia encontrada.

Si no se encuentra dicha subsecuencia, devuelve std :: ranges:: subrange { last, last } .

Si count <= 0 , devuelve std :: ranges:: subrange { first, first } .

2) Igual que (1) pero el tipo de retorno es ranges:: borrowed_subrange_t < R > .

Complejidad

Lineal: como máximo ranges:: distance ( first, last ) aplicaciones del predicado y la proyección.

Notas

Una implementación puede mejorar la eficiencia de la búsqueda en promedio si los iteradores modelan std:: random_access_iterator .

Macro de prueba de características	Valor	Std	Característica
`__cpp_lib_algorithm_default_value_type`	`202403`	(C++26)	Inicialización por lista para algoritmos

Implementación posible

struct search_n_fn
{
    template<std::forward_iterator I, std::sentinel_for<I> S,
             class Pred = ranges::equal_to, class Proj = std::identity,
             class T = std::projected_value_t<I, Proj>>
    requires std::indirectly_comparable<I, const T*, Pred, Proj>
    constexpr ranges::subrange<I>
        operator()(I first, S last, std::iter_difference_t<I> count,
                   const T& value, Pred pred = {}, Proj proj = {}) const
    {
        if (count <= 0)
            return {first, first};
        for (; first != last; ++first)
            if (std::invoke(pred, std::invoke(proj, *first), value))
            {
                I start = first;
                std::iter_difference_t<I> n{1};
                for (;;)
                {
                    if (n++ == count)
                        return {start, std::next(first)}; // encontrado
                    if (++first == last)
                        return {first, first}; // no encontrado
                    if (!std::invoke(pred, std::invoke(proj, *first), value))
                        break; // no igual al valor
                }
            }
        return {first, first};
    }
    template<ranges::forward_range R,
             class Pred = ranges::equal_to, class Proj = std::identity,
             class T = std::projected_value_t<ranges::iterator_t<R>, Proj>>
    requires std::indirectly_comparable<ranges::iterator_t<R>, const T*, Pred, Proj>
    constexpr ranges::borrowed_subrange_t<R>
        operator()(R&& r, ranges::range_difference_t<R> count,
                   const T& value, Pred pred = {}, Proj proj = {}) const
    {
        return (*this)(ranges::begin(r), ranges::end(r),
                       std::move(count), value,
                       std::move(pred), std::move(proj));
    }
};
inline constexpr search_n_fn search_n {};

Ejemplo

Ejecutar este código

#include <algorithm>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <string>
#include <vector>
int main()
{
    namespace ranges = std::ranges;
    static constexpr auto nums = {1, 2, 2, 3, 4, 1, 2, 2, 2, 1};
    constexpr int count{3};
    constexpr int value{2};
    typedef int count_t, value_t;
    constexpr auto result1 = ranges::search_n
    (
        nums.begin(), nums.end(), count, value
    );
    static_assert // encontrado
    (
        result1.size() == count &&
        std::distance(nums.begin(), result1.begin()) == 6 &&
        std::distance(nums.begin(), result1.end()) == 9
    );
    constexpr auto result2 = ranges::search_n(nums, count, value);
    static_assert // encontrado
    (
        result2.size() == count &&
        std::distance(nums.begin(), result2.begin()) == 6 &&
        std::distance(nums.begin(), result2.end()) == 9
    );
    constexpr auto result3 = ranges::search_n(nums, count, value_t{5});
    static_assert // no encontrado
    (
        result3.size() == 0 &&
        result3.begin() == result3.end() &&
        result3.end() == nums.end()
    );
    constexpr auto result4 = ranges::search_n(nums, count_t{0}, value_t{1});
    static_assert // no encontrado
    (
        result4.size() == 0 &&
        result4.begin() == result4.end() &&
        result4.end() == nums.begin()
    );
    constexpr char symbol{'B'};
    auto to_ascii = [](const int z) -> char { return 'A' + z - 1; };
    auto is_equ = [](const char x, const char y) { return x == y; };
    std::cout << "Encuentra una sub-secuencia " << std::string(count, symbol) << " en el ";
    std::ranges::transform(nums, std::ostream_iterator<char>(std::cout, ""), to_ascii);
    std::cout << '\n';
    auto result5 = ranges::search_n(nums, count, symbol, is_equ, to_ascii);
    if (not result5.empty())
        std::cout << "Encontrado en la posición "
                  << ranges::distance(nums.begin(), result5.begin()) << '\n';
    std::vector<std::complex<double>> nums2{{4, 2}, {4, 2}, {1, 3}};
    #ifdef __cpp_lib_algorithm_default_value_type
        auto it = ranges::search_n(nums2, 2, {4, 2});
    #else
        auto it = ranges::search_n(nums2, 2, std::complex<double>{4, 2});
    #endif
    assert(it.size() == 2);
}

Salida:

Encontrar una sub-secuencia BBB en ABBCDABBBA
Encontrado en la posición 6

Véase también

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::find ranges::find_if ranges::find_if_not (C++20) (C++20) (C++20)	encuentra el primer elemento que cumple criterios específicos (objeto función de algoritmo)
ranges::find_end (C++20)	encuentra la última secuencia de elementos en un rango determinado (objeto función de algoritmo)
ranges::find_first_of (C++20)	busca cualquiera de un conjunto de elementos (objeto función de algoritmo)
ranges::includes (C++20)	retorna true si una secuencia es subsecuencia de otra (objeto función de algoritmo)
ranges::mismatch (C++20)	encuentra la primera posición donde dos rangos difieren (objeto función de algoritmo)
ranges::search (C++20)	busca la primera ocurrencia de un rango de elementos (objeto función de algoritmo)
search_n	busca la primera ocurrencia de un número de copias consecutivas de un elemento en un rango (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