C++ map和unordered_map的区别
映射和无序映射之间存在巨大差异。只有我们清楚知道两者的内部工作原理,才能决定如何选择适合的那一个使用。
不同之处 :
比较项 | map | unordered_map |
---|---|---|
排序 | 递增顺序(默认) | 无排序 |
执行 | 自平衡BST(类似红黑树) | Hash Table |
搜索时间 | log(n) | O(1) -> 平均, O(n) -> 最坏情况 |
插入时间 | log(n) + 重新平衡 | 与搜索时间相同 |
删除时间 | log(n) + 重新平衡 | 与搜索时间相同 |
使用 std::map
- 需要有序数据。
- 必须打印/访问数据(按排序顺序)。
- 需要元素的前任/继任者。
示例代码:
// CPP program to demonstrate use of std::map
#include <bits/stdc++.h>
int main()
{
// Ordered map
std::map<int, int> order;
// Mapping values to keys
order[5] = 10;
order[3] = 5;
order[20] = 100;
order[1] = 1;
// Iterating the map and
// printing ordered values
for (auto i = order.begin(); i
!= order.end(); i++) {
std::cout << i->first
<< " : "\n << i->second << 'n';
}
}
运行结果:
1 : 1
3 : 5
5 : 10
20 : 100
使用 std::unordered_map
有以下情况时,可以考虑使用 std::unordered_map
:
- 需要保留一些数据的计数(示例 – 字符串)并且不需要排序。
- 需要单元素访问,即没有遍历。
// CPP program to demonstrate use of
// std::unordered_map
#include <bits/stdc++.h>
int main()
{
// Unordered map
std::unordered_map<int, int> order;
// Mapping values to keys
order[5] = 10;
order[3] = 5;
order[20] = 100;
order[1] = 1;
// Iterating the map and
// printing unordered values
for (auto i = order.begin();
i != order.end(); i++)
{
std::cout << i->first
<< " : "\n << i->second << 'n';
}
}
运行结果:
1 : 1
20 : 100
5 : 10
3 : 5