7.7. 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 <iostream> #include <istream> #include <string> #include <vector> #include <algorithm> #include <functional> #include <iterator> #include "utils.h" // For printContainer(): see Recipe 7.10 using namespace std; int main() { cout << "Enter a series of strings: "; istream_iterator<string> start(cin); istream_iterator<string> end; // This creates a "marker" vector<string> v(start, end); // Rearrange the elements in v so that those that are less // than "foo" occur before the rest. vector<string>::iterator p = partition(v.begin(), v.end(), bind2nd(less<string>(), "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 ...