C++ STL 之哈希 map unordered_map

一. 概述

在C++中，unordered_map 是一个关联容器，是一种基于哈希表的键值对容器，它存储了键值对（key-value），其中每个键（key）都是唯一的。

二. map & unordered_map的区别

map内部由红黑树实现，红黑树有自动排序的功能，因此map内部所有元素都是有序的，查找删除等为O(logN)，但是红黑树里的每个节点需要保存节点信息，所以占用空间大。
unordered_map内部由哈希表实现，通过把键值映射到Hash表中的位置来访问记录，查找为O(1)，元素的排列顺序是无序的。

三. 初始化

3.1. 头文件

#include <unordered_map>
#include <map>

3.2 声明

std::unordered_map<key_type, value_type> mp;
std::map<key_type, value_type> mp;

3.3 初始化方式

unordered_map<string,int> mp; 
unordered_map <ptr*, int> mp;

3.4 构造方式

//默认构造
unordered_map<string,int> mp;
//初始化函数列表
unordered_map<string,int> mp = {"语文",95}, {"数学",100}};
unordered_map<string,int> mp(5); // 构造并指定初始容量
//拷贝构造
unordered_map<string,int> mp2(mp1); 
//移动构造
unordered_map<string,int> mp3(move(mp1));

四. 常用接口

成员函数	释义
emplace()	插入键值对
insert()	插入键值对
find(key)	查找以 key 为键的键值对，若找到，则返回一个指向该键值对的正向迭代器；反之，则返回一个指向容器中最后一个键值对之后位置的迭代器
erase()	删除键值对
clear()	删除所有键值对
size()	键值对个数
empty()	判断是否为空，为空返回真，反之返回假
count(key)	在容器中查找以 key 键的键值对的个数
begin()	返回指向容器中第一个键值对的正向迭代器
end()	返回指向容器中最后一个键值对之后位置的正向迭代器
cbegin()	和 begin() 功能相同，返回的迭代器不能修改键值对
cend()	和 end() 功能相同，返回的迭代器不能修改键值对
at(key)	返回容器中存储的键 key 对应的值，若 key 不存在，则会抛出异常。
operator[key]	重载了 [] 运算符，根据key获取键值。（如果没有该键值对，就会将其插入）

五. 遍历

1. 迭代器

#include <iostream>
#include <unordered_map>
using namespace std;int main(){unordered_map<string,int> mp = {{"语文",95}, {"数学",100},{"英语",90}};// 迭代器访问for(unordered_map<string,int>::iterator it = mp.begin(); it != mp.end(); it++){cout << it->first << " " << it->second << endl;}//autofor(auto it = mp.begin(); it != mp.end(); it++){cout << it->first << " " << it->second << endl;}return 0;
}/*
output:
英语 90
数学 100
语文 95
英语 90
数学 100
语文 95
*/

2. 值遍历

#include <iostream>
#include <unordered_map>
using namespace std;int main(){unordered_map<string,int> mp = {pair<string,int>("语文",95),pair<string,int>("数学",100),pair<string,int>("英语",90),};// 值遍历for(pair<string,int> kv:mp){cout << kv.first << " " << kv.second << endl;}//autofor(auto kv:mp){cout << kv.first << " " << kv.second << endl;}return 0;
}/*
output:
英语 90
数学 100
语文 95
英语 90
数学 100
语文 95
*/

3.引用遍历

#include <iostream>
#include <unordered_map>
using namespace std;int main(){unordered_map<string,int> mp = {pair<string,int>("语文",95),pair<string,int>("数学",100),pair<string,int>("英语",90),};// 引用遍历，要加constfor(const pair<string,int>& kv:mp){cout << kv.first << " " << kv.second << endl;}//autofor(auto& kv:mp){cout << kv.first << " " << kv.second << endl;}return 0;
}/*
output:
英语 90
数学 100
语文 95
英语 90
数学 100
语文 95
*/

参考：
https://blog.csdn.net/qq_44431690/article/details/141650549?spm=1001.2014.3001.5506
https://www.runoob.com/cplusplus/cpp-libs-unordered_map.html
https://blog.csdn.net/qq_21539375/article/details/122003559#:~:text=c++%20unorde
https://blog.csdn.net/kingxzq/article/details/133364438#:~:text=%E5%9C%A8%20C++98/03