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.

Answer 2

They both use a binary search algorithm (for random access iterator).

• std::lower_bound requires that the range to be sorted according to (binary) predicate partitioned with respect to the expression element < value or comp(element, value) (which is the case if range is sorted according to binary predicate).
• std::partition_point requires that the range is partitioned according to the (unary) predicate.

You can indeed create a predicate to be able to use the other algorithm.

With:

const std::vector<int> v{1, 2, 3, 4, 5, 6, 7, 8};

You can do with lower_bound:

assert(std::is_sorted(v.begin, v.end(), std::less<>));
auto it1 = std::lower_bound(v.begin, v.end(), 5, std::less<>);

or with partition_point:

auto pred = [](int e){ return e < 5; }
assert(std::is_partition(v.begin, v.end(), pred));
auto it2 = std::partition_point(v.begin, v.end(), pred);

assert(it1 == it2); // *it1 = 5

Or, with the other side

const std::vector<int> v{1, 3, 4, 2, 7, 5, 8, 6};

You can do with partition_point:

auto pred = [](int e){ return e < 5; }
assert(std::is_partition(v.begin, v.end(), pred));
auto it1 = std::partition_point(v.begin, v.end(), pred);

or with lower_bound:

auto pred2 = [](int lhs, int rhs){ return (lhs < 5) > (rhs < 5); }
assert(std::is_sorted(v.begin, v.end(), pred2));
auto it2 = std::lower_bound(v.begin, v.end(), 5, pred2);

assert(it1 == it2); // *it1 == 7

Answer 3

They are more or less equivalent except that lower_bound will use operator< to search the elements if a predicate is not provided.* partition_point is more generic in that it allows that the range was partitioned according to some generic predicate rather than some predicate against avalue.

Note that lower_bound greatly predates the existence of more generic partitioning concepts in C++.

_{*and it's heavily implied that the predicate used in lower_bound should satisfy a less-than relationship, though not required}

---

From [alg.partitions]

template<class ForwardIterator, class Predicate> 
ForwardIterator partition_point(ForwardIterator first, ForwardIterator last, Predicate pred);

Requires: ForwardIterator’s value type shall be convertible to Predicate’s argument type. [first, last) shall be partitioned by pred, i.e. all elements that satisfy pred shall appear before those that do not.

Returns: An iterator mid such that all_of(first, mid, pred) and none_of(mid, last, pred) are both true.

Complexity: O(log(last - first)) applications of pred.

And from [lower.bound]

template<class ForwardIterator, class T>
ForwardIterator
lower_bound(ForwardIterator first, ForwardIterator last,
const T& value);

template<class ForwardIterator, class T, class Compare>
ForwardIterator
lower_bound(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);

Requires: The elements e of [first, last) shall be partitioned with respect to the expression e < value or comp(e, value).

Returns: 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.

Complexity: At most log2(last - first) + O(1) comparisons.