Standard C++ LibraryCopyright 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



privacy and legal statement