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：需要去重和排序multiset：需要排序但保留重复元素

5. deque的特点是什么？

答案：

• 底层结构双端队列分段连续内存（多个固定大小的数组）中央控制器管理各段
• 特点支持两端快速插入删除：O(1)支持随机访问：O(1)不保证内存完全连续
• 与vector对比deque两端操作快vector只有尾部操作快deque随机访问稍慢deque不会整体搬移
• 使用场景需要两端操作的场景queue和stack的底层容器

6. priority_queue的实现原理？

答案：

• 底层实现堆（heap）数据结构默认使用vector作为底层容器默认是大顶堆（最大元素在顶部）
• 时间复杂度插入：O(log n)删除顶部：O(log n)访问顶部：O(1)
• 自定义比较可以自定义比较函数实现小顶堆或其他排序规则
• 使用场景需要频繁获取最大/最小元素任务调度Dijkstra算法等

7. 如何选择合适的STL容器？

答案：

• 需要随机访问vector：默认选择deque：需要两端操作
• 需要频繁插入删除list：中间位置deque：两端位置
• 需要查找set/map：需要有序unordered_set/unordered_map：只需快速查找
• 需要排序set/multiset：自动排序priority_queue：只需最大/最小元素
• 考虑因素操作类型和频率内存占用是否需要有序是否允许重复

8. vector的reserve和resize的区别？

答案：

• reserve(n)预分配容量，不改变size只影响capacity不构造元素避免多次扩容
• resize(n)改变size和capacity如果n大于当前size，构造新元素如果n小于当前size，销毁多余元素
• 使用场景reserve：提前知道元素数量，优化性能resize：需要改变容器大小

9. 迭代器失效的情况有哪些？

答案：

• vector插入：插入点之后的迭代器失效删除：删除点之后的迭代器失效扩容：所有迭代器失效
• deque中间插入删除：所有迭代器失效首尾插入：迭代器失效，但引用和指针有效
• list插入：不影响其他迭代器删除：只有被删除元素的迭代器失效
• map/set插入：不影响其他迭代器删除：只有被删除元素的迭代器失效
• 避免方法使用返回的新迭代器及时更新迭代器避免在遍历时修改容器

10. STL容器的线程安全性如何？

答案：

• 读操作多线程同时读是安全的不需要加锁
• 写操作多线程写不安全需要外部同步（mutex）
• 读写混合不安全，需要同步一个线程写时，其他线程不能读写
• 解决方案使用互斥锁（mutex）使用读写锁（shared_mutex）使用线程安全的容器（C++11的atomic）每个线程使用独立容器