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 :(
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;
}
};
}