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></:string>—— 一般够用，但极端 case 下可能碰撞偏高
实操建议：如果知道最终元素数 n，构造时显式调用 unordered_map<int int> m; m.reserve(n);</int>，避免运行时扩容。
迭代器失效规则完全不同
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 左右，<code>map 的常数优势可能反超 unordered_map；而红黑树的 log n 在现代 CPU 上未必比一次 cache miss 的哈希查找慢 —— 别光看复杂度，得测。
