## stable_partition

    Algorithm

- Summary
- Data Type and Member Function Indexes
- Synopsis
- Description
- Complexity
- Example
- Warnings
- See Also

### Summary

Places all of the entities that satisfy the given predicate before all of the entities that do not, while maintaining the relative order of elements in each group.

### Data Type and Member Function Indexes
(exclusive of constructors and destructors)

None

### Synopsis

    #include <algorithm>
    template <class BidirectionalIterator, class Predicate>
      BidirectionalIterator
        stable_partition (BidirectionalIterator first,
                          BidirectionalIterator last,
                          Predicate pred);

### Description

For the range `[first, last)`, the stable_partition algorithm places all elements that satisfy `pred` before all elements that do not satisfy it. It returns an iterator `i` that is one past the end of the group of elements that satisfies `pred`. In other words stable_partition returns `i` such that for any iterator `j` in the range `[first, i)`, `pred(*j) == true`, and for any iterator `k` in the range `[i, last)`, `pred(*j) == false`. The relative order of the elements in both groups is preserved.

The partition algorithm can be used when it is not necessary to maintain the relative order of elements within the groups that do and do not match the predicate.

### Complexity

The stable_partition algorithm does at most `(last - first) * log(last - first)` swaps and applies the predicate exactly `last - first` times.

### Example

    //
    // prtition.cpp
    //
    #include <functional>
    #include <deque>
    #include <algorithm>
    #include <iostream>
    using namespace std;

    //Create a new predicate from unary_function
    template<class Arg>
    class is_even : public unary_function<Arg, bool>
    {
    public:
    bool operator()(const Arg& arg1)
    {
    return (arg1 % 2) == 0;
       }
     };

    int main()
    {
    //Initialize a deque with an array of ints
    int init[10] = {1,2,3,4,5,6,7,8,9,10};
    deque<int> d(init, init+10);

    //Print out the original values
    cout << "Unpartitioned values: " << endl << "     ";
    copy(d.begin(),d.end(),
         ostream_iterator<int,char>(cout," "));
    cout << endl << endl;

    //Partition the deque according to even/oddness
    stable_partition(d.begin(), d.end(), is_even<int>());

    //Output result of partition
    cout << "Partitioned values: " << endl << "     ";
    copy(d.begin(),d.end(),
         ostream_iterator<int,char>(cout," "));
    return 0;
     }

Program Output

    Unpartitioned values:           1 2 3 4 5 6 7 8 9 10
    Partitioned values:             10 2 8 4 6 5 7 3 9 1
    Stable partitioned values:      2 4 6 8 10 1 3 5 7 9

### Warnings

If your compiler does not support default template parameters, then you always need to supply the `Allocator` template argument. For instance, you need to write:

`deque<int, allocator<int> >`

instead of:

`deque<int>`

If your compiler does not support namespaces, then you do not need the using declaration for `std`.

### See Also

partition

Copyright (c) 1998, Rogue Wave Software, Inc.
Send mail to report errors or comment on the documentation.
OEM Release, June 1998