迭代器模式：STL的灵魂设计思想，面试问你理解有多深

郑伟强dev

59人浏览 · 2026-07-15 00:15:54

郑伟强dev · 2026-07-15 00:15:54 发布

上篇聊了stack和queue，STL容器的部分基本讲完了。今天聊一个贯穿整个STL的设计思想——迭代器。

迭代器是STL的灵魂。没有迭代器，容器和算法就是割裂的。有了迭代器，任何算法都能作用于任何容器。这就是STL最精妙的设计。

面试里考迭代器，通常从"什么是迭代器"开始，然后深入到迭代器的分类、traits、失效问题。

迭代器的本质

说白了，迭代器就是一个"智能指针"。它指向容器里的某个元素，支持解引用（*it）获取元素，支持移动（++it）到下一个元素。

std::vector<int> 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存的点云、甚至自定义容器存的点云。

// 通用的数据处理函数，不依赖具体容器类型
template<typename 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;
}

vector<double> v = {1.0, 2.0, 3.0};
list<double> 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需要随机访问迭代器，所以不能用于list（list有自己的sort成员函数）。std::find只需要输入迭代器，所以几乎可以用于所有容器。

迭代器失效：再强调一次

前面讲vector的时候提过迭代器失效，这里系统总结一下。

迭代器失效意味着迭代器指向的元素被删除或移动了，继续使用就是未定义行为。

vector：插入可能导致所有迭代器失效（扩容）。删除让被删元素之后的迭代器全部失效。

deque：中间插入所有迭代器失效，两端插入只有end()失效。删除只让被删元素的迭代器失效。

list/forward_list：插入不会使任何迭代器失效。删除只让被删元素的迭代器失效。

map/set/unordered_map：插入不会使任何迭代器失效。删除只让被删元素的迭代器失效。

关联容器的迭代器稳定性是最好的，这也是它们的优势之一。

反向迭代器和辅助函数

STL还提供了反向迭代器，从容器的末尾向前遍历：

vector<int> 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)。

list<int> 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。