stable_partition(3C++) - stable_partition(3C++)
Standard C++ Library Copyright 1998, Rogue Wave Software, Inc.
NAMEstable_partition
- 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>
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 ele‐
ments 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 main‐
tain 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 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
partition
Rogue Wave Software 02 Apr 1998 stable_partition(3C++)
