CODEWITHSUNDEEP
c++stl
John Tan
John Tan

Reputation: 147

why C++ lower_bound() allows return pointer equivalent to val while upper_bound() does not

I read the description for C++ upper_bound() function and lower_bound() function. It is interesting for me that upper_bound() only returns the first iterator with value > val (or return last iterator in the range [first, last) if val not found).

The implementation is different from lower_bound(), while it returns the first iterator NOT SMALLER than val, so it allows the return pointer equivalent to val.

I am just curious to know what is the purpose to design upper_bound() in this way that upper_bound() must NOT return an iterator with value equivalent to val?

For example:

vector<int> a = {1, 2, 3, 4};
auto i = lower_bound(a.begin(), a.end(), 2); // i is iterator at 2;
auto j = upper_bound(a.begin(), a.end(), 2); // j is iterator at 3;

http://www.cplusplus.com/reference/algorithm/lower_bound/

Upvotes: 3

Views: 918

Answers (2)

Saurav Sahu
Saurav Sahu

Reputation: 13934

upper_bound is useful in cases like std::multimap where values are stored in sorted order. It lets you traverse within a range where starting position can be decided by lower_bound, and end-before-this-position is decided by upper_bound. 

for (iter_type it = myMap.lower_bound("key_val"); it != myMap.upper_bound("key_val"); it++)

This for loop would traverse till the point key == key_val.

Upvotes: 0

Mooing Duck
Mooing Duck

Reputation: 66922

In C++, iterators usually work in pairs. The first iterator points to the first element to consider, and the last iterator points to one-past-the-last element to consider. This is to make looping easy:

for(it cur=first; cur!=last; cur++)

As such, lower_bound and upper bound together, form a "range of all elements equal to the item you searched for. The same range that std::equal_range returns.

Upvotes: 6

Related Questions