How to use unordered_set with custom types?

Question

Is it required that I create my own hash function for custom types? Is there no defaults I can use with unordered_set?

Crosscurrent

What's a "default way" to hash a Foo? – Adp

Answer 1

The standard library contains specialisations of std::hash<T> for the fundamental types, for pointers and for std::string (or rather, for all specializations of std::basic_string).

Unfortunately the library does not contain the following vital new-from-old combination function, which is however part of Boost, and which you should copy into your code:

template <class T>
inline void hash_combine(std::size_t & seed, const T & v)
{
    std::hash<T> hasher;
    seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

With this function, you can hash pairs, tuples, arrays, and any sort of range of elements that are themselves hashable. Browse the Boost sources for many examples and useful implementations. And obviously you can use this function to create a hash function for your own types. For example, here's hashing a pair:

template<typename S, typename T> struct pair_hash<std::pair<S, T>>
{
    inline std::size_t operator()(const std::pair<S, T> & v) const
    {
         std::size_t seed = 0;
         hash_combine(seed, v.first);
         hash_combine(seed, v.second);
         return seed;
    }
};

Please be aware, though, that hash-combining does not produce good hash values. The results have very poor statistic qualities (e.g. it is very easy to create hash collisions). Good hashing needs to be able to see all the raw input bits, and cannot be factored through partial hashes. (That's why there isn't a better solution in the current standard library; nobody has been able to come up with a satisfactory design.)

Adp

What is the explanation for the key line of the hash_combine function: seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2); – Airtoair

Nevermind, found the answer here (#4949280). – Airtoair

Answer 2

Yes, you will need to write your own hash function. This isn't as bad as it sounds: if your class has any hashable member that you know will be reasonably unique, you can just return the hash of that member.

You can provide this hash by specialising std::hash, or by explicitly passing the hash class as a template parameter.

Chaney