std::sort() algorithm
- od C++20
- od C++17
- do C++17
// (1)
template< class RandomIt >
constexpr void sort( RandomIt first, RandomIt last );
// (2)
template< class RandomIt, class Compare >
constexpr void sort( RandomIt first, RandomIt last, Compare comp );
// (3)
template< class ExecutionPolicy, class RandomIt >
void sort( ExecutionPolicy&& policy, RandomIt first, RandomIt last );
// (4)
template< class ExecutionPolicy, class RandomIt, class Compare >
void sort( ExecutionPolicy&& policy, RandomIt first, RandomIt last, Compare comp );
// (1)
template< class RandomIt >
void sort( RandomIt first, RandomIt last );
// (2)
template< class RandomIt, class Compare >
void sort( RandomIt first, RandomIt last, Compare comp );
// (3)
template< class ExecutionPolicy, class RandomIt >
void sort( ExecutionPolicy&& policy, RandomIt first, RandomIt last );
// (4)
template< class ExecutionPolicy, class RandomIt, class Compare >
void sort( ExecutionPolicy&& policy, RandomIt first, RandomIt last, Compare comp );
// (1)
template< class RandomIt >
void sort( RandomIt first, RandomIt last );
// (3)
template< class RandomIt, class Compare >
void sort( RandomIt first, RandomIt last, Compare comp );
Sorts the elements in the range [first
; last
) in ascending order.
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, comp(*(it + n), *it)
(or *(it + n) < *it
) evaluates to false
.
The order of equal elements is not guaranteed to be preserved.
-
(1) Elements are compared using
operator<
. -
(2) Elements are compared using the given binary comparison function
comp
. -
(3, 4) Same as (1) and (2), but executed according to policy.
Overload ResolutionThese overloads participate in overload resolution only if
std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>
istrue
. (do C++20)std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>
istrue
. (od C++20)
Parameters
first last | The range of elements to sort. |
policy | The execution policy to use. See execution policy for details. |
cmp | Comparison function object (i.e. an object that satisfies the requirements of Compare). The signature of the comparison function should be equivalent to the following:
|
Type requirements
RandomIt | ValueSwappable LegacyRandomAccessIterator |
Type of dereferenced RandomIt | MoveAssignable MoveConstructible |
Compare | Compare |
Return value
(none)
Complexity
Regardless of implementation, guaranteed O(N * log(N)) comparisons, where N is std::distance(first, last)
.
Exceptions
The overloads with a template parameter named ExecutionPolicy
report errors as follows:
- If execution of a function invoked as part of the algorithm throws an exception and
ExecutionPolicy
is one of the standard policies,std::terminate
is called. For any otherExecutionPolicy
, the behavior is implementation-defined. - If the algorithm fails to allocate memory,
std::bad_alloc
is thrown.
Possible implementation
See implementations from libstdc++ and libc++.
Notes
Before LWG713
, the complexity requirement allowed sort()
to be implemented using only Quicksort,
which may need O(N2) comparisons in the worst case.
Introsort can handle all cases with O(N * log(N)) comparisons (without incurring additional overhead in the average case), and thus is usually used for implementing sort()
.
libc++ has not implemented the corrected time complexity requirement until LLVM 14
.
Examples
#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
Hover to see the original license.