rationale for std::lower_bound and std::upper_bound?

If you have multiple elements in the range [first, last) whose value equals the value val you are searching for, then the range [l, u) where

l = std::lower_bound(first, last, val)
u = std::upper_bound(first, last, val)

is precisely the range of elements equal to val within the range [first, last). So l and u are the "lower bound" and "upper bound" for the equal range. It makes sense if you're accustomed to thinking in terms of half-open intervals.

(Note that std::equal_range will return both the lower and upper bound in a pair, in a single call.)

std::lower_bound

Returns an iterator pointing to the first element in the range [first, last) that is not less than (i.e. greater or equal to) value.

std::upper_bound

Returns an iterator pointing to the first element in the range [first, last) that is greater than value.

So by mixing both lower and upper bound you are able to exactly describe where your range begins and where it ends.

Does this make any sense??

Yes.

Example:

imagine vector

std::vector<int> data = { 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6 };

auto lower = std::lower_bound(data.begin(), data.end(), 4);

1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6
                  // ^ lower

auto upper = std::upper_bound(data.begin(), data.end(), 4);

1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6
                           // ^ upper

std::copy(lower, upper, std::ostream_iterator<int>(std::cout, " "));

prints: 4 4 4

---

http://en.cppreference.com/w/cpp/algorithm/lower_bound

http://en.cppreference.com/w/cpp/algorithm/upper_bound

In this case, I think a picture is worth a thousand words. Let's assume we use them to search for 2 in the following collections. The arrows show what iterators the two would return:

So, if you have more than one object with that value already present in the collection, lower_bound will give you an iterator that refers to the first one of them, and upper_bound will give an iterator that refers to the object immediately after the last one of them.

This (among other things) makes the returned iterators usable as the hint parameter to insert.

Therefore, if you use these as the hint, the item you insert will become the new first item with that value (if you used lower_bound) or last item with that value (if you used upper_bound). If the collection didn't contain an item with that value previously, you'll still get an iterator that can be used as a hint to insert it in the correct position in the collection.

Of course, you can also insert without a hint, but using a hint you get a guarantee that the insertion completes with constant complexity, provided that new item to insert can be inserted immediately before the item pointed to by the iterator (as it will in both these cases).