user8469759 user8469759 - 25 days ago 12
C++ Question

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

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

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