Upper/lower bounds don't work as I expect, can not understand why

Question

Here is the code. As a result I get "4 4". Don't understand why it is not "2 4" (according to lower and upper bounds' defenitions).

#include <bits/stdc++.h>
using namespace std;
int main()
{
    vector<int> v = {1, 2, 4, 5};
    vector<int>::iterator s , f;
    s = lower_bound(v.begin(), v.end(), 3);
    f = upper_bound(v.begin(), v.end(), 3);
    cout << (*s) << " " << (*f);
    return 0;
}

Please read [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) — Some programmer dude, Aug 21 '18 at 18:16
You misunderstand the definitions. In a case like this when the element is not part of the sequence, they will *always* return the same iterator. — Mark Ransom, Aug 21 '18 at 18:17
The two iterators returned by those functions designate a range that holds all the matching values. When there are no matching values the range is empty, so the iterators are equal. — Pete Becker, Aug 21 '18 at 18:45

score 6 · Accepted Answer · edited Aug 21 '18 at 18:30

From std::lower_bound:

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

The first element (from the beginning of the vector) which is not less than 3 is 4 and hence lower_bound returns 4.

From std::upper_bound:

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

The first element (from the beginning of the vector) which is greater than 3 is 4 and hence upper_bound returns 4.

The reason for this confusion is because upper_bound returns the first element that is greater than the given value, so by symmetry we expect lower_bound to return the last element (from the beginning of the vector) that is less than the given value. But alas, the std function doesn't obey this "expected" symmetry.

score 4 · Answer 2 · edited Aug 21 '18 at 20:36

It would be easier to understand/remember what std::lower_bound() and std::upper_bound() return knowing that std::equal_range() returns a pair of iterators, where the first one is equal to what std::lower_bound() returns, and the second one is equal to what std::upper_bound() returns.

So, here are different cases when they are called with a parameter of 4:

1 2 3 4 4 4 4 5 E
      |       |
      F       S    - first points to the first element, second to the one behind last, representing range which contains 4

1 2 3 4 5 E
      | |
      F S  same for one element

1 2 3 4 E
      | |
      F S  same as before, but 4 is the last element

1 2 3 5 E
      |
      F==S  first == second, which means range for elements equal to 4 is empty

1 2 3 E
      |
      F==S same as before but there is no element greater than 4

Where E means what container.end() returns - an iterator behind the last element.

Thanks, that actually does help make it easier for me to remember how `(lower|upper)_bound()` work :-) — Remy Lebeau, Aug 21 '18 at 20:37

score 3 · Answer 3 · answered Aug 21 '18 at 18:21

The naming of lower_bound and upper_bound is unfortunate as it invites confusion. The names refer to the results when searching through a sequence that has multiple elements that are exactly equivalent to the one you're searching; lower_bound returns the iterator to the start, and upper_bound returns one past the end.

When the element isn't part of the sequence, they both return an iterator to the first element greater than the one you were searching for. This might be the end iterator if there are none greater.

Upper/lower bounds don't work as I expect, can not understand why

3 Answers3

Linked