Declaration
template <class BidirectionalIterator, class Predicate> BidirectionalIterator partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred); template <class ForwardIterator, class Predicate> inline ForwardIterator stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred);
Description Both the partition and stable_partition functions place all the elements in the range [ first, last) that make the predicate pred return true (i.e. a non-zero value) before all the elements that make pred return false (i.e. zero), returning an iterator i such that pred returns true for the value of any iterator in the range [ first, i) and pred returns false for the value of any iterator in the range [ i, last) .
The difference between partition and stable_partition is that the relative order of the elements in both groups (i.e. the range [ first, i) and the range [ i, last) ) is preserved when the stable_partition function is used, but is not preserved when the partition function is used.
Type requirements
Group Value based permutations
Time complexity Linear for the partition function, and at most for the stable_partition function.
The partition function performs at most n/2 swaps and applies the predicate exactly n times, where n is the size of the range [ first, last) .
If the available memory for a buffer is smaller than the range [ first, last) , the stable_partition function requires time and performs
swaps , where n is the size of the range [ first, last) . If there is enough available memory for the buffer to contain all of the elements in the range [ first, last) , then the stable_partition function requires linear time, performing n + m assignment operations and applying the predicate exactly n times, where m is the size of the range [ i, last) and n is the size of the range [ first, last) .
Space complexity Constant for the partition function, and at most linear for the stable_partition function.
The required space is linear (i.e. n, where n is the size of the range [ first, last) ) for the stable_partition function if the buffer is large enough to hold the contents of the range [ first, last) ; otherwise, space is needed for recursive calls, where n is the size of the range [ first, last) .
Mutative? Yes.
Example Select here to view the source code for the example.
Implementation Select here to view source code (Copyright (C) 1994, Hewlett-Packard Company) for this algorithm.
Implementation notes If there is enough memory for a buffer large enough to hold the elements in the range [ first, last) , then the stable_partition function places the elements for which the predicate is true into the range [ first, i) with elements for which the predicate is false placed into the buffer, and then the buffer is copied into the range [ i, last) .
If there is not enough memory, the function is recursively called on halves of the sequence, making each half stably partitioned , and yielding four subranges -