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

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;
}

Answer 1

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.

Answer 2

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.

Answer 3

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.