Construir un mapa desordenado con tuplas como claves

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 sea recogido por ADL.

Estoy realmente sorprendido de que no ya escribir 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 lo he probado correcto, no lo he probado.

Todo está en los documentos...

• http://www.boost.org/doc/libs/1_38_0/doc/html/hash/custom.html
• http://www.boost.org/doc/libs/1_38_0/doc/html/hash/combine.html

Necesitas 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 hash explícita ahora:

boost::unordered_map< Edge, int > EdgeMap;

La documentación de Boost proporciona la interfaz requerida . Sin saber más sobre 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 i 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.

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 hashables estándar (cadenas, ints, etc.).

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

Ponga el código en un archivo de encabezado e inclúyalo y los conjuntos desordenados de tuplas funcionarán fuera 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://stackoverflow.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;                                 
        }                                              

    };
}