map vs unordered_map的选择与性能对比
在什么场景下选择std::map(红黑树)？什么场景选择std::unordered_map(哈希表)？请从时间复杂度、空间占用、迭代器稳定性、内存布局、自定义key要求等维度进行全面对比。
回答
屠龙少年
核心对比：
| 特性 | map(红黑树) | unordered_map(哈希表) |
|---|---|---|
| 查找 | O(log n) | O(1)均摊，最坏O(n) |
| 插入/删除 | O(log n) | O(1)均摊，rehash时O(n) |
| 有序遍历 | 按key升序 | 无序 |
| 空间开销 | 3指针/节点+颜色位 | 桶指针+节点链接 |
| 范围查询 | 支持(lower_bound/upper_bound) | 不支持 |
| 迭代器稳定性 | 插入不失效(除非删除) | rehash时桶迭代器失效 |
| 自定义key | 需要operator< | 需要hash+operator== |
| 缓存性能 | 差(节点分散) | 较好(桶数组连续) |
选择map当：
- 需要有序遍历/范围查询
- 需要lower_bound/upper_bound
- 哈希函数容易冲突/定制困难
- 需要稳定的迭代器(插入不失效)
- 元素数量较少(≤100时log n与O(1)差别不大)
选择unordered_map当：
- 快速查找是主要需求
- 不需要有序访问
- 元素数量大(万级以上)
- 有高效哈希函数(如int/string内置hash)
- 可预分配桶减少rehash
C++20改进：std::map::contains()、std::unordered_map::contains()统一接口。插入时可以try_emplace避免重复key的构造。