- A+

Category：Languages

c++11 includes the algorithm partition_point in the STL. However for all the cases I have tried it gives the same answer as 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?

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 `