一、map和unordered_map的区别
（1）需要引入的头文件不同
map: #include <map>
unordered_map: #include <unordered_map>
（2）内部实现机理不同
<1>map
map内部实现了一个红黑树（红黑树是非严格平衡二叉搜索树，而AVL是严格平衡二叉搜索树），红黑树具有自动排序的功能，因此map内部的所有元素都是有序的，红黑树的每一个节点都代表着map的一个元素。因此，对于map进行的查找，删除，添加等一系列的操作都相当于是对红黑树进行的操作，其时间复杂度都是O(logn)，最坏和平均都是。map中的元素是按照二叉搜索树（又名二叉查找树、二叉排序树，特点就是左子树上所有节点的键值都小于根节点的键值，右子树所有节点的键值都大于根节点的键值）存储的，使用中序遍历可将键值按照从小到大遍历出来。
<2>unordered_map
unordered_map内部实现了一个哈希表（也叫散列表，通过把关键码值映射到Hash表中一个位置来访问记录，查找的时间复杂度可达到O(1)，其在海量数据处理中有着广泛应用）。因此，其元素的排列顺序是无序的。但是并不是unordered_map查询时间一定比map短，因为实际情况中还要考虑到数据量，而且unordered_map的hash函数的构造速度也没那么快，所以不能一概而论，应该具体情况具体分析。
hash_map和unordered_map的底层实现是一样的，但是在C++11中将unordered_map引入了标准库，而hash_map没有，所以建议还是使用unordered_map比较好。
unordered_set就是在哈希表插入value，而这个value就是它自己的key。
（3）优缺点
<1>map
- 优点
（1）有序性，这是map结构最大的优点，其元素的有序性在很多应用中都会简化很多的操作；
（2）红黑树，内部实现一个红黑书使得map的很多操作在logn的时间复杂度下就可以实现，因此效率非常的高 - 缺点
空间占用率高，因为map内部实现了红黑树，虽然提高了运行效率，但是因为每一个节点都需要额外保存父节点、孩子节点和红/黑性质，使得每一个节点都占用大量的空间。
<2>unordered_map
- 优点
因为内部实现了哈希表，因此其查找速度非常的快。 - 缺点
哈希表的建立比较耗费时间。
（4）适用性
<1>map
对于那些有顺序要求的问题，用map会更高效一些
<2>unordered_map
对于查找问题，unordered_map会更加高效一些，因此遇到查找问题，常会考虑一下用unordered_map。
对于unordered_map或unordered_set容器，其遍历顺序与创建该容器时输入的顺序不一定相同，因为遍历是按照哈希表从前往后依次遍历的。
（5）使用
unordered_map的用法和map完全是一样的，提供了 insert，size，count，find等操作，并且里面的元素也是以pair类型来存贮的。其底层实现是完全不同的，上方已经解释了，但是就外部使用来说却是一致的
二、map和multimap的区别
multimap容器保存的是有序的键/值对，但是可以保存重复的元素。multimap中会出现具有相同键值的元素序列。multimap大部分成员函数的使用方式和map相同。因为重复键的原因，multimap有一些函数的使用方式和map有一些区别。
<1>访问元素
multimap不支持下标运算符，因为键并不能确定一个唯一元素。和 map 相似，multimap 也不能使用 at() 函数。
<2>删除元素
- 以待删除元素的迭代器作为参数，这个函数没有返回值；
-
erase()函数以一个键作为参数，它会删除容器中所有含这个键的元素，返回容器中被移除元素的个数 - 接受两个迭代器参数，这个范围内的所有元素都会被删除。
<3>count函数
multimap 的成员函数 count() 可以知道有多少个元素的键和给定的键相同。
三、unordered_multimap
在该数据结构里面的元素没有顺序，并且可以有多个key值相同。
网友评论