Construyendo un mapa desordenado con tuplas como llaves

En un progtwig de C ++ con Boost, estoy tratando de construir un mapa desordenado cuyas claves son tuplas de dobles:

typedef boost::tuples::tuple Edge; typedef boost::unordered_map EdgeMap; 

La inicialización del mapa se completa en Aceptar, sin embargo, cuando bash poblarlo 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&)' 

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

EDITAR:

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

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

¿Es posible acortarlo?

Necesitas un poco de materia delantera . Debido a la implementación subyacente de boost::tuples::tuple , haga de Edge una estructura para permitir que las sobrecargas se resuelvan correctamente. De lo contrario, no obtendrá partidos para

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

Código abajo:

 struct Edge { Edge(double x1, double x2, double x3, double x4) : tuple(x1,x2,x3,x4) {} boost::tuples::tuple 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; 

En realidad, podría 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 detecte.

En realidad me sorprende que no hayan escrito ya uno.

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

Nota: Solo lo he comprobado correctamente, no lo he probado.

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 predeterminado, por lo que debería funcionar sin una definición de hash explícita ahora:

 boost::unordered_map< Edge, int > EdgeMap; 

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

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

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

Coloque el código en un archivo de encabezado e inclúyalo, y los conjuntos de tuplas no ordenados funcionarán de manera inmediata:

 #include  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://stackoverflow.com/questions/4948780 template  inline void hash_combine(std::size_t& seed, T const& v) { seed ^= hash()(v) + 0x9e3779b9 + (seed<<6) + (seed>>2); } // Recursive template code derived from Matthieu M. template ::value - 1> struct HashValueImpl { static void apply(size_t& seed, Tuple const& tuple) { HashValueImpl::apply(seed, tuple); hash_combine(seed, get(tuple)); } }; template  struct HashValueImpl { static void apply(size_t& seed, Tuple const& tuple) { hash_combine(seed, get<0>(tuple)); } }; } template  struct hash> { size_t operator()(std::tuple const& tt) const { size_t seed = 0; HashValueImpl >::apply(seed, tt); return seed; } }; }