stable_partition()

Library:  Algorithms

Function

• Local Index
• Summary
• Synopsis
• Description
• Complexity
• Example
• See Also
• Standards Conformance

An algorithm that 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

#include <algorithm>

namespace std {
  template <class BidirectionalIterator, class Predicate>
  BidirectionalIterator
  stable_partition(BidirectionalIterator start,
                   BidirectionalIterator finish,
                   Predicate pred);
}

For the range [start, finish), 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. The relative order of the elements in both groups is maintained.

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.

The stable_partition() algorithm does at most (finish - start) * log(finish - start) swaps and applies the predicate exactly finish - start times.

//
//  prtition.cpp
//

#include <algorithm>    // for copy
#include <deque>        // for deque
#include <functional>   // for unary_function
#include <iostream>     // for cout, endl
#include <iterator>     // for ostream_iterator



// Create a new predicate from unary_function.
template <class Arg>
struct is_even : public std::unary_function<Arg, bool>
{
    bool operator()(const Arg &arg1) const {
        return (arg1 % 2) == 0;
    } 
};

int main ()
{
    typedef std::deque<int, std::allocator<int> > Deque;
    typedef std::ostream_iterator<int, char,
                                  std::char_traits<char> >
            Iter;

    // Initialize a deque with an array of integers.
    const Deque::value_type a[] = { 1, 2, 3, 4, 5,
                                    6, 7, 8, 9, 10 };

    Deque d1 (a + 0, a + sizeof a / sizeof *a);
    Deque d2 (d1);

    // Print out the original values.
    std::cout << "Unpartitioned values: \t\t";
    std::copy (d1.begin (), d1.end (), Iter (std::cout, " "));

    // A partition of the deque according to even/oddness.
    std::partition (d2.begin (), d2.end (), is_even<int>());

    // Output result of partition.
    std::cout << "\nPartitioned values: \t\t";
    std::copy (d2.begin (), d2.end (), Iter (std::cout, " "));

    // A stable partition of the deque according to 
    // even/oddness.
    std::stable_partition (d1.begin (), d1.end (),
                           is_even<int>());

    // Output result of partition.
    std::cout << "\nStable partitioned values: \t";
    std::copy (d1.begin (), d1.end (), Iter (std::cout, " "));
    std::cout << std::endl;

    return 0;
}


Program Files:

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 

partition()

ISO/IEC 14882:1998 -- International Standard for Information Systems -- Programming Language C++, Section 25.2.12