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?

Walrus

You have tried to read e.g. this std::partition_point reference and this std::lower_bound reference? There are some (subtle I'll admit) differences in regards to the predicate. – Cloddish

one is unary predicate and the other is binary predicate. i guess these little differences merited a seperate function – Walrus

Another difference is that std::partition_point doesn't require the range to be ordered, while std::lower_bound does. – Cloddish

i think both require it to be partitioned while ordered is a subset of partitioned – Walrus

@Someprogrammerdude I don't think that is required. From what I can tell all it requires it needs to be partitioned. For instance this seems to work: wandbox.org/permlink/q4WljInrpwK2POfo – Octroi

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.

Mousy

Is there any reasons your lambdas don't just use a default-capture &? Also, why does your lambda instead capture comp by value, is it guaranteed to be copyable? You could handle std::binary_search() too to make a clean sweep. Anyway, nice answer. – Tuppeny

@Tuppeny I have no idea why I did that - there is no such requirement as far as I can tell. – Mousy

Oh, I'm not sure adding const to the forwarded argument is actually allowed. There's even an active issue about it: cplusplus.github.io/LWG/lwg-active.html#3031 – Tuppeny

@Tuppeny That's about the arguments to the comparison itself. I'm not sure that's related to anything here. – Mousy

If you look it through, it makes the point that you the Standard does not quite give the implementation latitude nor mandate to unilaterally make the comparators argument a const&, though it may assume the comparator does not change ist arguments. Your implementations of the standard functions accepting a comparator does that though. It's a subtle point which should be emphasized if intended (unlikely) or fixed in the standard. – Tuppeny

@Tuppeny Oh... I see what you mean now. Yep, removing the consts. – Mousy

@Tuppeny BTW, the requirement on a comparator isn't just that it acts "like a const function", it must act as a pure functional (aka applicative) function, it cannot change any meaningful property, the only meaningful property in case of multisets being the result of the comparator. That requirement is implicit in any algebraic specification of a concept (f.ex. the anti symmetric requirement). – Eyot

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

Sather

i think this mostly covers it – Walrus

lower_bound does not require sorted – Mousy

@Eyot That is not what people mean when they say sorted. [1, 6, 3, 5, 20, 24, 21, 75] is partitioned by the predicate x < 10. It is not sorted. Saying it is sorted by the value of x < 10 is needlessly confusing. – Mousy

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.

Interdental

does it ? can you link to such a requirement? – Walrus

"it does not need to satisfy the requirements of Compare"en.cppreference.com/w/cpp/algorithm/lower_bound – Walrus

@AnkurS From this std::lower_bound refernece regarding the predicate: "binary predicate which returns ​true if the first argument is less than (i.e. is ordered before) the second." (emphasis mine) – Cloddish

@Someprogrammerdude: Actually I revisted the standard and it says *j < value or comp(*j, value) != false. which allows for a generic predicate used for partitioning – Interdental

Doesn't std::partition_point also require [first, last) to be ordered? – Octroi

@NathanOliver: Yeah, I conflated the return of partition_point with the Requires section. – Interdental

lower_bound doesn't use operator< to partition the range, the range must already be partitioned. Why do you say there's a heavy implication of less-than relationship for the predicate? It just needs to satisfy strict weak ordering. – Skindeep

@Praetorian: whoops on the misuse of 'partition' there. Also, see lwg 270 which states that the strict weak ordering was too strict a requirement and only a partitioning is necessary – Interdental

@Interdental You don't point out (though it's in the quoted complexity requirements) that, for lower_bound, binary logarithmic complexity is required, whereas for partition_point, any logarithm will suffice. (And, no, it's not clear to me when that would be a good thing for the user.) – Buine

"Partitioned" is the same as "increasing", for some ordering relation. – Eyot