std::ranges::stable_sort
来自cppreference.com
| 在标头 <algorithm> 定义
|
||
| 调用签名 |
||
| (1) | (C++20 起) (C++26 起为 constexpr) |
|
| (2) | (C++20 起) (C++26 起为 constexpr) |
|
以非降序排序范围 [first, last) 中的元素。等价元素的顺序是稳定的，即保证得到保持。
若对于指向序列的任何迭代器 it 与使得 it + n 为指向序列元素的合法迭代器的任何非负整数 n，std::invoke(comp, std::invoke(proj, *(it + n)), std::invoke(proj, *it))) 求值均为 false，则称序列为按照比较器 comp 与投影 proj 有序。
1) 用给定的二元比较函数
comp 比较元素。2) 同 (1)，但以
r 为范围，如同以 ranges::begin(r) 为 first 并以 ranges::end(r) 为 last。此页面上描述的函数式实体是算法函数对象（非正式地称为 niebloid），即：
参数
| first, last | - | 要排序的元素范围的迭代器-哨位对 |
| r | - | 要排序的范围 |
| comp | - | 应用到投影后元素的比较器 |
| proj | - | 应用到元素的投影 |
返回值
等于 last 的迭代器。
复杂度
若额外内存可用则比较 N·log(N) 次；其中 N 为 ranges::distance(first, last)。否则比较 N·log²(N) 次。两种情况下都进行二倍数量的投影。
注解
| 功能特性测试宏 | 值 | 标准 | 功能特性 |
|---|---|---|---|
__cpp_lib_constexpr_algorithms |
202306L |
(C++26) | constexpr 稳定排序
|
可能的实现
此实现仅展示无额外内存可用时使用的较慢的算法。参阅 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 //< 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{};
|
示例
运行此代码
#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};
// 以默认的 operator< 排序
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);
// 以 lambda 表达式排序
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
参阅
(C++20) |
将范围按升序排序 (算法函数对象) |
(C++20) |
将范围中前 N 个元素排序 (算法函数对象) |
(C++20) |
将元素分为两组，同时保留其相对顺序 (算法函数对象) |
| 将范围中元素排序，同时保持相等元之间的顺序 (函数模板) |