C++ map lower_bound causes debug assertion failed

Question

I'm using Visual Studio 2012.

I made a class for a map like this:

classA
{
private:
    string a;
    string b;
    uint32_t start;
    uint32_t end;
};

and I defined a map and a function like this:

typedef std::map<uint32_t, classA, std::greater<uint32_t> > ClassAMap;
typedef ClassAMap::iterator ClassAMapIterator;

ClassAMap classAMap;
void lowerBoundTest(ClassAMap &classAMap)
{
    uint32_t test = 0;
    ClassAMapIterator it;

    cin >> hex >> test;
    it = classAMap.lower_bound(test);
    cout << "lower_bound of " << test << ": "
         << it->first << endl;
}

then I got this error when dereferencing iterator of the map.

Debug Assertion Failed!
Program: C:\Windows\system32\MSVCP110D.dll
File: C:\program files (x86)\microsoft visual studio 11.0\vc\include\xtree
Line: 137
Expression: map/set iterator not dereferencable
For information on how your program can cause an assertion failure, 
see the Visual C++ documentation on asserts.
(Press Retry to debug the application)

I don't get any error message when I define a map like this:

typedef std::map<uint32_t, classA> ClassAMap;
typedef ClassAMap::iterator ClassAMapIterator;

But I need to put a greater<> function for purpose. How can I get rid of this assertion failure?

Answer 1

lower_bound will return the iterator equal to the map's end() when the item you're searching for isn't in the map, and it's insertion point would be at the end of the map. Since end() is one past the end of the map, it doesn't point to a valid element of the map. Trying to dereference it is an error. Be lucky that you were running this in Debug mode with a checked iterator, otherwise you'd have just gotten undefined behavior instead of a nice error message.

The reason it changes when you order the map without greater is that it changes the order of the map; lower_bound is now returning begin() instead of end(), which is a valid element.

To see whether the element was found in the map, you should use equal_range instead of lower_bound and check that the two iterators are not equal. The first of the two is identical to what lower_bound returns.