夜雨聆风
STL源码:浅析迭代器、萃取机、适配器、容器vector
3. 迭代器
3.1. 迭代器的“五大等级” (Iterator Categories)
你必须理解迭代器不是“平等”的，它们的能力决定了算法的效率。
- Input/Output Iterator
：只读/只写，单向。 - Forward Iterator
：可读写，单向（如 forward_list）。 - Bidirectional Iterator
：双向移动（如 list,map）。 - Random Access Iterator
：像指针一样随机跳跃（如 vector,deque）。 - 核心逻辑
：算法（如 sort）会根据这些等级来选择 O(1) 还是 O(n)的实现路径。
最经典的例子就是 std::advance （将迭代器前进 n 步）和 std::distance （计算两个迭代器的距离）。我们直接看 std::advance 的源码实现，它完美展示了如何利用这“五大等级”进行性能分发。它通常位于 stl_iterator_base_funcs.h 中。这就是著名的 Tag Dispatching (标签分发) 技术。
1、 入口函数 advance (第 222 行)：
它首先通过 std::__iterator_category(__i) 获取迭代器的身份标签（例如 random_access_iterator_tag ）。
然后调用 __advance(__i, __d, tag) 。
2、 重载函数 1 ：针对 random_access_iterator_tag (第 186 行)：直接执行 __i += __n 。这是 O(1) 的操作。
3、 重载函数 2 ：针对 bidirectional_iterator_tag (第 170 行)：只能用 while 循环一步步走。这是 O(N) 的操作。
template<typename _InputIterator, typename _Distance>__attribute__((__always_inline__))inline _GLIBCXX17_CONSTEXPR voidadvance(_InputIterator& __i, _Distance __n){// concept requirements -- taken care of in __advancetypename iterator_traits<_InputIterator>::difference_type __d = __n;std::__advance(__i, __d, std::__iterator_category(__i));}
__advance(_RandomAccessIterator& __i, _Distance __n,random_access_iterator_tag){// concept requirements__glibcxx_function_requires(_RandomAccessIteratorConcept<_RandomAccessIterator>)if (__builtin_constant_p(__n) && __n == 1)++__i;else if (__builtin_constant_p(__n) && __n == -1)--__i;else__i += __n;}
template<typename _BidirectionalIterator, typename _Distance>inline _GLIBCXX14_CONSTEXPR void__advance(_BidirectionalIterator& __i, _Distance __n,bidirectional_iterator_tag){// concept requirements__glibcxx_function_requires(_BidirectionalIteratorConcept<_BidirectionalIterator>)if (__n > 0)while (__n--)++__i;elsewhile (__n++)--__i;}
总结
– 五大等级 不仅仅是文档里的概念，它们对应着实实在在的 空结构体类型 。
– STL 算法通过 iterator_traits 提取出这些类型，然后利用 函数重载 ，在编译期自动选择最快的代码路径。
– 这就是为什么你写 std::advance(vec.begin(), 5) 极快，而 std::advance(list.begin(), 5) 较慢的原因
3.2. 迭代器的“五种契约类型” (The 5 Typedefs)
每一个合格的类类型迭代器，内部必须定义这 5 个 typedef，否则萃取机无法识别它：
value_type
：它指向的到底是什么类型？ difference_type
：两个迭代器之间的距离用什么表示？ pointer
：指向 T 的指针。 reference
：T 的引用。 iterator_category
：属于上述五个等级中的哪一个？
template<typename _Category, typename _Tp, typename _Distance = ptrdiff_t,typename _Pointer = _Tp*, typename _Reference = _Tp&>struct _GLIBCXX17_DEPRECATED iterator{/// One of the @link iterator_tags tag types@endlink.typedef _Category iterator_category;/// The type "pointed to" by the iterator.typedef _Tp value_type;/// Distance between iterators is represented as this type.typedef _Distance difference_type;/// This type represents a pointer-to-value_type.typedef _Pointer pointer;/// This type represents a reference-to-value_type.typedef _Reference reference;};
为什么要这 5 个？
1. iterator_category : 刚才说过了，用于算法选择 O(1) 还是 O(N) 路径。
2. value_type : 用于声明临时变量。比如 swap(*a, *b) 内部需要 T temp = *a; ，这里的 T 就是从 value_type 来的。
3. difference_type : 用于表示距离。比如 std::distance(a, b) 的返回值类型。
4. pointer & reference : 即使你的迭代器不是裸指针，你也得告诉大家怎么通过指针或引用访问元素。
那些不遵守契约的人怎么办？
如果你写了一个类，实现了 operator++ 和 operator* ，但就是没定义这 5 个 typedef，那它只能算是一个“像迭代器的东西”，但在 STL 的正规军算法（如 std::sort ）里是用不了的。
这就是为什么我们在实现自定义容器的迭代器时，第一件事就是写这 5 行 typedef ，或者继承 std::iterator 。
3.3. 萃取机 (iterator_traits) 的偏特化艺术
这是本阶段最难、最精妙的代码。
- 挑战
：如果我传给算法一个原生指针 int*，它没有成员定义，算法怎么知道它的value_type？ - 解决
： iterator_traits通过模板偏特化，专门为T*和const T*写了一套逻辑，强行规定它们的 category 是random_access。 - 本质
：它是算法查询迭代器属性的“中转站”。
iterator_traits 就像是一个“智能识别器”。不管你扔给它的是精心设计的类（如 vector::iterator ），还是原始粗糙的指针（如 int* ），它都能统一吐出那 5 个关键信息。我们再仔细看一遍这段**偏特化（Partial Specialization）**的代码，它是 C++ 模板元编程的教科书级范例。
// 1. 针对 T* 的偏特化template<typename _Tp>struct iterator_traits<_Tp*>{// 强行规定：所有原生指针都是随机访问迭代器typedef random_access_iterator_tag iterator_category;// 提取出 T 作为 value_typetypedef _Tp value_type;// 指针差值类型必然是 ptrdiff_ttypedef ptrdiff_t difference_type;typedef _Tp* pointer;typedef _Tp& reference;};
这一设计的伟大之处
1. 非侵入式（Non-intrusive） ：
它不需要修改 int 或 float 的定义（你也改不了）。通过外部的 Traits 类，赋予了原生类型额外的语义。
2. 统一了世界 ：
写算法的人（比如 std::sort 的作者）不需要写两套代码：
– 一套给 vector::iterator
– 一套给 int*
他只需要写一套：
template <typename Iter>voidsort(Iter begin, Iter end){// 统一通过 traits 获取类型typedef typename iterator_traits<Iter>::value_type T;// ...}
3.处理了 const T* ：
还有一个针对 const _Tp* 的特化（第 222 行）。
template<typename _Tp>struct iterator_traits<const _Tp*>{typedef random_access_iterator_tag iterator_category;typedef _Tp value_type;typedef ptrdiff_t difference_type;typedef const _Tp* pointer;typedef const _Tp& reference;};
这一点非常关键！如果 Iter 是 const int* ，那么 value_type 应该是 int 还是 const int ？
– 答案是 int 。因为你需要用它来声明临时变量 int tmp = *it; 。如果你声明 const int tmp ，你就没法对 tmp 赋值了。- 所以 Traits 的特化里会帮你把 const 去掉。
这就是为什么我们说 iterator_traits 是连接 算法 (Algorithms) 和 容器 (Containers) 之间的那座桥梁。没有它，STL 就不复存在。【通用】
3.4. 标签分发机制 (Tag Dispatching)
这是 STL 实现高性能的“潜规则”。
-
当你调用 std::advance(it, 10)时，编译器会：
-
通过 traits拿到迭代器的category。 -
利用重载机制，自动跳转到对应的函数（如果是随机访问，直接 it += 10；如果是链表，循环++it十次）。
- 复现重点
：理解为什么这比 if-else快（因为它在编译期就决定了路径）。
// 1. 编译期确定的重载函数void __advance(RandomIter& it, int n, random_access_iterator_tag) {it += n;}void __advance(InputIter& it, int n, input_iterator_tag) {while (n--) ++it;}// 2. 入口函数template <typename Iter>voidadvance(Iter& it, int n){// 3. 提取 Tag，创建一个临时的 Tag 对象__advance(it, n, typename iterator_traits<Iter>::iterator_category());}
为什么它比 if-else 快？
1. 编译期决议 (Static Resolution) ：
当你调用 advance(vec.begin(), 5) 时，编译器在 编译阶段 就知道 vec.begin() 的 Tag 是random_access_iterator_tag 。 它会直接匹配到第一个 __advance 函数。
2. 死代码消除 (Dead Code Elimination) ：
对于 vector ，第二个 __advance （那个 while 循环） 根本不会被编译进最终的二进制代码 。它就像从来不存在一样。
3. 零运行时开销 ：
那个临时的 Tag 对象（ random_access_iterator_tag() ）大小是 0 字节（或者 1 字节被优化掉），而且通常会被完全内联。最终生成的汇编代码里，甚至连函数调用都没有，只有一条机器指令： add reg, 5 。
这就是 “零成本抽象”——你写了通用的代码，但编译器生成了针对特定类型最优化的机器码，没有任何多余的判断逻辑。
3.5. 迭代器适配器 (Iterator Adapters)
这是对已有迭代器的“二次改装”。
- 代表作
： reverse_iterator。 - 物理本质
：它内部持有一个普通迭代器，但把 ++改装成内部的--。 - 关键点
：它如何通过 traits获取被适配者的属性并据为己有？
迭代器适配器是 Decorator 设计模式 在泛型编程中的完美体现。 std::reverse_iterator 是最经典的例子，它能把任何双向迭代器瞬间变成反向迭代器，而不需要重新写一套逻辑。
class reverse_iterator: public iterator<typename iterator_traits<_Iterator>::iterator_category,typename iterator_traits<_Iterator>::value_type,typename iterator_traits<_Iterator>::difference_type,typename iterator_traits<_Iterator>::pointer,typename iterator_traits<_Iterator>::reference>
它通过继承 std::iterator ，并且把模板参数全部填成 iterator_traits<_Iterator>::xxx ，从而完美地 复制 了原始迭代器的所有属性（Category, ValueType, etc.）。这就是所谓的“通过 traits 获取属性并据为己有”。
protected:_Iterator current;
倒退即前进
// 伪代码reverse_iterator& operator++() {--current; // 表面 ++，实际 --return *this;}reference operator*() const {_Iterator tmp = current;return *--tmp; // 关键！解引用的是 current 的前一个位置}
这里有一个极其重要的设计细节（在第 119 行注释里也提到了）： &*(reverse_iterator(i)) == &*(i – 1)，为什么要这样设计？
因为 STL 的区间是 前闭后开 [begin, end) 。
– end() 指向的是 最后一个元素的后面 （无效位置）。
– 如果要变成反向迭代器 rbegin() ，它必须指向 最后一个元素 （有效位置）。
– 为了避免把 rbegin() 变成一个特殊的迭代器，STL 采用了“错位”设计：
– rbegin() 内部持有的 current 其实就是 end() 。
– 但是当你解引用 *rbegin() 时，它会自动去取 *(current – 1) 。
这就是为什么反向迭代器有点“烧脑”的原因，也是它设计的精妙之处。
重点解释一下红色字：
1. 核心矛盾：边界的尴尬
假设我们有一个 vector<int> v = {10, 20, 30}; 。在正向迭代器中，内存布局是这样的：
地址： 0x100 0x104 0x108 0x10C数值： [ 10 ] [ 20 ] [ 30 ] [ ?? ]位置： begin end– begin() 指向 0x100 (10)。- end() 指向 0x10C (越界位置)。- 区间是 [0x100, 0x10C) ，左闭右开。
现在我们要 反向遍历 。逻辑上，反向的区间应该是 [30, 20, 10] 。那么 rbegin() 应该指向哪里？ rend() 应该指向哪里？
2. 方案 A：直观设计（不采用 STL 的做法）
如果我们不搞“错位”，直接让 reverse_iterator 内部的指针指向它代表的元素：
– rbegin() 代表 30，所以内部指针指向 0x108。
– rend() 代表“10的前面”，所以内部指针指向 0x09C (10 的前一个位置)。
这有个巨大的问题： C++ 标准规定， 指针指向数组越界后的第一个位置（End）是合法的，但指向数组开始位置的前一个位置（Before-Begin）是未定义的（Undefined Behavior）！
也就是说，如果你让 rend() 内部指针指向 0x09C，仅仅是创建这个指针，可能就会导致程序崩溃（在某些分段内存架构上）。所以， reverse_iterator 绝不能持有比 begin() 更小的指针 。
3. 方案 B：STL 的错位设计
为了避免指向“非法区域”，STL 决定： 反向迭代器的内部指针，永远比实际值“往后偏一个身位”。
我们来看转换关系：
– rbegin() ：逻辑上指向 30。
– 物理上，它持有 end() (0x10C)。
– 解引用 *rbegin() 时，它悄悄地做 *(0x10C – 1) ，拿到了 30。
– 安全！ 因为 end() 是合法的。
– rend() ：逻辑上指向“10的前面”。
– 物理上，它持有 begin() (0x100)。
– 解引用？ rend() 是不应该被解引用的 （就像 end() 不能被解引用一样）。
– 安全！ 因为 begin() 是合法的。
4. 总结：对称之美
这种设计虽然理解起来烧脑，但它带来了一个完美的数学对称性：
– rbegin().base() == end()
– rend().base() == begin()
这就意味着，你可以直接用 vector 现成的 begin() 和 end() 来构造 rend() 和 rbegin() ，中间不需要做任何指针运算，也不需要担心越界风险。
一句话总结 ：
反向迭代器是一个“挂羊头卖狗肉”的家伙——它 身在曹营（持有 end） ，但 心在汉（指向 end-1） 。这是为了规避 C++ 指针不能越过头部的硬件限制。
物理内存： [ 10 ] [ 20 ] [ 30 ] [ 哨兵 ]地址： 0x100 0x104 0x108 0x10C正向迭代器：begin() ---> 0x100end() ---> 0x10C反向迭代器（内部持有的指针）：rbegin() ---> 0x10C (借用了 end 的地址，但操作时会 -1)rend() ---> 0x100 (借用了 begin 的地址，但逻辑上代表 begin-1)3.6. 问题
在测试用例可以看到原生int*可以走我的自定义路径，但是vector,list没有走我的自定义路径
原因：我的标签名字： input_iterator_tag ，但是std中的标签是 bidirectional_iterator_tag ， 编译器在匹配函数时，发现“定义的规则”和“std 容器带的身份证”对不上号。
解决方案： 增加了两个“转发重载”。当 std::list 带着 std::bidirectional_iterator_tag 走进来时，我的转发函数会强行调用 __distance(..., input_iterator_tag())，但是感觉非必要适配std
#include<iostream>#include<vector>#include<list>#include<typeinfo>/*** @brief* 1、定义5大迭代器,使用继承关系，方便算法进行"向上兼容"的匹配*/struct input_iterator_tag {};struct output_iterator_tag {};struct forward_iterator_tag : public input_iterator_tag {};struct bidirectional_iterator_tag : public forward_iterator_tag {};struct random_access_iterator_tag : bidirectional_iterator_tag {};/*** @brief* 2、迭代器基类，自定义迭代器可以继承，可省去5个typedef的麻烦*/template <typename Category, typename T, typename Distance = ptrdiff_t,typename Pointer = T*, typename Reference = T&>struct MiniIterator {typedef Category iterator_category;typedef T value_type;typedef Distance difference_type;typedef Pointer pointer;typedef Reference reference;};/*** @brief* 萃取机* 算法不直接问迭代器，而是问“中转站”*/template <typename Iterator>struct MiniIterator_traits {typedef typename Iterator::iterator_category iterator_category;typedef typename Iterator::value_type value_type;typedef typename Iterator::difference_type difference_type;typedef typename Iterator::pointer pointer;typedef typename Iterator::reference reference;};/*** @brief* T*的偏特化版本【int*】*/template <typename T>struct MiniIterator_traits<T*> {typedef random_access_iterator_tag iterator_category;typedef T value_type;typedef ptrdiff_t difference_type;typedef T* pointer;typedef T& reference;};//const T*template <typename T>struct MiniIterator_traits<const T*> {typedef random_access_iterator_tag iterator_category;typedef T value_type;typedef ptrdiff_t difference_type;typedef const T* pointer;typedef const T& reference;};/*** @brief* 标签分发*/template <typename InputIterator>typename MiniIterator_traits<InputIterator>::difference_type__distance(InputIterator first, InputIterator last, random_access_iterator_tag) {std::cout << "[优化路径]" << "检测到随机访问迭代器，执行O(1)指针运算" << std::endl;return last - first;}template <typename InputIterator>typename MiniIterator_traits<InputIterator>::difference_type__distance(InputIterator first, InputIterator last, input_iterator_tag) {std::cout << "[常规检测]检测到顺序访问迭代器,执行O(n)循环累加" << std::endl;typename MiniIterator_traits<InputIterator>::difference_type n = 0;while (first != last) {++first;++n;}return n;}//统一对外接口template <typename InputIterator>typename MiniIterator_traits<InputIterator>::difference_typeMini_distance(InputIterator first, InputIterator last) {typedef typename MiniIterator_traits<InputIterator>::iterator_category category;return __distance(first, last, category());}intmain(){//原生指针会被偏特化到随机RandomAccessint arr[] = {1, 2, 3, 4, 5};std::cout << "测试原生指针::" << std::endl;auto d1 = Mini_distance(arr, arr + 5);std::cout << "Distance: " << d1 << std::endl;std::vector<int> v = {1, 2, 3};std::cout << "测试vector::" << std::endl;auto d2 = Mini_distance(v.begin(), v.end());std::cout << "Distance: " << d2 << std::endl;std::list<int> l = {1, 2, 3, 4};std::cout << "测试list::" << std::endl;auto d3 = Mini_distance(l.begin(), l.end());std::cout << "Distance: " << d2 << std::endl;return 0;}
在 STL 中，适配器就像是“转换插头”。它不从零开始制造新东西，而是包装现有的组件，改变其接口或行为。
为了让你接上之前的逻辑，我们先攻克最能体现迭代器与萃取机功力的适配器——反向迭代器（Reverse Iterator）
为什么这一步对你很重要？
- 验证萃取机
：你看代码里的 typedef typename MiniIterator_traits<Iterator>::value_type。适配器本身不需要知道它是处理int还是double，它只要通过萃取机去“问”就行了。 - 理解解耦
： mini_reverse_iterator不需要知道它是在包装vector的迭代器还是int*指针。只要对方符合迭代器契约，适配器就能把它“翻转”过来。 - 为容器做准备
：当写 MiniVector时，只需要写正向的iterator。对于reverse_iterator，直接写一行typedef mini_reverse_iterator<iterator> reverse_iterator;这行代码就像魔法一样，瞬间让你的容器具备了反向遍历的能力。
适配器这一站，你不仅学到了“包装”的思想，更见证了“萃取机”作为通信协议的强大。
你觉得反向迭代器里 *rit 返回 *(current - 1) 这个“错位”设计，是不是很巧妙地解决了 rbegin == end 的边界问题？
分配器+迭代器+萃取机+vector
#include<iostream>#include<vector>//迭代器萃取机template<typename Iterator>struct MiniIterator_traits {typedef typename Iterator::iterator_category iterator_category;typedef typename Iterator::value_type value_type;typedef typename Iterator::difference_type difference_type;typedef typename Iterator::pointer pointer;typedef typename Iterator::reference reference;};//原生指针的偏特化template <typename T>struct MiniIterator_traits<T*> {typedef std::random_access_iterator_tag iterator_category;typedef T value_type;typedef ptrdiff_t difference_type;typedef T* pointer;typedef T& reference;};/*** @brief* 反向迭代器*/template <typename Iterator>class mini_reverse_iterator {protected:Iterator current;//内部持有的正向迭代器public:// 1.适配器的精髓：通过萃取机“窃取”原始迭代器的属性 ---typedef typename MiniIterator_traits<Iterator>::iterator_category iterator_category;typedef typename MiniIterator_traits<Iterator>::value_type value_type;typedef typename MiniIterator_traits<Iterator>::difference_type difference_type;typedef typename MiniIterator_traits<Iterator>::pointer pointer;typedef typename MiniIterator_traits<Iterator>::reference reference;typedef Iterator iterator_type;//原始迭代器类型typedef mini_reverse_iterator<Iterator> self;//自身类型mini_reverse_iterator() {}explicitmini_reverse_iterator(iterator_type it) : current(it) {}iterator_type base()const{return current;}reference operator*() const {Iterator temp = current;return *--temp;}pointer operator->() const {return &(operator*());}self& operator++() {--current;return *this;}self& operator--() {++current;return *this;}self operator+(difference_type n) const {return self(current - n);}self operator-(difference_type n) const {return self(current + n);}bool operator!=(const self& other) {return current != other.current;}};intmain(){int arr[] = {10, 20, 30, 40, 50};typedef mini_reverse_iterator<int*> ReverseIter;ReverseIter r_beign(arr + 5);ReverseIter r_end(arr);while (r_beign != r_end) {std::cout << *r_beign << " ";++r_beign;}return 0;}
复现迭代器与萃取机，你会明白两个道理：
-
解耦是第一生产力：算法与容器通过迭代器彻底分手，互不相识却配合默契。
-
类型即情报：在泛型编程里，一个类型名（Tag）就能决定算法的生死时速。
结语
当你下次写下 for (auto it = v.begin(); ...) 时，希望你脑海中浮现的不再是一个简单的指针，而是那一套精密的 Traits 识别系统。请思考下列问题：
1. 关于迭代器与萃取机 (Iterators & Traits)
-
“为什么
traits必须是模板类，而不是模板函数？” -
核心提示：函数不支持偏特化，而处理原生指针
T*必须依赖类模板的偏特化。 -
“如果我自定义了一个类，没有定义那 5 个
typedef，std::iterator_traits还能识别它吗？” -
核心提示：不能，会编译报错。这引出了现代 C++ 中
concept（概念）对旧版traits的改进。 -
“
const T*的萃取结果中，value_type应该是const T还是T？” -
核心提示：在 STL 中是
T。因为value_type是为了声明变量，如果声明const T x;则无法给它赋值。
2. 关于适配器 (Adapters)
-
“反向迭代器的
operator*为什么要设计成取current - 1，直接取current不行吗？” -
核心提示：为了实现“左闭右开”区间的完美镜像，解决
rbegin指向end（不可解引用位置）的问题。 -
“为什么
stack不叫容器而叫容器适配器？” -
核心提示：因为它没有自己的内存管理逻辑，只是限制了
deque或list的接口。
3. 关于空间配置器 (Allocators)
-
“为什么
rebind必须存在？如果没有它，list还能工作吗？” -
核心提示：不能。容器模板参数拿到的是
allocator<T>，但链表内部需要分配Node<T>，必须通过rebind“变出”针对Node的分配器。 -
“在
allocate申请内存后，如果construct构造对象时抛出异常，分配器应该如何保证内存不泄露？” -
核心提示：涉及异常安全和 RAII，需要捕获异常并调用
deallocate释放已申请的地皮。
4. 关于容器设计 (Containers)
-
“
vector的扩容为什么选 2 倍（或 1.5 倍），而不是 10 倍？” -
核心提示：涉及均摊时间复杂度与内存碎片利用的博弈。
-
“
map为什么要用一个header哨兵节点连接根节点、最左节点和最右节点？” -
核心提示：为了让
begin()和end()的获取达到 $O(1)$，且方便实现循环迭代。
如果你对 STL 源码复现感兴趣，后台回复【Iterator】获取完整复现代码！
