partition()

Library:  Algorithms

Function

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

Algorithm that places all of the entities that satisfy the given predicate before all of the entities that do not

#include <algorithm>

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

For the range [start, finish), the partition() algorithm places all elements that satisfy the predicate pred before all 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 iterator j in the range [start, i), pred(*j) == true, and, for any iterator k in the range [i, finish), 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.

The partition() algorithm does at most (finish - start)/2 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 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 

stable_partition()

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