partition(3C++) - partition(3C++)
Standard C++ Library Copyright 1998, Rogue Wave Software, Inc.
NAMEpartition
- Places all of the entities that satisfy the given predicate before
all of the entities that do not.
SYNOPSIS
#include <algorithm>
template <;class BidirectionalIterator, class Predicate>
BidirectionalIteratorpartition (BidirectionalIterator first,
BidirectionalIterator last,
Predicate pred);
DESCRIPTION
For the range [first, last), the partition algorithm places all ele‐
ments 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 ele‐
ments 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 OutputUnpartitioned 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
Rogue Wave Software 02 Apr 1998 partition(3C++)
