std::ranges::stable_sort

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>
    I stable_sort( I first, S last, Comp comp = {}, Proj proj = {} );

template< ranges::random_access_range R, class Comp = ranges::less,
          class Proj = std::identity >
requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
ranges::borrowed_iterator_t<R>
    stable_sort( R&& r, Comp comp = {}, Proj proj = {} );

Sortiert die Elemente im Bereich [first, last) in nicht-absteigender Reihenfolge. Die Reihenfolge äquivalenter Elemente ist stabil, d.h. sie bleibt garantiert erhalten.

Eine Sequenz ist bezüglich eines Vergleichs comp sortiert, wenn für jeden Iterator it, der auf die Sequenz zeigt, und jede nicht-negative ganze Zahl n, so dass 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.

Die auf dieser Seite beschriebenen funktionsartigen Entitäten sind Algorithmus-Funktionsobjekte (informell als Niebloids bekannt), das heißt:

• Beim Aufruf einer von ihnen können keine expliziten Template-Argumentlisten angegeben werden.
• Keine von ihnen ist für argumentabhängige Namenssuche sichtbar.
• Wenn eine von ihnen durch normale unqualifizierte Namenssuche als Name links vom Funktionsaufrufoperator gefunden wird, wird die argumentabhängige Namenssuche unterdrückt.

Parameter

Rückgabewert

Ein Iterator gleich last .

Komplexität

\(\scriptsize N\cdot\log{(N)}\) N·log(N) Vergleiche, falls zusätzlicher Speicher verfügbar ist; wobei \(\scriptsize N\) N gleich ranges:: distance ( first, last ) ist. \(\scriptsize N\cdot\log^2{(N)}\) N·log²(N) Vergleiche andernfalls. In beiden Fällen doppelt so viele Projektionen wie die Anzahl der Vergleiche.

Hinweise

Mögliche Implementierung

Diese Implementierung zeigt nur den langsameren Algorithmus, der verwendet wird, wenn kein zusätzlicher Speicher verfügbar ist. Siehe auch Implementierung 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 //< seit 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 //< seit 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{};

Beispiel

#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};
    // Sortierung mit dem Standardoperator <
    std::ranges::stable_sort(s);
    print(s);
    // Sortierung mit einem Standardbibliotheks-Vergleichsfunktor
    std::ranges::stable_sort(s, std::ranges::greater());
    print(s);
    // Sortierung mit einem benutzerdefinierten Funktor
    struct
    {
        bool operator()(int a, int b) const { return a < b; }
    } customLess;
    std::ranges::stable_sort(s.begin(), s.end(), customLess);
    print(s);
    // Sortierung mit einem Lambda-Ausdruck
    std::ranges::stable_sort(s, [](int a, int b) { return a > b; });
    print(s);
    // Sortierung mit Projektion
    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); //< sortiert nach Name
    print(particles);
    std::ranges::stable_sort(particles, {}, &Particle::mass); //< sortiert nach Masse
    print(particles);
}

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

Siehe auch