Published October 10, 2017 - 2 Comments

**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:

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

1 2 |
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 1 2 3 4 5 |
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); |

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

1 2 |
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**:

1 2 3 4 |
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!

`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:

1 2 3 4 5 |
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

, with the predicate **std::upper_bound**`!(a < x)`

.

And `lower_bound`

and `upper_bound`

can themselves be used to implement ** std::equal_range**.

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.

1 2 3 4 5 6 7 |
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.

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