std:: search_n

From cppreference.net

Défini dans l'en-tête `<algorithm>`
	(1)
template < class ForwardIt, class Size, class T > ForwardIt search_n ( ForwardIt first, ForwardIt last, Size count, const T & value ) ;			(constexpr depuis C++20) (jusqu'à 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 ) ;			(depuis 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 ) ;				(depuis C++17) (jusqu'à 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 ) ;				(depuis 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 depuis C++20) (jusqu'à 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 ) ;					(depuis 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 ) ;						(depuis C++17) (jusqu'à 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 ) ;						(depuis C++26)

Recherche dans la plage [ first , last ) la première séquence de count éléments identiques, chacun égal à la value donnée.

1) Les éléments sont comparés en utilisant operator == .

3) Les éléments sont comparés en utilisant le prédicat binaire donné p .

2,4) Identique à (1,3) , mais exécuté selon la policy .

Ces surcharges participent à la résolution de surcharge seulement si toutes les conditions suivantes sont satisfaites :

std:: is_execution_policy_v < std:: decay_t < ExecutionPolicy >> est true .	(jusqu'à C++20)
std:: is_execution_policy_v < std:: remove_cvref_t < ExecutionPolicy >> est true .	(depuis C++20)

Table des matières

Paramètres

first, last	-	la paire d'itérateurs définissant la plage des éléments à examiner
count	-	la longueur de la séquence à rechercher
value	-	la valeur des éléments à rechercher
policy	-	la politique d'exécution à utiliser
p	-	prédicat binaire qui renvoie true si les éléments doivent être traités comme égaux. La signature de la fonction de prédicat doit être équivalente à ce qui suit : bool pred ( const Type1 & a, const Type2 & b ) ; Bien que la signature n'ait pas besoin d'avoir const & , la fonction ne doit pas modifier les objets qui lui sont passés et doit pouvoir accepter toutes les valeurs du type (éventuellement const) `Type1` et `Type2` indépendamment de la catégorie de valeur (ainsi, Type1 & n'est pas autorisé , pas plus que Type1 sauf si pour `Type1` un déplacement équivaut à une copie (depuis C++11) ). Le type Type1 doit être tel qu'un objet de type ForwardIt puisse être déréférencé puis implicitement converti en Type1 . Le type Type2 doit être tel qu'un objet de type T puisse être implicitement converti en Type2 .
Exigences de type
- `ForwardIt` doit satisfaire aux exigences de LegacyForwardIterator .
- `BinaryPred` doit satisfaire aux exigences de BinaryPredicate .
- `Size` doit être convertible en un type intégral .

Valeur de retour

Si count est positif, retourne un itérateur vers le début de la première séquence trouvée dans l'intervalle [ first , last ) . Chaque itérateur it dans la séquence doit satisfaire la condition suivante :

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

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

Si aucune telle séquence n'est trouvée, last est retourné.

Si count est nul ou négatif, first est renvoyé.

Complexité

Étant donné $\scriptsize N$ $N$ comme std:: distance ( first, last ) :

1,2) Au maximum

N

comparaisons en utilisant operator == .

3,4) Au plus

N

applications du prédicat p .

Exceptions

Les surcharges avec un paramètre de modèle nommé ExecutionPolicy signalent les erreurs comme suit :

Si l'exécution d'une fonction invoquée dans le cadre de l'algorithme lève une exception et que ExecutionPolicy fait partie des politiques standard , std::terminate est appelé. Pour tout autre ExecutionPolicy , le comportement est défini par l'implémentation.
Si l'algorithme ne parvient pas à allouer de la mémoire, std::bad_alloc est levé.

Implémentation possible

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; // succès
            ++first;
            if (first == last)
                return last; // liste épuisée
            if (!(*first == value))
                break; // trop peu consécutifs
        }
    }
    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; // succès
            ++first;
            if (first == last)
                return last; // liste épuisée
            if (!p(*first, value))
                break; // trop peu consécutifs
        }
    }
    return last;
}

Notes

Macro de test de fonctionnalité	Valeur	Std	Fonctionnalité
`__cpp_lib_algorithm_default_value_type`	`202403`	(C++26)	Initialisation par liste pour les algorithmes ( 1-4 )

Exemple

Exécuter ce code

#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
                  << "Possède " << n << " zéros consécutifs : "
                  << 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());
}

Sortie :

Possède 4 zéros consécutifs : false
Possède 3 zéros consécutifs : true
Possède 2 zéros consécutifs : true

Rapports de défauts

Les rapports de défauts modifiant le comportement suivants ont été appliqués rétroactivement aux normes C++ précédemment publiées.

DR	Appliqué à	Comportement publié	Comportement correct
LWG 283	C++98	`T` devait être EqualityComparable , mais le type de valeur de `InputIt` n'est pas toujours `T`	supprimé l'exigence
LWG 426	C++98	la limite supérieure de complexité était `N·count` , elle est négative si count est négatif	la limite supérieure est 0 si count est non positif
LWG 714	C++98	si count > 0 , la limite supérieure de complexité était `N·count` , mais dans le pire cas le nombre de comparaisons/opérations est toujours `N`	modifié la limite supérieure à `N` dans ce cas
LWG 2150	C++98	la condition d'"occurrence de séquence" était incorrecte	corrigée

Voir aussi

find_end	trouve la dernière séquence d'éléments dans une certaine plage (modèle de fonction)
find find_if find_if_not (C++11)	trouve le premier élément satisfaisant des critères spécifiques (modèle de fonction)
search	recherche la première occurrence d'une plage d'éléments (modèle de fonction)
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)

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