c++ map和unordered_map区别_c++哈希表与红黑树对比

unordered_map查找平均O(1)但不保序、可能因rehash失效迭代器；map查找O(log n)但有序、迭代器更稳定；小规模数据时map常数优势可能反超，需实测验证。

unordered_map 查找快但不保序，map 保证有序但稍慢

如果你只关心“查得快不快”和“需不需要按 key 排序”，结论很直接：unordered_map 平均 O(1) 查找，底层是哈希表；map 是 O(log n)，底层是红黑树，天然按键升序排列。选哪个，取决于你是否需要遍历时 key 有序，或者能否容忍哈希的额外内存与可能的扩容抖动。

插入性能差异明显，尤其在批量初始化时

map 插入稳定，每次都是 O(log n)，总时间可预测；unordered_map 理论均摊 O(1)，但实际中一旦触发 rehash（比如负载因子超过 max_load_factor() 默认 1.0），会重建整个桶数组，瞬间卡顿。常见坑：

• 没预估容量就循环 insert —— 可能多次 rehash，性能跳变
• 用自定义类型作 key 却没提供靠谱的 hash 和 operator== —— 表现未定义或大量冲突
• key 是字符串且长度差异大，但用默认 std::hash<:string> —— 一般够用，但极端 case 下可能碰撞偏高

实操建议：如果知道最终元素数 n，构造时显式调用 unordered_map m; m.reserve(n);，避免运行时扩容。

迭代器失效规则完全不同

map 的迭代器只在对应节点被 erase 时失效，插入不影响其他迭代器；unordered_map 更敏感：

立即学习“C++免费学习笔记（深入）”；

• insert 可能导致 rehash → 所有迭代器、引用、指针全部失效
• erase 只使被删元素的迭代器失效，其余仍有效（c++11 起）
• 哪怕只是 reserve 或 rehash，也会让所有迭代器失效

这意味着，若你在遍历 unordered_map 时中途插入新元素，不能假设当前迭代器还有效 —— 很多线上 bug 就出在这儿。

内存占用与缓存友好性反向权衡

unordered_map 需要维护桶数组 + 链表/动态数组（C++11 后多用单向链表或开放寻址变体），空载时也占不少内存；map 每个节点固定大小（通常 3 指针 + color bit），总内存更紧凑。但访问模式上：

• unordered_map 散列后地址跳跃，cache miss 高，尤其数据量大时
• map 中序遍历是树结构局部性较好，但随机查找跳转仍不如数组连续

如果你的 workload 是高频随机查 + 低频增删，且 key 类型支持高效哈希（如 int、size_t），unordered_map 多数情况赢；如果常做范围查询（如 lower_bound、upper_bound）、或需稳定内存+可预测延迟，map 更稳妥。

真正容易被忽略的是：哈希表不是万能加速器。当 n 左右，map 的常数优势可能反超 unordered_map；而红黑树的 log n 在现代 CPU 上未必比一次 cache miss 的哈希查找慢 —— 别光看复杂度，得测。