std::ranges::search_n - cppreference.com

De cppreference.com

Definido en el archivo de encabezado `<algorithm>`

Signatura de la llamada
`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 = {} );`	(1)	(desde C++20)
`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 = {} );`	(2)	(desde C++20)

1) Busca en el rango [first, last) la first secuencia de count elementos cuyos valores proyectados sean cada uno iguales al valor dado value de acuerdo con el predicado binario pred.

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

Las entidades similares a funciones descritas en esta página son niebloids, es decir:

Las listas de argumentos de plantilla explícitas no se pueden especificar al llamar a cualquiera de ellas.
Ninguna de ellas es visible para la búsqueda dependiente de argumentos.
Cuando alguna de ellas se encuentra mediante la búsqueda normal no calificada como el nombre a la izquierda del operador de llamada a función, se inhibe la búsqueda dependiente de argumentos.

En la práctica, pueden implementarse como objetos función o con extensiones de compilador especiales.

Parámetros

first, last	-	El rango de elementos a examinar (alias pajar).
r	-	El rango de elementos a examinar (alias pajar).
count	-	La longitud de la secuencia a buscar.
value	-	El valor a buscar (alias aguja).
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 el objeto std::ranges::subrange que contiene un par de iteradores en el rango [first, last) que designan la subsecuencia encontrada. Si no se encuentra tal 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: a lo sumo 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.

Posible implementación

struct search_n_fn
{
  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>
        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)}; // se encontró
                if (++first == last)
                  return {first, first}; // no se encontró
                if (!std::invoke(pred, std::invoke(proj, *first), value))
                  break; // not equ to value
              }
            }
          }
          return {first, first};
        }

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

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <string>

int main()
{
    static constexpr auto nums = {1, 2, 2, 3, 4, 1, 2, 2, 2, 1};
    constexpr int count{ 3 };
    constexpr int value{ 2 };

    constexpr auto result1 = std::ranges::search_n(
        nums.begin(), nums.end(), count, value
    );
    static_assert( // se encontró
        result1.size() == count &&
        std::distance(nums.begin(), result1.begin()) == 6 &&
        std::distance(nums.begin(), result1.end()) == 9
    );

    constexpr auto result2 = std::ranges::search_n(nums, count, value);
    static_assert( // se encontró
        result2.size() == count &&
        std::distance(nums.begin(), result2.begin()) == 6 &&
        std::distance(nums.begin(), result2.end()) == 9
    );

    constexpr auto result3 = std::ranges::search_n(nums, count, /* valor */ 5);
    static_assert( // no se encontró
        result3.size() == 0 &&
        result3.begin() == result3.end() &&
        result3.end() == nums.end()
    );

    constexpr auto result4 = std::ranges::search_n(nums, /* cuenta */ 0, /* valor */ 1);
    static_assert( // no se encontró
        result4.size() == 0 &&
        result4.begin() == result4.end() &&
        result4.end() == nums.begin()
    );

    constexpr char symbol{'B'};
    std::cout << std::boolalpha << "Encontrar una subsecuencia: "
              << std::quoted(std::string(count, symbol)) << '\n';

    auto result5 = std::ranges::search_n(nums, count, symbol,
        [](const char x, const char y) { // predicado binario
            const bool o{ x == y };
            std::cout << "bin_op(" << x << ", " << y << ") == " << o << "\n";
            return o;
        },
        [](const int z) { return 'A' + z - 1; } // proyecta nums -> ASCII
    );

    std::cout << "Se encontró: " << !result5.empty() << '\n';
}

Salida:

Encontrar una subsecuencia: "BBB"
bin_op(A, B) == false
bin_op(B, B) == true
bin_op(B, B) == true
bin_op(C, B) == false
bin_op(D, B) == false
bin_op(A, B) == false
bin_op(B, B) == true
bin_op(B, B) == true
bin_op(B, B) == true
Se encontró: true

Véase también

ranges::adjacent_find (C++20)	Encuentra dos primeros elementos contiguos idénticos (o que satisfagan un predicado dado). (niebloid) [editar]
ranges::findranges::find_ifranges::find_if_not (C++20)(C++20)(C++20)	Encuentra el primer elemento que satisfaga un criterio específico. (niebloid) [editar]
ranges::find_end (C++20)	Encuentra la última secuencia de elementos en un cierto rango. (niebloid) [editar]
ranges::find_first_of (C++20)	Busca por cualquiera de un conjunto de elementos. (niebloid) [editar]
ranges::includes (C++20)	Devuelve `true` si una secuencia es una subsecuencia de otra. (niebloid) [editar]
ranges::mismatch (C++20)	Encuentra la primera posición donde dos rangos difieren. (niebloid) [editar]
ranges::search (C++20)	Busca una subsecuencia de elementos en un rango. (niebloid) [editar]
search_n	Busca un número de copias consecutivas de un elemento en un rango. (plantilla de función) [editar]