Hash générique pour les tuples dans la carte non ordonnée / ensemble non ordonné
Pourquoi ne pas std::unordered_map<tuple<int, int>, string> juste
travailler hors de la boîte?
Il est fastidieux de devoir définir une fonction de hachage pour tuple<int, int>, par exemple
template<> struct do_hash<tuple<int, int>>
{ size_t operator()(std::tuple<int, int> const& tt) const {...} };
Construire une carte non ordonnée avec des tuples comme clés (Matthieu M.) montre comment
automatisez cela pour boost::tuple. Y a-t-il de toute façon de le faire pour les tuples C++0x sans utiliser de modèles variadiques?
Sûrement cela devrait être dans la norme: (
3 réponses
Cela fonctionne sur gcc 4.5 permettant à tous les tuples C++0x contenant des types hashables standard d'être membres de
unordered_map et unordered_set sans plus tarder.
(Je mets le code dans un fichier d'en-tête et je l'inclue simplement.)
La fonction doit vivre dans l'espace de noms std afin qu'elle soit captée par recherche de nom dépendante de l'argument (ADL).
Y a-t-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;
}
};
}
Code conforme aux normes
Yakk souligne que se spécialiser dans l'espace de noms std est en fait comportement indéfini. Si vous souhaitez avoir une solution conforme aux normes, vous devez déplacer tout ce code dans votre propre espace de noms et abandonner toute idée D'ADL trouvant automatiquement la bonne implémentation de hachage. 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 implémentation de hachage dans l'espace de noms hash_tuple. Cela transmettra tous les types non tuple au 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);
}
}
Ensuite, incluez tout l'autre code précédent mais mettez-le à l'intérieur namespace hash_tuple et non 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;
}
};
}
#include <boost/functional/hash.hpp>
#include <tuple>
namespace std
{
template<typename... T>
struct hash<tuple<T...>>
{
size_t operator()(tuple<T...> const& arg) const noexcept
{
return boost::hash_value(arg);
}
};
}
Dans mon brouillon C++0x, 20.8.15 dit que le hachage est spécialisé pour les types intégrés (y compris les pointeurs, mais ne semble pas impliquer de les déréférencer). 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é C++0x variadics, donc mon formatage est probablement loin, mais quelque chose dans ce sens 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 fonctionne
Yakk a observé que la spécialisation std::hash directement est techniquement pas autorisée, puisque nous spécialisons un modèle de bibliothèque standard avec une déclaration qui ne Pas dépend d'un type défini par l'utilisateur.