unordered_map基于哈希表，平均操作性能O(1)，无序且内存开销大；map基于红黑树，操作稳定O(log n)，支持有序遍历。大数据量追求速度选unordered_map，需顺序访问或稳定性选map，小数据量差异不明显。
C++ 中的 unordered_map 与 map 是两种常用的关联容器，它们都能将键映射到值，但在底层实现、性能特征和适用场景上有显著区别。 理解这些差异有助于在实际开发中做出更合理的选择。
底层实现机制不同
map 基于红黑树（一种自平衡二叉查找树）实现。这意味着元素在插入时会自动排序，按照键的升序排列。这种结构保证了稳定的 O(log n) 时间复杂度进行插入、删除和查找操作。
unordered_map 则基于哈希表实现。它通过哈希函数将键映射到桶中，理想情况下可以实现接近 O(1) 的平均时间复杂度。但当发生哈希冲突或负载因子过高时，性能可能退化为 O(n)。
性能对比：速度与稳定性权衡
在大多数情况下，unordered_map 的查找、插入和删除操作比 map 更快，尤其是在数据量较大时。这是因为哈希表避免了树结构的层级遍历。
立即学习“C++免费学习笔记（深入）”；
常见操作性能表现：
- 查找：unordered_map 平均 O(1)，map 为 O(log n)
- 插入：unordered_map 平均 O(1)，map 为 O(log n)
- 删除：两者均为平均 O(1) 或 O(log n)，取决于具体实现和情况
但 unordered_map 的性能受哈希函数质量和负载因子影响较大，最坏情况可能远不如 map 稳定。
是否需要有序遍历
如果需要按键的顺序访问元素，比如遍历时要求从小到大输出键值对，map 是唯一选择。它的迭代器按升序遍历所有元素。
unordered_map 不保证任何顺序，遍历结果是无序的。若后续需要排序，必须额外调用 sort 等函数，这会增加开销。
例如日志处理、时间序列分析等场景，常需有序结构，此时 map 更合适。
内存占用与哈希开销
unordered_map 通常比 map 占用更多内存。哈希表需要预留足够桶空间以减少冲突，同时维护指针和链表或其它冲突解决结构。
map 的节点只包含左右子节点指针和颜色标记，结构紧凑。虽然每个节点有固定开销，但整体空间利用率较高。
此外，unordered_map 需要定义合适的哈希函数。对于自定义类型作为键时，用户必须提供有效哈希算法，否则可能导致性能下降甚至错误行为。
基本上就这些。选择 map 还是 unordered_map 应根据实际需求权衡：追求高性能且无需排序时优先选 unordered_map；需要稳定性能和有序遍历则用 map。不复杂但容易忽略的是，小数据量下两者差异不大，过度优化反而增加代码复杂度。
