std::ranges::stable_sort
Defined in header <algorithm> |
||
|---|---|---|
| Call signature | ||
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 = {} ); |
(1) | (since 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>
ranges::borrowed_iterator_t<R>
stable_sort( R&& r, Comp comp = {}, Proj proj = {} ); |
(2) | (since C++20) |
Sorts the elements in the range [first, last) in non-descending order. The order of equivalent elements is stable, i.e. guaranteed to be preserved.
A sequence is sorted with respect to a comparator comp if for any iterator it pointing to the sequence and any non-negative integer n such that it + n is a valid iterator pointing to an element of the sequence, std::invoke(comp, std::invoke(proj, *(it + n)), std::invoke(proj, *it) evaluates to false.
comp.
r as the range, as if using
ranges::begin(r) as
first and
ranges::end(r) as
last.
The function-like entities described on this page are niebloids, that is:
- Explicit template argument lists may not be specified when calling any of them.
- None of them is visible to argument-dependent lookup.
- When one of them is found by normal unqualified lookup for the name to the left of the function-call operator, it inhibits argument-dependent lookup.
In practice, they may be implemented as function objects, or with special compiler extensions.
Parameters
| first, last | - | iterator-sentinel defining the range to sort |
| r | - | the range to sort |
| comp | - | comparison to apply to the projected elements |
| proj | - | projection to apply to the elements |
Return value
An iterator equal to last.
Complexity
\(\scriptsize N\cdot\log{(N)}\)N·log(N) comparisons, if extra memory is available; where \(\scriptsize N\)N is ranges::distance(first, last). \(\scriptsize N\cdot\log^2{(N)}\)N·log²(N) comparisons otherwise. Twice as many projections as the number of comparisons in both cases.
Possible implementation
This implementation only shows the slower algorithm used when no additional memory is available. See also implementation in MSVC STL and 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>
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>
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{};
|
Example
#include <algorithm>
#include <array>
#include <functional>
#include <iomanip>
#include <iostream>
void print(auto const& seq) {
for (auto const& elem : seq)
std::cout << elem << ' ';
std::cout << '\n';
}
struct Particle {
std::string name; double mass; // MeV
friend std::ostream& operator<< (std::ostream& os, Particle const& 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};
// sort using the default operator<
std::ranges::stable_sort(s);
print(s);
// sort using a standard library compare function object
std::ranges::stable_sort(s, std::ranges::greater());
print(s);
// sort using a custom function object
struct {
bool operator()(int a, int b) const {
return a < b;
}
} customLess;
std::ranges::stable_sort(s.begin(), s.end(), customLess);
print(s);
// sort using a lambda expression
std::ranges::stable_sort(s, [](int a, int b) {
return a > b;
});
print(s);
// sort with 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); //< sort by name
print(particles);
std::ranges::stable_sort(particles, {}, &Particle::mass); //< sort by mass
print(particles);
}
Output:
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
See also
|
(C++20)
|
sorts a range into ascending order (niebloid) |
|
(C++20)
|
sorts the first N elements of a range (niebloid) |
|
(C++20)
|
divides elements into two groups while preserving their relative order (niebloid) |
| sorts a range of elements while preserving order between equal elements (function template) |
© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/w/cpp/algorithm/ranges/stable_sort
