std::stable_sort
来自 cppreference.cn
定义于头文件 <algorithm> |
||
template< class RandomIt > void stable_sort( RandomIt first, RandomIt last ); |
(1) | (C++26 起为 constexpr) |
template< class ExecutionPolicy, class RandomIt > void stable_sort( ExecutionPolicy&& policy, |
(2) | (C++17 起) |
template< class RandomIt, class Compare > void stable_sort( RandomIt first, RandomIt last, Compare comp ); |
(3) | (C++26 起为 constexpr) |
template< class ExecutionPolicy, class RandomIt, class Compare > void stable_sort( ExecutionPolicy&& policy, |
(4) | (C++17 起) |
以非降序对范围 [
first,
last)
中的元素进行排序。保证保持等价元素的顺序。
3) 元素根据 comp 排序。
2,4) 同 (1,3),但按 policy 执行。
仅当满足所有以下条件时,这些重载才参与重载决议
std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> 为 true。 |
(C++20 前) |
std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> 为 true。 |
(C++20 起) |
如果满足以下任何条件,则行为是未定义的:
|
(C++11 前) |
|
(C++11 起) |
目录 |
[编辑] 参数
first, last | - | 定义待排序元素 范围 的迭代器对 |
policy | - | 要使用的 执行策略 |
comp | - | 比较函数对象(即满足 Compare 要求的对象),若第一个参数小于(即在第二个参数之前排序)第二个参数则返回 true。 比较函数的签名应等效于以下内容 bool cmp(const Type1& a, const Type2& b); 尽管函数签名不需要含有 const&,但函数不可修改传递给它的对象,且必须能接受 |
类型要求 | ||
-RandomIt 必须满足 LegacyRandomAccessIterator 的要求。 | ||
-Compare 必须满足 Compare 的要求。 |
[编辑] 复杂度
给定 N 为 last - first
1,2) 如果有足够的额外内存可用,使用 operator<(C++20 前)std::less{}(C++20 起) 进行 O(N·log(N)) 次比较,否则进行 O(N·log2
(N)) 次比较。
(N)) 次比较。
3,4) 如果有足够的额外内存可用,对比较器 comp 进行 O(N·log(N)) 次应用,否则进行 O(N·log2
(N)) 次应用。
(N)) 次应用。
[编辑] 异常
带有模板参数 ExecutionPolicy
的重载按如下方式报告错误
- 若作为算法一部分调用的函数执行抛出异常,且
ExecutionPolicy
为标准策略之一,则调用 std::terminate。对于任何其他ExecutionPolicy
,行为是实现定义的。 - 如果算法未能分配内存,则抛出 std::bad_alloc。
[编辑] 可能的实现
[编辑] 注意
此函数尝试分配一个大小等于要排序序列的临时缓冲区。如果分配失败,则选择效率较低的算法。
特性测试宏 | 值 | 标准 | 特性 |
---|---|---|---|
__cpp_lib_constexpr_algorithms |
202306L |
(C++26) | constexpr 稳定排序,重载 (1)、(3) |
[编辑] 示例
运行此代码
#include <algorithm> #include <array> #include <iostream> #include <string> #include <vector> struct Employee { int age; std::string name; // Does not participate in comparisons }; bool operator<(const Employee& lhs, const Employee& rhs) { return lhs.age < rhs.age; } #if __cpp_lib_constexpr_algorithms >= 202306L consteval auto get_sorted() { auto v = std::array{3, 1, 4, 1, 5, 9}; std::stable_sort(v.begin(), v.end()); return v; } static_assert(std::ranges::is_sorted(get_sorted())); #endif int main() { std::vector<Employee> v{{108, "Zaphod"}, {32, "Arthur"}, {108, "Ford"}}; std::stable_sort(v.begin(), v.end()); for (const Employee& e : v) std::cout << e.age << ", " << e.name << '\n'; }
输出
32, Arthur 108, Zaphod 108, Ford
[编辑] 另请参阅
将一个范围按升序排序 (函数模板) | |
对一个范围的前 N 个元素进行排序 (函数模板) | |
将元素分成两组,同时保留它们的相对顺序 (函数模板) | |
(C++20) |
对一个范围的元素进行排序,同时保留相等元素之间的顺序 (算法函数对象) |