2025 年 7 月 6 日 星期日 天气：晴
今天在 tuple hash 的过程中遇到了问题。原生的 std::tuple 并不支持 hash。那么我们就自己来写一个吧，顺便学习一下相关的奇怪知识。
以下实现是作者自己的理解，可能有误，望读者批评指正！
首先我们知道，对于一个哈希的重载，std::hash 是一个结构体，我们需要重载他的 () 来实现自己的哈希函数。我们的大概想法如下：
template<typename T>
struct std::hash<T> {
std::size_t operator()(const T & arg) const {
return my_hash(arg);
}
};
那么对于一个 tuple，因为他的模板特化时模板参数不定长，我们就需要采用变长模板来实现我们的 hash 结构体重载 operator()。这样我们大概为：
template<typename ... T>
struct std::hash<std::tuple<T...>> {
std::size_t operator()(const std::tuple<T...> & arg) const {
// variadic template deal;
}
};
这样我们就需要思考如何递归地解决我们的模板展开。我们需要通过实现递归式地展开直到到达模板的末尾，通过 hash_combine 的方式来一个个组合成我们的最终 hash 值。首先我们先定义 hash_combine, 他将获得 tuple 中含有的基本类型
template <typename T>
inline void hash_combine(std::size_t& seed, const T& val) {
std::hash<T> hasher;
seed ^= hasher(val) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
接下来我们需要一个个地取值放入其中。我们可以通过：
template<std::size_t I = 0, typename ... T>
typename std::enable_if<(I < sizeof...(T)), void>::type
my_hash(std::size_t & seed, const std::tuple<T...> & tup) {
hash_combine(seed, std::get<I>(tup));
my_hash<I + 1, T...>(seed, tup);
}
首先学习一下 std::enable_if<B,T>。在 cppreference 上你可以看到：
If B is true, std::enable_if has a public member typedef type, equal to T; otherwise, there is no member typedef.
This metafunction is a convenient way to leverage SFINAE prior to C++20’s concepts, in particular for conditionally removing functions from the candidate set based on type traits, allowing separate function overloads or specializations based on those different type traits.
当 B（表达式）为 true 的时候，我们的 std::enable_if 将会具有 public 成员类型 T, 否则将不会具有类型的定义。这样，我们的元方程就可以使用 SFINAE(“Substitution Failure Is Not An Error”，替代失败并不是错误) 特性（其实我还没弄懂这到底是个什么），特别是基于类型萃取来讲函数从候选集合中移除（这里涉及到重载决议），允许不同的函数重载/特化基于不同的类型萃取。
说了一大段废话，其实就是：符合 B 的时候，函数出现并返回 T 类型。否则函数不会出现（不会被重载选择）。
这样在最后我们补充一个递归终点：
template <std::size_t Index = 0, typename... Types>
inline typename std::enable_if<Index == sizeof...(Types), void>::type
my_hash(std::size_t&, const std::tuple<Types...>&) {
}
这样，在 index 没有到达模板参数长度时，我们将采取前面的函数，持续递归。否则什么都不做。
最后补充上我们的结构体。在 C++11 的标准下就可以运行。可以尝试使用查看：
compiler explorer 1 C+±11 version
compiler explorer 2 boost mimic
C++-11 Version
template <typename T>
inline void hash_combine(std::size_t& seed, const T& val) {
std::hash<T> hasher;
seed ^= hasher(val) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
template <std::size_t Index = 0, typename... Types>
inline typename std::enable_if<Index == sizeof...(Types), void>::type
my_hash(std::size_t&, const std::tuple<Types...>&) {
}
template<std::size_t I = 0, typename ... T>
typename std::enable_if<(I < sizeof...(T)), void>::type
my_hash(std::size_t & seed, const std::tuple<T...> & tup) {
hash_combine(seed, std::get<I>(tup));
my_hash<I + 1, T...>(seed, tup);
}
template <typename ... T>
struct std::hash<std::tuple<T...> > {
std::size_t operator()(const tuple<T...> & tup) const {
std::size_t seed = 0;
my_hash(seed, tup);
return seed;
}
};
实际上这已经很接近我们 boost 库的实现，在 boost 库中，我们的 enable_if 采用的是通过 std::tuple_size<T>::size 来实现。
Boost Implementation（戏仿）
template<class T>
void hash_combine(std::size_t & seed, T element) {
std::hash<T> hasher;
seed ^= hasher(element) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
template<std::size_t I, typename T>
typename std::enable_if<(I == std::tuple_size<T>::value), void>::type
hash_combine_tuple_like(std::size_t &, T const &)
{
}
template<std::size_t I, typename T>
typename std::enable_if<(I < std::tuple_size<T>::value), void>::type
hash_combine_tuple_like(std::size_t & seed, T const & v)
{
hash_combine(seed, std::get<I>(v));
hash_combine_tuple_like<I+1>(seed, v);
}
template <class T>
std::size_t hash_tuple(T const & v) {
std::size_t seed = 0;
hash_combine_tuple_like<0>(seed, v);
return seed;
}
template <class T>
struct hash_tup {
std::size_t operator()(T const & val) const {
return hash_tuple<T>(val);
}
};
参考资料： boost container.hash
挖坑：后面再学习闭包，闭包展开，折叠表达式等相关技巧。
今日每日一题：
1865. 找出和为指定值的下标对
C++
class FindSumPairs {
private:
vector<int> nums1, nums2;
unordered_map<int, int> cnt;
public:
FindSumPairs(vector<int>& nums1, vector<int>& nums2) {
this->nums1 = nums1;
this->nums2 = nums2;
for (int num: nums2) {
++cnt[num];
}
}
void add(int index, int val) {
cnt[nums2[index]]--;
nums2[index] += val;
cnt[nums2[index]]++;
}
int count(int tot) {
int ans = 0;
for (int num: nums1) {
int res = tot - num;
if (cnt.count(res)) {
ans += cnt[res];
}
}
return ans;
}
};
明天再贴，因为想睡觉 
群：Introducing maple trees
