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 在哈希分布良好时平均接近常数时间,但最坏情况下可能退化为线性时间。

用同一组数据观察差别

下面的程序让 map 负责有序遍历,让 unordered_map 负责按键查找。示例不打印 unordered_map 的遍历顺序,因为标准没有规定那个顺序。

cpp
#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';
    }
}

预期输出

text
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 为维护顺序付出额外的树操作成本。实际选择时,先判断是否需要排序和范围能力,再考虑常数开销、内存占用与真实数据分布。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

unordered_map 和 map 差在哪

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通