std::sort
来自cppreference.com
| 在标头 <algorithm> 定义
|
||
| (1) | ||
| template< class RandomIt > void sort( RandomIt first, RandomIt last ); |
(C++20 前) | |
| template< class RandomIt > constexpr void sort( RandomIt first, RandomIt last ); |
(C++20 起) | |
| template< class ExecutionPolicy, class RandomIt > void sort( ExecutionPolicy&& policy, RandomIt first, RandomIt last ); |
(2) | (C++17 起) |
| (3) | ||
| template< class RandomIt, class Compare > void sort( RandomIt first, RandomIt last, Compare comp ); |
(C++20 前) | |
| template< class RandomIt, class Compare > constexpr void sort( RandomIt first, RandomIt last, Compare comp ); |
(C++20 起) | |
| template< class ExecutionPolicy, class RandomIt, class Compare > void sort( ExecutionPolicy&& policy, |
(4) | (C++17 起) |
以不降序排序范围 [first, last) 中的元素。不保证维持相等元素的顺序。
如果对于任何指向序列的迭代器 it 与任何使得 it + n 为指向序列元素的合法迭代器的非负整数 n，comp(*(it + n), *it) 求值为 false，那么称序列相对于 comp 已排序。
1) 用 operator< 比较元素。
3) 用给定的二元比较函数 comp 比较元素。
2,4) 同 (1,3)，但按照 policy 执行。这些重载只有在 std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> (C++20 前)std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> (C++20 起) 是 true 时才会参与重载决议。
目录 |
[编辑] 参数
| first, last | - | 要排序的元素范围 |
| policy | - | 所用的执行策略。细节见执行策略。 |
| comp | - | 比较函数对象（即满足比较 (Compare) 概念的对象），在第一参数小于（即先序于）第二参数时返回 true。 比较函数的签名应等价于如下： bool cmp(const Type1 &a, const Type2 &b); 虽然签名不必有 |
| 类型要求 | ||
-RandomIt 必须符合值可交换 (ValueSwappable) 和 老式随机访问迭代器 (LegacyRandomAccessIterator) 的要求。
| ||
-解引用 RandomIt 结果的类型必须满足可移动赋值 (MoveAssignable) 和可移动构造 (MoveConstructible) 的要求。
| ||
-Compare 必须符合比较 (Compare) 的要求。
| ||
[编辑] 返回值
（无）
[编辑] 复杂度
O(N·log(N)) 次比较，其中 N 是 std::distance(first, last)。
[编辑] 异常
拥有名为 ExecutionPolicy 的模板形参的重载按下列方式报告错误：
- 如果作为算法一部分调用的函数的执行抛出异常，且
ExecutionPolicy是标准策略之一，那么调用 std::terminate。对于任何其他ExecutionPolicy，行为由实现定义。 - 如果算法无法分配内存，那么抛出 std::bad_alloc。
[编辑] 可能的实现
[编辑] 示例
运行此代码
#include <algorithm> #include <array> #include <functional> #include <iostream> #include <string_view> int main() { std::array<int, 10> s = {5, 7, 4, 2, 8, 6, 1, 9, 0, 3}; auto print = [&s](std::string_view const rem) { for (auto a : s) std::cout << a << ' '; std::cout << "：" << rem << '\n'; }; std::sort(s.begin(), s.end()); print("用默认的 operator< 排序"); std::sort(s.begin(), s.end(), std::greater<int>()); print("用标准库比较函数对象排序"); struct { bool operator()(int a, int b) const { return a < b; } } customLess; std::sort(s.begin(), s.end(), customLess); print("用自定义函数对象排序"); std::sort(s.begin(), s.end(), [](int a, int b) { return a > b; }); print("用 lambda 表达式排序"); }
输出：
0 1 2 3 4 5 6 7 8 9 ：用默认的 operator< 排序 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 ：用 lambda 表达式排序
[编辑] 缺陷报告
下列更改行为的缺陷报告追溯地应用于以前出版的 C++ 标准。
| 缺陷报告 | 应用于 | 出版时的行为 | 正确行为 |
|---|---|---|---|
| LWG 713 | C++98 | 没有强制复杂度要求[1] | 只允许 O(N·log(N)) 次比较 |
- ↑ 之前的复杂度要求是“平均大约 O(N·log(N)) 次比较”。这样就可以使用快速排序实现
sort()，因为它在最差情况可能会需要 O(N2
) 或更多次比较。然而，内省排序只需要 O(N·log(N)) 次比较就能处理所有情况，而且对于通常情况不会有额外开销。因此可以强制要求复杂度。
[编辑] 参阅
| 排序一个范围的前 N 个元素 (函数模板) | |
| 将范围内的元素排序，同时保持相等的元素之间的顺序 (函数模板) | |
| (C++20) |
将范围按升序排序 (niebloid) |
