Apache C++ Standard Library Reference Guide

## partition()

Library:  Algorithms

`Function`

No Entries

### Summary

Algorithm that places all of the entities that satisfy the given predicate before all of the entities that do not

### Synopsis

```#include <algorithm>

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

### Description

For the range [start, finish), the partition() algorithm places all elements that satisfy the predicate pred before all elements that do not satisfy pred. It returns an iterator that is one past the end of the group of elements that satisfy pred. In other words, partition() returns i such that for any iterator j in the range [start, i), pred(*j) == true, and, for any iterator k in the range [i, finish), pred(*j) == false.

Note that partition() does not necessarily maintain the relative order of the elements that match and elements that do not match the predicate. Use the algorithm stable_partition() if relative order is important.

### Complexity

The partition() algorithm does at most (finish - start)/2 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 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
```