当前位置：首页 > news >正文

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

news 2025/7/21 9:10:54

文章目录

前言
一、迭代器到底是什么？
二、五种迭代器类型
三、Traits 技术：类型萃取的魔法
四、标签分发：用“空类”实现重载策略
五、常用适配器介绍（配合容器更强大）
六、源码中 __normal_iterator 的作用
七、侯捷源码剖析特色总结
八、结语：学习迭代器的意义

前言

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

一、迭代器到底是什么？

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

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

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

二、五种迭代器类型

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

类型	能力	举例容器
InputIterator（输入）	只读，前移	istream_iterator
OutputIterator（输出）	只写，前移	ostream_iterator
ForwardIterator（前向）	可读写，前移	forward_list
BidirectionalIterator（双向）	可读写，前后移动	list、set
RandomAccessIterator（随机访问）	可读写，可跳跃	vector、deque

你可以理解为五个“段位”：
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; }...
};