## What is the difference between partition_point and lower_bound?

18

3

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?

13

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

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.

4

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

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 a`value`.

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.