上篇聊了stack和queueSTL容器的部分基本讲完了。今天聊一个贯穿整个STL的设计思想——迭代器。迭代器是STL的灵魂。没有迭代器容器和算法就是割裂的。有了迭代器任何算法都能作用于任何容器。这就是STL最精妙的设计。面试里考迭代器通常从什么是迭代器开始然后深入到迭代器的分类、traits、失效问题。迭代器的本质说白了迭代器就是一个智能指针。它指向容器里的某个元素支持解引用*it获取元素支持移动it到下一个元素。std::vectorint v {1, 2, 3, 4, 5}; // 用迭代器遍历 for (auto it v.begin(); it ! v.end(); it) { cout *it ; } // 输出: 1 2 3 4 5有了迭代器算法就不需要关心底层容器是什么// 同一个find算法可以用于vector、list、deque... auto it1 std::find(v.begin(), v.end(), 3); // vector auto it2 std::find(lst.begin(), lst.end(), 3); // list这就是迭代器的价值——解耦容器和算法。在机器人开发里迭代器的这个特性特别有用。比如你写了一个处理点云的算法参数传迭代器而不是具体的容器类型那这个算法就能处理vector存的点云、list存的点云、甚至自定义容器存的点云。// 通用的数据处理函数不依赖具体容器类型 templatetypename Iterator double computeMean(Iterator begin, Iterator end) { double sum 0; int count 0; for (auto it begin; it ! end; it) { sum *it; count; } return sum / count; } vectordouble v {1.0, 2.0, 3.0}; listdouble l {1.0, 2.0, 3.0}; cout computeMean(v.begin(), v.end()); // 都能用 cout computeMean(l.begin(), l.end());五种迭代器分类面试高频考点。STL把迭代器分成五类能力递增输入迭代器Input Iterator只读只能向前。*it读取it前进。比如istream_iterator。输出迭代器Output Iterator只写只能向前。*it value写入。比如ostream_iterator。前向迭代器Forward Iterator可读可写只能向前。比如unordered_map的迭代器。双向迭代器Bidirectional Iterator可读可写可以前后移动。多了--it。比如list、map的迭代器。随机访问迭代器Random Access Iterator可读可写可以跳跃式访问。支持it n、it - n、it[n]、it1 - it2。比如vector、deque的迭代器。// vector的迭代器是随机访问迭代器 auto it v.begin(); it 3; // 跳到第4个元素 cout it[1]; // 访问第5个元素 auto dist v.end() - v.begin(); // 距离O(1) // list的迭代器是双向迭代器 auto it2 lst.begin(); it2; // 可以 --it2; // 可以 // it2 3; // 编译错误不支持随机访问为什么分这么细因为不同的算法需要不同能力的迭代器。std::sort需要随机访问迭代器所以不能用于listlist有自己的sort成员函数。std::find只需要输入迭代器所以几乎可以用于所有容器。迭代器失效再强调一次前面讲vector的时候提过迭代器失效这里系统总结一下。迭代器失效意味着迭代器指向的元素被删除或移动了继续使用就是未定义行为。vector插入可能导致所有迭代器失效扩容。删除让被删元素之后的迭代器全部失效。deque中间插入所有迭代器失效两端插入只有end()失效。删除只让被删元素的迭代器失效。list/forward_list插入不会使任何迭代器失效。删除只让被删元素的迭代器失效。map/set/unordered_map插入不会使任何迭代器失效。删除只让被删元素的迭代器失效。关联容器的迭代器稳定性是最好的这也是它们的优势之一。反向迭代器和辅助函数STL还提供了反向迭代器从容器的末尾向前遍历vectorint v {1, 2, 3, 4, 5}; for (auto it v.rbegin(); it ! v.rend(); it) { cout *it ; } // 输出: 5 4 3 2 1还有两个很实用的辅助函数std::advance(it, n)把迭代器向前移动n步。对于随机访问迭代器是O(1)对于双向迭代器是O(N)。std::distance(it1, it2)计算两个迭代器之间的距离。同样随机访问迭代器O(1)其他O(N)。listint lst {1, 2, 3, 4, 5}; auto it lst.begin(); std::advance(it, 3); // 移动到第4个元素 cout *it; // 4 auto dist std::distance(lst.begin(), it); // 3在机器人开发里如果你需要对传感器数据做回看操作比如看前3帧的数据advance就很好用。手写迭代器面试偶尔会让你给自己的容器写迭代器。实现一个简单的前向迭代器class IntArray { int* data_; size_t size_; public: IntArray(int* data, size_t size) : data_(data), size_(size) {} class Iterator { int* ptr; public: Iterator(int* p) : ptr(p) {} int operator*() { return *ptr; } Iterator operator() { ptr; return *this; } bool operator!(const Iterator other) const { return ptr ! other.ptr; } }; Iterator begin() { return Iterator(data_); } Iterator end() { return Iterator(data_ size_); } }; IntArray arr(data, 5); for (auto val : arr) { // 支持range-based for cout val ; }关键点实现operator*、operator和operator!提供begin()和end()就能支持range-based for循环。实战中还有一个容易踩坑的地方迭代器失效的调试。在release模式下迭代器失效通常不会立刻崩溃而是读出脏数据或者跑到错误的位置这种bug特别难排查。我的经验是在开发阶段开启STL的调试模式——GCC下编译时加-D_GLIBCXX_DEBUG这样迭代器失效会直接报运行时错误而不是默默出错。MSVC在Debug模式下也有类似的迭代器检查。另外在代码review时看到在循环里对容器做insert或erase操作就要特别警惕先确认用的是哪个版本的迭代器。养成这个习惯能帮你避免很多隐蔽的迭代器失效bug。给正在准备面试的你一点建议迭代器在面试里考得比较灵活。必须掌握的五种迭代器分类及区别、迭代器失效规则、begin/end的用法。加分项能手写一个简单的迭代器、理解iterator_traits的作用、知道为什么sort不能用于list。iterator_traits是迭代器特征萃取它能获取迭代器指向的值类型、距离类型等。这是STL算法能针对不同迭代器类型做优化的基础。这个比较深入面试偶尔会提到。下篇进入现代C的世界——shared_ptr智能指针的第一篇。如果这篇文章对你有帮助欢迎点赞、在看、转发三连。 你的支持是我持续更新的最大动力。「机器人软件开发面试·从入门到精通」连载系列上一篇第33篇 STL之stack与queue——BFS/DFS的标配数据结构 下一篇预告第35篇 智能指针shared_ptr——现代C内存管理的答案有任何问题欢迎评论区留言我会尽量回复。