std::search_n

 

C++

Compiler-Unterstützung

Freestanding und gehostet

Sprache

Standardbibliothek

Header der Standardbibliothek

Benannte Anforderungen

Feature-Test-Makros (C++20)

Bibliothek für Sprachunterstützung

Konzepte-Bibliothek (C++20)

Diagnostik-Bibliothek

Speicherverwaltungsbibliothek

Metaprogrammierungsbibliothek (C++11)

Allgemeine Dienstprogramme-Bibliothek

Container-Bibliothek

Iterator-Bibliothek

Ranges-Bibliothek (C++20)

Algorithmen-Bibliothek

Bibliothek für Zeichenketten

Textverarbeitungsbibliothek

Numerik-Bibliothek

Datums- und Zeitbibliothek

Ein-/Ausgabe-Bibliothek

Dateisystembibliothek (C++17)

Unterstützung für nebenläufige Programmierung (C++11)

Ausführungssteuerungsbibliothek (C++26)

Technische Spezifikationen

Symbolverzeichnis

Externe Bibliotheken

 

Algorithmenbibliothek

Beschränkte Algorithmen und Algorithmen für Bereiche (C++20)
Beschränkte Algorithmen, z.B. ranges::copy, ranges::sort, ...
Ausführungsrichtlinien (C++17)
is_execution_policy (C++17)   execution::seqexecution::parexecution::par_unseqexecution::unseq (C++17)    (C++17)(C++17)(C++20)	execution::sequenced_policyexecution::parallel_policyexecution::parallel_unsequenced_policyexecution::parallel_unsequenced (C++17)(C++17)(C++17)(C++20)
Nicht-modifizierende Sequenzoperationen Stapeloperationen for_each for_each_n (C++17) Suchoperationen all_ofany_ofnone_of (C++11)                (C++11)(C++11) countcount_if mismatch equal findfind_iffind_if_not (C++11) find_end find_first_of adjacent_find search search_n Modifizierende Sequenzoperationen Kopieroperationen copycopy_if (C++11) copy_backward copy_n (C++11) move (C++11) move_backward (C++11) Tauschoperationen swap iter_swap swap_ranges Transformationsoperationen replacereplace_if transform replace_copyreplace_copy_if Generierungsoperationen fill fill_n generate generate_n Entfernungsoperationen removeremove_if unique remove_copyremove_copy_if unique_copy Ordnungsändernde Operationen reverse reverse_copy rotate rotate_copy random_shuffleshuffle (bis C++17)(C++11) shift_leftshift_right (C++20)(C++20) Stichprobenoperationen sample (C++17)	Sortier- und verwandte Operationen Partitionierungsoperationen partition partition_copy (C++11)   stable_partition is_partitioned (C++11) partition_point (C++11) Sortieroperationen sort stable_sort partial_sort partial_sort_copy is_sorted (C++11) is_sorted_until (C++11) nth_element Binäre Suchoperationen (auf partitionierten Bereichen) lower_bound upper_bound equal_range binary_search Mengenoperationen (auf sortierten Bereichen) includes set_union set_intersection set_difference set_symmetric_difference Zusammenführungsoperationen (auf sortierten Bereichen) merge inplace_merge Heapoperationen push_heap pop_heap make_heap sort_heap is_heap (C++11) is_heap_until (C++11) Minimum/Maximum-Operationen max min minmax (C++11) clamp (C++17) max_element min_element minmax_element (C++11) Lexikographische Vergleichsoperationen lexicographical_compare lexicographical_compare_three_way (C++20) Permutationsoperationen next_permutation prev_permutation is_permutation (C++11) C-Bibliothek qsort bsearch
Numerische Operationen
iota (C++11) inner_product adjacent_difference    accumulate reduce (C++17) transform_reduce (C++17)	partial_sum inclusive_scan (C++17)    exclusive_scan (C++17) transform_inclusive_scan (C++17) transform_exclusive_scan (C++17)
Operationen auf uninitialisiertem Speicher
uninitialized_copy uninitialized_move (C++17)    uninitialized_fill uninitialized_copy_n (C++11) uninitialized_move_n (C++17) uninitialized_fill_n	destroy (C++17) destroy_n (C++17) destroy_at (C++17) construct_at (C++20)       uninitialized_default_construct (C++17) uninitialized_value_construct (C++17) uninitialized_default_construct_n (C++17) uninitialized_value_construct_n (C++17)

 

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 gleich dem gegebenen value sind.

1) Elemente werden mit operator== verglichen.

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

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

Diese Überladungen nehmen an der Auflösungsauflösung teil, nur 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)

Parameter

first, last	-	das Iteratorenpaar, das den Bereich der zu untersuchenden Elemente definiert
zählt	-	die Länge der zu durchsuchenden Sequenz
value	-	der Wert der zu durchsuchenden Elemente
policy	-	die Ausführungsrichtlinie, die verwendet werden soll
p	-	binäre Prädikatfunktion, die ​true zurückgibt, wenn die Elemente als gleich behandelt werden sollen. Die Signatur der Prädikatfunktion sollte äquivalent zur folgenden sein:  bool pred(const Type1 &a, const Type2 &b); Obwohl die Signatur nicht zwingend const & haben muss, darf die Funktion die ihr übergebenen Objekte nicht modifizieren und muss alle Werte vom Typ (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 gleichbedeutend mit 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 an BinaryPredicate erfüllen.
- Size muss konvertierbar in einen ganzzahligen Typ sein.

Rückgabewert

Wenn count positiv ist, wird ein Iterator zurückgegeben, der auf den Anfang der ersten gefundenen Sequenz im Bereich [first, last) zeigt. Jeder Iterator it in der Sequenz muss 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, wird last zurückgegeben.

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

Komplexität

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

1,2) Höchstens \(\scriptsize N\)N Vergleiche mittels operator==.

3,4) Höchstens \(\scriptsize N\)N Anwendungen des Prädikats p.

Ausnahmen

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

• Wenn die Ausführung einer Funktion, die als Teil des Algorithmus aufgerufen wird, eine Ausnahme auslöst und ExecutionPolicy eine der Standardrichtlinien ist, wird std::terminate aufgerufen. Für jede andere ExecutionPolicy ist das Verhalten implementierungsabhängig.
• Wenn dem Algorithmus der Speicher zur Neuzuweisung fehlt, wird std::bad_alloc ausgelöst.

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; // success   ++first; if (first == last) return last; // exhausted the list   if (!(*first == value)) break; // too few in a row } } 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; // success   ++first; if (first == last) return last; // exhausted the list   if (!p(*first, value)) break; // too few in a row } } return last; }

Hinweise

Feature-Test-Makro	Wert	Std	Feature
__cpp_lib_algorithm_default_value_type	202403	(C++26)	List-Initialisierung für Algorithmen (1-4)

Beispiel

Führen Sie diesen Code aus

#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
                  << "Has " << n << " consecutive zeros: "
                  << 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

Has 4 consecutive zeros: false
Has 3 consecutive zeros: true
Has 2 consecutive zeros: true

Fehlerberichte

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

DR	angewendet auf	Verhalten wie veröffentlicht	Korrigiertes 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 obere Grenze der Komplexität war N·count, ist negativ, wenn count negativ ist	die obere Grenze ist ​0​ wenn count nicht-positiv ist
LWG 714	C++98	wenn count > 0, war die obere Grenze der Komplexität N·count, aber in der schlechtesten Fall ist die Anzahl der Vergleiche/Operationen immer N	die obere Grenze wurde in diesem Fall auf N geändert
LWG 2150	C++98	Die Bedingung "Sequenzvorkommen" war falsch.	korrigiert

Siehe auch

find_end	Findet die letzte Sequenz von Elementen in einem bestimmten Bereich (Funktionstempelat)
findfind_iffind_if_not (C++11)	Findet das erste Element, das bestimmte Kriterien erfüllt (Funktionstempelat)
search	Sucht nach dem ersten Vorkommen eines Elementbereichs (Funktionstempelat)
ranges::search_n (C++20)	Sucht nach dem ersten Vorkommen einer Anzahl aufeinanderfolgender Kopien eines Elements in einem Bereich (Algorithmus-Funktionsobjekt)