C++ STL中迭代器学习笔记

前言

初学C++ 时一提 STL 头就大，尤其看到源码中复杂的 __iterator_traits、advance、__distance 等等时，直接劝退。而在侯捷老师的《STL源码剖析》中，迭代器的讲解尤为精彩，深入浅出地剖析了“迭代器本质就是一个聪明指针”。

一、迭代器到底是什么？

通俗讲：迭代器是一个用来遍历容器的“泛型指针”。
在 C 语言里我们操作数组靠指针，而 C++ STL 容器结构多样：vector 是动态数组，list 是双向链表，map 是红黑树。那么算法如 sort、copy 如何统一处理？——这就要靠迭代器。
迭代器本质上是一个封装了指针行为的对象，重载了：

• *p 访问元素
• ++p / --p 移动
• p == q 比较位置

侯捷老师总结：指针是最原始的迭代器，而 STL 中的迭代器就是“行为像指针的类”。

二、五种迭代器类型

STL 根据操作能力，把迭代器分为五大类，每种都是前一种的超集。

你可以理解为五个“段位”：
Input < Forward < Bidirectional < RandomAccess

侯捷提到：STL 的设计哲学是“最小需求设计”，算法根据最弱要求选择最小类型，然后在运行时通过模板 + traits 实现“能力分发”。

三、Traits 技术：类型萃取的魔法

当我们写一个泛型算法时，并不知道传入的迭代器是啥类型。这时就靠iterator_traits这个结构体提取类型信息：

template<typename Iterator>
struct iterator_traits {
    using iterator_category = typename Iterator::iterator_category;
    using value_type = typename Iterator::value_type;
    using difference_type = typename Iterator::difference_type;
    ...
};

这样就能在算法中写：

typename iterator_traits<Iter>::iterator_category()

来获得标签（如 random_access_iterator_tag），再通过函数重载进行调度。

👉 侯捷称其为 “类型的标签分发器”。

注意：
在定义类模板或者函数模板时，typename 和 class 关键字都可以用于指定模板参数中的类型。也就是说，以下两种用法是完全等价的。

template<typename T> /* ... */;
template<class T>    /* ... */;

核心问题：泛型算法中的迭代器不确定性
当我们编写泛型算法时（如 std::advance 或 std::distance），算法需要处理任意类型的迭代器：

template <typename Iter>
void my_algorithm(Iter first, Iter last) {
    // 这里不知道 Iter 是什么类型的迭代器
    // 应该用 ++it 还是 it + n？
}

iterator_traits 的解决方案
iterator_traits 是一个类型萃取（type trait）工具，它提供了标准化的方式来获取迭代器的属性：

template<typename Iterator>
struct iterator_traits {
    // 从迭代器类型本身提取信息
    using iterator_category = typename Iterator::iterator_category;
    using value_type = typename Iterator::value_type;
    using difference_type = typename Iterator::difference_type;
    // ...
};

关键设计：迭代器标签（Tags）
迭代器标签是空结构体，用于标识迭代器的能力等级：

struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : input_iterator_tag {};
// ... 其他标签

标签分发（Tag Dispatching）机制
在算法中，我们这样使用标签：

template <typename Iter>
void my_advance(Iter& it, int n) {
    // 获取迭代器标签类型
    using category = typename iterator_traits<Iter>::iterator_category;
    
    // 创建标签实例并分发到具体实现
    my_advance_impl(it, n, category{});
}

具体实现的分派
针对不同标签提供不同的实现：

// 基础实现（输入迭代器）
template <typename Iter>
void my_advance_impl(Iter& it, int n, input_iterator_tag) {
    while (n-- > 0) ++it;
}

// 优化实现（随机访问迭代器）
template <typename Iter>
void my_advance_impl(Iter& it, int n, random_access_iterator_tag) {
    it += n;  // 直接跳转，O(1) 复杂度
}

四、标签分发：用“空类”实现重载策略

在 advance 和 distance 函数中，STL 利用标签分发实现了“为不同迭代器走不同逻辑”的技巧：

例：advance() 实现

template <typename InputIterator, typename Distance>
void advance(InputIterator& it, Distance n) {
    _advance(it, n, iterator_traits<InputIterator>::iterator_category());
}

void _advance(InputIterator& it, Distance n, input_iterator_tag) {
    while (n--) ++it;
}

void _advance(BidirectionalIterator& it, Distance n, bidirectional_iterator_tag) {
    if (n >= 0) while (n--) ++it;
    else while (n++) --it;
}

void _advance(RandomAccessIterator& it, Distance n, random_access_iterator_tag) {
    it += n;
}

这样就能根据it的类型自动调度最高效版本，而不需要用户干预。你不写 if，编译器帮你选最优路径。
这就是模板 + 类型标签的魅力，侯捷称其为 STL 最经典技巧之一。

五、常用适配器介绍（配合容器更强大）

STL 提供了很多“迭代器适配器”，用于将普通容器包装为“具有特殊行为”的对象。
1）reverse_iterator：反向迭代器
让你从容器尾部向前遍历。

vector<int> v = {1,2,3,4};
for (auto rit = v.rbegin(); rit != v.rend(); ++rit)
    cout << *rit; // 输出 4 3 2 1

它的 base() 实际指向正向迭代器的“后一位”，所以 *rit 实际是 *(base() - 1)。

2）back_insert_iterator：尾部插入器
把赋值操作转成容器的 push_back：

vector<int> v;
auto it = back_inserter(v);
*it = 1;  // 等价于 v.push_back(1);

适合配合 copy 使用：

copy(src.begin(), src.end(), back_inserter(dest));

3）insert_iterator：中间插入器
让插入发生在指定位置上：

insert_iterator it(v, v.begin() + 3);
*it = 99;  // 插入在第4位前

六、源码中 __normal_iterator 的作用

侯捷特别分析了 __normal_iterator：STL 的 vector、string 的迭代器其实就是对原生指针加壳。

template<typename T>
class __normal_iterator {
    T* ptr;
public:
    __normal_iterator& operator++() { ++ptr; return *this; }
    reference operator*() const { return *ptr; }
    ...
};

为什么不直接用裸指针？为了统一接口（traits支持、自定义功能等），让 vector<int>::iterator 看起来也是一个类，而不仅仅是 int*。

七、侯捷源码剖析特色总结

侯捷老师在书中对迭代器实现做了大量细节还原，比如：

• 自己写 __type_traits 结构体讲解
• distance_type()、value_type() 这些函数如何萃取类型
• 反复强调 template + traits + tag dispatching 是 STL 三大法宝

这些思想你在看完这篇文章后再读《STL 源码剖析》会更有感觉。

八、结语：学习迭代器的意义

理解 STL 迭代器，不只是为了写for (auto it = ...)而已，更重要的是：

1. 看懂源码 / 编写泛型库
2. 掌握 STL 高性能设计技巧
3. 为自己写容器打基础
4. 为面试算法题打通容器适配技巧

就像侯捷说的：“STL 是 C++ 的皇冠，迭代器是皇冠上的明珠。” 把这颗明珠理解透，你就打开了 C++ 泛型编程的大门。