Silicon Graphics, Inc.

partition

Category: algorithms Component type: function

Prototype

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

Description

Partition reorders the elements in the range [first, last) based on the function object 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.

Definition

Defined in algo.h.

Requirements on types

Preconditions

Complexity

Linear. Exactly last - first applications of pred, and at most (last - first)/2 swaps.

Example

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". [1]

Notes

[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, function object
[Silicon Surf] [STL Home]
Copyright © 1996 Silicon Graphics, Inc. All Rights Reserved. TrademarkInformation