map是一种有索引的数据存储方式，即key-value结构。c++中，map有两种常见实现，分别是unordered_map与map。
#介绍
unordered_map底层使用了哈希表（Hash table，也称散列表），map底层使用了自平衡二叉查找树（类红黑树）。
#对比
正如名字里展示的那样，unordered_map是没有顺序的，而map默认按照key的值从小到大的顺序排序。下面是两种实现的时间复杂度对比。
| unordered_map | map | |
|---|---|---|
| 查找 | log(n) | 平均O(1)；最差O(n) |
| 插入 | log(n) + 再平衡 | 平均O(1)；最差O(n) |
| 删除 | log(n) + 再平衡 | 平均O(1)；最差O(n) |
stackoverflow上有两种实现的应用对比[1]，注意，不同的数据，不同的编译器，不同版本的编译器，都会对实际情况产生影响，下面的测试实例仅供参考。
#选择
在以下情况，建议使用map：
- 你需要这些元素有顺序
- 没有了
其他情况，都建议使用unordered_map。