home | help 
std::ranges::nth_element(3)    C++ Standard Libary   std::ranges::nth_element(3)

NAME
     std::ranges::nth_element - std::ranges::nth_element

Synopsis
	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> 			     (1)
     (since C++20)
	constexpr I

	    nth_element( I first, I nth, S last, Comp comp = {}, Proj proj
	= {} );
	template< ranges::random_access_range R,

		  class Comp = ranges::less, class Proj = std::identity >
	requires std::sortable<iterator_t<R>, Comp,  Proj>		     (2)
     (since C++20)
	constexpr ranges::borrowed_iterator_t<R>

	    nth_element( R&& r, iterator_t<R> nth, Comp comp = {}, Proj
	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  ob-
     ject comp and
	projection object proj.
	2) Same as (1), but uses r as the 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, 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  inhib-
     ited.

	In  practice,  they may be implemented as function objects, or with spe-
     cial compiler
	extensions.

Parameters
	first, last - the range of elements to reorder
	r	    - the range of elements to reorder
	nth	    - the iterator defining the partition point
	comp	    - comparator used to compare the projected elements
	proj	    - projection to apply to the elements

Return value
	1) An iterator equal to last.
	2) Same as (1) if r is an lvalue or of a borrowed_range type.  Otherwise
     returns
	std::ranges::dangling.

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

Notes
	The algorithm used is typically introselect although other selection al-
     gorithms 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, 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

See also
	ranges::max_element  returns the largest element in a range
	(C++20) 	     (niebloid)
	ranges::min_element  returns the smallest element in a range
	(C++20) 	     (niebloid)
	ranges::partition    divides a range of elements into two groups
	(C++20) 	     (niebloid)
	ranges::partial_sort sorts the first N elements of a range
	(C++20) 	     (niebloid)
			     partially sorts the given range making sure that it
     is
	nth_element	     partitioned by the given element
			     (function template)

http://cppreference.com 	   2024.06.10	     std::ranges::nth_element(3)
home | help