Was this page helpful?
Your feedback about this content is important. Let us know what you think.
Additional feedback?
1500 characters remaining
Export (0) Print
Expand All

partition

Classifies elements in a range into two disjoint sets, with those elements satisfying a unary predicate preceding those that fail to satisfy it.

template<class BidirectionalIterator, class Predicate>
   BidirectionalIterator partition(
      BidirectionalIterator _First, 
      BidirectionalIterator _Last, 
      BinaryPredicate _Comp
   );

Parameters

_First
A bidirectional iterator addressing the position of the first element in the range to be partitioned.
_Last
A bidirectional iterator addressing the position one past the final element in the range to be partitioned.
_Comp
User-defined predicate function object that defines the condition to be satisfied if an element is to be classified. A predicate takes a single argument and returns true or false.

Return Value

A bidirectional iterator addressing the position of the first element in the range to not satisfy the predicate condition.

Remarks

The range referenced must be valid; all pointers must be dereferenceable and within the sequence the last position is reachable from the first by incrementation.

Elements a and b are equivalent, but not necessarily equal, if both Pr (a, b) is false and Pr (b, a) if false, where Pr is the parameter-specified predicate. The partition algorithm is not stable and does not guarantee that the relative ordering of equivalent elements will be preserved. The algorithm stable_ partition does preserve this original ordering.

The complexity is linear: there are (_Last – _First) applications of _Comp and at most (_Last – _First)/2 swaps.

Example

// alg_partition.cpp
// compile with: /EHsc
#include <vector>
#include <algorithm>
#include <iostream>

bool greater5 ( int value )
{
   return value >5;
}

int main( ) {
   using namespace std;
   vector <int> v1, v2;
   vector <int>::iterator Iter1, Iter2;

   int i;
   for ( i = 0 ; i <= 10 ; i++ )
   {
      v1.push_back( i );
   }
   random_shuffle( v1.begin( ), v1.end( ) );

   cout << "Vector v1 is ( " ;
   for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
      cout << *Iter1 << " ";
   cout << ")." << endl;

   // Partition the range with predicate greater10
   partition ( v1.begin( ), v1.end( ), greater5 );
   cout << "The partitioned set of elements in v1 is: ( " ;
   for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
      cout << *Iter1 << " ";
   cout << ")." << endl;
}

Output

Vector v1 is ( 10 1 9 2 0 5 7 3 4 6 8 ).
The partitioned set of elements in v1 is: ( 10 8 9 6 7 5 0 3 4 2 1 ).

See Also

<algorithm> Members | partition Sample

Show:
© 2015 Microsoft