What is the difference between partition_point and lower_bound?

Question

C++11 includes the algorithm std::partition_point(). However for all the cases I have tried it gives the same answer as std::lower_bound(). The only difference being the convenient T& value parameter.

Did I miss something or are these two functions doing more or less the same thing?

Answer 1

They are basically equivalent. This would be a valid implementation of lower_bound:

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

template <typename ForwardIterator, typename T, typename Compare>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
    T const& value, Compare comp)
{
    return partition_point(first, last, [&](auto&& elem) {
        return comp(elem, value);
    });
}

The two algorithms rely upon finding the partition point of a partitioned range, they just take different arguments with which to search (a unary predicate for partition_point, vs a value or value and binary predicate for lower_bound).

We just typically think of lower_bound in the context of sorted range with a binary predicate - even though a fully sorted range with respect to such a predicate is not a requirement for that algorithm.

---

While we're at it, upper_bound can also be implemented in terms of partition_point, just with the operands flipped and the predicate negated:

template <typename ForwardIterator, typename T>
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
    T const& value)
{
    return partition_point(first, last, [&](auto&& elem) {
        return !(value < elem);
    });
}

template <typename ForwardIterator, typename T, typename Compare>
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
    T const& value, Compare comp)
{
    return partition_point(first, last, [&](auto&& elem) {
        return !comp(value, elem);
    });
}

---

It's weird how differently the two are worded.

lower_bound returns (the upper_bound wording is similar):

The furthermost iterator i in the range [first, last] such that for every iterator j in the range [first, i) the following corresponding conditions hold: *j < value or comp(*j, value) != false.

while partition_point returns

An iterator mid such that all_­of(first, mid, pred) and none_­of(mid, last, pred) are both true.

Those phrases are equivalent since the requirement is that the range is partitioned. But it sure doesn't seem that way at first glance.