Man Page partition.3

                       Standard C++ Library
             Copyright 1998, Rogue Wave Software, Inc.

NAME

     partition

      - Places all of the entities that satisfy the given  predi-
     cate 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

     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 itera-
     tor k in the range [i, last), pred(*j) == false.

     Note that partition does not necessarily maintain the  rela-
     tive  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  parame-
     ters,  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