【STL源码分析】迭代器

前言

之前在巩固C++基础时，学习了侯捷老师的《STL泛型编程》这一视频课程，当时也是边看边记录，但是记录得也比较松散，看完之后大概也就是有点印象，到现在基本上又想不起太多了。然后在网上看到了STL源码分析的相关文章，阅读学习之后大为收益。

本文主要内容参考：手撕 STL 迭代器源码与 traits 编程技法，因为原文内容很充实，一些图画得很精妙，所以为了避免重复造轮子，也会直接引用其中的一些图片、文字，如果有造成侵权，请及时告知。

本文将摘录总结其中关键的知识点，以便日后复习时，可以帮助自己快速找到要点。而如果此前没有学习了解过STL组件的话，建议阅读学习原文。

迭代器的作用描述

在设计模式中，关于 iterator 的描述如下：一种能够顺序访问容器中每个元素的方法，使用该方法不能暴露容器内部的表达方式。而类型萃取技术就是为了要解决和 iterator 有关的问题。

那么在STL相关组件中，迭代器就是容器和算法之间的桥梁，算法通过迭代器来访问操作容器中的数据，如下图所示。

迭代器的设计实现思路

STL中的迭代器类似一种智能指针，拥有一般指针的特性——能够对其进行 *和 ->操作。其设计思路如下图所示。

因为迭代器需要获取所指元素对应的类型，所以首先想到使用模板参数自动推导的方法。但是模板参数推导只能推导参数类型，无法推导函数的返回值类型。

所以想到用内嵌型别的方法，也就是在迭代器类（class）里面定义所指的元素类型（使用typedef），那么在需要的时候直接使用即可。

但是存在的一个隐晦的问题：实际上并不是所有的迭代器都是 class type ，原生指针也是一种迭代器，由于原生指针不是 class type ，所以没法为它定义内嵌型别。然后就有了模板偏特化的解决思路，具体实现上就是引入中间一层类型萃取traits，由该类模板来获取迭代器的元素类型，源码相关定义如下所示。

如果不引入类型萃取traits的话，那么为了支持原生指针，每个跟迭代器有关的模板函数都需要实现对原生指针的模板偏特化，为了节省这一代码开销，所以需要引入中间层iterator_traits来获取迭代器元素类型。

最后总结一下，在STL中获取迭代器元素类型的过程如下图所示：

迭代器里定义的类型

一般迭代器里会定义五种类型：

• value_type：迭代器所指对象的类型，原生指针也是一种迭代器，对于原生指针 int*，int 即为指针所指对象的类型，也就是所谓的 value_type 。
• difference_type：用来表示两个迭代器之间的距离，对于原生指针，STL 以 C++ 内建的 ptrdiff_t （是 long 类型的别名）作为原生指针的 difference_type。
• reference_type：是指迭代器所指对象的类型的引用，reference_type 一般用在迭代器的 * 运算符重载上，如果 value_type 是 T，那么对应的 reference_type 就是 T&；如果 value_type 是 const T，那么对应的reference_type 就是 const T&。
• pointer_type：就是相应的指针类型，对于指针来说，最常用的功能就是 operator* 和 operator-> 两个运算符。
• iterator_category：的作用是标识迭代器的移动特性和可以对迭代器执行的操作，从 iterator_category 上，可将迭代器分为 Input Iterator、Output Iterator、Forward Iterator、Bidirectional Iterator、Random Access Iterator 五类，这样分可以尽可能地提高效率。

下图是源码中定义的 iterator：

迭代器的分类

刚刚在迭代器的iterator_category 中也谈到了迭代器的分类，主要有五种：

• Input Iterator：此迭代器不允许修改所指的对象，是只读的。支持 ==、!=、++、* 、-> 等操作。（*、-> 返回类型具有const修饰）

• Output Iterator：允许算法在这种迭代器所形成的区间上进行只写操作。支持 ++、* 等操作。

• Forward Iterator：允许算法在这种迭代器所形成的区间上进行读写操作，但只能单向移动，每次只能移动一步。支持 Input Iterator 和 Output Iterator 的所有操作。

• Bidirectional Iterator：允许算法在这种迭代器所形成的区间上进行读写操作，可双向移动，每次只能移动一步。支持 Forward Iterator 的所有操作，并另外支持 – 操作。

• Random Access Iterator：包含指针的所有操作，可进行随机访问，随意移动指定的步数。支持前面四种 Iterator 的所有操作，并另外支持 [n] 操作符等操作。

小结

根据参考文章：手撕 STL 迭代器源码与 traits 编程技法，梳理了STL组件中的迭代器关键知识点，最后再整理一下STL六大组件的交互关系：

container（容器） 通过 allocator（分配器） 取得数据储存空间，algorithm（算法）通过 iterator（迭代器）存取 container（容器） 内容，functor（仿函数） 可以协助 algorithm（算法） 完成不同的策略变化，adapter（适配器） 可以修饰或套接 functor（仿函数）。