如何为无序集合中的元组实现通用哈希函数？

无序集合中元组的通用哈希函数

std::unordered_map 和 std::unordered_set 容器提供高效的元素查找和插入基于它们的哈希值。但是，在不定义自定义哈希函数的情况下使用元组作为这些集合中的键可能会导致意外行为。

要纠正此问题，一种方法是为特定元组类型手动定义哈希函数，例如：

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

虽然这种方法有效，但为每个使用的元组类型定义哈希函数可能很乏味。要自动执行此操作，可以按如下方式实现通用哈希函数：

#include <tuple>

namespace std {
  namespace {

    // Code derived from Boost
    template<class T>
    inline void hash_combine(std::size_t& seed, T const& v) { ... }

    // Recursive template code from Matthieu M.
    template<class Tuple, size_t Index = std::tuple_size<Tuple>::value - 1>
    struct HashValueImpl { ... };

  }

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

此函数利用参数相关名称查找 (ADL) 来允许编译器根据元组类型自动选择正确的哈希实现.

标准一致性解决方案

值得注意的是，在std命名空间中定义非标准函数是未定义的行为。对于符合标准的解决方案，可以创建自定义命名空间并用于定义哈希函数：

namespace my_hash {

  // Forward non-tuple types to the std::hash
  template<typename TT>
  struct hash { ... };

  // Provide the optimized hash for tuples
  template<typename... TT>
  struct hash<std::tuple<TT...>> { ... };

}

使用此解决方案时，无序集合必须显式引用自定义哈希实现，如下所示：

unordered_set<
  std::tuple<double, int>,
  std::hash<std::tuple<double, int>>,
  std::equal_to<std::tuple<double, int>>
> test;  

以上是如何为无序集合中的元组实现通用哈希函数？的详细内容。更多信息请关注PHP中文网其他相关文章！