C++ unordered_map

unordered_map和map类似，都是存储的key-value的值，可以通过key快速索引到value。不同的是unordered_map不会根据key的大小进行排序，

存储时是根据key的hash值判断元素是否相同，即unordered_map内部元素是无序的，而map中的元素是按照二叉搜索树存储，进行中序遍历会得到有序遍历。

所以使用时map的key需要定义operator<。而unordered_map需要定义hash_value函数并且重载operator==。但是很多系统内置的数据类型都自带这些，

那么如果是自定义类型，那么就需要自己重载operator<或者hash_value()了。

结论：如果需要内部元素自动排序，使用map，不需要排序使用unordered_map

unordered_map可类比于Python中的字典。其实现使用了哈希表，可以以O(1)的时间复杂度访问到对应元素，但缺点是有较高的额外空间复杂度。与之对应，STL中的map对应的数据结构是红黑树，红黑树内的数据时有序的，在红黑树上查找的时间复杂度是O(logN)，相对于unordered_map的查询速度有所下降，但额外空间开销减小。

unordered_map常用函数
需要包含的文件

#include <unordered_map>
using namespace std;声明一个unordered_map
在< >中需要指明两个变量类型，类比Python的字典，第一个是key的类型，第二个是key对应的value的类型

unordered_map<char, int> map;插入键值对的方法，下面介绍两种方法
首先是使用[]的方法map['A'] = 1;在Python中，如果事先声明了一个字典，也可以用这种方法增加（key, value）对

## Python字典示例
dic = {} # 声明一个字典
dic['A'] = 1 # 增加键值对此外也可以用insert函数插入键值对。map.insert(make_pair('A', 1)); //这其中用到了std中的另外一个函数make_pair
判断所有key中是否包含某key

首先是使用iterator来判断的方法。假设我们要检验 'B' 是否在我们刚刚声明的map中，可以用unordered_map的成员函数：find()函数和end()函数。注意这里find()和end()所返回的数据类型均为iterator。在unordered_map中，如果find()没找到要找的key，就返回和end()一样的iterator值。

if(map.find('B') == map.end()) { //此时'B'不存在于map的键(key)中
// do something
}
其次也可以用count()函数。count()返回要查找的key在map的所有key种的出现次数。因为此容器不允许重复，故count()只可能返回 1 或 0，即可判断此key是否存在。

if(map.count('B') == 0) { //此时'B'不存在于map的键(key)中
// do something
}

移除元素
移除元素可以用erase()函数来完成，有三种形式：
iterator erase( const_iterator pos );
iterator erase( const_iterator first, const_iterator last );
size_type erase( const key_type& key );前两者使用迭代器指明移除范围，第三个移除特定key的键值对。
示例程序：（摘自cppreference.com）
#include <unordered_map>
#include <iostream>
int main()
{
std::unordered_map<int, std::string> c = {{1, "one"}, {2, "two"}, {3, "three"},
{4, "four"}, {5, "five"}, {6, "six"}};
// 从 c 擦除所有奇数
for(auto it = c.begin(); it != c.end(); ) //使用std::unordered_map<int,std::string>::iterator来表明
if(it->first % 2 == 1) //it的类型未免太冗长，因此用auto
it = c.erase(it);
else
++it;
for(auto& p : c) //for each 类型的loop
std::cout << p.second << ' '; //当使用iterator时，iterator的first指向key，second指向value
}

---------------------

参考文献：

https://blog.csdn.net/a690938218/article/details/79162529?utm_source=copy

https://www.cnblogs.com/muziyun1992/p/6829051.html