Przejdź do głównej zawartości

std::ranges::stable_sort() algorithm

// (1)
I stable_sort( I first, S last, Comp comp = {}, Proj proj = {} );

// (2)
ranges::borrowed_iterator_t<R> stable_sort( R&& r, Comp comp = {}, Proj proj = {} );

The type of arguments are generic and have following constraints:

  • I - std::random_access_iterator
  • S - std::sentinel_for<I>
  • R - std::ranges::random_access_range
  • Comp - (none)
  • Proj - (none)

The Proj and Comp template arguments have, the following default types for all overloads: std::identity, ranges::less.

Additionally, each overload has the following constraints:

  • (1) - sortable<I, Comp, Proj>
  • (2) - sortable<ranges::iterator_t<R>, Comp, Proj>

(The std:: namespace was ommitted here for readability)

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.

  • (1) Elements are compared using the given binary comparison function comp.

  • (2) Same as (1), but uses r as the source 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.

Parameters

first
last

The range to sort.

r

The range to sort.

comp

Comparison object to apply to the projected elements.

proj

Projection to apply to the elements.

Return value

An iterator equal to last.

Complexity

Given N as ranges::distance(first, last):

N * log^2(N) comparisons and twice as many projections.

N * log (N) comparisons and twice as many projections, if extra memory is available;

Exceptions

(none)

Possible implementation

stable_sort(1) and stable_sort(2)
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 //< since 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 //< since 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 {};

Examples

Main.cpp
#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
This article originates from this CppReference page. It was likely altered for improvements or editors' preference. Click "Edit this page" to see all changes made to this document.
Hover to see the original license.

std::ranges::stable_sort() algorithm

// (1)
I stable_sort( I first, S last, Comp comp = {}, Proj proj = {} );

// (2)
ranges::borrowed_iterator_t<R> stable_sort( R&& r, Comp comp = {}, Proj proj = {} );

The type of arguments are generic and have following constraints:

  • I - std::random_access_iterator
  • S - std::sentinel_for<I>
  • R - std::ranges::random_access_range
  • Comp - (none)
  • Proj - (none)

The Proj and Comp template arguments have, the following default types for all overloads: std::identity, ranges::less.

Additionally, each overload has the following constraints:

  • (1) - sortable<I, Comp, Proj>
  • (2) - sortable<ranges::iterator_t<R>, Comp, Proj>

(The std:: namespace was ommitted here for readability)

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.

  • (1) Elements are compared using the given binary comparison function comp.

  • (2) Same as (1), but uses r as the source 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.

Parameters

first
last

The range to sort.

r

The range to sort.

comp

Comparison object to apply to the projected elements.

proj

Projection to apply to the elements.

Return value

An iterator equal to last.

Complexity

Given N as ranges::distance(first, last):

N * log^2(N) comparisons and twice as many projections.

N * log (N) comparisons and twice as many projections, if extra memory is available;

Exceptions

(none)

Possible implementation

stable_sort(1) and stable_sort(2)
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 //< since 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 //< since 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 {};

Examples

Main.cpp
#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
This article originates from this CppReference page. It was likely altered for improvements or editors' preference. Click "Edit this page" to see all changes made to this document.
Hover to see the original license.