unordered_map / unordered_set 中元组的通用哈希

Question

为什么 std::unordered_map<tuple<int, int>, string> 不能开箱即用？必须为 tuple<int, int> 定义一个哈希函数是很乏味的，例如

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

构建一个以元组为键的无序映射(Matthieu M.) 展示了如何为 boost::tuple 自动执行此操作。有没有在不使用可变参数模板的情况下为 c++0x 元组执行此操作？

当然这应该是标准:(

原文由 Leo Goodstadt 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

这适用于 gcc 4.5，允许所有包含标准哈希类型的 c++0x 元组成为 unordered_map 和 unordered_set 的成员，无需多言。 （我将代码放在头文件中并包含它。）

该函数必须位于 std 命名空间中，以便它被参数相关名称查找 (ADL) 拾取。

有没有更简单的解决方案？

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

    };
}

标准符合代码

Yakk 指出，在 std 命名空间中专门化事物实际上是未定义的行为。如果您希望有一个符合标准的解决方案，那么您需要将所有这些代码移动到您自己的命名空间中，并放弃 ADL 自动找到正确哈希实现的任何想法。代替 ：

 unordered_set<tuple<double, int> > test_set;

你需要：

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

其中 hash_tuple 是您自己的命名空间，而不是 std:: 。

为此，您首先必须在 hash_tuple 命名空间中声明一个哈希实现。这会将所有非元组类型转发到 std::hash ：

 namespace hash_tuple{

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

确保 hash_combine 调用 hash_tuple::hash 而不是 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);
    }
}

然后包含所有其他先前的代码，但将其放入 namespace hash_tuple 而不是 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;
        }
    };

}

原文由 Leo Goodstadt 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

在我的 C++0x 草案中， 20.8.15 表示 hash 专门用于内置类型（包括指针，但似乎并不意味着取消引用它们）。 It also appears to be specialized for error_code , bitset<N> , unique_ptr<T, D> , shared_ptr<T> , typeindex , string , u16string , u32string , wstring , vector<bool, Allocator> , and thread::id . （有趣的清单！）

我没有使用 C++0x 可变参数，所以我的格式可能有问题，但是这些方面的东西可能适用于所有元组。

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

这个版本实际编译运行

Yakk 观察到，直接 std::hash 在 技术上 是不允许的，因为我们正在特化一个标准库模板，其声明 不 依赖于用户定义的类型。

原文由 Mooing Duck 发布，翻译遵循 CC BY-SA 3.0 许可协议