std::ranges::nth_element
From cppreference.com
| Defined in header <algorithm>
|
||
| Call signature |
||
template< std::random_access_iterator I, std::sentinel_for<I> S,
class Comp = ranges::less, class Proj = std::identity >
requires std::sortable<I, Comp, Proj>
constexpr I
nth_element( I first, I nth, S last, Comp comp = {}, Proj proj = {} );
|
(1) | (since C++20) |
template< ranges::random_access_range R,
class Comp = ranges::less, class Proj = std::identity >
requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
constexpr ranges::borrowed_iterator_t<R>
nth_element( R&& r, iterator_t<R> nth, Comp comp = {}, Proj proj = {} );
|
(2) | (since C++20) |
template< /*execution-policy*/ Ep,
std::random_access_iterator I, std::sized_sentinel_for<I> S,
class Comp = ranges::less, class Proj = std::identity >
requires std::sortable<I, Comp, Proj>
I nth_element( Ep&& policy, I first, I nth, S last,
Comp comp = {}, Proj proj = {} );
|
(3) | (since C++26) |
template< /*execution-policy*/ Ep, /*sized-random-access-range*/ R,
class Comp = ranges::less, class Proj = std::identity >
requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
ranges::borrowed_iterator_t<R>
nth_element( Ep&& policy, R&& r, ranges::iterator_t<R> nth,
Comp comp = {}, Proj proj = {} );
|
(4) | (since C++26) |
For the definition of /*execution-policy*/, see this page; for the definition of /*sized-random-access-range*/, see this page.
1) Let
[sorted_first, sorted_last) be a hypothetical (random-access) range containing all elements of the target range [first, last) and is sorted with respect to the comparator comp and projection proj. Rearranges elements in the target range such that after the rearrangement:
[first,nth)is a permutation of[sorted_first,sorted_first + (nth - first)).- If
nth == lastisfalse:nthpoints to the element corresponding to the element atsorted_first + (nth - first).[nth + 1,last)is a permutation of[sorted_first + (nth - first) + 1,sorted_last).
2) Same as (1), but uses
ranges::begin(r) as first and ranges::end(r) as last.3) Same as (1), but executed according to
policy.4) Same as (3), but uses
ranges::begin(r) as first and ranges::begin(r) + ranges::distance(r) as last.The function-like entities described on this page are algorithm function objects (informally known as niebloids), that is:
- Explicit template argument lists cannot be specified when calling any of them.
- None of them are visible to argument-dependent lookup.
- When any of them are found by normal unqualified lookup as the name to the left of the function-call operator, argument-dependent lookup is inhibited.
Parameters
| first, last | - | the iterator-sentinel pair defining the target range |
| r | - | the target range |
| nth | - | the iterator indicating the “partition” point |
| comp | - | the comparator to be applied to the (projected) elements |
| proj | - | the projection to be applied to the elements |
| policy | - | the execution policy to use |
Return value
The past-the-end iterator of the target range.
Complexity
Given N as ranges::distance(first, last) or ranges::distance(r):
1,2) 𝓞(N) applications of
comp on average, and twice as many applications of proj.3,4) 𝓞(N) applications of
comp, twice as many applications of proj, and 𝓞(N·log(N)) swaps.Exceptions
3,4) During the execution process:
- If the temporary memory resources required for parallelization are not available, std::bad_alloc is thrown.
- If an uncaught exception is thrown while accessing objects via an algorithm argument, the behavior is determined by the execution policy (for standard policies, std::terminate is invoked).
Notes
The algorithm used is typically Introselect although other Selection algorithm with suitable average-case complexity are allowed.
Possible implementation
See also the implementation in msvc stl, libstdc++, and libc++: (1) / (2).
Example
Run this code
#include <algorithm>
#include <array>
#include <functional>
#include <iostream>
#include <ranges>
#include <string_view>
void print(std::string_view rem, const std::ranges::input_range auto& a)
{
for (std::cout << rem; const auto e : a)
std::cout << e << ' ';
std::cout << '\n';
}
int main()
{
std::array v{5, 6, 4, 3, 2, 6, 7, 9, 3};
print("Before nth_element: ", v);
std::ranges::nth_element(v, v.begin() + v.size() / 2);
print("After nth_element: ", v);
std::cout << "The median is: " << v[v.size() / 2] << '\n';
std::ranges::nth_element(v, v.begin() + 1, std::greater<int>());
print("After nth_element (descending): ", v);
std::cout << "The second largest element is: " << v[1] << '\n';
std::cout << "The largest element is: " << v[0] << "\n\n";
using namespace std::literals;
std::array names
{
"Diva"sv, "Cornelius"sv, "Munro"sv, "Rhod"sv,
"Zorg"sv, "Korben"sv, "Bender"sv, "Leeloo"sv,
};
print("Before nth_element: ", names);
auto fifth_element{std::ranges::next(names.begin(), 4)};
std::ranges::nth_element(names, fifth_element);
print("After nth_element: ", names);
std::cout << "The 5th element is: " << *fifth_element << '\n';
}
Possible output:
Before nth_element: 5 6 4 3 2 6 7 9 3
After nth_element: 2 3 3 4 5 6 6 7 9
The median is: 5
After nth_element (descending): 9 7 6 6 5 4 3 3 2
The second largest element is: 7
The largest element is: 9
Before nth_element: Diva Cornelius Munro Rhod Zorg Korben Bender Leeloo
After nth_element: Diva Cornelius Bender Korben Leeloo Rhod Munro Zorg
The 5th element is: Leeloo