Partition with elements that satisfy a predicate first

Source code

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

• BidirectionalIterator must be at least a regular bidirectional iterator .
• Predicate must be a function object type that provides int operator()(S), where S is the dereference type of BidirectionalIterator.

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 -

1. [ first, first_cut) (these elements are in the first half and make pred return true),
2. [ first_cut, middle) (these elements are in the first half and make pred return false),
3. [ middle, second_cut) (these elements are in the second half and make pred return true),
4. [ second_cut, last) (these elements are in the second half and make pred return false).