Adobe Systems Incorporated


Category: algorithms Component type: function


template <class ForwardIterator, class Predicate>
ForwardIterator partition(ForwardIterator first,
                          ForwardIterator last, Predicate pred) 


Partition reorders the elements in the range [first, last) based on the functors pred, such that the elements that satisfy pred precede the elements that fail to satisfy it. The postcondition is that, for some iterator middle in the range [first, last), pred(*i) is true for every iterator i in the range [first, middle) and false for every iterator i in the range [middle, last). [1] The return value of partition is middle.


Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.

Requirements on types

  • ForwardIterator is a model of ForwardIterator.
  • Predicate is a model of Predicate.
  • ForwardIterator's value type is convertible to Predicate's argument type.


  • [first, last) is a valid range.


Linear. Exactly last - first applications of pred. For ForwardIterator at most (last - first) swaps. For BidirectionalIterator at most (last - first)/2 swaps.


Reorder a sequence so that even numbers precede odd numbers.

int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
const int N = sizeof(A)/sizeof(int);
partition(A, A + N,
          compose1(bind2nd(equal_to<int>(), 0),
                   bind2nd(modulus<int>(), 2)));
copy(A, A + N, ostream_iterator<int>(cout, " "));
// The output is "10 2 8 4 6 5 7 3 9 1". <A href="#1">[1]</A>


[1] The relative order of elements in these two blocks is not necessarily the same as it was in the original sequence. A different algorithm, stable_partition, does guarantee to preserve the relative order.

See also

stable_partition, Predicate, functors

Copyright © 2006-2007 Adobe Systems Incorporated.

Use of this website signifies your agreement to the Terms of Use and Online Privacy Policy.

Search powered by Google