Impact of comparison function on upper_bound and lower_bound

Question

I would like to understand the impact of the comparison function (< or <=) on both lower_bound and upper_bound functions.

Consider this program:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


int main() {
        vector<int> v = {0, 1, 2, 3, 3, 3, 3, 3, 4, 5, 6, 7};

        auto it1 = lower_bound(v.begin(), v.end(), 3, [](int a, int b) {return a < b;});
        auto it2 = lower_bound(v.begin(), v.end(), 3, [](int a, int b) {return a <= b;});
        auto it3 = upper_bound(v.begin(), v.end(), 3, [](int a, int b) {return a < b;});
        auto it4 = upper_bound(v.begin(), v.end(), 3, [](int a, int b) {return a <= b;});


        cout << distance(v.begin(), it1) << endl;
        cout << distance(v.begin(), it2) << endl;
        cout << distance(v.begin(), it3) << endl;
        cout << distance(v.begin(), it4) << endl;

        return 0;
}

this result is:

3
8
8
3

Could anybody explain this results?

Could we say that lower_bound with < is equivalent to upper_bound with <= all the time?

Same question for (lower_bound, <=) and (upper_bound, <).

Answer 1

Could anybody explain this results?

I'll try by describing what they do and by showing a table:

• std::lower_bound - Returns the first iterator iter in [first, last) where bool(comp(*iter, value)) is false.
• std::upper_bound - Returns the first iterator iter in [first, last) where bool(comp(value, *iter)) is true.

alg.	0	1	2	3	3	3	3	3	4	5	6	7
lower: *iter < 3	T	T	T	F									3 < 3 first false
lower: *iter <= 3	T	T	T	T	T	T	T	T	F				4 <= 3 first false
upper: 3 < *iter	F	F	F	F	F	F	F	F	T				3 < 4 first true
upper: 3 <= *iter	F	F	F	T									3 <= 3 first true

Could we say that lower_bound with < is equivalent to upper_bound with <= all the time? [and vice versa]

As long as the range is partitioned according to bool(comp(elem, value)) (lower_bound) and bool(comp(value, elem)) (upper_bound) using both < and <=, as it is in your case, then yes. As you can hopefully see above, *iter < 3 will then find the first false when 3 <= *iter finds the first true and vice versa. You get:

*iter < value == !(value <= *iter) and *iter <= value == !(value < *iter)