std::ranges::stable_sort

Definiert in Header `<algorithm>`
Aufruf-Signatur
template< std::random_access_iterator I, std::sentinel_for<I> S, class Comp = ranges::less, class Proj = std::identity > erfordert std::sortable<I, Comp, Proj> I stable_sort( I first, S last, Comp comp = {}, Proj proj = {} );	(1)	(seit C++20) (constexpr seit C++26)
template< ranges::random_access_range R, class Comp = ranges::less, class Proj = std::identity > erfordert std::sortable<ranges::iterator_t<R>, Comp, Proj> ranges::borrowed_iterator_t<R> stable_sort( R&& r, Comp comp = {}, Proj proj = {} );	(2)	(seit C++20) (constexpr seit C++26)

Sortiert die Elemente im Bereich [first, last) in nicht absteigender Reihenfolge. Die Reihenfolge äquivalenter Elemente ist stabil, d.h. ihre Beibehaltung ist garantiert.

Eine Sequenz ist in Bezug auf einen Comparator comp sortiert, wenn für jeden Iterator it, der auf die Sequenz zeigt, und jede nicht-negative ganze Zahl n, für die it + n ein gültiger Iterator ist, der auf ein Element der Sequenz zeigt, std::invoke(comp, std::invoke(proj, *(it + n)), std::invoke(proj, *it) zu false ausgewertet wird.

1) Elemente werden mit der gegebenen binären Vergleichsfunktion comp verglichen.

2) Dasselbe wie (1), verwendet aber r als Bereich, als ob ranges::begin(r) als first und ranges::end(r) als last verwendet würden.

Die auf dieser Seite beschriebenen funktionsähnlichen Entitäten sind Algorithmus-Funktionsobjekte (informell als niebloids bekannt), d.h.

Können explizite Template-Argumentlisten bei keinem von ihnen angegeben werden.
Keiner von ihnen ist für Argument-abhängige Suche sichtbar.
Wenn einer von ihnen durch normale unqualifizierte Suche als Name links vom Funktionsaufrufoperator gefunden wird, wird die Argument-abhängige Suche unterdrückt.

[bearbeiten] Parameter

first, last	-	das Iterator-Sentinel-Paar, das den Bereich der zu sortierenden Elemente definiert
r	-	der zu sortierende Bereich
comp	-	Vergleich, der auf die projizierten Elemente angewendet wird
proj	-	Projektion, die auf die Elemente angewendet wird

[bearbeiten] Rückgabewert

Ein Iterator, der gleich last ist.

[bearbeiten] Komplexität

$\scriptsize N\cdot\log{(N)}$ $N\cdotlog(N)$ Vergleiche, wenn zusätzlicher Speicher verfügbar ist; wobei $\scriptsize N$ $N$ ranges::distance(first, last) ist. $\scriptsize N\cdot\log^2{(N)}$ $N\cdotlog²(N)$ Vergleiche sonst. In beiden Fällen doppelt so viele Projektionen wie Vergleiche.

[bearbeiten] Hinweise

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

[bearbeiten] Mögliche Implementierung

Diese Implementierung zeigt nur den langsameren Algorithmus, der verwendet wird, wenn kein zusätzlicher Speicher verfügbar ist. Siehe auch Implementierungen in MSVC STL und libstdc++.

struct stable_sort_fn
{
    template<std::random_access_iterator I, std::sentinel_for<I> S,
             class Comp = ranges::less, class Proj = std::identity>
    requires std::sortable<I, Comp, Proj>
    constexpr //< since C++26
    I operator()(I first, S last, Comp comp = {}, Proj proj = {}) const
    {
        auto count = ranges::distance(first, last);
        auto mid = first + count / 2;
        auto last_it = first + count;
 
        if (count <= 1)
            return last_it;
 
        (*this)(first, mid, std::ref(comp), std::ref(proj));
        (*this)(mid, last_it, std::ref(comp), std::ref(proj));
 
        ranges::inplace_merge(first, mid, last_it);
 
        return last_it;
    }
 
    template<ranges::random_access_range R, class Comp = ranges::less,
             class Proj = std::identity>
    requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
    constexpr //< since C++26
    ranges::borrowed_iterator_t<R> operator()(R&& r, Comp comp = {}, Proj proj = {}) const
    {
        return (*this)(ranges::begin(r), ranges::end(r), std::move(comp), std::move(proj));
    }
};
 
inline constexpr stable_sort_fn stable_sort{};

[bearbeiten] Beispiel

Führen Sie diesen Code aus

#include <algorithm>
#include <array>
#include <functional>
#include <iomanip>
#include <iostream>
 
void print(const auto& seq)
{
    for (const auto& elem : seq)
        std::cout << elem << ' ';
    std::cout << '\n';
}
 
struct Particle
{
    std::string name; double mass; // MeV
    friend std::ostream& operator<<(std::ostream& os, const Particle& p)
    {
        return os << '\n' << std::left << std::setw(8) << p.name << " : " << p.mass;
    }
};
 
int main()
{
    std::array s{5, 7, 4, 2, 8, 6, 1, 9, 0, 3};
 
    // sort using the default operator<
    std::ranges::stable_sort(s);
    print(s);
 
    // sort using a standard library compare function object
    std::ranges::stable_sort(s, std::ranges::greater());
    print(s);
 
    // sort using a custom function object
    struct
    {
        bool operator()(int a, int b) const { return a < b; }
    } customLess;
    std::ranges::stable_sort(s.begin(), s.end(), customLess);
    print(s);
 
    // sort using a lambda expression
    std::ranges::stable_sort(s, [](int a, int b) { return a > b; });
    print(s);
 
    // sort with projection
    Particle particles[]
    {
        {"Electron", 0.511}, {"Muon", 105.66}, {"Tau", 1776.86},
        {"Positron", 0.511}, {"Proton", 938.27}, {"Neutron", 939.57}
    };
    print(particles);
    std::ranges::stable_sort(particles, {}, &Particle::name); //< sorts by name
    print(particles);
    std::ranges::stable_sort(particles, {}, &Particle::mass); //< sorts by mass
    print(particles);
}

Ausgabe

0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0
 
Electron : 0.511
Muon     : 105.66
Tau      : 1776.86
Positron : 0.511
Proton   : 938.27
Neutron  : 939.57
 
Electron : 0.511
Muon     : 105.66
Neutron  : 939.57
Positron : 0.511
Proton   : 938.27
Tau      : 1776.86
 
Electron : 0.511
Positron : 0.511
Muon     : 105.66
Proton   : 938.27
Neutron  : 939.57
Tau      : 1776.86

[bearbeiten] Siehe auch

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