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

NAME
     std::ranges::stable_sort - std::ranges::stable_sort

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
     (since C++20)
	>								     (1)
     (constexpr since
	requires	     std::sortable<I,		  Comp, 	   Proj>
     C++26)

	    I stable_sort( I first, S last, Comp comp = {}, Proj proj =
	{} );
	template< ranges::random_access_range R, class Comp =
	ranges::less,
									    (since
     C++20)
		  class  Proj  =  std::identity  >			     (2)
     (constexpr since
	requires      std::sortable<ranges::iterator_t<R>,	Comp,	   Proj>
     C++26)
	ranges::borrowed_iterator_t<R>

	    stable_sort( R&& r, Comp comp = {}, Proj proj = {} );

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

	A sequence is sorted with respect to a comparator comp if for any itera-
     tor 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, std::invoke(comp,
     std::invoke(proj,
	*(it + n)), std::invoke(proj, *it) evaluates to false.

	1) Elements are compared using	the  given  binary  comparison	function
     comp.
	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 - iterator-sentinel defining the range to sort
	r	    - the range to sort
	comp	    - comparison to apply to the projected elements
	proj	    - projection to apply to the elements

Return value
	An iterator equal to last.

Complexity
	\(\scriptsize N\cdot\log{(N)}\)NA.log(N) comparisons, if extra memory is
     available;
	where \(\scriptsize N\)N is ranges::distance(first, last). \(\scriptsize
	N\cdot\log^2{(N)}\)NA.logA^2(N) comparisons  otherwise.  Twice	as  many
     projections as the
	number of comparisons in both cases.

Notes
	      Feature-test macro	Value  Std	   Feature
	__cpp_lib_constexpr_algorithms 202306L	   constexpr stable sorting

Possible implementation
	This  implementation  only shows the slower algorithm used when no addi-
     tional memory
	is available. See also implementation in MSVC STL and libstdc++.

     struct stable_sort_fn {
	 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>
	 constexpr //< since C++26
	 I operator()(I first, S last, Comp comp = {}, Proj proj = {}) const
	 {
	     auto count = ranges::distance(first, last);
	     auto mid = first + count / 2;
	     auto last_it = first + count;

	     if (count <= 1)
		 return last_it;

	     (*this)(first, mid, std::ref(comp), std::ref(proj));
	     (*this)(mid, last_it, std::ref(comp), std::ref(proj));

	     ranges::inplace_merge(first, mid, last_it);

	     return last_it;
	 }

	 template<ranges::random_access_range R, class Comp = ranges::less,
		  class Proj = std::identity>
	 requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
	 constexpr //< since C++26
	 ranges::borrowed_iterator_t<R> operator()(R&& r, Comp comp =  {},  Proj
     proj = {}) const
	 {
	     return  (*this)(ranges::begin(r),	ranges::end(r), std::move(comp),
     std::move(proj));
	 } };

     inline constexpr stable_sort_fn stable_sort {};

Example
     // Run this code

      #include <algorithm>
      #include <array>
      #include <functional>
      #include <iomanip>
      #include <iostream>

      void print(auto const& seq)
      {
	  for (auto const& elem : seq)
	      std::cout << elem << ' ';
	  std::cout << '\n';
      }

      struct Particle
      {
	  std::string name; double mass; // MeV
	  friend std::ostream& operator<<(std::ostream& os, Particle const& p)
	  {
	      return os << '\n' << std::left << std::setw(8) << p.name << " :  "
     << p.mass;
	  }
      };

      int main()
      {
	  std::array s {5, 7, 4, 2, 8, 6, 1, 9, 0, 3};

	  // sort using the default operator<
	  std::ranges::stable_sort(s);
	  print(s);

	  // sort using a standard library compare function object
	  std::ranges::stable_sort(s, std::ranges::greater());
	  print(s);

	  // sort using a custom function object
	  struct
	  {
	      bool operator()(int a, int b) const
	      {
		  return a < b;
	      }
	  } customLess;
	  std::ranges::stable_sort(s.begin(), s.end(), customLess);
	  print(s);

	  // sort using a lambda expression
	  std::ranges::stable_sort(s, [](int a, int b) { return a > b; });
	  print(s);

	  // sort with projection
	  Particle particles[]
	  {
	      {"Electron", 0.511}, {"Muon", 105.66}, {"Tau", 1776.86},
	      {"Positron", 0.511}, {"Proton", 938.27}, {"Neutron", 939.57}
	  };
	  print(particles);
	  std::ranges::stable_sort(particles,  {}, &Particle::name); //< sort by
     name
	  print(particles);
	  std::ranges::stable_sort(particles, {}, &Particle::mass); //< sort  by
     mass
	  print(particles);
      }

Output:
      0 1 2 3 4 5 6 7 8 9
      9 8 7 6 5 4 3 2 1 0
      0 1 2 3 4 5 6 7 8 9
      9 8 7 6 5 4 3 2 1 0

      Electron : 0.511
      Muon     : 105.66
      Tau      : 1776.86
      Positron : 0.511
      Proton   : 938.27
      Neutron  : 939.57

      Electron : 0.511
      Muon     : 105.66
      Neutron  : 939.57
      Positron : 0.511
      Proton   : 938.27
      Tau      : 1776.86

      Electron : 0.511
      Positron : 0.511
      Muon     : 105.66
      Proton   : 938.27
      Neutron  : 939.57
      Tau      : 1776.86

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

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