Man Page stable_partition.3

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

NAME

     stable_partition

      - Places all of the entities that satisfy the given  predi-
     cate before all of the entities that do not, while maintain-
     ing 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

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

     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

     partition