std::hash<std::pair<int, int> >
2024-09-18 06:00:05
标题是搞笑的
! 这个问题只需要 since C++11
问题:怎么让 unordered_map
支持使用 pair
作为 key?
如果你能把两个东西压到一个基本类型里那么就不用解决这个问题了 .
我们需要手写一个 Hash 函数吧 .
如果你用 xor 会被轻易卡掉
注意 unordered_map
如果哈希冲突了是单次线性的 .
事实证明一个有效的 Hash 函数是能加快程序运行速度的 .
#include <functional>
// from boost (functional/hash):
// see http://www.boost.org/doc/libs/1_35_0/doc/html/hash/combine.html template
template <typename T>
inline void hash_combine(std::size_t &seed, const T &val) {
seed ^= std::hash<T>()(val) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
// auxiliary generic functions to create a hash value using a seed
template <typename T> inline void hash_val(std::size_t &seed, const T &val) {
hash_combine(seed, val);
}
template <typename T, typename... Types>
inline void hash_val(std::size_t &seed, const T &val, const Types &... args) {
hash_combine(seed, val);
hash_val(seed, args...);
}
template <typename... Types>
inline std::size_t hash_val(const Types &... args) {
std::size_t seed = 0;
hash_val(seed, args...);
return seed;
}
struct pair_hash {
template <class T1, class T2>
std::size_t operator()(const std::pair<T1, T2> &p) const {
return hash_val(p.first, p.second);
}
};
// unordered_map<pair<string, string>, int, pair_hash>
Bonus.
Tuple
#include <functional>
namespace hash_tuple {
template <typename TT> struct hash {
size_t operator()(TT const &tt) const { return std::hash<TT>()(tt); }
};
// from boost (functional/hash):
// see http://www.boost.org/doc/libs/1_35_0/doc/html/hash/combine.html template
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);
}
// Recursive template code derived from Matthieu M.
template <class Tuple, size_t Index = std::tuple_size<Tuple>::value - 1>
struct HashValueImpl {
void operator()(size_t &seed, Tuple const &tuple) const {
HashValueImpl<Tuple, Index - 1>{}(seed, tuple);
hash_combine(seed, std::get<Index>(tuple));
}
};
template <class Tuple> struct HashValueImpl<Tuple, 0> {
void operator()(size_t &seed, Tuple const &tuple) const {
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...>>{}(seed, tt);
return seed;
}
};
// auxiliary generic functions to create a hash value using a seed
template <typename T> inline void hash_val(std::size_t &seed, const T &val) {
hash_combine(seed, val);
}
template <typename T, typename... Types>
inline void hash_val(std::size_t &seed, const T &val, const Types &... args) {
hash_combine(seed, val);
hash_val(seed, args...);
}
template <typename... Types>
inline std::size_t hash_val(const Types &... args) {
std::size_t seed = 0;
hash_val(seed, args...);
return seed;
}
struct pair_hash {
template <class T1, class T2>
std::size_t operator()(const std::pair<T1, T2> &p) const {
return hash_val(p.first, p.second);
}
};
} // namespace hash_tuple
#include <bits/stdc++.h>
int main() {
using ll = long long;
// std::unordered_map<std::pair<ll, ll>, ll, hash_tuple::pair_hash>
// hashmapPair; std::unordered_set<std::pair<ll, ll>, hash_tuple::pair_hash>
// hashsetPair;
std::unordered_map<std::pair<ll, ll>, ll, hash_tuple::pair_hash>
hashmapPair;
hashmapPair[{0, 0}] = 10;
std::unordered_set<std::pair<ll, ll>, hash_tuple::pair_hash> hashsetPair;
hashsetPair.insert({1, 1});
using TI = std::tuple<ll, ll, ll, ll>;
std::unordered_map<TI, ll, hash_tuple::hash<TI>> hashmapTuple;
hashmapTuple[{0, 1, 2, 3}] = 10;
std::unordered_set<TI, hash_tuple::hash<TI>> hashsetTuple;
hashsetTuple.emplace(0, 1, 2, 3);
return 0;
}
Reference:
- Why can't I compile an unordered_map with a pair as key? - Stack Overflow
- pair 作为 unordered_map unordered_set 的键值 C++ - YoungForest;English Ver. .
最新文章
- SQL Server读写分离实现方案简介
- 使用nbrbutil工具來處理requested media id is in use, cannot process request
- 在package.json里面的script设置环境变量,区分开发及生产环境。注意mac与windows的设置方式不一样
- tracert命令详解
- 如何ping通两台计算机
- 【Unity--Apwork框架】AOP编程--拦截,用于缓存和异常处理(Unity框架的拦截注入-Interception)
- Sharepoint 列表
- 事务Isolation Level 例子详解
- ORCL_INSTALL_WIN10
- OpenCV学习笔记(一)安装及运行第一个OpenCV程序
- JVM问题诊断常用命令:jinfo,jmap,jstack
- 利用原生JS判断组合键
- springboot集成Actuator
- Python基本类常用方法
- ubuntu tomcat 8.5.33 开启https
- 前端基础之jQuery
- (error) LOADING Redis is loading the dataset in memory
- JavaScript和Ajax部分(6)
- iOS 测试之非代码获取 iPhone 型号及其他信息
- JSON.stringify转化报错