Namespaces
Variants

    std::stable_sort

    Von de.cppreference.net
     
    C++
     
    Algorithmus-Bibliothek
    Eingeschränkte Algorithmen und Algorithmen auf Bereichen (C++20)
    Eingeschränkte Algorithmen, z. B. ranges::copy, ranges::sort, ...
    Nicht modifizierende Sequenzoperationen    
    Stapeloperationen
    (C++17)
    Suchoperationen
    Modifizierende Sequenzoperationen
    Kopieroperationen
    (C++11)
    (C++11)
    (C++11)
    Tauschoperationen
    Transformationsoperationen
    Generierungsoperationen
    Entfernungsoperationen
    Reihenfolgeändernde Operationen
    (bis C++17)(C++11)
    (C++20)(C++20)
    Stichprobenoperationen
    (C++17)

    Sortier- und verwandte Operationen
    Partitionierungsoperationen
    (C++11)    
    (C++11)

    Sortieroperationen
    Binäre Suchoperationen
    (auf partitionierten Bereichen)
    Mengenoperationen (auf sortierten Bereichen)
    Mischoperationen (auf sortierten Bereichen)
    Heap-Operationen
    Minimum/Maximum-Operationen
    (C++11)
    (C++17)
    Lexikografische Vergleichsoperationen
    (C++20)
    Permutationsoperationen


     
    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 äquivalenter Elemente bleibt erhalten.

    1) Elemente werden sortiert bezüglich operator<(bis C++20)std::less{}(seit C++20).
    3) Elemente werden bezüglich comp sortiert.
    2,4) Dasselbe wie (1,3), aber ausgeführt gemäß policy.
    Diese Überladungen nehmen nur an der Überladungsauflösung teil, wenn der Wert des folgenden Ausdrucks true ist:

    std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>

    		(bis C++20)

    std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>

    		(seit C++20)

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

    (bis C++11)
    (seit C++11)

    Parameter

    first, last - das Paar von Iteratoren, das den Bereich der zu sortierenden Elemente definiert
    policy - die zu verwendende Ausführungsrichtlinie
    comp - Vergleichsfunktionsobjekt (d.h. ein Objekt, das die Anforderungen von Compare erfüllt), das ​ true zurückgibt, wenn das erste Argument kleiner als (d.h. vor dem zweiten geordnet ist) das zweite ist.

    Die Signatur der Vergleichsfunktion sollte äquivalent zu Folgendem sein:

    bool cmp ( const Type1 & a, const Type2 & b ) ;

    Obwohl die Signatur keine 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) ).
    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 von LegacyRandomAccessIterator erfüllen.
    -
    Compare muss die Anforderungen von Compare erfüllen.

    Komplexität

    Gegeben N als last - first :

    1,2) O(N·log(N)) Vergleiche mit operator < (bis C++20) std:: less { } (seit C++20) falls genügend zusätzlicher Speicher verfügbar ist, andernfalls O(N·log 2
    (N))     Vergleiche.
    3,4) O(N·log(N)) Anwendungen des Vergleichsoperators comp falls genügend zusätzlicher Speicher verfügbar ist, andernfalls O(N·log 2
    (N))     Anwendungen.

    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 allokieren kann, wird std::bad_alloc geworfen.

    Mögliche Implementierung

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

    Hinweise

    Diese Funktion versucht, einen temporären Puffer in der Größe der zu sortierenden Sequenz zu reservieren. Wenn die Reservierung 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 )

    Beispiel

    Diesen Code ausführen 
    #include <algorithm>
#include <array>
#include <iostream>
#include <string>
#include <vector>
struct Employee
{
    int age;
    std::string name; // Nimmt nicht an Vergleichen teil
};
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

    Siehe auch

    		 sortiert einen Bereich von Elementen
    (Funktionsschablone & Algorithmus-Funktionsobjekt)
    (C++20)
    		sortiert die ersten N Elemente eines Bereichs
    (Funktionsschablone & Algorithmus-Funktionsobjekt)
    (C++20)
    		teilt Elemente in zwei Gruppen auf, wobei die relative Reihenfolge innerhalb jeder Gruppe erhalten bleibt
    (Funktionsschablone & Algorithmus-Funktionsobjekt)
    (C++20)
    (C++20)
    		 sortiert einen Bereich von Elementen unter Beibehaltung der relativen Reihenfolge zwischen äquivalenten Elementen
    (Algorithmus-Funktionsobjekt)