Std :: set, how do lower_bound and upper_bound work?

Question

I have this simple piece of code:

#include <iostream> #include <set> using std::set; int main(int argc, char argv) { set<int> myset; set<int>::iterator it_l, it_u; myset.insert(10); it_l = myset.lower_bound(11); it_u = myset.upper_bound(9); std::cout << *it_l << " " << *it_u << std::endl; } 

This prints 1 as the lower bound for 11 and 10 as the upper bound for 9.

I do not understand why 1 is printed. I was hoping to use these two methods to get a range of values ​​for a given upper bound / lower bound.

Answer 1

From cppreference.com to std :: set :: lower_bound :

Return value

An iterator pointing to the first element that is no less than a key. If such an element is not found, an iterator of the past end is returned (see end () ).

In your case, since you do not have elements in your set that is not less (that is, greater than or equal to) than 11, the iterator of the past end is returned and assigned to it_l . Then in your line:

 std::cout << *it_l << " " << *it_u << std::endl; 

You put off this prototype iterator it_l : this behavior is undefined and can lead to something (1 in your test, 0 or any other value with another compiler, or the program may even crash).

Your lower bound should be less than or equal to the upper bound, and you should not dereference iterators outside of a loop or any other test environment:

 #include <iostream> #include <set> using std::set; int main(int argc, char argv) { set<int> myset; set<int>::iterator it_l, it_u; myset.insert(9); myset.insert(10); myset.insert(11); it_l = myset.lower_bound(10); it_u = myset.upper_bound(10); while(it_l != it_u) { std::cout << *it_l << std::endl; // will only print 10 it_l++; } } 

Answer 2

This is UB. Your it_l = myset.lower_bound(11); returns myset.end() (since it cannot find anything in the set) that you do not check, and then you essentially print the value of the iterator of the past end.

Answer 3

Lower_bound () returns the first element to the iterator, which is no less than the key. When such an element is not found, the end () is returned.

Note that the iterator returned with end () points to an element that is end-to-end in the collection. This is the normal behavior of standard containers, indicating that something went wrong. Generally, you should always check this and act accordingly.

Your part of the code is an example of the aforementioned situation, since there are no elements in the set that are at least 11. “1” is printed - this is just the garbage value coming from the end () iterator.

Look at it with the following snippet:

 #include <iostream> #include <set> using std::set; int main(int argc, char argv) { set<int> myset; set<int>::iterator it_l, it_u; myset.insert(10); it_l = myset.lower_bound(11); if (it_l == myset.end()) { std::cout << "we are at the end" << std::endl; } it_u = myset.upper_bound(9); std::cout << *it_l << " " << *it_u << std::endl; }