std::stable_sort

Definiert in Header `<algorithm>`
template< class RandomIt > void stable_sort( RandomIt first, RandomIt last );	(1)	(constexpr seit C++26)
template< class ExecutionPolicy, class RandomIt > void stable_sort( ExecutionPolicy&& policy, RandomIt first, RandomIt last );	(2)	(seit C++17)
template< class RandomIt, class Compare > void stable_sort( RandomIt first, RandomIt last, Compare comp );	(3)	(constexpr seit C++26)
template< class ExecutionPolicy, class RandomIt, class Compare > void stable_sort( ExecutionPolicy&& policy, RandomIt first, RandomIt last, Compare comp );	(4)	(seit C++17)

Sortiert die Elemente im Bereich [first, last) in nicht absteigender Reihenfolge. Die Reihenfolge von äquivalenten Elementen ist garantiert erhalten zu bleiben.

1) Die Elemente werden bezüglich operator<(bis C++20)std::less{}(seit C++20) sortiert.

3) Die Elemente werden bezüglich comp sortiert.

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)

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

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

[edit] Parameter

first, last	-	das Paar von Iteratoren, das den zu sortierenden Bereich von Elementen definiert
policy	-	die Ausführungsrichtlinie, die verwendet werden soll
comp	-	Vergleichsfunktions-Objekt (d.h. ein Objekt, das die Anforderungen an Compare erfüllt), das true zurückgibt, wenn das erste Argument weniger (d.h. vorher) als das zweite geordnet ist. Die Signatur der Vergleichsfunktion sollte äquivalent zu Folgendem sein bool cmp(const Type1& a, const Type2& b); Obwohl die Signatur nicht unbedingt const& haben muss, darf die Funktion die übergebenen Objekte nicht verändern und muss in der Lage sein, alle Werte vom Typ (möglicherweise const) `Type1` und `Type2` unabhängig von der Wertkategorie zu akzeptieren (daher ist `Type1&` nicht erlaubt, ebenso wenig `Type1`, es sei denn, für `Type1` ist ein Move äquivalent zu einem Kopieren(since C++11)). Die Typen Type1 und Type2 müssen so beschaffen sein, dass ein Objekt vom Typ RandomIt dereferenziert und dann implizit in beide konvertiert werden kann.
Typanforderungen
- `RandomIt` muss die Anforderungen an einen LegacyRandomAccessIterator erfüllen.
- `Compare` muss die Anforderungen an Compare erfüllen.

[edit] Komplexität

Gegeben $\scriptsize N$ $N$ als last - first

1,2)

O(N\cdotlog(N))

Vergleiche mittels operator<(bis C++20)std::less{}(seit C++20), wenn genügend zusätzlicher Speicher verfügbar ist, andernfalls

O(N\cdotlog 2 (N))

Vergleiche.

3,4)

O(N\cdotlog(N))

Anwendungen des Komparators comp, wenn genügend zusätzlicher Speicher verfügbar ist, andernfalls

O(N\cdotlog 2 (N))

Anwendungen.

[edit] 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.

[edit] Mögliche Implementierung

Siehe auch die Implementierungen in libstdc++ und libc++.

[edit] Hinweise

Diese Funktion versucht, einen temporären Puffer zu allozieren, der so groß ist wie die zu sortierende Sequenz. Wenn die Allokation fehlschlägt, wird der weniger effiziente Algorithmus gewählt.

Feature-Test-Makro	Wert	Std	Feature
`__cpp_lib_constexpr_algorithms`	`202306L`	(C++26)	constexpr stabile Sortierung, Überladungen (1), (3)

[edit] Beispiel

Führen Sie diesen Code aus

#include <algorithm>
#include <array>
#include <iostream>
#include <string>
#include <vector>
 
struct Employee
{
    int age;
    std::string name; // Does not participate in comparisons
};
 
bool operator<(const Employee& lhs, const Employee& rhs)
{
    return lhs.age < rhs.age;
}
 
#if __cpp_lib_constexpr_algorithms >= 202306L
consteval auto get_sorted()
{
    auto v = std::array{3, 1, 4, 1, 5, 9};
    std::stable_sort(v.begin(), v.end());
    return v;
}
static_assert(std::ranges::is_sorted(get_sorted()));
#endif
 
int main()
{
    std::vector<Employee> v{{108, "Zaphod"}, {32, "Arthur"}, {108, "Ford"}};
 
    std::stable_sort(v.begin(), v.end());
 
    for (const Employee& e : v)
        std::cout << e.age << ", " << e.name << '\n';
}

Ausgabe

32, Arthur
108, Zaphod
108, Ford

[edit] Siehe auch

sort	Sortiert einen Bereich aufsteigend (Funktionstemplate) [edit]
partial_sort	Sortiert die ersten N Elemente eines Bereichs (Funktionstemplate) [edit]
stable_partition	Teilt Elemente in zwei Gruppen auf und behält dabei ihre relative Reihenfolge bei (Funktionstemplate) [edit]
ranges::stable_sort (C++20)	Sortiert einen Bereich von Elementen und behält dabei die Reihenfolge zwischen gleichen Elementen bei (Algorithmus-Funktionsobjekt)[edit]

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

cppreference.com

Namensräume

Varianten

Ansichten

Aktionen