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

NAME
     std::ranges::stable_partition - std::ranges::stable_partition

Synopsis
	Defined in header <algorithm>
	Call signature
	template< std::bidirectional_iterator I, std::sentinel_for<I>
	S,

		  class Proj = std::identity,
		  std::indirect_unary_predicate<std::projected<I,
     (since C++20)
	Proj>>	 Pred	>						     (1)
     (constexpr since
	requires					      std::permutable<I>
     C++26)
	ranges::subrange<I>

	    stable_partition( I first, S last, Pred pred, Proj proj =
	{} );
	template< ranges::bidirectional_range R, class Proj =
	std::identity,

		  std::indirect_unary_predicate<
     (since C++20)
		      std::projected<ranges::iterator_t<R>,   Proj>>   Pred  (2)
     (constexpr since
	>
     C++26)
	requires std::permutable<ranges::iterator_t<R>>
	ranges::borrowed_subrange_t<R>

	    stable_partition( R&& r, Pred pred, Proj proj = {} );

	1) Reorders the elements in the range [first, last) in such a  way  that
     the
	projection  proj  of  all  elements for which the predicate pred returns
     true precede
	the projection proj of elements for which predicate pred returns  false.
     The
	algorithms is stable, i.e. the relative order of elements is preserved.
	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 - the range of elements to reorder
	r	    - the range of elements to reorder
	pred	    - predicate to apply to the projected elements
	proj	    - projection to apply to the elements

Return value
	1) An object equal to {pivot, last}, where pivot is an iterator  to  the
     first element
	of the second group.
	2)  Same as (1) if r is an lvalue or of a borrowed_range type. Otherwise
     returns
	std::ranges::dangling.

Complexity
	Given N = ranges::distance(first, last),  the  complexity  is  at  worst
     \(\scriptsize
	N\cdot\log{(N)}\)NA.log(N)   swaps,   and   only   \(\scriptsize  \math-
     cal{O}(N)\)dh(N) swaps
	in case an extra memory buffer is used. Exactly \(\scriptsize  N\)N  ap-
     plications of
	the predicate pred and projection proj.

Notes
	This function attempts to allocate a temporary buffer. If the allocation
     fails, the
	less efficient algorithm is chosen.

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

Possible implementation
	This  implementation does not use extra memory buffer and as such can be
     less
	efficient. See also the implementation in MSVC STL and libstdc++.

     struct stable_partition_fn {
	 template<std::bidirectional_iterator I, std::sentinel_for<I> S,
		  class Proj = std::identity,
		  std::indirect_unary_predicate<std::projected<I, Proj>> Pred>
	 requires std::permutable<I>
	 constexpr ranges::subrange<I>
	     operator()(I first, S last, Pred pred, Proj proj = {}) const
	 {
	     first = ranges::find_if_not(first, last, pred, proj);
	     I mid = first;
	     while (mid != last)
	     {
		 mid = ranges::find_if(mid, last, pred, proj);
		 if (mid == last)
		     break;
		 I last2 = ranges::find_if_not(mid, last, pred, proj);
		 ranges::rotate(first, mid, last2);
		 first = ranges::next(first, ranges::distance(mid, last2));
		 mid = last2;
	     }
	     return {std::move(first), std::move(mid)};
	 }

	 template<ranges::bidirectional_range R, class Proj = std::identity,
		  std::indirect_unary_predicate<
		      std::projected<ranges::iterator_t<R>, Proj>> Pred>
	 requires std::permutable<ranges::iterator_t<R>>
	 constexpr ranges::borrowed_subrange_t<R>
	     operator()(R&& r, Pred pred, Proj proj = {}) const
	 {
	     return (*this)(ranges::begin(r),  ranges::end(r),	std::move(pred),
     std::move(proj));
	 } };

     inline constexpr stable_partition_fn stable_partition {};

Example
     // Run this code

      #include <algorithm>
      #include <iostream>
      #include <iterator>
      #include <vector>

      namespace rng = std::ranges;

      template<std::permutable I, std::sentinel_for<I> S>
      constexpr void stable_sort(I first, S last)
      {
	  if (first == last)
	      return;

	  auto pivot = *rng::next(first, rng::distance(first, last) / 2, last);
	  auto left = [pivot](const auto& em) { return em < pivot; };
	  auto tail1 = rng::stable_partition(first, last, left);
	  auto right = [pivot](const auto& em) { return !(pivot < em); };
	  auto tail2 = rng::stable_partition(tail1, right);

	  stable_sort(first, tail1.begin());
	  stable_sort(tail2.begin(), tail2.end());
      }

      void print(const auto rem, auto first, auto last, bool end = true)
      {
	  std::cout << rem;
	  for (; first != last; ++first)
	      std::cout << *first << ' ';
	  std::cout << (end ? "\n" : "");
      }

      int main()
      {
	  const auto original = {9, 6, 5, 2, 3, 1, 7, 8};

	  std::vector<int> vi {};
	  auto even = [](int x) { return 0 == (x % 2); };

	  print("Original vector:\t", original.begin(), original.end(), "\n");

	  vi = original;
	  const auto ret1 = rng::stable_partition(vi, even);
	  print("Stable partitioned:\t", vi.begin(), ret1.begin(), 0);
	  print("a ", ret1.begin(), ret1.end());

	  vi = original;
	  const auto ret2 = rng::partition(vi, even);
	  print("Partitioned:\t\t", vi.begin(), ret2.begin(), 0);
	  print("a ", ret2.begin(), ret2.end());

	  vi = {16, 30, 44, 30, 15, 24, 10, 18, 12, 35};
	  print("Unsorted vector: ", vi.begin(), vi.end());

	  stable_sort(rng::begin(vi), rng::end(vi));
	  print("Sorted vector:   ", vi.begin(), vi.end());
      }

Possible output:
      Original vector:	      9 6 5 2 3 1 7 8
      Stable partitioned:     6 2 8 a 9 5 3 1 7
      Partitioned:	      8 6 2 a 5 3 1 7 9
      Unsorted vector: 16 30 44 30 15 24 10 18 12 35
      Sorted vector:   10 12 15 16 18 24 30 30 35 44

See also
	ranges::partition      divides a range of elements into two groups
	(C++20) 	       (niebloid)
	ranges::partition_copy	copies	a  range  dividing the elements into two
     groups
	(C++20) 	       (niebloid)
	ranges::is_partitioned determines if the range	is  partitioned  by  the
     given predicate
	(C++20) 	       (niebloid)
			       divides elements into two groups while preserving
     their
	stable_partition       relative order
			       (function template)

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