Standard C++	Library
 		 Copyright 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 itera- tor 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