What is the difference between partition_point and lower_bound?

  • 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 

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: