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 = {} );

Trie les éléments dans la plage [first, last) dans l'ordre non décroissant. L'ordre des éléments équivalents est stable, c'est-à-dire garanti d'être préservé.

Une séquence est triée par rapport à un comparateur comp si pour tout itérateur it pointant vers la séquence et tout entier non négatif n tel que it + n est un itérateur valide pointant vers un élément de la séquence, std::invoke(comp, std::invoke(proj, *(it + n)), std::invoke(proj, *it) évalue à false.

Les entités de type fonction décrites sur cette page sont des objets fonction d'algorithme (informellement connus sous le nom de niebloids), c'est-à-dire :

• Les listes d'arguments de modèle explicites ne peuvent pas être spécifiées lors de l'appel de l'une d'entre elles.
• Aucune d'entre elles n'est visible par recherche dépendante des arguments.
• Lorsque l'une d'entre elles est trouvée par recherche normale non qualifiée comme nom à gauche de l'opérateur d'appel de fonction, recherche dépendante des arguments est inhibée.

Paramètres

Valeur de retour

Un itérateur égal à last .

Complexité

\(\scriptsize N\cdot\log{(N)}\) N·log(N) comparaisons, si de la mémoire supplémentaire est disponible ; où \(\scriptsize N\) N est ranges:: distance ( first, last ) . \(\scriptsize N\cdot\log^2{(N)}\) N·log²(N) comparaisons sinon. Deux fois plus de projections que le nombre de comparaisons dans les deux cas.

Notes

Implémentation possible

Cette implémentation montre uniquement l'algorithme plus lent utilisé lorsqu'aucune mémoire supplémentaire n'est disponible. Voir également l'implémentation dans MSVC STL et 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 //< depuis 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 //< depuis 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{};

Exemple

#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};
    // trier en utilisant l'opérateur < par défaut
    std::ranges::stable_sort(s);
    print(s);
    // trier en utilisant un objet de fonction de comparaison standard
    std::ranges::stable_sort(s, std::ranges::greater());
    print(s);
    // trier en utilisant un objet de fonction personnalisé
    struct
    {
        bool operator()(int a, int b) const { return a < b; }
    } customLess;
    std::ranges::stable_sort(s.begin(), s.end(), customLess);
    print(s);
    // trier en utilisant une expression lambda
    std::ranges::stable_sort(s, [](int a, int b) { return a > b; });
    print(s);
    // trier avec 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); //< trie par nom
    print(particles);
    std::ranges::stable_sort(particles, {}, &Particle::mass); //< trie par 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

Voir aussi