C++ STL算法与迭代器面试题

1. STL中常用的算法有哪些？

答案：

• 查找算法find：查找元素find_if：按条件查找binary_search：二分查找（需有序）lower_bound/upper_bound：查找边界
• 排序算法sort：快速排序stable_sort：稳定排序partial_sort：部分排序nth_element：第n个元素
• 修改算法copy：拷贝元素transform：变换元素replace：替换元素remove：删除元素（不真正删除）
• 数值算法accumulate：累加inner_product：内积partial_sum：部分和

2. 迭代器的分类有哪些？

答案：

• 输入迭代器（Input Iterator）只读，单向移动支持：++、*、==、!=例如：istream_iterator
• 输出迭代器（Output Iterator）只写，单向移动支持：++、*例如：ostream_iterator
• 前向迭代器（Forward Iterator）读写，单向移动支持：++、*、==、!=例如：forward_list的迭代器
• 双向迭代器（Bidirectional Iterator）读写，双向移动支持：++、--、*、==、!=例如：list、set、map的迭代器
• 随机访问迭代器（Random Access Iterator）读写，随机访问支持：+、-、[]、<、>等例如：vector、deque的迭代器

3. sort函数的实现原理是什么？

答案：

• 混合排序算法主要使用快速排序（Quick Sort）数据量小时使用插入排序（Insertion Sort）递归深度过大时使用堆排序（Heap Sort）称为内省排序（Introspective Sort）
• 时间复杂度平均：O(n log n)最坏：O(n log n)优于纯快速排序的O(n²)最坏情况
• 稳定性sort是不稳定排序stable_sort是稳定排序
• 使用要求需要随机访问迭代器元素需要支持<运算符或提供比较函数

4. remove和erase的区别是什么？

答案：

• removeSTL算法，不真正删除元素将不删除的元素移到前面返回新的逻辑结尾迭代器容器size不变
• erase容器成员函数，真正删除元素改变容器大小释放内存
• remove-erase惯用法vec.erase(remove(vec.begin(), vec.end(), value), vec.end());先remove移动元素，再erase删除
• 为什么这样设计算法不依赖具体容器提高灵活性和通用性可以一次remove多个值，再统一erase

5. lambda表达式在STL中的应用？

答案：

• 基本语法[捕获列表](参数列表) -> 返回类型 { 函数体 }简化版：[捕获列表](参数列表) { 函数体 }
• 捕获方式[]：不捕获[=]：值捕获所有[&]：引用捕获所有[x, &