std::map 适合有序遍历和范围查询，o(log n) 稳定性能；std::unordered_map 平均 o(1) 查找但依赖哈希质量，实际性能受数据分布、负载因子和缓存局部性影响显著。
std::map 查找慢但有序，适合需要遍历或范围查询的场景
std::map 底层是红黑树，find() 时间复杂度稳定在 O(log n)，插入 / 删除也是 O(log n)。它天然保持键的升序排列，所以你能用 lower_bound()、upper_bound() 做区间查找，也能直接用迭代器顺序遍历——这些在 std::unordered_map 里要么不支持，要么得额外排序。
常见错误现象：std::map 被误用于高频随机查、无序场景，结果发现比 unordered_map 慢一倍还多，尤其数据量上万后；或者反过来，有人想用 map 做“按插入顺序遍历”，结果发现是按 key 排的，不是插入顺序。
- 适用场景：需要
equal_range()、需要遍历时保证 key 有序、key 类型没有合适哈希函数（比如自定义结构体没写std::hash特化） - 注意
operator 必须严格弱序，否则行为未定义——常见坑是用了 <code> 或漏处理相等情况 - 内存占用比
unordered_map小，指针开销固定，无哈希桶数组膨胀问题
std::unordered_map 查找快但无序，哈希质量决定实际性能
std::unordered_map 平均查找是 O(1)，但这是理想哈希分布下的摊销结果。实际中，如果哈希函数太弱（比如所有 key 都映射到同一个桶），会退化成 O(n) 链表遍历——这时候比 map 还慢。
常见错误现象：用 std::string 当 key 时没注意短字符串优化（SSO）不影响哈希，但频繁构造临时 string 对象导致哈希计算开销被忽略；或者对 int 类型 key 直接用默认哈希，却没意识到小整数集中时桶分布不均。
立即学习 “C++ 免费学习笔记（深入）”；
- 必须提供可接受的哈希函数和等价判断（
KeyEqual），自定义类型要显式特化std::hash或传入仿函数 - 负载因子（
load_factor()）超过默认阈值（通常是 1.0）会触发 rehash，瞬间卡顿——可用reserve()预分配桶数避免 - 不支持
lower_bound()等有序操作；迭代器遍历顺序完全不可预测
插入性能差异比查找更明显，尤其批量初始化时
插入 std::map 是 O(log n) 每次，而 unordered_map 在不 rehash 时接近 O(1)，但每次都要算哈希 + 可能的冲突处理。真正拉开差距的是批量构建：如果你有一组已知数据，unordered_map 用 reserve() 预设容量后插入，比 map 构建快 2–5 倍（取决于 n 和 key 类型）。
但反过来说，如果边插边查，且 key 分布极不均匀（比如大量哈希碰撞），unordered_map 插入可能反复 rehash，反而拖垮整体节奏。
- 初始化时知道元素数量？先调
reserve(n)，再循环insert()或emplace() - 用
emplace_hint()对map有帮助，但对unordered_map无效（无 hint 概念） - 移动语义影响：两者都支持 C++11 移动，但
unordered_map的桶数组移动成本略高
别只看“平均 O(1)”，先测你的数据分布和使用模式
理论复杂度只是起点。真实性能取决于你的 key 类型、数据量、访问 pattern（是随机查？还是连续查相邻 key？）、以及编译器和 STL 实现细节。比如 libc++ 的 unordered_map 默认桶数增长策略比 libstdc++ 更激进，同样代码在不同平台表现可能差 30%。
最容易被忽略的一点：缓存局部性。map 的节点在堆上分散分配，unordered_map 的桶数组是连续的，但每个桶里的链表节点仍是散的。如果 key 很小（如 int），unordered_map 的哈希表头 + 指针开销可能比红黑树还重。
- 实测建议：用你的真实数据集，跑
find()10 万次，对比 wall time，别信玩具例子 - 检查是否启用了
-DNDEBUG，debug 模式下unordered_map的调试检查会严重拖慢 - 如果 key 是指针或小整数，考虑用
absl::flat_hash_map替代——它把 key/value 内联存储，缓存友好得多
