C++ STL容器面试题

1. vector的底层实现原理是什么？

答案：

• 底层结构动态数组，连续内存空间三个指针：start（起始）、finish（结束）、end_of_storage（容量结束）
• 扩容机制容量不足时重新分配更大空间通常扩容为原来的1.5倍或2倍拷贝原有元素到新空间释放旧空间
• 时间复杂度随机访问：O(1)尾部插入/删除：平摊O(1)中间插入/删除：O(n)查找：O(n)
• 优缺点优点：随机访问快，内存连续，缓存友好缺点：插入删除慢，扩容有开销

2. list和vector的区别是什么？

答案：

• 底层结构list：双向链表，非连续内存vector：动态数组，连续内存
• 性能对比随机访问：vector O(1)，list O(n)插入删除：list O(1)，vector O(n)内存占用：list额外存储指针
• 迭代器vector：随机访问迭代器list：双向迭代器
• 使用场景vector：频繁随机访问，尾部操作list：频繁中间插入删除，不需要随机访问

3. map和unordered_map的区别？

答案：

• 底层实现map：红黑树（平衡二叉搜索树）unordered_map：哈希表
• 元素顺序map：按键有序（默认升序）unordered_map：无序
• 时间复杂度map：查找/插入/删除 O(log n)unordered_map：平均O(1)，最坏O(n)
• 内存占用map：较少，只存储节点指针unordered_map：较多，需要哈希表和桶
• 使用场景map：需要有序，范围查询unordered_map：只需快速查找，不关心顺序

4. set和multiset的区别？

答案：

• 元素唯一性set：元素唯一，不允许重复multiset：允许重复元素
• 底层实现都是红黑树自动排序
• 插入行为set：重复插入失败，返回已存在元素multiset：重复插入成功
• 使用场景set：需要去