Partitioning with the STL

Partitioning a collection consists in reordering it so that the elements that satisfy a given predicate are moved up to the beginning, and those that don’t satisfy it are moved down after them. The first element that does not satisfy the predicate is called the partition point. This is also the end of the subrange of elements that do satisfy the predicate:

Performing a partitioning with the STL

std::partition accepts a range and a predicate, and reorders the elements of the range so that they are partitioned according to this predicate:

template<typename ForwardIterator, typename Predicate>
ForwardIterator partition(ForwardIterator first, ForwardIterator last, Predicate p);

std::partition returns an iterator to the partition point of the reordered range. Its complexity is O(n).

std::partition does not guarantee to keep the order of elements that satisfy (resp. don’t satisfy) the predicate. If you need this guarantee, use std::stable_partition. std::stable_partition also returns an iterator to the partition point of the reordered range.

EDIT: As Jason Turner pointed out when discussing this article on CppCast, std::stable_partition, contrary to the other algorithms, is allowed to attempt to allocate a temporary buffer. Its complexity is then O(n) if it there is enough extra memory to allocate it, and O(n.log(n)) otherwise.

If you need to leave the range unchanged and have the output somewhere else, use std::partition_copy. It writes outputs in 2 ranges: the first one for elements that satisfy the predicate, and the second one for elements that don’t. std::partition_copy returns a pair of iterators, pointing respectively to the end of the first output range and to the end of the second one. Here is its interface:

template<typename InputIt, typename OutputIt1, typename OutputIt2, typename Predicate>
std::pair<OutputIt1, OutputIt2>
        partition_copy(InputIt first, InputIt last,
                       OutputIt first_true, OutputIt first_false,
                       Predicate p);

Checking for partitioning properties of a range

To check whether a range is partitioned according to a certain predicate, use std::is_partitioned. Here is its interface:

template<typename InputIt, typename Predicate>
bool is_partitioned(InputIt first, InputIterator last, Predicate p);

And to get the partition point of a partitioned range, use std::partition_point:

template<typename ForwardIterator, typename Predicate>
ForwardIterator partition_point(ForwardIterator first,
                                ForwardIterator last,
                                Predicate p);

Much like std::is_sorted_until that we saw in Sorting with the STL, Boost adds an is_partitioned_until function. This algorithm takes a range and a predicate, and returns the iterator of the first position from which the range is no longer partitioned. Thanks to Alexander Zaitsev for pointing out this algorithm!

Examples of things that can be achieved with partitioning

lower_bound, upper_bound and equal_range

As pointed out in Elements of Programming, std::lower_bound can be implemented by using partitioning algorithms. Indeed, every element x preceding the the lower bound of a range for a given value a satisfies the predicate x < a. The lower bound is the first element that does not satisfy this predicate, so the lower bound of a is effectively the partition point for the predicate x < a.

So a possible implementation for lower_bound is:

template<typename ForwardIt, typename T>
ForwardIterator lower_bound(ForwardIt first, ForwardIt last, const T& value)
{
    return std::partition_point(first, last, [value](const auto& x){return x < value;});
}

The same applies for std::upper_bound, with the predicate !(a < x).

And lower_bound and upper_bound can themselves be used to implement std::equal_range.

gather

This example is taken from Sean Parent’s very popular talk C++ Seasoning that he gave at GoingNative 2013.

How to gather up at a given position all elements of a range that satisfy a predicate ? That is, how to get from here…:

…to there ?

This can in fact be achieved fairly easily with std::stable_partition.

The idea is to view the initial range as 2 parts: [begin, position[ and [position, end[, and

• apply a stable partition on [begin, position[, that puts all the elements that satisfy the predicate at the end (so partition with the negation of the predicate)
• apply a stable partition on [position, end[ that pulls up all the elements that satisfy the element of the range.

Each call to std::stable_partition returns the corresponding partition point, which happen to be respectively the beginning and the end of the gathered range. This range can be returned from the function.

template<typename BidirIterator, typename Predicate>
Range<BidirIterator> gather(BidirIterator first, BidirIterator last,
                            BidirIterator position, Predicate p)
{
    return { std::stable_partition(first, position, std::not_fn(p)),
             std::stable_partition(position, last, p) };
}

(thanks to /u/tcanens on Reddit for pointing out the not_fn function from C++17 that supersedes the old std::not1 to negate a function).

Range being a class that can be initialized with 2 iterators representing a begin and an end, like boost::iterator_range or the one in range-v3 for example. An std::pair of iterators could also be used, like it is for std::equal_range, but in a more clumsy manner (as seen in How to (std::)find something efficiently with the STL for more on this type of interface).

Note that the gather algorithm is available in boost with the boost::algorithm::gather function, that returns a pair of iterators.

In conclusion, knowing how to achieve partitioning with the STL is useful, as this concept appears in more situations than meets the eye. It is yet another tool in our C++ toolbox.

Don't want to miss out ? Follow:   
Share this post!