前言
这段时间研读SGI-STL-v2.91源码，并提炼核心代码自己实现一遍，感觉受益颇深。觉得有必要写一些文章记录下学习过程的思考，行文旨在总结，会大量参考侯捷《STL源码剖析》的内容。
迭代器概述
迭代器定义：提供一种方法，使之能够依序巡访某个聚合物（容器）所含的各个元素，而无需暴露该聚合物的内部表述方式。
STL的中心思想在于：将数据容器和算法分开，彼此独立设计，然后再以一贴胶着剂撮合在一起。在STL中，迭代器就扮演着胶着剂的作用。迭代器是一种类似指针的对象，而指针的各种行为中最常见也是最重要的便是解引用和成员访问，因此迭代器最要的编程工作就是对operator*和operator->进行重载。
泛型编程和面向对象编程
认识迭代器之前我觉得有必要了解一下C++中两个非常重要的编程范式，即GP（泛型编程）和OOP（面向对象编程）。
泛型编程：亦称为"静态多态"，多种数据类型在同一种算法或者结构上皆可操作，其效率与针对某特定数据类型而设计的算法或结构相同， 具体数据类型在编译期确定，编译器承担更多，代码执行效率高。在STL中利用GP将methods和datas实现了分而治之。
面向对象编程：将methods和datas关联到一起 ，也就是方法和成员变量放到一个类中实现，通过继承的方式，利用虚函数表（virtual）实现运行时类型判定，也叫"动态多态", 由于运行过程中需根据类型去检索虚函数表，因此效率相对较低。
STL全部采用泛型编程，因此，相对来说STL的效率较高且易于维护。
萃取编程技法
在STL算法中需要用到迭代器相应型别，即迭代器所指对象的型别。但C++只支持 sizeof() 并未支持 typeof() 。STL的解决方法之一是利用 function template 的参数推导机制，但 value type 必须用于函数的返回值时 function template 就束手无策。STL利用class类的声明内嵌型别以及针对原生指针的偏特化方式，设计迭代器的萃取机萃取迭代器的特性，解决用于函数返回值的问题，value type 是迭代器的特性之一。下面是STL源码利用class类的声明内嵌型别设计的萃取机，也是萃取机的泛化版本：
//STL萃取器的泛化版本 template<class Iterator> struct iterator_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; };
因为原生指针不是class type，无法为它定义内嵌型别。STL利用C++偏特化的方式为泛化设计提供一个特化版本，即将泛化版本中的某些template参数赋予明确的指定。下面是STL源码针对原生指针T*设计的特化版本萃取机，源码还设计了一个const T*原生指针的特化版本，与T*类型这里不再呈现源码：
//针对T*类型的原生指针设计的特化版本 template<class T> struct iterator_traits<T*> { typedef random_access_iterator_tag iterator_categoty; typedef T value_type; typedef ptrdiff_t difference_type; typedef T* pointer; typedef T& reference; };
然后STL源码设计了一个获取迭代器 value type 的全局函数，将迭代器作为参数，函数可返回迭代器的型别，具体源代码如下：
template<class Iterator> inline typename iterator_traits<Iterator>::value_type* value_type(const Iterator&) { //根据掺入的Iterator是class type还是T*或const T*原生指针调用泛化或特化的iterator_traits return static_cast<typename iterator_traits<Iterator>::value_type*>(0); }
源码还设计了获取迭代器其他特性 iterator_categoty 和 distance_type 的全局函数，和value_type类似，源码如下：
template<class Iterator> inline typename iterator_traits<Iterator>::iterator_category iterator_category(const Iterator&) { typedef typename iterator_traits<Iterator>::iterator_category category; return category(); } template<class Iterator> inline typename iterator_traits<Iterator>::difference_type* distance_type(const Iterator&) { return static_cast<typename iterator_traits<Iterator>::difference_type*>(0); }
这种萃取编程技法是STL迭代器实现最重要的方法，萃取机能够萃取各种迭代器的特性。正是这种技法弥补了C++没有typeof()功能的缺陷，让迭代器能够真正脱离于容器，应用于算法中去。
迭代器分类和从属关系
STL源码中定义五个classes代表五种迭代器的型别，定义如下：
//五种迭代器型别 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 : public bidirectional_iterator_tag {};
这些classes只作为标记用，所以不需要任何成员。这五种迭代器型别的关系如下图所示：
迭代器型别巧用--函数重载
上图能够非常明确看出迭代器的分类和从属关系，设计算法时，如有可能，我们尽量针对上图的某种迭代器提供一个明确定义，并针对更强化的某种迭代器提供另一种定义，保证在不同情况下提供最大效率。在源码中 advance 算法的实现非常能体现这一设计原则。函数入口和针对不同迭代器不同的定义的源码如下：
//advance函数入口 template<class InputIterator, class Distance> inline void advance(InputIterator& i, Distance n) { __advance(i, n, iterator_category(i)); } //InputIterator类型定义 template<class InputIterator, class Distance> inline void __advance(InputIterator& i, Distance n, input_iterator_tag) { while (n--) ++i; } //BidirectionalIterator类型定义 template<class BidirectionalIterator, class Distance> inline void __advance(BidirectionalIterator& i, Distance n, bidirectional_iterator_tag) { if (n >= 0) while (n--) ++i; else while (n++) --i; } //RandomAccessIterator类型定义 template<class RandomAccessIterator, class Distance> inline void __advance(RandomAccessIterator& i, Distance n, random_access_iterator_tag) { i += n; }
上面的源码分别对 InputIterator、BidirectionalIterator 和 RandomAccessIterator 三种类型的迭代器设计了不同的 __advance 定义，根据第三参数的不同，使函数形成重载。第三参数只是声明型别并未指定参数名称，因为它纯粹只是用来激活重载机制，函数根本不使用该参数。从源码可以看出 advance 函数根据 iterator_category 获取迭代器型别而重载不同的 __advance 函数，而函数的重载过程是发生在编译期，所以函数的运行效率非常高。
行文至此，我认为已经将STL源码中迭代器和和萃取编程技巧的核心思想总结出来，具体的源码实现可以参考我github的实现：https://github.com/evenleo/sgi-stl-even，关于迭代器的源码在 stl_iterator.h 文件中。