【c++】std::pair, std::tuple哈希

一般不能将函数/类注入namespace std，但模板函数对象类std::hash是一个例外
为了能使用std::pair / std::tuple作为哈希表的键值与哈希集合的元素，需要特化std::hash函数对象（operator()返回std::size_t的哈希值），std::pair / std::tuple包含了多个元素，参与到哈希值计算中的元素都相同时，哈希值相同，所以每个元素都应该参与到哈希值计算中。

采用boost::hash_combine的实现，先定义一个辅助函数组合总体哈希值与某一元素的哈希值

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

std::pair的哈希特化是简单的，因为std::pair定长为2

namespace std { 
template <typename U, typename V> struct hash<std::pair<U, V>> {
  size_t operator()(std::pair<U, V> const &tt) const {
    size_t seed = 0;
    hash_combine(seed, tt.first);
    hash_combine(seed, tt.second);
    return seed;
  }
};
} // namespace std

对于变长的std::tuple，可以使用std::apply解构std::tuple，std::apply会将tuple中每一个元素完美转发到f的形参上，而f是std::apply第一个实参。f参数长度不确定，可以使用变长模板参数的lambda来接tuple中的元素...x，函数体内部再用折叠表达式展开一个逗号表达式，其子表达式调用hash_combine(seed, x)即可

namespace std { 
template <typename... TT> struct hash<std::tuple<TT...>> {
  size_t operator()(std::tuple<TT...> const &tt) const {
    size_t seed = 0;
    std::apply([&seed](auto &&...x) { ((hash_combine(seed, x)), ...); }, tt);
    return seed;
  }
};
} // namespace std

完整代码

#include <tuple>
namespace std {
namespace {
template <typename T> inline void hash_combine(std::size_t &seed, T const &v) {
  seed ^= hash<T>()(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
} // namespace

template <typename... TT> struct hash<std::tuple<TT...>> {
  size_t operator()(std::tuple<TT...> const &tt) const {
    size_t seed = 0;
    std::apply([&seed](auto &&...x) { ((hash_combine(seed, x)), ...); }, tt);
    return seed;
  }
};

template <typename U, typename V> struct hash<std::pair<U, V>> {
  size_t operator()(std::pair<U, V> const &tt) const {
    size_t seed = 0;
    hash_combine(seed, tt.first);
    hash_combine(seed, tt.second);
    return seed;
  }
};
} // namespace std

使用例

#include <iostream>
#include <unordered_map>
#include <unordered_set>
int main() {
  std::unordered_set<std::pair<std::string, int>> h1{
      {"java", 18}, {"golang", 105}, {"cpp", 23}, {"rust", 172}};
  std::unordered_map<std::tuple<float, std::string, int>, int> h2{
      {{1.8, "java", 18}, -1}, {{1.05, "golang", 105}, -2}};
  for (auto && v: h1)
    std::cout << v.first << ", " << v.second << '\n';
}