Skip site navigation (1)Skip section navigation (2)

FreeBSD Manual Pages

  
 
  

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) (const-
       expr 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) (const-
       expr 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
       rearrangement:

	    *  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 un-
       defined:

	    * [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
       details.
			 comparison function object (i.e. an object that  sat-
       isfies 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
       equivalent 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  re-
       gardless	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(Nlog(N))
       swaps.
	  3)  \(\scriptsize  O(N)\)O(N)	applications of	the comparator comp on
       average.
	  4) \(\scriptsize O(N)\)O(N) applications of the comparator comp, and
       \(\scriptsize
	  O(N \cdot \log(N))\)O(Nlog(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::termi-
       nate is called.
	      For  any	other ExecutionPolicy, the behavior is implementation-
       defined.
	    * 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
       algorithm 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		  Cor-
       rect behavior
			      after the	rearrangement, only one
	  LWG 2150 C++98      element before nth		     corrected
       the
			      was  required to be not greater than    require-
       ment
			      one element after	nth
	  P0896R4  C++98      [first, nth) and [nth, last)	      the  be-
       havior 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
       between 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)

Want to link to this manual page? Use this URL:
<https://man.freebsd.org/cgi/man.cgi?query=std::nth_element&sektion=3&manpath=FreeBSD+Ports+15.1.quarterly>

home | help