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

NAME
     std::nth_element - std::nth_element

Synopsis
	Defined in header <algorithm>
	template< class RandomIt >
	void  nth_element( RandomIt first, RandomIt nth, RandomIt (1) (constexpr
     since C++20)
	last );
	template< class ExecutionPolicy, class RandomIt >

	void  nth_element(  ExecutionPolicy&&  policy,		     (2)  (since
     C++17)

			  RandomIt first, RandomIt nth, RandomIt
	last );
	template< class RandomIt, class Compare >

	void  nth_element( RandomIt first, RandomIt nth, RandomIt (3) (constexpr
     since C++20)
	last,

			  Compare comp );
	template< class ExecutionPolicy, class RandomIt, class
	Compare >

	void  nth_element(  ExecutionPolicy&&  policy,		     (4)  (since
     C++17)
			  RandomIt first, RandomIt nth, RandomIt
	last,

			  Compare comp );

	nth_element rearranges elements in [first, last) such that after the re-
     arrangement:

	  *  The  element pointed at by nth is changed to whatever element would
     occur in that
	    position if [first, last) were sorted.
	  * For every iterator i in [first, nth) and every iterator j  in  [nth,
     last), the
	    following condition is met:
	1,2)
	bool(*j < *i)
	(until C++20)
	std::less{}(*j, *i)
	(since C++20) is false.
	3,4) bool(comp(*j, *i)) is false.

	1) Elements are hypothetically sorted with respect to
	operator<
	(until C++20)
	std::less{}
	(since C++20).
	3) Elements are hypothetically sorted with respect to comp.
	2,4) Same as (1,3), but executed according to policy.
	These overloads participate in overload resolution only if

	std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>    is    true.
     (until
										  C++20)
	std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>      is
     true. (since
										  C++20)

	If  any  of the following conditions is satisfied, the behavior is unde-
     fined:

	  * [first, nth) or [nth, last) is not a valid range.

	  * The type of *first is not Swappable.	   (until C++11)
	  * RandomIt is not ValueSwappable.
	  * The type of *first is not MoveConstructible.   (since C++11)
	  * The type of *first is not MoveAssignable.

Parameters
	first, last -  random access iterators defining the range sort
	nth	    -  random access iterator defining the sort partition point
	policy	    -  the execution policy to use. See execution policy for de-
     tails.
		       comparison function object (i.e. an object that satisfies
     the
		       requirements of Compare) which returns true if the  first
     argument is
		       less than (i.e. is ordered before) the second.

		       The signature of the comparison function should be equiv-
     alent to the
		       following:

		       bool cmp(const Type1& a, const Type2& b);
	comp	    -
		       While  the  signature  does  not need to have const&, the
     function must
		       not modify the objects passed to it and must be	able  to
     accept all
		       values  of  type (possibly const) Type1 and Type2 regard-
     less of value
		       category (thus, Type1& is not allowed
		       , nor is Type1 unless for Type1 a move is equivalent to a
     copy
		       (since C++11)).
		       The types Type1 and Type2 must be such that an object  of
     type
		       RandomIt  can  be  dereferenced	and then implicitly con-
     verted to both of
		       them.

Type requirements
	-
	RandomIt must meet the requirements of LegacyRandomAccessIterator.
	-
	Compare must meet the requirements of Compare.

Complexity
	Given \(\scriptsize N\)N as last - first:

	1) \(\scriptsize O(N)\)O(N) comparisons using
	operator<
	(until C++20)
	std::less{}
	(since C++20) on average.
	2) \(\scriptsize O(N)\)O(N) comparisons using
	operator<
	(until C++20)
	std::less{}
	(since C++20), and \(\scriptsize O(N \cdot \log(N))\)O(NA.log(N)) swaps.
	3) \(\scriptsize O(N)\)O(N) applications of the comparator comp on aver-
     age.
	4) \(\scriptsize O(N)\)O(N) applications of  the  comparator  comp,  and
     \(\scriptsize
	O(N \cdot \log(N))\)O(NA.log(N)) swaps.

Exceptions
	The overloads with a template parameter named ExecutionPolicy report er-
     rors 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  other  ExecutionPolicy, the behavior is implementation-de-
     fined.
	  * If the algorithm fails to allocate memory, std::bad_alloc is thrown.

Possible implementation
	See also the implementations in libstdc++, libc++, and msvc stl.

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

Example
     // Run this code

      #include <algorithm>
      #include <cassert>
      #include <functional>
      #include <iostream>
      #include <numeric>
      #include <vector>

      void printVec(const std::vector<int>& vec)
      {
	  std::cout << "v = {";
	  for (char sep[]{0, ' ', 0}; const int i : vec)
	      std::cout << sep << i, sep[0] = ',';
	  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);
      }

Possible output:
      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};

	Defect reports

	The following behavior-changing defect	reports  were  applied	retroac-
     tively to
	previously published C++ standards.

	   DR	  Applied  to	      Behavior as published		 Correct
     behavior
			    after the rearrangement, only one
	LWG 2150 C++98	    element before nth			   corrected the
			    was required to be not greater than    requirement
			    one element after nth
	P0896R4  C++98	    [first, nth) and [nth, last)	   the	behavior
     is undefined
			    were  not  required  to  be valid ranges   if any of
     them is invalid

See also
	max_element	    returns the largest element in a range
			    (function template)
	min_element	    returns the smallest element in a range
			    (function template)
	partial_sort_copy   copies and partially sorts a range of elements
			    (function template)
			    sorts a range of elements while preserving order be-
     tween equal
	stable_sort	    elements
			    (function template)
	sort		    sorts a range into ascending order
			    (function template)
	ranges::nth_element partially sorts the given range making sure that  it
     is
	(C++20) 	    partitioned by the given element
			    (niebloid)

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