partition

partition takes all elements in a range and moves those that satisfy some unary predicate op to the front of the range begin; all other elements sit at the back of the range. The criterion can be a function object that we can use to test the elements in the container. For example, we could use less with bind2nd and some value that we want to test against for a container of integers.

Here's the signature of partition:

     BidirectionalIterator partition(BidirectionalIterator begin,
                                   BidirectionalIterator end,
                                   Operation op);
     

Here's a simple example that uses integers:

     /* generic5.cc
      * Compiled using g++ generic5.cc -o generic5
      * Run using ./generic5 */
     
     #include <vector>
     #include <algorithm>
     #include <functional>
     
     int main()
     {
       std::vector<int> v;
       for (int i=9; i>-1; i--)
         v.push_back(i);
       std::vector<int>::iterator pos, iter;
       cout << "v: ";
       for (pos = v.begin(); pos != v.end(); ++pos)
         cout << *pos << " ";
       pos = partition(v.begin(), v.end(), bind2nd(less<int>(), 5));
       cout << "\nv, after partition: ";
       for (iter = v.begin(); iter != v.end(); ++iter)
         cout << *iter << " ";
       cout << "\nFirst element not matching in v: " << *pos << endl;
       return 0;
     }
     

     Example 3.23: generic5.cc
     

The output may seem strange at first:

     v: 9 8 7 6 5 4 3 2 1 0
     v, after partition: 0 1 2 3 4 5 6 7 8 9
     First element not matching in v: 5
     

- it appears more or less as if we've performed a sort on the elements of the vector; and in a sense we have. We have said that we want to partition the data into two discreet sections; that which is less than five, and that which is greater than four. However, partition also sorts the elements, and as a result the ordering of the original elements in the partition is not preserved, unlike with stable_partition, which is similar (and the signature is the same as partition), but preserves the order of the elements in the partition:

     /* generic6.cc
      * Compiled using g++ generic6.cc -o generic6
      * Run using ./generic6 */
     
     #include <vector>
     #include <algorithm>
     #include <functional>
     
     int main()
     {
       std::vector<int> v;
       for (int i=9; i>-1; i--)
         v.push_back(i);
       std::vector<int>::iterator pos, iter;
       cout << "v: ";
       for (pos = v.begin(); pos != v.end(); ++pos)
         cout << *pos << " ";
       pos = stable_partition(v.begin(), v.end(), bind2nd(less<int>(), 5));
       cout << "\nv, after stable_partition: ";
       for (iter = v.begin(); iter != v.end(); ++iter)
         cout << *iter << " ";
       cout << "\nFirst element not matching in v: " << *pos << endl;
       return 0;
     }
     

     Example 3.24: generic6.cc
     

The result is a little more predictable:

     v: 9 8 7 6 5 4 3 2 1 0
     v, after stable_partition: 4 3 2 1 0 9 8 7 6 5
     First element not matching in v: 9
     

As a result, the time complexity of stable_partition is better than that of partition; stable_partition has linear complexity (worst-case is n log n), whereas partition has linear time complexity, worst-case number of elements / 2 swaps.