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

Сортирует элементы в диапазоне [first, last) в порядке неубывания. Порядок эквивалентных элементов является устойчивым, т.е. гарантированно сохраняется.

Последовательность отсортирована относительно компаратора comp, если для любого итератора it, указывающего на последовательность, и любого неотрицательного целого n такого, что it + n является корректным итератором, указывающим на элемент последовательности, std::invoke(comp, std::invoke(proj, *(it + n)), std::invoke(proj, *it) вычисляется в false.

Объекты, подобные функциям, описанные на этой странице, представляют собой функциональные объекты алгоритма (неофициально известные как niebloids), то есть:

• Явные списки аргументов шаблона не могут быть указаны при вызове любого из них.
• Ни один из них не виден для поиска, зависящего от аргументов.
• Когда любой из них находится с помощью обычного неквалифицированного поиска в качестве имени слева от оператора вызова функции, поиск, зависящий от аргументов, подавляется.

Параметры

Возвращаемое значение

Итератор, равный last .

Сложность

\(\scriptsize N\cdot\log{(N)}\) N·log(N) сравнений, если доступна дополнительная память; где \(\scriptsize N\) N это ranges:: distance ( first, last ) . \(\scriptsize N\cdot\log^2{(N)}\) N·log²(N) сравнений в противном случае. Вдвое больше проекций, чем количество сравнений в обоих случаях.

Примечания

Возможная реализация

Эта реализация показывает только более медленный алгоритм, используемый когда дополнительная память недоступна. Смотрите также реализацию в MSVC STL и 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 //< начиная с 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 //< начиная с 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{};

Пример

#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};
    // сортировка с использованием оператора < по умолчанию
    std::ranges::stable_sort(s);
    print(s);
    // сортировка с использованием стандартного объекта функции сравнения
    std::ranges::stable_sort(s, std::ranges::greater());
    print(s);
    // сортировка с использованием пользовательского объекта функции
    struct
    {
        bool operator()(int a, int b) const { return a < b; }
    } customLess;
    std::ranges::stable_sort(s.begin(), s.end(), customLess);
    print(s);
    // сортировка с использованием лямбда-выражения
    std::ranges::stable_sort(s, [](int a, int b) { return a > b; });
    print(s);
    // сортировка с проекцией
    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); //< сортировка по имени
    print(particles);
    std::ranges::stable_sort(particles, {}, &Particle::mass); //< сортировка по массе
    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

См. также