std::ranges::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>
constexpr I 
    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>
constexpr ranges::borrowed_iterator_t<R>
    sort( R&& r, Comp comp = {}, Proj proj = {} );

Sortiert die Elemente im Bereich [first, last) in nicht-absteigender Reihenfolge. Die Reihenfolge äquivalenter Elemente bleibt nicht unbedingt erhalten.

Eine Sequenz ist bezüglich eines Vergleichsoperators 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)) den Wert false ergibt.

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

• Explizite Vorlagenargumentlisten können beim Aufruf keiner von ihnen angegeben werden.
• Keine von ihnen ist für die argumentabhängige Suche sichtbar.
• Wenn eine von ihnen durch normale unqualifizierte Suche als Name links vom Funktionsaufrufoperator gefunden wird, wird die argumentabhängige Suche unterdrückt.

Parameter

Rückgabewert

Ein Iterator gleich last .

Komplexität

\(\scriptsize \mathcal{O}(N\cdot\log{(N)})\) 𝓞(N·log(N)) Vergleiche und Projektionen, wobei N = ranges:: distance ( first, last ) .

Mögliche Implementierung

Beachten Sie, dass typische Implementierungen Introsort verwenden. Siehe auch die Implementierung in MSVC STL und libstdc++ .

struct 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 I
        operator()(I first, S last, Comp comp = {}, Proj proj = {}) const
    {
        if (first == last)
            return first;
        I last_iter = ranges::next(first, last);
        ranges::make_heap(first, last_iter, std::ref(comp), std::ref(proj));
        ranges::sort_heap(first, last_iter, std::ref(comp), std::ref(proj));
        return last_iter;
    }
    template<ranges::random_access_range R, class Comp = ranges::less,
             class Proj = std::identity>
    requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
    constexpr 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 sort_fn sort {};

Hinweise

std::sort verwendet std::iter_swap zum Austauschen von Elementen, wohingegen ranges::sort stattdessen ranges::iter_swap verwendet (welches ADL für iter_swap durchführt, im Gegensatz zu std::iter_swap )

Beispiel

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

Sort using the default operator<
0 1 2 3 4 5 6 7 8 9
Sort using a standard library compare function object
9 8 7 6 5 4 3 2 1 0
Sort using a custom function object
0 1 2 3 4 5 6 7 8 9
Sort using a lambda expression
9 8 7 6 5 4 3 2 1 0
Sort by name using a projection
Electron : 0.511
Muon     : 105.66
Neutron  : 939.57
Positron : 0.511
Proton   : 938.27
Tau      : 1776.86
Sort by mass using a projection
Electron : 0.511
Positron : 0.511
Muon     : 105.66
Proton   : 938.27
Neutron  : 939.57
Tau      : 1776.86

Siehe auch