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, &y]：x值捕获，y引用捕获
• STL中的应用sort自定义比较：sort(v.begin(), v.end(), [](int a, int b) { return a > b; });find_if条件查找：find_if(v.begin(), v.end(), [](int x) { return x > 10; });for_each遍历：for_each(v.begin(), v.end(), [](int x) { cout << x; });transform变换：transform(v.begin(), v.end(), v.begin(), [](int x) { return x * 2; });
• 优势代码简洁，就地定义避免定义额外函数对象可以捕获局部变量

6. 什么是函数对象（仿函数）？

答案：

• 定义重载了operator()的类对象可以像函数一样调用也叫仿函数（Functor）
• 优势可以保存状态可以内联优化，性能好可以作为模板参数
• STL中的函数对象算术：plus、minus、multiplies关系：less、greater、equal_to逻辑：logical_and、logical_or
• 示例

struct Compare {    bool operator()(int a, int b) const {        return a > b;    }};sort(v.begin(), v.end(), Compare());

7. 什么是适配器（Adapter）？

答案：

• 容器适配器stack：基于deque或vectorqueue：基于deque或listpriority_queue：基于vector
• 迭代器适配器reverse_iterator：反向迭代insert_iterator：插入迭代器stream_iterator：流迭代器
• 函数适配器bind：绑定参数not1/not2：逻辑取反mem_fn：成员函数适配
• 作用改变接口，提供新功能复用现有组件提高灵活性

8. 如何自定义比较函数？

答案：

• 函数指针

bool cmp(int a, int b) { return a > b; }sort(v.begin(), v.end(), cmp);

• 函数对象

struct Cmp {    bool operator()(int a, int b) const { return a > b; }};sort(v.begin(), v.end(), Cmp());

• lambda表达式

sort(v.begin(), v.end(), [](int a, int b) { return a > b; });

• 使用场景sort、stable_sort排序priority_queue、set、map的比较find_if、count_if等条件算法

9. STL中的空间配置器是什么？

答案：

• 作用负责内存分配和释放对象构造和析构隐藏内存管理细节
• 两级配置器第一级：大于128字节，直接malloc/free第二级：小于128字节，使用内存池
• 内存池优势减少malloc/free调用减少内存碎片提高分配效率
• 自定义配置器可以自定义内存分配策略用于特殊内存管理需求

10. 如何遍历和修改容器？

答案：

• 传统for循环

for (size_t i = 0; i < vec.size(); ++i) {    vec[i] *= 2;}

• 迭代器

for (auto it = vec.begin(); it != vec.end(); ++it) {    *it *= 2;}

• 范围for（C++11）

for (auto& elem : vec) {    elem *= 2;}

• 算法

for_each(vec.begin(), vec.end(), [](int& x) { x *= 2; });transform(vec.begin(), vec.end(), vec.begin(), [](int x) { return x * 2; });

• 注意事项修改时使用引用避免在遍历时改变容器大小注意迭代器失效