c++ - Construyendo un mapa desordenado con tuplas como claves

boost tuples (5)

En realidad, puedes definir perfectamente una función hash general para boost::tuple . El único requisito es que viva dentro del mismo espacio de nombres para que ADL lo recoja.

De hecho, me sorprende que aún no hayan escrito uno.

namespace boost { namespace tuples { namespace detail { template <class Tuple, size_t Index = length<Tuple>::value - 1> struct HashValueImpl { static void apply(size_t& seed, Tuple const& tuple) { HashValueImpl<Tuple, Index-1>::apply(seed, tuple); boost::hash_combine(seed, tuple.get<Index>()); } }; template <class Tuple> struct HashValueImpl<Tuple,0> { static void apply(size_t& seed, Tuple const& tuple) { boost::hash_combine(seed, tuple.get<0>()); } }; } // namespace detail template <class Tuple> size_t hash_value(Tuple const& tuple) { size_t seed = 0; detail::HashValueImpl<Tuple>::apply(seed, tuple); return seed; } } }

Nota: solo he demostrado que es correcto, no lo he probado.

En un programa en C ++ con Boost, intento crear un mapa desordenado cuyas claves sean tuplas de dobles:

typedef boost::tuples::tuple<double, double, double, double> Edge; typedef boost::unordered_map< Edge, int > EdgeMap;

La inicialización del mapa se completa, sin embargo, cuando intento llenarlo con claves y valores

EdgeMap map; Edge key (0.0, 0.1, 1.1, 1.1); map[key] = 1;

Me aparece el siguiente mensaje de error:

/usr/include/boost/functional/hash/extensions.hpp:176: error: no matching function for call to ‘hash_value(const boost::tuples::tuple<double, double, double, double, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type>&)’

Supongo que es porque necesito especificar una función hash para las claves de tupla. ¿Cómo puedo hacer eso?

EDITAR:

Siguiendo las sugerencias a continuación, escribí la siguiente implementación:

#include <boost/tuple/tuple.hpp> #include <boost/unordered_map.hpp> typedef boost::tuples::tuple<double, double, double, double> Edge; struct ihash : std::unary_function<Edge, std::size_t> { std::size_t operator()(Edge const& e) const { std::size_t seed = 0; boost::hash_combine( seed, e.get<0>() ); boost::hash_combine( seed, e.get<1>() ); boost::hash_combine( seed, e.get<2>() ); boost::hash_combine( seed, e.get<3>() ); return seed; } }; struct iequal_to : std::binary_function<Edge, Edge, bool> { bool operator()(Edge const& x, Edge const& y) const { return ( x.get<0>()==y.get<0>() && x.get<1>()==y.get<1>() && x.get<2>()==y.get<2>() && x.get<3>()==y.get<3>()); } }; typedef boost::unordered_map< Edge, int, ihash, iequal_to > EdgeMap; int main() { EdgeMap map; Edge key (0.0, 0.1, 1.1, 1.1); map[key] = 1; return 0; }

¿Es posible acortarlo?

Este código de hash genérico para tuplas en unordered_map / unordered_set proporciona soporte mágico para todas las tuplas de c ++ 11 de tipos hashable estándar (strings, ints, etc.).

Como era de esperar, se parece mucho a la solución anterior de Matthieu M. pero sin dependencias de refuerzo.

Ponga el código en un archivo de cabecera e inclúyalo y los conjuntos de tuplas no ordenados funcionarán de la caja:

#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: // https://.com/questions/4948780 template <class T> inline void hash_combine(std::size_t& seed, T const& v) { seed ^= 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, get<Index>(tuple)); } }; template <class Tuple> struct HashValueImpl<Tuple,0> { static void apply(size_t& seed, Tuple const& tuple) { hash_combine(seed, 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; } }; }

La documentación de Boost proporciona la interfaz requerida . Sin saber más acerca de los valores involucrados, es difícil decir mucho más. Dado un objeto clave como entrada, tiene que producir un size_t que es determinista, es decir, es una función pura, donde el resultado depende únicamente del valor de entrada, por lo que dar la misma entrada siempre producirá el mismo código hash.

Necesitas un poco de atención . Debido a la implementación subyacente de boost::tuples::tuple , haga de Edge una estructura que permita que las sobrecargas se resuelvan correctamente. De lo contrario, no obtendrás ninguna coincidencia para

boost::hash_value(const Edge &)
operator==(const Edge &, const Edge &)

Código a continuación:

struct Edge { Edge(double x1, double x2, double x3, double x4) : tuple(x1,x2,x3,x4) {} boost::tuples::tuple<double, double, double, double> tuple; }; // XXX: less than ideal implementation! bool operator==(const Edge &a, const Edge &b) { return a.tuple.get<0>() == b.tuple.get<0>() && a.tuple.get<1>() == b.tuple.get<1>() && a.tuple.get<2>() == b.tuple.get<2>() && a.tuple.get<3>() == b.tuple.get<3>(); } // XXX: me too! std::size_t hash_value(const Edge &e) { std::size_t seed = 0; boost::hash_combine(seed, e.tuple.get<0>()); boost::hash_combine(seed, e.tuple.get<1>()); boost::hash_combine(seed, e.tuple.get<2>()); boost::hash_combine(seed, e.tuple.get<3>()); return seed; } typedef boost::unordered_map< Edge, int > EdgeMap;

Todo está en los documentos ...

Necesitarías algo como:

std::size_t hash_value(Edge const& e) { std::size_t seed = 0; boost::hash_combine( seed, e.get<0>() ); boost::hash_combine( seed, e.get<1>() ); boost::hash_combine( seed, e.get<2>() ); boost::hash_combine( seed, e.get<3>() ); return seed; }

... y luego puedes definir:

boost::unordered_map< Edge, int, boost::hash< Edge > > EdgeMap;

... en realidad esto es el predeterminado, por lo que debería funcionar ahora sin la definición de hash explícita:

boost::unordered_map< Edge, int > EdgeMap;