map基于红黑树，有序、O(log n)稳定；unordered_map基于哈希表，无序、平均O(1)但最坏O(n)，内存开销大。小数据量优先map，大数据量且无需排序时选unordered_map。
map 和 unordered_map 都是 C++ 标准库中用于键值对存储的关联容器，但底层实现、性能特征和适用场景差异显著——选错可能让查找从 O(log n) 变成 O(n)，或让本该稳定的遍历顺序彻底打乱。
底层实现：红黑树 vs 哈希表
map 基于自平衡二叉搜索树（通常是红黑树），保证键按严格弱序排列；unordered_map 基于哈希表，通过哈希函数将键映射到桶中，不维护任何顺序。
- map 的插入、删除、查找时间复杂度均为 O(log n)，且稳定可预测
- unordered_map 平均情况为 O(1)，但最坏情况（大量哈希冲突）退化为 O(n)
- map 支持 lower_bound/upper_bound 等范围查询；unordered_map 不支持，只能逐个遍历
迭代顺序：有序 vs 无序
map 的迭代器按 key 的升序（或自定义比较规则）遍历，天然适合需要排序输出、区间统计或二分查找的场景；unordered_map 迭代顺序完全不确定，与插入顺序、哈希分布、rehash 行为都有关。
- 若代码依赖“先插后出”或“按键递增遍历”，必须用 map
- 打印调试时看到 unordered_map 输出乱序，不是 bug，是设计使然
- 想模拟有序遍历 unordered_map？只能拷贝 key 到 vector 再 sort —— 多一次 O(n log n) 开销
内存与哈希成本：空间换时间
unordered_map 通常占用更多内存：需预留空桶（默认负载因子 1.0，实际常 >0.7 就 rehash），还要存哈希值、处理冲突的指针或链表节点；map 结构紧凑，每个节点只存 key、value、颜色和两个子指针。
立即学习“C++免费学习笔记（深入）”；
- 小数据量（如 n
- 自定义类型作 key 时，unordered_map 要求提供 hash 函数和 == 操作符；map 只需支持 operator< 或传入比较函数
- 字符串 key 下，std::hash<std::string> 效率高；但对长字符串频繁计算哈希，也可能成为瓶颈
何时选哪个？看这三点
不用死记复杂度，盯住三个实际需求：
- 要顺序？→ map（比如实现 LRU 缓存需按访问时间排序，但注意：map 本身按 key 排，真要按访问序得配合 list）
- 纯查改为主 + key 类型易哈希 + 数据量大？→ unordered_map（如配置项字典、DNS 缓存、图的邻接表）
- 不确定？先用 map，性能瓶颈再换 unordered_map 并压测（尤其注意极端 case 下的哈希碰撞，可用 reserve() 预分配桶数缓解）
基本上就这些。没有银弹，只有权衡——map 安全稳重，unordered_map 敏捷但有点脾气。
