'Difference between upper_bound and lower_bound in stl

I was looking at how the upper_bound and lower_bound algorithms work in stl on these pages: lower_bound, upper_bound, and it's documented the same way on these pages: lower_bound, upper_bound

Looking at the code from the links, they seem to do exactly the same thing to me, with only the following lines being different (looking at the code from the first 2 links):

lower_bound (line 10):

if (*it<val) {                 // or: if (comp(*it,val)), for version (2)

upper_bound (line 10):

 if (!(val<*it))                // or: if (!comp(val,*it)), for version (2)

but surely reversing the compared elements and then comparing them to false is a double negative, and thus they do exactly the same thing?

Is there actually a difference that I'm just not seeing, Is this an error in the documentation on the websites? If the latter, what would be the correct way?

c++stl


Solution 1:[1]

A simple answer is and less confusing WAY to remember this is below

std::lower_bound - returns iterator to first element in the given range which is EQUAL_TO or Greater than val.

std::upper_bound - returns iterator to first element in the given range which is Greater than val.

Solution 2:[2]

lower_bound:

Returns an iterator pointing to the first element in the range [first,last) which does not compare less than val.

upper_bound:

Returns an iterator pointing to the first element in the range [first,last) which compares greater than val.

Now there is a difference between being no less than something and greater than something.

For example, if you compare 4 and 5, you can say that

5 is _not less than_ 4
5 is _greater than_  4

However if you compare you compare 4 and 4:

4 is _not less than_    4
4 is _not greater than_ 4

Solution 3:[3]

A simple answer from vscode

lower_bound: find the first pos in which val could be inserted without changing the order

upper_bound: find last postion in which val could be inserted without changing the order

Solution 4:[4]

The simple answer is [ lower_bound, upper_bound )

s.lower_bound(t) will return iterator to the first element v in set such that v >= t
s.upper_bound(t) will return iterator to the first element v in set such that v > t.

When we often call xxxxx_bound for the STL set or map,
we often want to find the data in some range.

I share some usages of lower_bound & upper_bound samples here. So it could be easy for everyone to use it and remember it.

iterate all values in [A, B)

set<int> s = {0,1,2,10,11,12,15};
int A=1, B=11;
for(auto iter = s.lower_bound(A); iter != s.lower_bound(B); iter++) {
    cout<<*iter<<"\t";
}

Result

1       2       10

It show all v in set s satsify 1 < v <= 11 a.k.a all v in [1, 11)

iterate all values in [A, B]

set<int> s = {0,1,2,10,11,12,15};
int A=1, B=11;
for(auto iter = s.lower_bound(A); iter != s.upper_bound(B); iter++) {
    cout<<*iter<<"\t";
}

Result

1       2       10      11

It show all v in set s satsify 1 <= v <= 11 a.k.a all v in [1, 11]

iterate all values in (A, B)

set<int> s = {0,1,2,10,11,12,15};
int A=1, B=11;
for(auto iter = s.upper_bound(A); iter != s.lower_bound(B); iter++) {
    cout<<*iter<<"\t";
}

Result

2       10

It show all v in set s satsify 1 < v < 11 a.k.a all v in (1, 11)

Iterate all values in (A, B]

set<int> s = {0,1,2,10,11,12,15};
int A=1, B=11;
for(auto iter = s.upper_bound(A); iter != s.upper_bound(B); iter++) {
    cout<<*iter<<"\t";
}

Result

2       10      11

It show all v in set s satsify 1 < v <= 11 a.k.a all v in (1, 11]

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 Ruben Helsloot
Solution 2 SingerOfTheFall
Solution 3 dinesh maaan
Solution 4 Milo Chen

Related Questions