stable_partition


Category: algorithms 
Component type: function 
Prototype
template <class ForwardIterator, class Predicate>
ForwardIterator stable_partition(ForwardIterator first, ForwardIterator last,
Predicate pred);
Description
Stable_partition is much like partition: it
reorders the elements in the range [first, last) based
on the function object pred, such that all
of the elements that satisfy pred appear before all of 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).
The return value of stable_partition is middle.
Stable_partition differs from partition in that
stable_partition is guaranteed to preserve relative order. That is,
if x and y are elements in [first, last) such that pred(x) == pred(y),
and if x precedes y, then it will still be true after stable_partition
is true that x precedes y. [1]
Definition
Defined in the standard header algorithm, and in the nonstandard
backwardcompatibility header algo.h.
Requirements on types

ForwardIterator is a model of Forward Iterator

Predicate is a model of Predicate

ForwardIterator's value type is convertible to Predicate's
argument type.
Preconditions

[first, last) is a valid range.
Complexity
Stable_partition
is an adaptive algorithm: it attempts to
allocate a temporary memory buffer, and its runtime complexity depends
on how much memory is available.
Worstcase behavior (if no auxiliary memory is available) is
at most N*log(N) swaps, where N is last  first,
and best case (if a large enough auxiliary memory buffer is available) is
linear in N. In either case, pred is applied exactly N times.
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);
stable_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 "2 4 6 8 10 1 3 5 7 9". [1]
Notes
[1]
Note that the complexity of stable_partition is greater than
that of partition: the guarantee that relative order will be preserved
has a significant runtime cost. If this guarantee isn't important to
you, you should use partition.
See also
partition, Predicate, function object
Copyright ©
1999 Silicon Graphics, Inc. All Rights Reserved.
TrademarkInformation
webmaster@www.sgi.com