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

FreeBSD Manual Pages

  
 
  

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
       object comp and
	  projection object proj.
	  2)  Same  as	(1),  but uses r as the	range, as if using ranges::be-
       gin(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 call-
       ing 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 in-
       hibited.

	  In practice, they may	be implemented as function  objects,  or  with
       special 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.	Other-
       wise returns
	  std::ranges::dangling.

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

Notes
	  The algorithm	used is	typically introselect although other selection
       algorithms 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)

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

home | help