unordered_map是哈希表，平均O(1)查找但无序；map是红黑树，稳定O(log n)且按键有序、支持范围查找；前者要求key可哈希，后者要求key可比较；适用场景取决于是否需顺序、范围查询及性能敏感度。
unordered_map 是哈希表，map 是红黑树；前者平均 O(1) 查找，后者稳定 O(log n)；前者不排序、无序遍历，后者按键有序、支持范围查找。
底层实现与时间复杂度
unordered_map 基于哈希表（开放寻址或链地址法），插入、查找、删除的平均时间复杂度是 O(1)，最坏情况（大量哈希冲突）退化为 O(n)。实际中只要哈希函数合理、负载因子控制得当，性能非常接近常数。
map 基于自平衡红黑树，所有操作严格保证 O(log n) 时间复杂度，没有“最坏退化”风险，适合对最坏性能有强要求的场景。
常见操作对比：
立即学习“C++免费学习笔记（深入）”；
- 查找元素：unordered_map 平均快很多，尤其数据量大时；map 稳定但稍慢
- 遍历全部元素：两者都是 O(n)，但 unordered_map 遍历顺序完全随机，map 按 key 升序
- 按范围遍历（如 [k1, k2]）：map 支持 lower_bound + upper_bound 高效完成；unordered_map 只能全表扫描
键值约束与哈希要求
map 要求 key 支持 operator<（可比较），内置类型和大多数自定义类型只要定义了 < 就能用。
unordered_map 要求 key 可哈希：必须提供 hash 函数（std::hash 的特化）和 == 比较。内置类型（int、string 等）已自带；自定义类需手动特化 std::hash 或传入自定义哈希仿函数。
例如，若用 pair<int, int> 作 key：
- map 直接可用（pair 已定义 <）
- unordered_map 默认报错，需自己写 hash 结构或用 boost::hash
内存占用与缓存友好性
unordered_map 内部是桶数组 + 链表/动态数组，存在空桶（负载因子通常 ≤0.7～1.0），内存占用一般比 map 高；且节点分散在堆上，遍历时缓存命中率低。
map 是树形结构，每个节点单独 new，指针多、内存碎片略多，但节点布局相对紧凑，遍历局部性略好于严重冲突的 unordered_map。
小数据量（比如几百以内）时，两者差异不明显；数据量上万后，哈希表的常数优势才显著体现。
适用场景怎么选？
优先用 unordered_map 当：
- 只关心快速单点查找/插入/删除，不依赖顺序
- key 类型容易哈希（int、string、枚举等）
- 能接受无序遍历，或不需要迭代器区间操作
坚持用 map 当：
- 需要按键有序遍历（比如打印字典序结果）
- 频繁做范围查询（如统计某区间内有多少个 key）
- key 类型难哈希或不想写 hash 特化（如嵌套容器、自定义结构体）
- 对 worst-case 延迟敏感（实时系统、硬实时逻辑）
基本上就这些。别迷信“哈希一定更快”，也别因“有序”就默认选 map——看需求，测数据，再决定。
