std::ranges:: stable_sort

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

Eine Sequenz ist bezüglich eines Komparators comp sortiert, wenn für jeden Iterator it , der auf die Sequenz zeigt, und jede nicht-negative Ganzzahl n , sodass 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 funktionsähnlichen Entitäten sind algorithm function objects (informell bekannt als niebloids ), das heißt:

• Explizite Template-Argumentlisten können beim Aufruf keiner von ihnen angegeben werden.
• Keiner von ihnen ist sichtbar für argument-dependent lookup .
• Wenn einer von ihnen durch normal unqualified lookup als Name links vom Funktionsaufrufoperator gefunden wird, wird argument-dependent lookup 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