## 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.

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

None

### Synopsis

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

### Description

For the range `[first, last)`, the partition algorithm places all elements that satisfy `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 `[first, i)`, `pred(*j) == true`, and, for any iterator `k` in the range `[i, last)`, `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 `(last - first)/2` 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 integers.
       //
       int init[10] = { 1,2,3,4,5,6,7,8,9,10 };
       deque<int> d1(init+0, init+10);
       deque<int> d2(init+0, init+10);
       //
       // Print out the original values.
       //
       cout << "Unpartitioned values: " << "\t\t";
       copy(d1.begin(), d1.end(),
            ostream_iterator<int,char>(cout," "));
       cout << endl;
       //
       // A partition of the deque according to even/oddness.
       //
       partition(d2.begin(), d2.end(), is_even<int>());
       //
       // Output result of partition.
       //
       cout << "Partitioned values: " << "\t\t";
       copy(d2.begin(), d2.end(),
            ostream_iterator<int,char>(cout," "));
       cout << endl;
       //
       // A stable partition of the deque according
       // to even/oddness.
       //
       stable_partition(d1.begin(), d1.end(), is_even<int>());
       //
       // Output result of partition.
       //
       cout << "Stable partitioned values: " << "\t";
       copy(d1.begin(), d1.end(),
            ostream_iterator<int,char>(cout," "));
       cout << 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

### 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

stable_partition

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