std::ranges::sort — cppreference.com

Материал из cppreference.com

Определено в заголовочном файле `<algorithm>`
Сигнатура вызова
`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 = {} );`	(1)	(начиная с C++20)
`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 = {} );`	(2)	(начиная с C++20)

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

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

1) Элементы сравниваются с использованием заданной функции двоичного сравнения. comp.

2) Аналогичной (1), но использующей r в качестве исходного диапазона, как если бы использовалась ranges::begin(r) как first и ranges::end(r) как last.

Функционально-подобные объекты, описанные на этой странице, являются ниблоидами, то есть:

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

На практике они могут быть реализованы как функциональные объекты или со специальными расширениями компилятора.

Параметры

first, last	—	итераторы-охранные выражения определяющие диапазон для сортировки
r	—	диапазон для сортировки
comp	—	условие, применяемое к проецируемым элементам
proj	—	проекция, применяемая к элементам

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

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

Сложность

𝓞(N·log(N)) сравнений и проекций, где N = ranges::distance(first, last).

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

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

Заметки

std::sort использует std::iter_swap чтобы менять местами элементы, в то время как ranges::sort вместо этого использует ranges::iter_swap (который выполняет ADL для iter_swap, в отличие от std::iter_swap)

Пример

#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

Смотри также

Категории: