std::nth_element() algorithm
- od C++20
- od C++17
- do C++17
// (1)
template< class RandomIt >
constexpr void nth_element( RandomIt first, RandomIt nth, RandomIt last );
// (2)
template< class RandomIt, class Compare >
constexpr void nth_element( RandomIt first, RandomIt nth, RandomIt last, Compare comp );
// (3)
template< class ExecutionPolicy, class RandomIt >
void nth_element( ExecutionPolicy&& policy, RandomIt first, RandomIt nth, RandomIt last );
// (4)
template< class ExecutionPolicy, class RandomIt, class Compare >
void nth_element( ExecutionPolicy&& policy, RandomIt first, RandomIt nth, RandomIt last, Compare comp );
// (1)
template< class RandomIt >
void nth_element( RandomIt first, RandomIt nth, RandomIt last );
// (2)
template< class RandomIt, class Compare >
void nth_element( RandomIt first, RandomIt nth, RandomIt last, Compare comp );
// (3)
template< class ExecutionPolicy, class RandomIt >
void nth_element( ExecutionPolicy&& policy, RandomIt first, RandomIt nth, RandomIt last );
// (4)
template< class ExecutionPolicy, class RandomIt, class Compare >
void nth_element( ExecutionPolicy&& policy, RandomIt first, RandomIt nth, RandomIt last, Compare comp );
// (1)
template< class RandomIt >
void nth_element( RandomIt first, RandomIt nth, RandomIt last );
// (2)
template< class RandomIt, class Compare >
void nth_element( RandomIt first, RandomIt nth, RandomIt last, Compare comp );
std::nth_element
is a partial sorting algorithm that rearranges elements in [first
; last
) such that:
- The element pointed at by
nth
is changed to whatever element would occur in that position if [first
;last
) were sorted. - All of the elements before this new nth element are less than or equal to the elements after the new
nth
element. - If
nth == last
then the function has no effect.
More formally, nth_element
partially sorts the range [first
; last
) in ascending order so that the condition
!(*j < *i)
(for (1, 3), or !comp(*j, *i)
for (2, 4)) is met for any i
in the range [first
; nth
)
and for any j
in the range [nth
; last
).
The element placed in the nth
position is exactly the element that would occur in this position if the range was fully sorted.
-
(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. |
nth | The iterator defining the sort partition point. |
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
(1, 2) Linear in std::distance(first, last)
on average.
(3, 4) Given N
as last - first
:
O(N) applications of the predicate, and O(N * log(N)) swaps.
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.
Notes
The algorithm used is typically Introselect although other Selection algorithm with suitable average-case complexity are allowed.
Examples
#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <numeric>
#include <vector>
void printVec(const std::vector<int>& vec)
{
std::cout << "v = {";
for (auto n {vec.size()}; const int i : vec)
std::cout << i << (--n ? ", " : "");
std::cout << "};\n";
}
int main()
{
std::vector<int> v {5, 10, 6, 4, 3, 2, 6, 7, 9, 3};
printVec(v);
auto m = v.begin() + v.size() / 2;
std::nth_element(v.begin(), m, v.end());
std::cout << "\nThe median is " << v[v.size() / 2] << '\n';
// The consequence of the inequality of elements before/after the Nth one:
assert(std::accumulate(v.begin(), m, 0) < std::accumulate(m, v.end(), 0));
printVec(v);
// Note: comp function changed
std::nth_element(v.begin(), v.begin() + 1, v.end(), std::greater{});
std::cout << "\nThe second largest element is " << v[1] << '\n';
std::cout << "The largest element is " << v[0] << '\n';
printVec(v);
}
v = {5, 10, 6, 4, 3, 2, 6, 7, 9, 3};
The median is 6
v = {3, 2, 3, 4, 5, 6, 10, 7, 9, 6};
The second largest element is 9
The largest element is 10
v = {10, 9, 6, 7, 6, 3, 5, 4, 3, 2};
Hover to see the original license.