std::sort
在头文件 <algorithm> 中定义 |
||
template< class RandomIt > void sort( RandomIt first, RandomIt last ); |
(1) | (自 C++20 起为 constexpr) |
template< class ExecutionPolicy, class RandomIt > void sort( ExecutionPolicy&& policy, |
(2) | (自 C++17 起) |
template< class RandomIt, class Compare > void sort( RandomIt first, RandomIt last, Compare comp ); |
(3) | (自 C++20 起为 constexpr) |
template< class ExecutionPolicy, class RandomIt, class Compare > void sort( ExecutionPolicy&& policy, |
(4) | (自 C++17 起) |
对范围 [
first,
last)
中的元素进行非递减排序。不保证相等元素的顺序被保留。
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 | - | 比较函数对象(即满足 比较 要求的对象),如果第一个参数小于(即在之前排序)第二个参数,则返回 true。 比较函数的签名应等效于以下内容 bool cmp(const Type1& a, const Type2& b); 虽然签名不需要包含 const&,但函数必须不能修改传递给它的对象,并且必须能够接受类型为(可能是常量) |
类型要求 | ||
-RandomIt 必须满足 LegacyRandomAccessIterator 的要求。 | ||
-Compare 必须满足 Compare 的要求。 |
[编辑] 复杂度
假设 N 为 last - first
[编辑] 异常
带有名为 ExecutionPolicy
的模板参数的重载会报告以下错误
- 如果作为算法一部分调用的函数的执行抛出异常,并且
ExecutionPolicy
是 标准策略 之一,则会调用 std::terminate。对于任何其他ExecutionPolicy
,行为由实现定义。 - 如果算法未能分配内存,则会抛出 std::bad_alloc。
[编辑] 可能的实现
[编辑] 说明
在 LWG713 之前,复杂度要求允许 sort()
仅使用 快速排序 来实现,这在最坏情况下可能需要 O(N2
) 次比较。
内省排序 可以用 O(N·log(N)) 次比较来处理所有情况(不会在平均情况下产生额外的开销),因此通常用于实现 sort()
。
libc++ 直到 LLVM 14 才实现了修正后的时间复杂度要求。
[编辑] 示例
#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("sorted with the default operator<"); std::sort(s.begin(), s.end(), std::greater<int>()); print("sorted with the standard library compare function object"); struct { bool operator()(int a, int b) const { return a < b; } } customLess; std::sort(s.begin(), s.end(), customLess); print("sorted with a custom function object"); std::sort(s.begin(), s.end(), [](int a, int b) { return a > b; }); print("sorted with a lambda expression"); }
输出
0 1 2 3 4 5 6 7 8 9 : sorted with the default operator< 9 8 7 6 5 4 3 2 1 0 : sorted with the standard library compare function object 0 1 2 3 4 5 6 7 8 9 : sorted with a custom function object 9 8 7 6 5 4 3 2 1 0 : sorted with a lambda expression
[编辑] 缺陷报告
以下行为更改缺陷报告已追溯应用于之前发布的 C++ 标准。
DR | 应用于 | 已发布的行为 | 正确行为 |
---|---|---|---|
LWG 713 | C++98 | 仅在平均情况下需要 O(N·log(N)) 的时间复杂度 | 在最坏情况下也是必须的 |
[编辑] 另请参阅
对范围的前 N 个元素进行排序 (函数模板) | |
对元素范围进行排序,同时保留相等元素之间的顺序 (函数模板) | |
(C++20) |
将范围排序为升序 (niebloid) |