如何在C++中创建无序对unordered_map
无序映射(unordered_map)不包含类似于int、string等的pair的哈希函数,因此如果我们想要哈希一个pair,则必须显式地提供能够哈希一个pair的哈希函数。unordered_map可接受最多5个参数:
- Key:键值类型
- Value:要存储在该键上的值类型
- Hash Function:用于哈希给定键的函数。如果未提供,则使用默认哈希函数。
- Pred:用于使两个密钥不具有相同哈希值的函数
- Alloc:用于为映射定义内存模型的对象
hash_function可以是任何东西,只要可以哈希给定的键。
// CPP program to demonstrate implementation of
// unordered_map for a pair.
#include
using namespace std;
// A hash function used to hash a pair of any kind
struct hash_pair {
template
size_t operator()(const pair& p) const
{
auto hash1 = hash{}(p.first);
auto hash2 = hash{}(p.second);
if (hash1 != hash2) {
return hash1 ^ hash2;
}
// 如果hash1 == hash2,则它们的XOR为零。
return hash1;
}
};
int main()
{
// 将哈希函数作为第三个参数发送
unordered_map, bool, hash_pair> um;
// 创建一些要用作键的对
pair p1(1000, 2000);
pair p2(2000, 3000);
pair p3(3005, 3005);
pair p4(4000, 4000);
// 将值插入无序映射。
um[p1] = true;
um[p2] = false;
um[p3] = true;
um[p4] = false;
cout << "Contents of the unordered_map : \n";
for (auto p : um)
cout << "[" << (p.first).first << ", "
<< (p.first).second << "] ==> " << p.second
<< "\n";
return 0;
}
输出
Contents of the unordered_map :
[4000, 4000] ==> 0
[3005, 3005] ==> 1
[1000, 2000] ==> 1
[2000, 3000] ==> 0
注意: 我们可以为pair创建映射。请查看 map of pair。原因是map基于自平衡BST,不需要哈希函数。
练习问题: 尼克尔(Nikhil)是一个旅行推销员,今天他正在拜访一座新城市的房子,以销售百科全书。新城市以x * y(1 <= x <= 10 ^ 9,1 <= y <= 10 ^ 9)的网格形式存在,在每个交叉口处都有一所房子。现在他记不住他已经访问过的房子,所以每当他进入一所房子时,他告诉你房子的坐标。您的工作是记住坐标,并在一天结束时告诉他所访问的所有房子。
示例:
输入:
输入他今天访问的房子数量:5
输入HouseNo. 1的坐标:1000 12985
输入HouseNo. 2的坐标:12548 25621
输入HouseNo. 3的坐标:14586 26481
输入HouseNo. 4的坐标:12 63
输入HouseNo. 5的坐标:14689 36945
输出:
今天访问的房子:
12 63
14689 36945
14586 26481
1000 12985
12548 25621