Is it required that I create my own hash function for custom types? Is there no defaults I can use with unordered_set?
unordered_set time was better than set (15494846) : 93<155. Only with adding this line: s.
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.
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.
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++.
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.)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With