hash_map: why it defines less, rather than equal_to

Question

C++, using Visual Studio 2010. A question about why a user-defined trait of hash_map actually requires total ordering.

I have a simple structure, say FOO, which only has a number of integers. I'd like to use hash_map, which is a hash table whose keys are unordered, to store the structure of FOO. I just need a fast searching of its associated value, so this is a right choice: hash_map<FOO, int32_t>.

However, I need to implement my own hash function and some compare functions for FOO. Here is the definitions of hash_map, taken from MSDN:

template <
   class Key, 
   class Type, 
   class Traits=hash_compare<Key, less<Key> >, 
   class Allocator=allocator<pair <const Key, Type> > 
>
class hash_map

It turned out that I needed to implement hash_compare functors:

template<class Key, class Traits = less<Key> >
   class hash_compare
   {
   Traits comp;
public:
   const size_t bucket_size = 4;
   const size_t min_buckets = 8;
   hash_compare( );
   hash_compare( Traits pred );
   size_t operator( )( const Key& _Key ) const; // This is a hash function
   bool operator( )(                            // This is an ordering function
      const Key& _Key1,
      const Key& _Key2
   ) const;
   };

Here is the detailed description of the bool operatod() from MSDN:

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.

The function supplied by hash_compare returns comp(_Key2, _Key1), where comp is a stored object of type Traits that you can specify when you construct the object hash_comp. For the default Traits parameter type less, sort keys never decrease in value.

It was easy to write the hash_compare class for FOO. This question is not for asking how to implement a class. However, it's not straightforward for me that why they have the default trait parameter as less<key> and require total ordering.

hash_map is an unordered data structure. So, I thought that it would be sufficient to have equal_to or not_equal_to instead of less or greater. However, the description of MSDN explicitly states that keys are ordered, which confuses me.

Did I misunderstand the definition of hash_map? Why STL's hash_map actually require orders of its key?

Answer 1

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).

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;