map基于红黑树实现，插入、删除和查找时间复杂度为O(log n)，元素有序；unordered_map基于哈希表，平均时间复杂度O(1)，最坏O(n)，元素无序。频繁查找或大数据量优先unordered_map，需排序或范围查询选map。unordered_map依赖高质量哈希函数，内存占用高；小数据量或内存敏感场景两者差异小，map更稳定。选择依据使用场景权衡性能与顺序需求。
在C++中，map 和 unordered_map 是两种常用的关联容器，用于存储键值对。它们在性能上有明显差异，选择哪一个取决于具体使用场景。
底层结构不同导致性能差异
map 基于红黑树实现，元素按键有序排列，插入、删除和查找的时间复杂度为 O(log n)。由于是自平衡二叉搜索树，每次操作都会保持排序状态。
unordered_map 基于哈希表实现，元素无序存储，理想情况下插入、删除和查找的平均时间复杂度为 O(1)，最坏情况可能退化到 O(n)，比如发生大量哈希冲突时。
插入与查找性能对比
在大多数实际场景中，unordered_map 的平均性能优于 map，特别是在数据量较大且不需要排序的情况下：
立即学习“C++免费学习笔记（深入）”；
- 频繁的查找操作更适合 unordered_map，因为哈希表能快速定位元素
- 如果经常插入并立即查找，unordered_map 通常更快
- map 在每次插入时需要维护树结构和顺序，开销略高
但需要注意，unordered_map 的性能高度依赖于哈希函数的质量。如果哈希分布不均，可能导致链表过长，显著降低效率。
内存占用与遍历表现
unordered_map 通常比 map 占用更多内存，因为哈希表需要预留桶空间以减少冲突，负载因子一般低于1。而 map 每个节点只保存左右子树指针和颜色标记，结构更紧凑。
遍历时 map 表现稳定，且天然有序，适合需要按键排序输出的场景。unordered_map 遍历速度稍慢，访问顺序不可预测，且可能因 rehash 导致迭代器失效。
何时选择哪个？
根据需求做选择：
- 需要按键排序或范围查询（如找小于某值的所有键），用 map
- 追求最快速度且不关心顺序，用 unordered_map
- 自定义类型作为 key 时，确保提供高效的哈希函数才能发挥 unordered_map 优势
- 对内存敏感或数据量小（几百以内），两者差异不大，可优先考虑 map 的确定性
基本上就这些。unordered_map 平均性能更好，但有不确定性；map 性能稳定且自带排序，适合要求可预测行为的场景。合理选择能有效提升程序效率。
