hash_map: why it defines less, rather than equal_to

Answer 1

The exact requirements on hash_map vary with the implementation, and some of them (as you've seen) don't make a whole lot of sense. That's part of why they decided not to include a hash_map (or hash_*) in TR1 and/or C++0x. Instead, they have unordered_[multi](map|set), which requires only equal_key, not operator<.

Bottom line: unless you have a truly outstanding reason to do otherwise, use unordered_map instead of hash_map.

Answer 2

hash_map that you are looking at is a Microsoft extension that came in in VS2003 and is actually now in stdext in Visual C++ - it's not part of the STL.

std::unordered_map is the official STL version of an associative container with value access by hashable key - the predicate on that is for equality, as you expected.

template<class Key,
    class Ty,
    class Hash = std::hash<Key>,
    class Pred = std::equal_to<Key>,
    class Alloc = std::allocator<std::pair<const Key, Ty> > >
    class unordered_map;

Answer 3

For any value _Key1 of type Key that precedes _Key2 in the sequence and has the same hash value (value returned by the hash function), hash_comp(_Key2, _Key1) is false. The function must impose a total ordering on values of type Key.

A total ordering of keys with the same hash value guarantees a total ordering of keys which hash to the same bucket.

That provides the opportunity for a more efficient implementation of search for a key within a particular bucket - e.g. Θ(log n) binary search is possible. If there is no such guaranteed ordering, the worst case (many different keys which are all in the same bucket because they all hash to the same value) is Θ(n).