Apache C++ Standard Library Reference Guide

## stable_partition()

Library:  Algorithms

`Function`

No Entries

### Summary

An algorithm that 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

### Synopsis

```#include <algorithm>

namespace std {
template <class BidirectionalIterator, class Predicate>
BidirectionalIterator
stable_partition(BidirectionalIterator start,
BidirectionalIterator finish,
Predicate pred);
}
```

### Description

For the range [start, finish), 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. The relative order of the elements in both groups is maintained.

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 (finish - start) * log(finish - start) swaps and applies the predicate exactly finish - start times.

### Example

```//
//  prtition.cpp
//

#include <algorithm>    // for copy
#include <deque>        // for deque
#include <functional>   // for unary_function
#include <iostream>     // for cout, endl
#include <iterator>     // for ostream_iterator

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

int main ()
{
typedef std::deque<int, std::allocator<int> > Deque;
typedef std::ostream_iterator<int, char,
std::char_traits<char> >
Iter;

// Initialize a deque with an array of integers.
const Deque::value_type a[] = { 1, 2, 3, 4, 5,
6, 7, 8, 9, 10 };

Deque d1 (a + 0, a + sizeof a / sizeof *a);
Deque d2 (d1);

// Print out the original values.
std::cout << "Unpartitioned values: \t\t";
std::copy (d1.begin (), d1.end (), Iter (std::cout, " "));

// A partition of the deque according to even/oddness.
std::partition (d2.begin (), d2.end (), is_even<int>());

// Output result of partition.
std::cout << "\nPartitioned values: \t\t";
std::copy (d2.begin (), d2.end (), Iter (std::cout, " "));

// A stable partition of the deque according to
// even/oddness.
std::stable_partition (d1.begin (), d1.end (),
is_even<int>());

// Output result of partition.
std::cout << "\nStable partitioned values: \t";
std::copy (d1.begin (), d1.end (), Iter (std::cout, " "));
std::cout << std::endl;

return 0;
}

Program Files:
```
```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
```