Partitioning a Range

Problem

You have a range of elements that you need to partition in some well-defined way. For example, you may want all elements less than a particular value moved to the front of the range.

Solution

Use the partition standard algorithm with a predicate functor to move the elements around however you like. See Example 7-7.

Example 7-7. Partitioning a range

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include "utils.h" // For printContainer( ): see Recipe 7.10

using namespace std;

int main( ) {

 cout << "Enter a series of strings: ";
 istream_iterator start(cin);
 istream_iterator end; // This creates a "marker"
 vector v(start, end);

 // Rearrange the elements in v so that those that are less
 // than "foo" occur before the rest.
 vector::iterator p = 
 partition(v.begin( ), v.end( ),
 bind2nd(less( ), "foo"));
 printContainer(v);

 cout << "*p = " << *p << endl;
}

The output for Example 7-7 would look like the following:

Enter a series of strings: a d f j k l
^Z
-----
a d f j k l
*p = j

After the partition, the iterator p refers to the first element for which less(*p, "foo") is not true.

Discussion

partition takes the beginning and end of a range and a predicate, and moves all elements for which the predicate is true to the beginning of the range. It returns an iterator to the first element where the predicate is not TRue, or the end of the range if all elements satisfy the predicate. Its declaration looks like this:

Bi partition(Bi first, Bi last, Pred pred);

pred is a functor that takes one argument and returns TRue or false. There is no default predicate; you have to supply one that makes sense for what you are trying to partition. You can write your own predicate, or use one from the standard library. For example, from Example 7-7, you can see that I used less and bind2nd to create a functor for me:

vector::iterator p = 
 partition(v.begin( ), v.end( ),
 bind2nd(less( ), "foo"));

What this does is move all elements less than "foo" before everything that is not. bind2nd is not required here, but it is a convenient way to create automatically a functor that takes one argument and returns the result of less(*i, "foo") for each element i in the sequence. You can also use stable_partition if you want equivalent elements to retain their relative order.

partition, and other algorithms that change the order of the elements in a range, do not work with the standard associative containers set, multiset, map, and multimap. This is because associative containers keep their elements in a well-defined order and only the containers themselves are allowed to move or remove elements. You can use partition with any range for which you can obtain at least bidirectional iterators, which includes all of the standard sequence containers deque, vector, and list.