Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to use unordered_set with custom types?

Tags:

c++

visual-c++

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

like image 554
Sriram Subramanian Avatar asked Mar 15 '12 22:03

Sriram Subramanian


People also ask

Is unordered_set faster than set?

unordered_set time was better than set (15494846) : 93<155. Only with adding this line: s.

How is unordered_set implemented in C++?

An unordered_set is implemented using a hash table where keys are hashed into indices of a hash table so that the insertion is always randomized.

How does unordered_set work?

Unordered sets are containers that store unique elements in no particular order, and which allow for fast retrieval of individual elements based on their value. In an unordered_set, the value of an element is at the same time its key, that identifies it uniquely.

Can we use pair in unordered_set?

We can use it to hash integers, floats, pointers, strings, arrays, pairs, and standard containers. That's all about using pair as a key in std::unordered_set in C++.


1 Answers

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

like image 86
Kerrek SB Avatar answered Oct 06 '22 05:10

Kerrek SB