std::ranges::sort
Определено в заголовочном файле <algorithm>
|
||
Сигнатура вызова |
||
template< std::random_access_iterator I, std::sentinel_for<I> S, class Comp = ranges::less, class Proj = std::identity > |
(1) | (начиная с C++20) |
template< ranges::random_access_range R, class Comp = ranges::less, class Proj = std::identity > |
(2) | (начиная с C++20) |
Сортирует элементы в диапазоне [
first,
last)
в неубывающем порядке. Порядок эквивалентных элементов не определен.
Последовательность сортируется с использованием предиката comp если для каждого итератора it
указывающего на последовательность и для каждого неотрицательного целого n
такого, что it + n
является допустимым итератором, указывающим на элемент последовательности, std::invoke(comp, std::invoke(proj, *(it + n)), std::invoke(proj, *it)) становится false.
Функционально-подобные объекты, описанные на этой странице, являются ниблоидами, то есть:
- Явные списки аргументов шаблона не могут быть указаны при вызове любого из них.
- Ни один из них не виден для поиска, зависящего от аргумента.
- Когда какой-либо из них обнаруживается обычным неквалифицированным поиском по имени слева от оператора вызова функции, поиск, зависящий от аргумента запрещён.
На практике они могут быть реализованы как функциональные объекты или со специальными расширениями компилятора.
Содержание |
[править] Параметры
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
[править] Смотри также
(C++20) |
сортирует первые N элементов диапазона (ниблоид) |
(C++20) |
сортирует диапазон элементов, сохраняя порядок между равными элементами (ниблоид) |
(C++20) |
делит диапазон элементов на две группы (ниблоид) |
сортирует диапазон в порядке возрастания (шаблон функции) |