C++ map 和unordered_map 的区别
C++中的map和unordered_map是两种常用的关联容器，
主要区别如下：
1. 底层实现
map：基于红黑树（自平衡二叉搜索树）实现，元素按键值自动排序 。
unordered_map：基于哈希表实现，元素存储顺序与插入顺序无关，通过哈希函数快速定位。
2. 性能特点
| 操作 | map (红黑树) | unordered_map (哈希表) |
|---|---|---|
| 插入/删除 | O(log n) | 平均O(1)，最坏O(n) |
| 查找 | O(log n) | 平均O(1)，最坏O(n) |
| 范围查询 | 支持（有序） | 不支持 |
| 内存占用 | 较低 | 较高（需维护哈希表） |
3. 适用场景
map：需要有序遍历、范围查询或稳定性能的场景。
unordered_map：追求快速查找、插入/删除，且无需顺序的场景。
4. 其他差异
头文件：map需<map>，unordered_map需<unordered_map>。
自定义排序：map支持通过比较函数自定义排序，unordered_map仅依赖哈希函数。
总结
选择map：需有序性、稳定时间复杂度或低内存占用。
选择unordered_map：需高频操作且能容忍哈希冲突。
问题思考：
- 什么是红黑树？ 红黑树排序算法是什么？
- unordered_map 的查找为什么可以做到O(1)? 其内部是如和实现的？