C / C++ / 系统课时
unordered_map 和 map 差在哪
unordered_map 和 map 差在哪
map 和 unordered_map 都保存键值对,但它们最重要的差别不是名字,而是是否维护键的顺序以及为此采用的查找结构。选对容器,通常要先回答:是否需要有序遍历,再考虑查找性能。
学习目标
- 区分
map与unordered_map的顺序保证 - 理解两者典型查找复杂度及底层组织方式
- 能根据有序遍历、范围查询和哈希查找需求选择容器
顺序保证决定了最直接的差异
std::map 会按照比较器维护键的顺序,默认使用 std::less<Key>,因此从 begin() 遍历到 end() 时,键按升序出现。std::unordered_map 不提供这样的遍历顺序保证,元素顺序还可能在重新哈希后变化。
如果业务需要“按键从小到大输出”“从某个键开始做范围扫描”或使用 lower_bound、upper_bound,map 更合适。若只是按完整键查找、插入和删除,通常不关心遍历顺序,unordered_map 往往更直接。
两种容器怎样组织元素
C++ 标准规定的是行为和复杂度,不要求 map 必须使用某一种具体树结构。常见实现会用平衡搜索树组织 map,从根到叶通过键的大小关系缩小查找范围;unordered_map 则按哈希值把元素分配到多个桶中,再在目标桶内确认键是否相等。

这种结构差异也解释了复杂度:map 的查找、插入和删除通常有对数复杂度保证;unordered_map 在哈希分布良好时平均接近常数时间,但最坏情况下可能退化为线性时间。
用同一组数据观察差别
下面的程序让 map 负责有序遍历,让 unordered_map 负责按键查找。示例不打印 unordered_map 的遍历顺序,因为标准没有规定那个顺序。
#include <iostream>
#include <map>
#include <string>
#include <unordered_map>
int main() {
std::map<std::string, int> ordered{
{"carol", 95},
{"alice", 88},
{"bob", 91}
};
std::unordered_map<std::string, int> hashed{
{"carol", 95},
{"alice", 88},
{"bob", 91}
};
// map 的遍历顺序由键的比较规则决定。
bool first = true;
for (const auto& [name, score] : ordered) {
if (!first) {
std::cout << ' ';
}
std::cout << name;
first = false;
}
std::cout << '\n';
// unordered_map 更适合直接按完整键查找。
auto it = hashed.find("bob");
if (it != hashed.end()) {
std::cout << "bob=" << it->second << '\n';
}
}预期输出
alice bob carol
bob=91即使两种容器都能通过键找到 bob,只有 map 对遍历顺序作出保证。不要依赖某次运行中 unordered_map “碰巧有序”的结果。
选择时先看需求而不是只看 O(1)
| 需求 | 更合适的容器 | 原因 |
|---|---|---|
| 按键有序遍历 | map |
始终维护排序关系 |
| 范围查找 | map |
提供基于顺序的边界查找 |
| 大量完整键等值查找 | unordered_map |
平均查找通常为 O(1) |
| 键没有可用哈希函数 | map |
只需可比较 |
| 需要稳定、可预测的最坏查找上界 | map |
查找有 O(log n) 保证 |
unordered_map 的平均 O(1) 还依赖哈希函数质量、桶数量与负载因子;而 map 为维护顺序付出额外的树操作成本。实际选择时,先判断是否需要排序和范围能力,再考虑常数开销、内存占用与真实数据分布。