std:: search_n

From cppreference.net

(Anmerkung: Der bereitgestellte HTML-Code enthält keinen übersetzbaren Text, da alle Tags leer sind oder nur Klassenattribute enthalten. Gemäß den Anweisungen wurden HTML-Tags und Attribute unverändert beibehalten.)

Definiert in Header `<algorithm>`
	(1)
template < class ForwardIt, class Size, class T > ForwardIt search_n ( ForwardIt first, ForwardIt last, Size count, const T & value ) ;			(constexpr seit C++20) (bis 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 ) ;			(seit 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 ) ;				(seit C++17) (bis 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 ) ;				(seit 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 seit C++20) (bis 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 ) ;					(seit 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 ) ;						(seit C++17) (bis 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 ) ;						(seit C++26)

Durchsucht den Bereich [ first , last ) nach der ersten Sequenz von count identischen Elementen, die jeweils dem gegebenen value entsprechen.

1) Elemente werden mit operator == verglichen.

3) Elemente werden mit dem gegebenen binären Prädikat p verglichen.

2,4) Gleich wie (1,3) , aber ausgeführt gemäß policy .

Diese Überladungen nehmen nur dann an der Überladungsauflösung teil, wenn alle folgenden Bedingungen erfüllt sind:

std:: is_execution_policy_v < std:: decay_t < ExecutionPolicy >> ist true .	(bis C++20)
std:: is_execution_policy_v < std:: remove_cvref_t < ExecutionPolicy >> ist true .	(seit C++20)

Inhaltsverzeichnis

Parameter

first, last	-	das Paar von Iteratoren, das den Bereich der zu untersuchenden Elemente definiert
count	-	die Länge der zu suchenden Sequenz
value	-	der Wert der zu suchenden Elemente
policy	-	die zu verwendende Ausführungsrichtlinie
p	-	binäres Prädikat, das true zurückgibt, wenn die Elemente als gleich behandelt werden sollen. Die Signatur der Prädikatfunktion sollte äquivalent zu Folgendem sein: bool pred ( const Type1 & a, const Type2 & b ) ; Obwohl die Signatur nicht const & benötigt, darf die Funktion die übergebenen Objekte nicht modifizieren und muss alle Werte des Typs (möglicherweise const) `Type1` und `Type2` unabhängig von der Wertkategorie akzeptieren können (daher ist Type1 & nicht erlaubt , ebenso wenig wie Type1 , es sei denn, für `Type1` ist eine Verschiebung äquivalent zu einer Kopie (seit C++11) ). Der Typ Type1 muss so beschaffen sein, dass ein Objekt vom Typ ForwardIt dereferenziert und dann implizit in Type1 konvertiert werden kann. Der Typ Type2 muss so beschaffen sein, dass ein Objekt vom Typ T implizit in Type2 konvertiert werden kann.
Typanforderungen
- `ForwardIt` muss die Anforderungen von LegacyForwardIterator erfüllen.
- `BinaryPred` muss die Anforderungen von BinaryPredicate erfüllen.
- `Size` muss in einen integralen Typ konvertierbar sein.

Rückgabewert

Wenn count positiv ist, gibt es einen Iterator zum Anfang der ersten Sequenz zurück, die im Bereich [ first , last ) gefunden wurde. Jeder Iterator it in der Sequenz sollte die folgende Bedingung erfüllen:

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

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

Wenn keine solche Sequenz gefunden wird, last wird zurückgegeben.

Wenn count null oder negativ ist, wird first zurückgegeben.

Komplexität

Gegeben $\scriptsize N$ $N$ als std:: distance ( first, last ) :

1,2) Höchstens

N

Vergleiche mit operator == .

3,4) Höchstens

N

Anwendungen des Prädikats p .

Ausnahmen

Die Überladungen mit einem Template-Parameter namens ExecutionPolicy melden Fehler wie folgt:

Wenn die Ausführung einer als Teil des Algorithmus aufgerufenen Funktion eine Exception wirft und ExecutionPolicy einer der Standard-Policies ist, wird std::terminate aufgerufen. Für jede andere ExecutionPolicy ist das Verhalten implementierungsdefiniert.
Wenn der Algorithmus keinen Speicher allozieren kann, wird std::bad_alloc geworfen.

Mögliche Implementierung

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; // Erfolg
            ++first;
            if (first == last)
                return last; // Liste erschöpft
            if (!(*first == value))
                break; // Zu wenige in Folge
        }
    }
    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; // Erfolg
            ++first;
            if (first == last)
                return last; // Liste erschöpft
            if (!p(*first, value))
                break; // Zu wenige in Folge
        }
    }
    return last;
}

Hinweise

Feature-Test Makro	Wert	Std	Funktion
`__cpp_lib_algorithm_default_value_type`	`202403`	(C++26)	Listeninitialisierung für Algorithmen ( 1-4 )

Beispiel

Diesen Code ausführen

#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
                  << "Hat " << n << " aufeinanderfolgende Nullen: "
                  << 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());
}

Ausgabe:

Hat 4 aufeinanderfolgende Nullen: false
Hat 3 aufeinanderfolgende Nullen: true
Hat 2 aufeinanderfolgende Nullen: true

Fehlerberichte

Die folgenden verhaltensändernden Fehlerberichte wurden rückwirkend auf zuvor veröffentlichte C++-Standards angewendet.

DR	Angewendet auf	Verhalten wie veröffentlicht	Korrektes Verhalten
LWG 283	C++98	`T` musste EqualityComparable sein, aber der Werttyp von `InputIt` ist nicht immer `T`	Anforderung entfernt
LWG 426	C++98	die Komplexitätsobergrenze war `N·count` , sie ist negativ wenn count negativ ist	die Obergrenze ist 0 wenn count nicht-positiv ist
LWG 714	C++98	wenn count > 0 , war die Komplexitätsobergrenze `N·count` , aber im Worst-Case ist die Anzahl der Vergleiche/Operationen immer `N`	änderte die Obergrenze auf `N` in diesem Fall
LWG 2150	C++98	die Bedingung für "Sequenzvorkommen" war inkorrekt	korrigiert

Siehe auch

find_end	findet die letzte Sequenz von Elementen in einem bestimmten Bereich (Funktions-Template)
find find_if find_if_not (C++11)	findet das erste Element, das bestimmte Kriterien erfüllt (Funktions-Template)
search	sucht nach dem ersten Vorkommen eines Elementbereichs (Funktions-Template)
ranges::search_n (C++20)	sucht nach dem ersten Vorkommen einer Anzahl aufeinanderfolgender Kopien eines Elements in einem Bereich (Algorithmus-Funktionsobjekt)

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