如何std ::散列无序std :: pair [英] How to std::hash an unordered std::pair

问题描述

我希望能够将std::pair用作unordered_container中的键.我知道我可以通过以下方式做到这一点:

I want to be able to use a std::pair as a key in an unordered_container. I know that I could do this the following way:

template<typename T>
void
hash_combine(std::size_t &seed, T const &key) {
  std::hash<T> hasher;
  seed ^= hasher(key) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

namespace std {
  template<typename T1, typename T2>
  struct hash<std::pair<T1, T2>> {
    std::size_t operator()(std::pair<T1, T2> const &p) const {
      std::size_t seed(0);
      ::hash_combine(seed, p.first);
      ::hash_combine(seed, p.second);
      return seed;
    }
  };
}

但是，我希望散列忽略std::pair中元素的顺序(即为std::pair<A, B>和std::pair<B, A>)返回相同的种子.

However, I want the hashing to ignore the order of the elements in the std::pair (i.e., to return the same seed for std::pair<A, B> and std::pair<B, A>).

我想实现这一目标的一种方法是在创建我的std::pair<A, B>时应用某种排序(即某种自定义std::make_pair). 但这太严格了，因为对象A, B可能没有顺序.

One way I thought to achieve this is to apply some kind of ordering when creating my std::pair<A, B> (i.e., some kind of custom std::make_pair). But this is too restrictive since objects A, B might not have an order.

是否存在对std::pair进行哈希处理的标准方法，这样可以忽略元素的顺序并为std::pair<A, B>和std::pair<B, A>返回相同的种子?

Is there a standard way to hash a std::pair, such that the order of elements is ignored and the same seed is returned either for std::pair<A, B> and std::pair<B, A>?

推荐答案

不要排序对，而是排序散列:

Don't order the pairs, order the hashes:

namespace std {
  template<typename T1, typename T2>
  struct hash<std::pair<T1, T2>> {
    std::size_t operator()(std::pair<T1, T2> const &p) const {
      std::size_t seed1(0);
      ::hash_combine(seed1, p.first);
      ::hash_combine(seed1, p.second);

      std::size_t seed2(0);
      ::hash_combine(seed2, p.second);
      ::hash_combine(seed2, p.first);

      return std::min(seed1, seed2);
    }
  };
}

[实时示例]

这篇关于如何std ::散列无序std :: pair的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！