std:: search_n

From cppreference.net

Definido en el encabezado `<algorithm>`
	(1)
template < class ForwardIt, class Size, class T > ForwardIt search_n ( ForwardIt first, ForwardIt last, Size count, const T & value ) ;			(constexpr desde C++20) (hasta C++26)
template < class ForwardIt, class Size, class T = typename std:: iterator_traits < ForwardIt > :: value_type > constexpr ForwardIt search_n ( ForwardIt first, ForwardIt last, Size count, const T & value ) ;			(desde C++26)
		(2)
template < class ExecutionPolicy, class ForwardIt, class Size, class T > ForwardIt search_n ( ExecutionPolicy && policy, ForwardIt first, ForwardIt last, Size count, const T & value ) ;				(desde C++17) (hasta C++26)
template < class ExecutionPolicy, class ForwardIt, class Size, class T = typename std:: iterator_traits < ForwardIt > :: value_type > ForwardIt search_n ( ExecutionPolicy && policy, ForwardIt first, ForwardIt last, Size count, const T & value ) ;				(desde C++26)
			(3)
template < class ForwardIt, class Size, class T, class BinaryPred > ForwardIt search_n ( ForwardIt first, ForwardIt last, Size count, const T & value, BinaryPred p ) ;					(constexpr desde C++20) (hasta C++26)
template < class ForwardIt, class Size, class T = typename std:: iterator_traits < ForwardIt > :: value_type , class BinaryPred > constexpr ForwardIt search_n ( ForwardIt first, ForwardIt last, Size count, const T & value, BinaryPred p ) ;					(desde C++26)
				(4)
template < class ExecutionPolicy, class ForwardIt, class Size, class T, class BinaryPred > ForwardIt search_n ( ExecutionPolicy && policy, ForwardIt first, ForwardIt last, Size count, const T & value, BinaryPred p ) ;						(desde C++17) (hasta C++26)
template < class ExecutionPolicy, class ForwardIt, class Size, class T = typename std:: iterator_traits < ForwardIt > :: value_type , class BinaryPred > ForwardIt search_n ( ExecutionPolicy && policy, ForwardIt first, ForwardIt last, Size count, const T & value, BinaryPred p ) ;						(desde C++26)

Busca en el rango [ first , last ) la primera secuencia de count elementos idénticos, cada uno igual al value dado.

1) Los elementos se comparan utilizando operator == .

3) Los elementos se comparan utilizando el predicado binario dado p .

2,4) Igual que (1,3) , pero ejecutado de acuerdo con policy .

Estas sobrecargas participan en la resolución de sobrecarga solo si se satisfacen todas las siguientes condiciones:

std:: is_execution_policy_v < std:: decay_t < ExecutionPolicy >> es true .	(until C++20)
std:: is_execution_policy_v < std:: remove_cvref_t < ExecutionPolicy >> es true .	(since C++20)

Contenidos

Parámetros

first, last	-	el par de iteradores que define el rango de elementos a examinar
count	-	la longitud de la secuencia a buscar
value	-	el valor de los elementos a buscar
policy	-	la política de ejecución a utilizar
p	-	predicado binario que retorna true si los elementos deben tratarse como iguales. La firma de la función predicado debe ser equivalente a la siguiente: bool pred ( const Type1 & a, const Type2 & b ) ; Aunque la firma no necesita tener const & , la función no debe modificar los objetos pasados a ella y debe poder aceptar todos los valores de tipo (posiblemente const) `Type1` y `Type2` independientemente de la categoría de valor (por lo tanto, Type1 & no está permitido , ni tampoco Type1 a menos que para `Type1` un movimiento sea equivalente a una copia (desde C++11) ). El tipo Type1 debe ser tal que un objeto de tipo ForwardIt pueda ser desreferenciado y luego convertido implícitamente a Type1 . El tipo Type2 debe ser tal que un objeto de tipo T pueda convertirse implícitamente a Type2 .
Requisitos de tipo
- `ForwardIt` debe cumplir con los requisitos de LegacyForwardIterator .
- `BinaryPred` debe cumplir con los requisitos de BinaryPredicate .
- `Size` debe ser convertible a un tipo integral .

Valor de retorno

Si count es positivo, retorna un iterador al inicio de la primera secuencia encontrada en el rango [ first , last ) . Cada iterador it en la secuencia debe satisfacer la siguiente condición:

1,2) * it == value es true .

3,4) p ( * it, value ) ! = false es true .

Si no se encuentra dicha secuencia, last es retornado.

Si count es cero o negativo, first es devuelto.

Complejidad

Dado $\scriptsize N$ $N$ como std:: distance ( first, last ) :

1,2) Como máximo

N

comparaciones usando operator == .

3,4) Como máximo

N

aplicaciones del predicado p .

Excepciones

Las sobrecargas con un parámetro de plantilla llamado ExecutionPolicy reportan errores de la siguiente manera:

Si la ejecución de una función invocada como parte del algoritmo lanza una excepción y ExecutionPolicy es uno de los standard policies , std::terminate es llamado. Para cualquier otro ExecutionPolicy , el comportamiento está definido por la implementación.
Si el algoritmo falla al asignar memoria, std::bad_alloc es lanzado.

Implementación posible

search_n (1)

template<class ForwardIt, class Size,
         class T = typename std::iterator_traits<ForwardIt>::value_type>
ForwardIt search_n(ForwardIt first, ForwardIt last, Size count, const T& value)
{
    if (count <= 0)
        return first;
    for (; first != last; ++first)
    {
        if (!(*first == value))
            continue;
        ForwardIt candidate = first;
        for (Size cur_count = 1; true; ++cur_count)
        {
            if (cur_count >= count)
                return candidate; // éxito
            ++first;
            if (first == last)
                return last; // lista agotada
            if (!(*first == value))
                break; // muy pocos consecutivos
        }
    }
    return last;
}

search_n (3)

template<class ForwardIt, class Size,
         class T = typename std::iterator_traits<ForwardIt>::value_type,
         class BinaryPred>
ForwardIt search_n(ForwardIt first, ForwardIt last, Size count, const T& value,
                   BinaryPred p)
{
    if (count <= 0)
        return first;
    for (; first != last; ++first)
    {
        if (!p(*first, value))
            continue;
        ForwardIt candidate = first;
        for (Size cur_count = 1; true; ++cur_count)
        {
            if (cur_count >= count)
                return candidate; // éxito
            ++first;
            if (first == last)
                return last; // lista agotada
            if (!p(*first, value))
                break; // muy pocos consecutivos
        }
    }
    return last;
}

Notas

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

Ejemplo

Ejecutar este código

#include <algorithm>
#include <cassert>
#include <complex>
#include <iostream>
#include <iterator>
#include <vector>
template<class Container, class Size, class T>
constexpr bool consecutive_values(const Container& c, Size count, const T& v)
{
    return std::search_n(std::begin(c), std::end(c), count, v) != std::end(c);
}
int main()
{
    constexpr char sequence[] = ".0_0.000.0_0.";
    static_assert(consecutive_values(sequence, 3, '0'));
    for (int n : {4, 3, 2})
        std::cout << std::boolalpha
                  << "Tiene " << n << " ceros consecutivos: "
                  << consecutive_values(sequence, n, '0') << '\n';
    std::vector<std::complex<double>> nums{{4, 2}, {4, 2}, {1, 3}};
    #ifdef __cpp_lib_algorithm_default_value_type
        auto it = std::search_n(nums.cbegin(), nums.cend(), 2, {4, 2});
    #else
        auto it = std::search_n(nums.cbegin(), nums.cend(), 2, std::complex<double>{4, 2});
    #endif
    assert(it == nums.begin());
}

Salida:

Tiene 4 ceros consecutivos: false
Tiene 3 ceros consecutivos: true
Tiene 2 ceros consecutivos: true

Informes de defectos

Los siguientes informes de defectos que modifican el comportamiento se aplicaron retroactivamente a los estándares de C++ publicados anteriormente.

DR	Aplicado a	Comportamiento publicado	Comportamiento correcto
LWG 283	C++98	`T` se requería que fuera EqualityComparable , pero el tipo de valor de `InputIt` no siempre es `T`	se eliminó el requisito
LWG 426	C++98	el límite superior de complejidad era `N·count` , es negativo si count es negativo	el límite superior es 0 si count es no positivo
LWG 714	C++98	si count > 0 , el límite superior de complejidad era `N·count` , pero en el peor caso el número de comparaciones/operaciones es siempre `N`	se cambió el límite superior a `N` en este caso
LWG 2150	C++98	la condición de "ocurrencia de secuencia" era incorrecta	corregida

Véase también

find_end	encuentra la última secuencia de elementos en un rango determinado (plantilla de función)
find find_if find_if_not (C++11)	encuentra el primer elemento que satisface criterios específicos (plantilla de función)
search	busca la primera ocurrencia de un rango de elementos (plantilla de función)
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)

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