-
c++ unordered_map自定义key
一、unordered_map简介
unordered_map 是用哈希函数组织的map，采用哈希表存储数据，元素的位置取决于计算的散列值，是关联容器的一种。unordered_map使用一个哈希函数和关键字类型的==运算符（==运算符用来当发生碰撞时比较关键字key）来组织元素。
unordered_map的元素是关键字 - 值（key-value）对，无序保存元素，查询效率较高。在无序容器中，元素没有明确的排列次序，我们只关心的是，某个特定元素是否位于容器内。
元素值或其insert顺序，都不影响元素的位置，而且元素的位置有可能在容器生命中被改变。比如你放n个元素到这种集合内，它们的次序不明确，并且可能随时间而改变。
哈希表是一种以空间换时间的一种思想。
哈希函数又叫散列函数，哈希表又叫散列表。
二、自定义key
默认情况下，unordered_map使用关键字类型的 == 运算符来比较元素，因此默认情况下我们可以直接定义关键字是内置类型，比如string ，int ，指针等，标准库为这些内置类型提供了一个hash模板，hash
来组织其元素。 但是不能直接自定义关键字类型，比如结构体，因为我们不能使用标准库提供的默认hash模板，我们必须自己提供hash模板。
unordered_map是一个模板类，有5个参数：
/** * @brief A standard container composed of unique keys (containing * at most one of each key value) that associates values of another type * with the keys. * * @ingroup unordered_associative_containers * * @tparam _Key Type of key objects. * @tparam _Tp Type of mapped objects. * @tparam _Hash Hashing function object type, defaults to hash<_Value>. * @tparam _Pred Predicate function object type, defaults * to equal_to<_Value>. * @tparam _Alloc Allocator type, defaults to * std::allocator. * * Base is _Hashtable, dispatched at compile time via template * alias __umap_hashtable. */ - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
unordered_map模板类的第一参数就是key，对 key 的要求反而比map的要求更严格。它要求 key 具备两个条件，一是可以计算 hash 值，二是能够执行相等比较操作。第一个是因为散列表的要求，只有计算 hash 值才能放入散列表，第二个则是因为 hash 值可能会冲突，所以当 hash 值相同时，就要比较真正的 key 值
因此我们要自定义key，主要修改是第三个参数和第四个参数。
第三个参数是：哈希函数对象类型，用来确定key在哈希表中的位置，默认是hash<_Key>模板。
可以使用类模板特例化hash<_Key>模板，或者用函数重载调用operator()。第四个参数是：发生碰撞时用来比较key值，因为我们自定义key值，所以我们要重载 key 类型 == 运算符。
默认的 std::equal_to 会去调用 key 类型的 operator() 函数，比较内置类型的key值。typename _Pred = equal_to<_Key>,- 1
// One of the @link comparison_functors comparison functors@endlink. template<typename _Tp> struct equal_to : public binary_function<_Tp, _Tp, bool> { _GLIBCXX14_CONSTEXPR bool operator()(const _Tp& __x, const _Tp& __y) const { return __x == __y; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
当我们自定义key时，重载equal_to函数时，由于equal_to的比较函数参数和函数体都有const修饰，因此我们重载的比较函数参数和函数体也要有const修饰。
小结：
如果要自定义key，那么要修改两个地方：unordered_map模板类的第三个参数和第四个参数。
（1）Hashing function object type。
（2）Predicate（equal_to） function object type。
（3）重载比较函数时函数参数和函数体const修饰保持不变。对于typename _Hash = hash<_Key>模板，可以自定义hash模板，也可以特例化原模板所在命名空间的hash模板，即 std：：hash。
三、代码演示API
3.1 自定义哈希模板
#include#include #include struct student_id_info { std::string name; int arge; std::string grade; student_id_info(std::string a, int b, std::string c) : name(a), arge(b), grade(c){} student_id_info(){} //相等比较函数 //自己提供函数来替代==运算符：operator重载==运算符，当哈希需要处理碰撞时，用来比较结构体student_id_info，比较真正的key值是否相等 //简单点说就是多个key的value值在一个桶里（发生哈希碰撞），用来比较其key是否相等 //这里重载时参数和函数体的const修饰要与默认比较函数保持不变 bool operator==(const student_id_info& id) const { return name == id.name && arge == id.arge && grade == id.grade; } }; //自己提供的哈希模板 struct hash_fn { //哈希函数 //重载函数调用符：operator()，函数调用运算符必须是成员函数 std::size_t operator() (const student_id_info & id) const { //生成name的哈希值 std::size_t h1 = std::hash<std::string>()(id.name); 生成arge的哈希值 std::size_t h2 = std::hash<int>()(id.arge); //生成grade的哈希值 std::size_t h3 = std::hash<std::string>()(id.grade); //h1 ^ h2 ^ h3进行异或运算，形成给定的完整的student_id_info哈希值 //使用异或运算来降低哈希碰撞 return h1 ^ h2 ^ h3; } }; struct student_score { int math; int chinese; int english; student_score(int a, int b, int c) : math(a), chinese(b), english(c){} student_score(){} }; int main() { //umap多了我们自定义的 哈希模板参数：hash_fn std::unordered_map< student_id_info, student_score, hash_fn > umap = { {{"xiaoming", 18, "freshman"}, {100, 90, 80}}, {{"xiaohong", 19, "sophomore"}, {95, 90, 85}}, }; umap.emplace(student_id_info("xiaoli", 20, "Junior year"), student_score(90, 80, 95)); for (const auto &student: umap) { std::cout << "{" << student.first.name<< "," << student.first.arge << ","<< student.first.grade <<"}: " << "{" << student.second.math<< "," << student.second.chinese<< ","<< student.second.english <<"}" << std::endl; } student_id_info s_id = {"xiaohong", 19, "sophomore"}; if(umap.find(s_id) == umap.end()){ printf("dont't find the student\n"); }else{ printf("student math= %d, chinese = %d, english = %d\n", umap[s_id].math, umap[s_id].chinese, umap[s_id].english); } return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
结果展示：
3.2 类模板特例化
#include#include #include struct student_id_info { std::string name; int arge; std::string grade; student_id_info(std::string a, int b, std::string c) : name(a), arge(b), grade(c){} student_id_info(){} bool operator==(const student_id_info& id) const { return name == id.name && arge == id.arge && grade == id.grade; } }; //打开std命名空间，特例化std::hash namespace std { //定义一个特例化版本 template<> //模板参数为student_id_info struct hash<student_id_info> { std::size_t operator() (const student_id_info & id) const { std::size_t h1 = std::hash<std::string>()(id.name); std::size_t h2 = std::hash<int>()(id.arge); std::size_t h3 = std::hash<std::string>()(id.grade); return h1 ^ h2 ^ h3; } }; }//关闭std命名空间 struct student_score { int math; int chinese; int english; student_score(int a, int b, int c) : math(a), chinese(b), english(c){} student_score(){} }; int main() { //umap没有hash函数参数 std::unordered_map< student_id_info, student_score > umap = { {{"xiaoming", 18, "freshman"}, {100, 90, 80}}, {{"xiaohong", 19, "sophomore"}, {95, 90, 85}}, }; umap.emplace(student_id_info("xiaoli", 20, "Junior year"), student_score(90, 80, 95)); for (const auto &student: umap) { std::cout << "{" << student.first.name<< "," << student.first.arge << ","<< student.first.grade <<"}: " << "{" << student.second.math<< "," << student.second.chinese<< ","<< student.second.english <<"}" << std::endl; } student_id_info s_id = {"xiaohong", 19, "sophomore"}; if(umap.find(s_id) == umap.end()){ printf("dont't find the student\n"); }else{ printf("student math= %d, chinese = %d, english = %d\n", umap[s_id].math, umap[s_id].chinese, umap[s_id].english); } return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
其中 for (const auto &student: umap) 和 for (const auto student: umap)相比较，前者是引用umap的元素，后者是拷贝umap的元素，前者可以避免更多拷贝。
如果不加const修饰，即for (auto &student: umap) 和 for ( auto student: umap)，前者由于是引用，那么修改student就相当于修改了umap中的元素，而后者仅仅只是拷贝，修改student不会修改umap中的元素。
拷贝的开销远远大于引用。
总结
以上就是unordered_map自定义key结构体方法。
参考资料
c++ primer
https://finixlei.blog.csdn.net/article/details/110267430
https://blog.csdn.net/Histranger_/article/details/120199102 -
相关阅读:
GateWay实现负载均衡
apache shiro安全框架反序列化漏洞
ctfshow JWT (Web345-350)
产品经理书籍推荐
【python3】5.正则表达式
Java基础——了解进制和位运算
[PyTorch][chapter 54][GAN- 1]
JavaScript 任务池
数组模拟栈
[附源码]Python计算机毕业设计SSM隆庆祥企业服装销售管理系统（程序+LW)
- 原文地址：https://blog.csdn.net/weixin_45030965/article/details/126880141
