Standard C++ LibraryCopyright 1996, Rogue Wave Software, Inc.

NAME

  partition  - 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>
  BidirectionalIterator
  partition (BidirectionalIterator first,
            BidirectionalIterator last,
            Predicate pred);

DESCRIPTION

  The partition algorithm places all the elements in the range [first, last)
  that satisfy pred before all the 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.h>

   //
   // 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: " << "";
    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: " << "";
    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: " << "";
    copy(d1.begin(), d1.end(),
         ostream_iterator<int,char>(cout," "));
    cout << endl;

    return 0;
   }

  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

WARNING

  If your compiler does not support default template parameters, then you
  need to always supply the Allocator template argument.  For instance, you
  need to write :

  deque<int, allocator<int> >

  instead of :

  deque<int>

SEE ALSO

  stable_partition

STANDARDS CONFORMANCE

  ANSI X3J16/ISO WG21 Joint C++ Committee



privacy and legal statement