How to specialize std::hash<Key>::operator() for user-defined type in unordered containers?

Ren&#233; Richter picture René Richter · Nov 16, 2011 · Viewed 51.3k times · Source

To support user-defined key types in std::unordered_set<Key> and std::unordered_map<Key, Value> one has to provide operator==(Key, Key) and a hash functor:

struct X { int id; /* ... */ };
bool operator==(X a, X b) { return a.id == b.id; }

struct MyHash {
  size_t operator()(const X& x) const { return std::hash<int>()(x.id); }
};

std::unordered_set<X, MyHash> s;

It would be more convenient to write just std::unordered_set<X> with a default hash for type X, like for types coming along with the compiler and library. After consulting

  • C++ Standard Draft N3242 §20.8.12 [unord.hash] and §17.6.3.4 [hash.requirements],
  • Boost.Unordered
  • g++ include\c++\4.7.0\bits\functional_hash.h
  • VC10 include\xfunctional
  • various related questions in Stack Overflow

it seems possible to specialize std::hash<X>::operator():

namespace std { // argh!
  template <>
  inline size_t 
  hash<X>::operator()(const X& x) const { return hash<int>()(x.id); } // works for MS VC10, but not for g++
  // or
  // hash<X>::operator()(X x) const { return hash<int>()(x.id); }     // works for g++ 4.7, but not for VC10 
}                                                                             

Given compiler support for C++11 is yet experimental---I did not try Clang---, these are my questions:

  1. Is it legal to add such a specialization to namespace std? I have mixed feelings about that.

  2. Which of the std::hash<X>::operator() versions, if any, is compliant with C++11 standard?

  3. Is there a portable way to do it?

Answer

Kerrek SB picture Kerrek SB · Nov 16, 2011

You are expressly allowed and encouraged to add specializations to namespace std*. The correct (and basically only) way to add a hash function is this:

namespace std {
  template <> struct hash<Foo>
  {
    size_t operator()(const Foo & x) const
    {
      /* your code here, e.g. "return hash<int>()(x.value);" */
    }
  };
}

(Other popular specializations that you might consider supporting are std::less, std::equal_to and std::swap.)

*) as long as one of the involved types is user-defined, I suppose.