std::is_partitioned() and std::partition_point()

The C++0x standard has made easier working with partitioning. Now we have a standard function, is_partitioned(), to check if an interval in a container is partitioned against a predicate, and another one, partition_point() that returns an iterator to the first element out of the first group

As we can expect, partition_point() assumes the elements have been already partitioned by the passed predicate.

We are going to test these features on this container:

std::vector<int> vi;
vi.reserve(10);
for(int i = 0; i < 10; ++i) 
    vi.push_back(i);
dump(vi);

We need a predicate for partitioning the container, say, in even and odd elements. Best choice is a lambda fuction, being the test so easy, but we need to store the function in a local variable, since we have to reuse it a couple of times. The explicit way of doing that is using a function object (declared in the standard functional include file):

std::function<bool (int)> isEven = [] (int i) -> bool { return i%2 == 0; };

But if we want to save some typing we could use the autodetecting type deducing, by the auto keyword, and not specify the lambda return type - letting the compiler deducing it from the code, too:

auto isEven = [] (int i) { return i%2 == 0; };

We are paying our lazyness (and the concision/readability of the produced code) with less control on what we are writing - it is a choice that you have to take.

In any case, now we can test if our sequence is partitioned in even/odd elements:

if(std::is_partitioned(vi.begin(), vi.end(), isEven))
    std::cout << "I don't expect this" << std::endl;

After typedeffing the iterator on our vector:

typedef std::vector<int>::iterator IT;

we partition the sequence, and test it again, this time for getting a positive result. Notice the paranoid check on the partitioning result. In this case is just overkilling, but I put it there as I would do in production code:

IT pivot = std::partition(vi.begin(), vi.end(), isEven);
if(std::is_partitioned(vi.begin(), vi.end(), isEven))
{
    std::cout << "Now the container is partitioned: ";
    dump(vi);
    if(pivot != vi.end())
        std::cout << "Second group starts at: " << *pivot << std::endl;
}

Now that the sequence is partitioned, we can get its partition point. Actually, here this is not useful at all, since that is the iterator we get back from partition(). But OK, this is just an example:

IT ppoint = std::partition_point(vi.begin(), vi.end(), isEven);
if(ppoint != vi.end())
    std::cout << "Partition point is: " << *ppoint << std::endl;