Générique de hachage pour les tuples dans unordered_map / unordered_set

Cela fonctionne sur gcc 4.5 permettant à tous de c++0x tuples contenant standard hashable types de membres de
unordered_map et unordered_set sans plus tarder.
(J'ai mis le code dans un fichier d'en-tête et simplement l'inclure.)

La fonction est de vivre dans l'espace de noms std de sorte qu'il est pris par
argument dépendant de recherche de nom (ADL).

Est-il une solution plus simple?

#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;                                 
}                                              
};
}

Standard Conforme code

Yakk souligne que la spécialisation des choses dans l'espace de noms std est en fait un comportement indéterminé. Si vous souhaitez avoir des normes conformes solution, alors vous avez besoin de déplacer l'ensemble de ce code dans votre propre espace de noms et d'abandonner toute idée de l'ADL de trouver le bon hash mise en œuvre automatiquement. Au lieu de :

unordered_set<tuple<double, int> > test_set;

Vous avez besoin:

unordered_set<tuple<double, int>, hash_tuple::hash<tuple<double, int>>> test2;

où hash_tuple est votre propre espace de noms plutôt que std::.

Pour ce faire, vous devez d'abord déclarer une valeur de hachage de la mise en œuvre à l'intérieur de la hash_tuple espace de noms. Cela permettra de transférer tous les non tuple types de std::hash:

namespace hash_tuple{
template <typename TT>
struct hash
{
size_t
operator()(TT const& tt) const
{                                              
return std::hash<TT>()(tt);                                 
}                                              
};
}

Assurez-vous que hash_combine appels hash_tuple::hash et pas 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);
}
}

Puis d'inclure tous les autres code précédent, mais le mettre à l'intérieur namespace hash_tuple et pas 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;                                 
}                                              
};
}

Dans mon C++0x projet, 20.8.15 dit de hachage est spécialisé pour les types intégrés (y compris les pointeurs, mais ne semble pas impliquer un déréférencement de mer). Il semble également être spécialisé pour error_code, bitset<N>, unique_ptr<T, D>, shared_ptr<T>, typeindex, string, u16string, u32string, wstring, vector<bool, Allocator>, et thread::id. (thème fascinant de la liste!)

Je n'ai pas utilisé le C++0x variadics, donc ma mise en forme est probablement la façon de congé, mais quelque chose le long de ces lignes pourrait fonctionner pour tous les tuples.

size_t hash_combiner(size_t left, size_t right) //replacable
{ return left + 0x9e3779b9 + (right<<6) + (right>>2);}
template<int index, class...types>
struct hash_impl {
size_t operator()(size_t a, const std::tuple<types...>& t) const {
typedef typename std::tuple_element<index, std::tuple<types...>>::type nexttype;
hash_impl<index-1, types...> next;
size_t b = std::hash<nexttype>()(std::get<index>(t));
return next(hash_combiner(a, b), t); 
}
};
template<class...types>
struct hash_impl<0, types...> {
size_t operator()(size_t a, const std::tuple<types...>& t) const {
typedef typename std::tuple_element<0, std::tuple<types...>>::type nexttype;
size_t b = std::hash<nexttype>()(std::get<0>(t));
return hash_combiner(a, b); 
}
};
template<class...types>
struct tuple_hash<std::tuple<types...>> {
size_t operator()(const std::tuple<types...>& t) {
const size_t begin = std::tuple_size<std::tuple<types...>>::value-1;
return hash_impl<begin, types...>()(0, t);
}
}

Cette version compile et s'exécute

Yakk a observé que, spécialisée std::hash est directement techniquement pas autorisé, car nous sommes spécialisé une bibliothèque standard modèle avec une déclaration qui ne pas dépendent d'un type défini par l'utilisateur.