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 lower bound for 11, and 10 as upper bound for 9.

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

Answer 1

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

Return value

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

In your case, since you have no elements in your set which is not less (i.e. greater or equal) than 11, a past-the-end iterator is returned and assigned to it_l. Then in your line:

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

You're deferencing this past-the-end iterator it_l: that's undefined behavior, and can result in anything (1 in your test, 0 or any other value with an other compiler, or the program may even crash).

Your lower bound should be less than, or equal to to the upper bound, and you should not dereference the iterators outside a loop or any other tested 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 can't find anything in the set), which you are not checking, and then you essentially print out the value of past-the-end iterator.

Answer 3

The lower_bound() returns iterator to the first element which is not less than a key. When such element is not found the end() is returned.

Note that the iterator returned with end() points to the element which is past-the-end in the collection. This is a normal behavior of standard containers to indicate that something went wrong. As a rule of thumb you should always check for this and act accordingly.

Your piece of code is the example of the above situation as there are no elements that are not less than 11 in the set. The '1' that is printed is just a garbage value coming from the end() iterator.

See it by yourself 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;
}