std::stable_partition

 

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>
template< class BidirIt, class UnaryPred > BidirIt stable_partition( BidirIt first, BidirIt last, UnaryPred p );	(1)	(constexpr seit C++26)
template< class ExecutionPolicy, class BidirIt, class UnaryPred > BidirIt stable_partition( ExecutionPolicy&& policy,                           BidirIt first, BidirIt last, UnaryPred p );	(2)	(seit C++17)

1) Ordnet die Elemente im Bereich [first, last) so um, dass alle Elemente, für die der Prädikat p true zurückgibt, vor den Elementen stehen, für die das Prädikat p false zurückgibt. Die relative Reihenfolge der Elemente wird beibehalten.

2) Wie (1), wird aber gemäß policy ausgeführt.

Diese Überladung nimmt an der Überladungsauflö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)

Wenn eine der folgenden Bedingungen erfüllt ist, ist das Verhalten undefiniert

Der Typ von *first ist nicht Swappable.	(bis C++11)
BidirIt ist nicht ValueSwappable. Der Typ von *first ist nicht MoveConstructible. Der Typ von *first ist kein MoveAssignable.	(seit C++11)

Parameter

first, last	-	Das Iteratorenpaar, das den Bereich der neu zu ordnenden Elemente definiert
policy	-	die Ausführungsrichtlinie, die verwendet werden soll
p	-	unäres Prädikat, das ​true zurückgibt, wenn das Element vor anderen Elementen geordnet werden soll. Der Ausdruck p(v) muss für jedes Argument v vom Typ (möglicherweise const) VT, wobei VT der Werttyp von BidirIt ist, unabhängig von der Wertkategorie, in bool konvertierbar sein und darf v nicht verändern. Daher ist ein Parametertyp von VT&nicht erlaubt, ebenso wenig wie VT, es sei denn, für VT ist eine Verschiebung gleichbedeutend mit einer Kopie(seit C++11). ​
Typanforderungen
- BidirIt muss die Anforderungen von LegacyBidirectionalIterator erfüllen.
- UnaryPred muss die Anforderungen von Predicate erfüllen.

Rückgabewert

Iterator auf das erste Element der zweiten Gruppe.

Komplexität

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

1) Genau \(\scriptsize N\)N Anwendungen von p.

\(\scriptsize O(N)\)O(N) Vertauschungen, wenn genügend zusätzlicher Speicher vorhanden ist, andernfalls höchstens \(\scriptsize N \cdot log_{2}(N)\)N⋅log2(N) Vertauschungen.

2) \(\scriptsize O(N)\)O(N) Anwendungen von p.

\(\scriptsize N \cdot log(N)\)N⋅log(N) Vertauschungen.

Ausnahmen

Die Überladung mit einem Template-Parameter namens ExecutionPolicy meldet 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.

Hinweise

Diese Funktion versucht, einen temporären Puffer zu allokieren. Schlägt die Allokation fehl, wird der weniger effiziente Algorithmus gewählt.

Implementierungen in libc++ und libstdc++ akzeptieren auch Bereiche, die von LegacyForwardIteratoren bezeichnet werden, als Erweiterung.

Feature-Test-Makro	Wert	Std	Feature
__cpp_lib_constexpr_algorithms	202306L	(C++26)	constexpr stabile Sortierung (1)

Beispiel

Führen Sie diesen Code aus

#include <algorithm>
#include <iostream>
#include <vector>
 
int main()
{
    std::vector<int> v{0, 0, 3, -1, 2, 4, 5, 0, 7};
    std::stable_partition(v.begin(), v.end(), [](int n) { return n > 0; });
    for (int n : v)
        std::cout << n << ' ';
    std::cout << '\n';
}

Ausgabe

3 2 4 5 7 0 0 -1 0

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 2150	C++98	std::stable_partition war nur dazu verpflichtet, ein Element, das p erfüllt, vor ein Element zu stellen, das p nicht erfüllt	korrigierte die Anforderung

Siehe auch

partition	Teilt einen Bereich von Elementen in zwei Gruppen auf (Funktionstemplate)
ranges::stable_partition (C++20)	Teilt Elemente in zwei Gruppen auf und behält dabei ihre relative Reihenfolge bei (Algorithmus-Funktionsobjekt)