STL 中几种 map 的区别(有序/无序、是否允许重复键)
哪些公司问过
答案要点
- 四种映射容器:map、multimap、unordered_map、unordered_multimap,按有序/无序和 key 是否唯一两维度划分
- map、multimap 基于红黑树,key 有序,增删查 O(log n),支持 lower_bound 等范围操作
- unordered 系列基于哈希表,平均 O(1),遍历无序,哈希冲突严重时可能退化
- map、unordered_map 的 key 唯一且支持 operator[],multi 版本允许重复 key 无下标访问
- 对应还有 set/multiset/unordered_set 等,只存 key,底层结构与 map 系列一致
易错点
- map 的 operator[] 在 key 不存在时会插入默认值,只查询时误用会意外改变容器
- unordered_map 遍历顺序不保证,不能依赖它输出有序结果
- multimap 没有 operator[],访问要用 find/equal_range
- 自定义类型做 unordered_map 的 key 需同时提供 hash 和相等比较,否则编译不过
面试官常见追问
- 哈希表在 STL 中的实现原理是什么?
- std::map 为什么用红黑树而不是普通二叉搜索树?
- unordered_map 的查找最坏情况是什么?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- vector 的扩容机制与性能174 场
- map 与 unordered_map 的区别167 场
- STL 的组成与常用容器151 场
- vector 与 list 的区别85 场
- STL 迭代器失效的场景47 场
- map 的底层实现:为什么用红黑树47 场
- STL 内存分配器12 场
- deque 的底层实现10 场
- unordered_map 底层实现、哈希冲突与 rehash9 场
- vector 和数组的区别8 场