Przejdź do głównej zawartości

std::ranges::nth_element() algorithm

// (1)
constexpr I nth_element( I first, I nth, S last, Comp comp = {}, Proj proj = {} );

// (2)
constexpr ranges::borrowed_iterator_t<R>
nth_element( R&& r, iterator_t<R> nth, Comp comp = {}, Proj proj = {} );

The type of arguments are generic and have following constraints:

  • I - std::random_access_iterator
  • S - std::sentinel_for<I>
  • R - std::ranges::random_access_range
  • Comp - (none)
  • Proj - (none)

The Proj and Comp template arguments have, the following default types for all overloads: std::identity, ranges::less.

Additionally, each overload has the following constraints:

  • (1) - std::sortable<I, Comp, Proj>
  • (2) - std::sortable<ranges::iterator_t<R>, Comp, Proj>

Reorders the 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 with respect to comp and proj.

  • All of the elements before this new nth element are less than or equal to the elements after the new nth element. That is, for every iterator i, j in the ranges [first; nth), [nth; last) respectively, the expression std::invoke(comp, std::invoke(proj, *j), std::invoke(proj, *i)) evaluates to false.

  • If nth == last then the function has no effect.

  • (1) Elements are compared using the given binary comparison function comp and projection proj.

  • (2) Same as (1), but uses r as the source range, as if using ranges::begin(r) as first and ranges::end(r) as last.

The function-like entities described on this page are niebloids.

Parameters

first
last

The range to sort.

r

The range to sort.

nth

The iterator defining the sort partition point.

comp

Comparison object to apply to the projected elements.

proj

Projection to apply to the elements.

Return value

Complexity

Linear in ranges::distance(first, last) on average.

Exceptions

(none)

Notes

The algorithm used is typically Introselect although other Selection algorithm with suitable average-case complexity are allowed.

Examples

Main.cpp
#include <algorithm>
#include <array>
#include <functional>
#include <iostream>
#include <ranges>
#include <string_view>

void print(std::string_view rem, std::ranges::input_range auto const& 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: ", 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';
}
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: 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
This article originates from this CppReference page. It was likely altered for improvements or editors' preference. Click "Edit this page" to see all changes made to this document.
Hover to see the original license.

std::ranges::nth_element() algorithm

// (1)
constexpr I nth_element( I first, I nth, S last, Comp comp = {}, Proj proj = {} );

// (2)
constexpr ranges::borrowed_iterator_t<R>
nth_element( R&& r, iterator_t<R> nth, Comp comp = {}, Proj proj = {} );

The type of arguments are generic and have following constraints:

  • I - std::random_access_iterator
  • S - std::sentinel_for<I>
  • R - std::ranges::random_access_range
  • Comp - (none)
  • Proj - (none)

The Proj and Comp template arguments have, the following default types for all overloads: std::identity, ranges::less.

Additionally, each overload has the following constraints:

  • (1) - std::sortable<I, Comp, Proj>
  • (2) - std::sortable<ranges::iterator_t<R>, Comp, Proj>

Reorders the 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 with respect to comp and proj.

  • All of the elements before this new nth element are less than or equal to the elements after the new nth element. That is, for every iterator i, j in the ranges [first; nth), [nth; last) respectively, the expression std::invoke(comp, std::invoke(proj, *j), std::invoke(proj, *i)) evaluates to false.

  • If nth == last then the function has no effect.

  • (1) Elements are compared using the given binary comparison function comp and projection proj.

  • (2) Same as (1), but uses r as the source range, as if using ranges::begin(r) as first and ranges::end(r) as last.

The function-like entities described on this page are niebloids.

Parameters

first
last

The range to sort.

r

The range to sort.

nth

The iterator defining the sort partition point.

comp

Comparison object to apply to the projected elements.

proj

Projection to apply to the elements.

Return value

Complexity

Linear in ranges::distance(first, last) on average.

Exceptions

(none)

Notes

The algorithm used is typically Introselect although other Selection algorithm with suitable average-case complexity are allowed.

Examples

Main.cpp
#include <algorithm>
#include <array>
#include <functional>
#include <iostream>
#include <ranges>
#include <string_view>

void print(std::string_view rem, std::ranges::input_range auto const& 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: ", 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';
}
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: 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
This article originates from this CppReference page. It was likely altered for improvements or editors' preference. Click "Edit this page" to see all changes made to this document.
Hover to see the original license.