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

FreeBSD Manual Pages

  
 
  

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

NAME
       std::stable_sort	- std::stable_sort

Synopsis
	  Defined in header <algorithm>
	  template<		  class		      RandomIt		     >
       (1)
	  void stable_sort( RandomIt first, RandomIt last );
	  template< class ExecutionPolicy, class RandomIt >
	  void	stable_sort(   ExecutionPolicy&&   policy,   RandomIt	first,
       (2) (since C++17)
	  RandomIt last	);
	  template<	  class	      RandomIt,	     class	Compare	     >
       (3)
	  void stable_sort( RandomIt first, RandomIt last, Compare comp	);
	  template< class ExecutionPolicy, class RandomIt, class Compare >
	  void	stable_sort(   ExecutionPolicy&&   policy,   RandomIt	first,
       (4) (since C++17)
	  RandomIt last, Compare comp );

	  Sorts	 the elements in the range [first, last) in non-descending or-
       der. The	order of
	  equivalent elements is guaranteed to be preserved.

	  A sequence is	sorted with respect to a comparator comp  if  for  any
       iterator	it
	  pointing to the sequence and any non-negative	integer	n such that it
       + n is a	valid
	  iterator  pointing  to  an  element of the sequence, comp(*(it + n),
       *it) (or	*(it + n)
	  < *it) evaluates to false.

	  1) Elements are compared using operator<.
	  3) Elements are compared using the given comparison function comp.
	  2,4) Same as (1,3), but executed according to	 policy.  These	 over-
       loads do	not
	  participate in overload resolution unless
	  std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>
	  (until C++20)
	  std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>
	  (since C++20)	is true.

Parameters
	  first, last -	 the range of elements to sort
	  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 ValueSwappable	and
	  LegacyRandomAccessIterator.
	  -
	  The type of dereferenced RandomIt  must  meet	 the  requirements  of
       MoveAssignable and
	  MoveConstructible.

Return value
	  (none)

Complexity
	  O(Nlog(N)^2),	 where	N = std::distance(first, last) applications of
       cmp. If
	  additional memory is available, then the complexity is O(Nlog(N)).

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.

Notes
	  This	function attempts to allocate a	temporary buffer equal in size
       to the sequence
	  to be	sorted.	If the allocation fails, the less efficient  algorithm
       is chosen.

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

Example
       // Run this code

	#include <algorithm>
	#include <iostream>
	#include <string>
	#include <vector>

	struct Employee
	{
	    int	age;
	    std::string	name;  // Does not participate in comparisons
	};

	bool operator<(const Employee &	lhs, const Employee & rhs)
	{
	    return lhs.age < rhs.age;
	}

	int main()
	{
	    std::vector<Employee> v =
	    {
		{108, "Zaphod"},
		{32, "Arthur"},
		{108, "Ford"},
	    };

	    std::stable_sort(v.begin(),	v.end());

	    for	(const Employee	& e : v)
		std::cout << e.age << ", " << e.name <<	'\n';
	}

Output:
	32, Arthur
	108, Zaphod
	108, Ford

See also
	  sort		      sorts a range into ascending order
			      (function	template)
	  partial_sort	      sorts the	first N	elements of a range
			      (function	template)
			      divides  elements	into two groups	while preserv-
       ing their relative
	  stable_partition    order
			      (function	template)
	  ranges::stable_sort sorts a range of elements	while preserving order
       between equal
	  (C++20)	      elements
			      (niebloid)

http://cppreference.com		  2022.07.31		   std::stable_sort(3)

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

home | help