Standard library partition algorithm

Question

I wrote this partition function:

template <class I, class P> I partition(I beg, I end, P p)
{
    I first = beg;
    while(beg != end) {
        if(!p(*beg))
            beg++;
        else {
            // if(beg != first) - EDIT: add conditional to prevent swapping identical elements
            std::swap(*beg, *first);
            first++;
            beg++;
        }
    }
    return first;
}

I've tested it with a few outputs and I haven't found anything wrong with it.

The standard library partition function is equivalent to:

template <class BidirectionalIterator, class UnaryPredicate>
  BidirectionalIterator partition (BidirectionalIterator first,
                                   BidirectionalIterator last, UnaryPredicate pred)
{
  while (first!=last) {
    while (pred(*first)) {
      ++first;
      if (first==last) return first;
    }
    do {
      --last;
      if (first==last) return first;
    } while (!pred(*last));
    swap (*first,*last);
    ++first;
  }
  return first;
}

The latter seems much more complicated and has nested loops. Is there something wrong with my version? If not why the more complicated version?

Here is some output using the following predicate:

bool greaterthantwo(double val)
{
    return val > 2;
}

MAIN

std::vector<double> test{1,2,3,4,2,5,6,7,4,8,2,4,10};
std::vector<double>::iterator part = ::partition(test.begin(), test.end(), greaterthantwo);
for(const auto &ref:test)
    std::cout << ref << " ";
std::cout << std::endl;
for(auto it = part; it != test.end(); it++)
    std::cout << *it << " ";
std::cout << std::endl;

OUTPUT

3 4 5 6 7 4 8 4 10 2 2 2 1 
2 2 2 1 

Answer 1

Your version is close to Nico Lomuto partition. Such partition works on ForwardIterators and is semi-stable (first part is stable, which can be useful in some circumstances).

Version from implementation of standard library which you quoted is close to partition described by C. A. R. Hoare at his paper "Quicksort". It works on BidirectionalIterators, and does not imply any stability.

Let's compare them on following case:

FTTTT

Forward partition will proceed like this:

FTTTT
TFTTT
TTFTT
TTTFT
TTTTF

resulting in swap on each iteration except first, while Bidirectional partition will go thru following permutations:

FTTTT
TTTTF

resulting only in one swap for all iterations.

Moreover, in general case Bidirectional will do N/2 swaps at maximum, while Forward version can do up to ~N swaps.

std::partition in C++98/03 works on BidirectionalIterators, but in C++11 they relaxed requirements to ForwardIterators (though, it doesn't have to be semi-stable). Complexity requirements:

Complexity: If ForwardIterator meets the requirements for a BidirectionalIterator, at most (last -first) / 2 swaps are done; otherwise at most last - first swaps are done. Exactly last - first applications of the predicate are done.

As you can see, implementations of standard library most likely will use Lomuto's partition for ForwardIterators and Hoare's partition for BidirectionalIterators.

Alexander Stepanov discuses partition problem in his Notes on Programming and in Elements of Programming co-authored with Paul McJones

---

Live Demo

#include <initializer_list>
#include <forward_list>
#include <algorithm>
#include <iostream>
#include <iterator>
#include <list>
using namespace std;

int counter = 0;

struct T
{
    int value;
    T(int x = 0) : value(x) {}
    T(const T &x)
    {
        ++counter;
        value = x.value;
    }
    T &operator=(const T &x)
    {
        ++counter;
        value = x.value;
        return *this;
    }
};
auto pred = [](const T &x){return x.value;};

template<typename Container>
void test()
{
    Container l = {0, 1, 1, 1, 1};
    counter = 0;
    partition(begin(l), end(l), pred);
    cout << "Moves count: " << counter << endl;
}

int main()
{
    test<forward_list<T>>();
    test<list<T>>();
}

Output is:

Moves count: 12
Moves count: 3

(swap is 3 moves)

Answer 2

Your function has a serious defect. It swaps each element that satisfies the predicate with itself if initial elements of the sequence satisfy the predicate.