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

 NAME

   stable_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

   The stable_partition algorithm places	all the	elements in the	range
   [first, last)	that satisfy pred before all the elements that do not
   satisfy it. It returns an	iterator i that	is one past the	end of
   the group of elements that satisfy 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
   maintain 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.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 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;
    }

   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 will need to write :

   deque<int, allocator<int> >

   instead of :

   deque<int>

 SEE ALSO

   partition

 STANDARDS CONFORMANCE
   ANSI X3J16/ISO WG21 Joint C++	Committee