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.

Answer 2

You asked for a range consisting of all elements in your unordered_map whose key is 'a'. Your unordered map contains no such elements. So, the range is empty.

The same is true of the map case. However, the way in which this condition is signified differs by container (although not really; keep reading). The containers std::map and std::unordered_map are not the same thing (hence they have different names). The former is ordered, whereas the latter is not, so for logical implementation reasons it works slightly differently:

unordered_map

Return value
std::pair containing a pair of iterators defining the wanted range. If there are no such elements, past-the-end (see end()) iterators are returned as both elements of the pair.

map

Return value
std::pair containing a pair of iterators defining the wanted range: the first pointing to the first element that is not less than key and the second pointing to the first element greater than key. If there are no elements not less than key, past-the-end (see end()) iterator is returned as the first element. Similarly if there are no elements greater than key, past-the-end iterator is returned as the second element.)

This difference does not matter. In either case you should simply iterate (first, second] to examine the elements (if any exist) in your range, as you would with any iterator range.

In your code, you didn't examine both parts of the pair returned in your map case. If you do then you'll find that first == second (again, signifiying an empty range).

Your map code effectively dereferences the "past-the-end" iterator of the returned range.

---

#include <iostream>
#include <map>
#include <unordered_map>

using namespace std;

int main ()
{
    {
        std::map<char,int> mymap;
        mymap['c'] = 60;
        std::map<char, int>::iterator itlo = mymap.equal_range('a').first;
        std::map<char, int>::iterator itup = mymap.equal_range('a').second;

        // This compares each range extent to the map's end, which is not really useful
        cout << "map::itup " << (itup == mymap.end() ? "END" : "NOT END") << '\n';
        cout << "map::itlo " << (itlo == mymap.end() ? "END" : "NOT END") << '\n';

        // This examines the range itself
        cout << "map range empty: " << (itlo == itup ? "YES" : "NO") << '\n';
        cout << "map range size: " << std::distance(itlo, itup) << '\n';
    }

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

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

        // This compares each range extent to the map's end, which is not really useful
        cout << "unordered_map::itup " << (itup == mymap.end() ? "END" : "NOT END") << std::endl;
        cout << "unordered_map::itlo " << (itlo == mymap.end() ? "END" : "NOT END") << std::endl;

        // This examines the range itself
        cout << "unordered_map range empty: " << (itlo == itup ? "YES" : "NO") << '\n';
        cout << "unordered_map range size: " << std::distance(itlo, itup) << '\n';
    }
}

// Output:
// 
// map::itup NOT END
// map::itlo NOT END
// map range empty: YES
// map range size: 0
// unordered_map::itup END
// unordered_map::itlo END
// unordered_map range empty: YES
// unordered_map range size: 0

(live demo)