Different comparison signature for std :: upper_bound and std :: lower_bound

Question

Here is an example of an example for std::lower_bound and std::upper_bound , note that the signature Compare lambda is passed for them -

 const auto lower_x = std::lower_bound( points.begin(), points.end(), rec.min_corner.x, [](const RankedPoint &rp, const double x) { return rp.point.x < x; }); const auto upper_x = std::upper_bound( points.begin(), points.end(), rec.max_corner.x, [](const double x, const RankedPoint &rp) { return x < rp.point.x; }); 

What is the possible argument that the signature is completely opposite to each other? I did not know about this and compiled gcc (clang) when I used auto instead of certain types with the wrong signatures. It cost me 10 minutes of disappointment.

Answer 1

Custom versions of the comparator lower_bound and upper_bound are generalizations of the simple use of < . lower_bound gives the first element that is not less than value , so the check is done elem < value (or !(elem < value) really). upper_bound gives the first element greater than value , but instead of writing elem > value (which requires operator> ), we simply translate the order into value < elem . This supports the only operator< requirement, but as a result, the order of the arguments is reversed.

This generalizes from elem < value to comp(elem, value) and value < elem to comp(value, elem) .

Ultimately, when designing, we can make two choices: we can use the same comparator everywhere, but for some algorithms the order of the arguments is reversed. Or we could use different comparators for each algorithm, depending on what makes sense for that particular algorithm. Using the same comparator around the world has many advantages - you just use the same comparator:

 std::vector<int> vs = ...; std::sort(vs.begin(), vs.end(), std::greater<>{}); auto lo = std::lower_bound(vs.begin(), vs.end(), 5, std::greater<>{}); auto hi = std::upper_bound(vs.begin(), vs.end(), 5, std::greater<>{}); 

The same comparator is everywhere, the code looks right and does the right thing. If we flip the order of the arguments that upper_bound() goes to its comparator, we need to go to std::less<>{} . That would be just ... wrong.

---

You will probably be interested in Ranges TS , which solves this problem with invokable projectionions.