Why unordered_map::equal_range upper_bound returns end if a key is less than first map element

Question

I've noticed that unordered_map::equal_range upper_bound (first) returns end if the passed key is less than map's first one

#include <iostream>
#include <map>
#include <tr1/unordered_map>

using namespace std;

int main ()
{
    {
        std::map<char,int> mymap;
        mymap['c'] = 60;
        std::map<char,int>::iterator itup = mymap.equal_range('a').first;
        std::cout << "map::itup " << itup->first << std::endl;
    }

    {
        tr1::unordered_map<char, int> mymap;
        mymap['c'] = 60;
        mymap['d'] = 70;

        tr1::unordered_map<char, int>::iterator itlo = mymap.equal_range('a').first;
        tr1::unordered_map<char, int>::iterator itup = mymap.equal_range('a').second;

        cout << "unordered_map::itup " << (itup == mymap.end() ? "END" : "NOT END") << std::endl;
        cout << "unordered_map::itlo " << (itlo == mymap.end() ? "END" : "NOT END") << std::endl;
    }

    return 0;
}

Output is:

map::itup c
unordered_map::itup END
unordered_map::itlo END

Note that the behavior is different for map and unordered_map - any reasons for that or is this a problem in unordered_map?

Answer 1

This happens because an unordered_map is, not too surprisingly, unordered.

See §22.2.7 [unord.req], Table 70, regarding the requirements on equal_range:

Returns: A range containing all elements with keys equivalent to k. Returns make_­pair(b.end(), b.end()) if no such elements exist.

This is different from the requirements on an ordered associative container, like std::map, where equal_range is defined in terms of lower_bound and upper_bound.

std::unordered_map doesn't have lower_bound and upper_bound, for obvious reasons.