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

NAME
     std::stable_partition - std::stable_partition

Synopsis
	Defined in header <algorithm>
	template< class BidirIt, class UnaryPred >
	BidirIt  stable_partition( BidirIt first, BidirIt last,   (1) (constexpr
     since C++26)
	UnaryPred p );
	template< class ExecutionPolicy, class BidirIt, class
	UnaryPred >

	BidirIt  stable_partition(  ExecutionPolicy&&  policy,	     (2)  (since
     C++17)

				  BidirIt first, BidirIt last,
	UnaryPred p );

	1)  Reorders  the elements in the range [first, last) in such a way that
     all elements
	for which the predicate p returns true precede the  elements  for  which
     predicate p
	returns false. Relative order of the elements is preserved.
	2) Same as (1), but executed according to policy.
	This overload participates 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 unde-
     fined:

	  * The type of *first is not Swappable.	   (until C++11)
	  * BidirIt is not ValueSwappable.
	  * The type of *first is not MoveConstructible.   (since C++11)
	  * The type of *first is not MoveAssignable.

Parameters
	first, last -  the range of elements to reorder
	policy	    -  the execution policy to use. See execution policy for de-
     tails.
		       unary predicate which returns true if the element  should
     be ordered
		       before other elements.

		       The expression p(v) must be convertible to bool for every
     argument v
	p	     -	 of type (possibly const) VT, where VT is the value type
     of BidirIt,
		       regardless of value category,  and  must  not  modify  v.
     Thus, a
		       parameter type of VT&is not allowed
		       , nor is VT unless for VT a move is equivalent to a copy
		       (since C++11).

Type requirements
	-
	BidirIt must meet the requirements of LegacyBidirectionalIterator.
	-
	UnaryPred must meet the requirements of Predicate.

Return value
	Iterator to the first element of the second group.

Complexity
	Given \(\scriptsize N\)N as std::distance(first, last):

	1) Exactly \(\scriptsize N\)N applications of p.
	\(\scriptsize  O(N)\)O(N)  swaps if there is enough extra memory, other-
     wise at most
	\(\scriptsize N \cdot log_{2}(N)\)Nalog
	2(N) swaps.
	2) \(\scriptsize O(N)\)O(N) applications of p.
	\(\scriptsize N \cdot log(N)\)Nalog(N) swaps.

Exceptions
	The overload with a template parameter named ExecutionPolicy reports er-
     rors 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::terminate
     is called.
	    For any other ExecutionPolicy, the	behavior  is  implementation-de-
     fined.
	  * If the algorithm fails to allocate memory, std::bad_alloc is thrown.

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

	Implementations in libc++ and libstdc++ also accept ranges denoted by
	LegacyForwardIterators as an extension.

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

Example
     // Run this code

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

      int main()
      {
	  std::vector<int> v{0, 0, 3, -1, 2, 4, 5, 0, 7};
	  std::stable_partition(v.begin(),  v.end(),  [](int  n) { return n > 0;
     });
	  for (int n : v)
	      std::cout << n << ' ';
	  std::cout << '\n';
      }

Output:
      3 2 4 5 7 0 0 -1 0

	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
			    std::stable_partition was only required to
	LWG 2150 C++98	    place one					    cor-
     rected the
			    element  satisfying p before one element not     re-
     quirement
			    satisfying p

See also
	partition		 divides a range of elements into two groups
				 (function template)
	ranges::stable_partition divides elements into two groups while preserv-
     ing their
	(C++20) 		 relative order
				 (niebloid)

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