c++ - example - Hash genérico para tuplas en unordered_map/unordered_set

unordered_map c++ example

Question

¿Por qué std::unordered_map<tuple<int, int>, string> simplemente funciona de la caja? Es tedioso tener que definir una función hash para tuple<int, int> , por ej.

template<> struct do_hash<tuple<int, int>>                               
{   size_t operator()(std::tuple<int, int> const& tt) const {...}  }; 

Construir un mapa desordenado con tuplas como teclas (Matthieu M.) muestra cómo automatizar esto para boost::tuple . ¿Hay alguna forma de hacer esto para c ++ 0x tuplas sin usar plantillas variadas?

Seguramente esto debería estar en el estándar :(

Answer 1

En mi borrador de C ++ 0x, 20.8.15 dice que el hash está especializado en tipos incorporados (incluyendo punteros, pero no parece implicar desreferenciarlos). También parece estar especializado para error_code , bitset<N> , unique_ptr<T, D> , shared_ptr<T> , typeindex , string , u16string , u32string , wstring , vector<bool, Allocator> y thread::id . (Lista fascinante!)

No he usado variadicas de C ++ 0x, por lo que mi formateo probablemente esté apagado, pero algo en esta línea podría funcionar para todas las tuplas.

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

Esta versión realmente compila y ejecuta

Yakk ha observado que la especialización de std::hash directamente no está técnicamente permitida, ya que estamos especializando una plantilla de biblioteca estándar con una declaración que no depende de un tipo definido por el usuario.

Answer 2

Esto funciona en gcc 4.5 permitiendo que todas las tuplas de c ++ 0x que contienen tipos de elementos hashables estándar sean miembros de unordered_map y unordered_set sin más preámbulos. (Pongo el código en un archivo de cabecera y simplemente lo incluyo).

La función tiene que vivir en el espacio de nombres estándar para que sea captada por búsqueda de nombre dependiente del argumento (ADL).

¿Hay una solución más 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://.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;                                 
        }                                              

    };
}

Código de conformidad estándar

Yakk señala que las cosas especializadas en el espacio de nombres estándar son en realidad un comportamiento indefinido. Si desea tener una solución conforme a los estándares, entonces necesita mover todo este código a su propio espacio de nombres y renunciar a cualquier idea de que ADL encuentre la implementación correcta de hash automáticamente. En lugar de :

unordered_set<tuple<double, int> > test_set;

Necesitas:

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

donde hash_tuple es tu propio espacio de nombres en lugar de std:: .

Para hacer esto, primero debe declarar una implementación hash dentro del espacio de nombres hash_tuple . Esto reenviará todos los tipos que no sean de tupla al std::hash :

namespace hash_tuple{

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

Asegúrate de que hash_combine llamadas hash_tuple::hash y no 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);
    }
}

Luego incluya todos los demás códigos anteriores pero namespace hash_tuple dentro del namespace hash_tuple y no 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;                                 
        }                                              
    };

}

Answer 3

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

}