# 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 backward-compatibility 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 run-time complexity depends on how much memory is available. Worst-case 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