Why doesn't std::unordered_map<tuple<int, int>, string>
just work out of the box? It is tedious to have to define a hash function for tuple<int, int>
, e.g.
template<> struct do_hash<tuple<int, int>> { size_t operator()(std::tuple<int, int> const& tt) const {...} };
Building an unordered map with tuples as keys (Matthieu M.) shows how to automate this for boost::tuple
. Is there anyway of doing this for c++0x tuples without using variadic templates?
Surely this should be in the standard :(
The unordered_map::hash_function() is a built in function in C++ STL which is used to get the hash function. This hash function is a unary function which takes a single argument only and returns a unique value of type size_t based on it.
The answer is no, can't be done for all tuples, since a tuple is a variadic template type.
An unordered set of tuples is an unordered set in which each of the elements is a tuple. Note that by default an unordered set doesn't have the functionality of tuples.
Unordered_map IS a hash table actually. You may want to use a better example as, as is the second insert will fail since it has the same key.
This works on gcc 4.5 allowing all c++0x tuples containing standard hashable types to be members of unordered_map
and unordered_set
without further ado. (I put the code in a header file and just include it.)
The function has to live in the std namespace so that it is picked up by argument-dependent name lookup (ADL).
Is there a simpler solution?
#include <tuple> namespace std{ namespace { // Code from boost // Reciprocal of the golden ratio helps spread entropy // and handles duplicates. // See Mike Seymour in magic-numbers-in-boosthash-combine: // http://stackoverflow.com/questions/4948780 template <class T> inline void hash_combine(std::size_t& seed, T const& v) { seed ^= std::hash<T>()(v) + 0x9e3779b9 + (seed<<6) + (seed>>2); } // Recursive template code derived from Matthieu M. template <class Tuple, size_t Index = std::tuple_size<Tuple>::value - 1> struct HashValueImpl { static void apply(size_t& seed, Tuple const& tuple) { HashValueImpl<Tuple, Index-1>::apply(seed, tuple); hash_combine(seed, std::get<Index>(tuple)); } }; template <class Tuple> struct HashValueImpl<Tuple,0> { static void apply(size_t& seed, Tuple const& tuple) { hash_combine(seed, std::get<0>(tuple)); } }; } template <typename ... TT> struct hash<std::tuple<TT...>> { size_t operator()(std::tuple<TT...> const& tt) const { size_t seed = 0; HashValueImpl<std::tuple<TT...> >::apply(seed, tt); return seed; } }; }
Yakk points out that specialising things in the std namespace is actually undefined behaviour. If you wish to have a standards conforming solution, then you need to move all of this code into your own namespace and give up any idea of ADL finding the right hash implementation automatically. Instead of :
unordered_set<tuple<double, int> > test_set;
You need:
unordered_set<tuple<double, int>, hash_tuple::hash<tuple<double, int>>> test2;
where hash_tuple
is your own namespace rather than std::
.
To do this, you first have to declare a hash implementation inside the hash_tuple
namespace. This will forward all non tuple types to the std::hash
:
namespace hash_tuple{ template <typename TT> struct hash { size_t operator()(TT const& tt) const { return std::hash<TT>()(tt); } }; }
Make sure that hash_combine
calls hash_tuple::hash
and not std::hash
namespace hash_tuple{ namespace { template <class T> inline void hash_combine(std::size_t& seed, T const& v) { seed ^= hash_tuple::hash<T>()(v) + 0x9e3779b9 + (seed<<6) + (seed>>2); } }
Then include all the other previous code but put it inside namespace hash_tuple
and not std::
namespace hash_tuple{ namespace { // Recursive template code derived from Matthieu M. template <class Tuple, size_t Index = std::tuple_size<Tuple>::value - 1> struct HashValueImpl { static void apply(size_t& seed, Tuple const& tuple) { HashValueImpl<Tuple, Index-1>::apply(seed, tuple); hash_combine(seed, std::get<Index>(tuple)); } }; template <class Tuple> struct HashValueImpl<Tuple,0> { static void apply(size_t& seed, Tuple const& tuple) { hash_combine(seed, std::get<0>(tuple)); } }; } template <typename ... TT> struct hash<std::tuple<TT...>> { size_t operator()(std::tuple<TT...> const& tt) const { size_t seed = 0; HashValueImpl<std::tuple<TT...> >::apply(seed, tt); return seed; } }; }
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