迭代器是一种抽象的设计概念，现实程序语言中并没有直接对应于这个概念的实物。
《Design Patterns》提供有23个设计模式的完整描述，iterator 模式定义如下：
提供一种方法，使之能够依序巡访某个聚合物（容器）所含的各个元素，而又无需暴露该聚合物的内部表述方式。
以下全文皆为 侯捷——STL源码剖析 学习总结。
3.1 迭代器设计思维
STL的中心思想是：将 数据容器 和 算法 分开，彼此独立设计，最后再以一贴胶着剂将他们撮合一起。
3.2 迭代器是一种 smart pointer
迭代器是一种行为类似指针的对象。其最重要的工作是解引用和成员访问。
对 operator* 和 operator-> 进行重载工作。
每一种STL容器都有专属迭代器，让设计容器的人来设计它的专属迭代器。
3.3 迭代器相应型别
迭代器所指之物型别就是其中之一，但是C++并无typeof()
解决办法是利用 function template 的参数推导机制：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
template <class I, class T> void func_impl(I iter, T t) { T tmp;//这里T 就是迭代器所指之物的型别 //... } template <class I> inline void Func(I iter) { func_impl(iter, *iter); } int main() { int i; func(&i); } |
迭代器相应型别不只是“迭代器所指对象的型别”一种，最常用的相应型别总共有五种，然而并非任何情况下任何一种都可利用上述的template参数推导机制来取的。
所以有了 traits方法：
3.4 Traits编程方法——STL源代码门钥
迭代器所指之物型别，称为该迭代器的 value_type，参数推导机制的确可以获得类型，但是无法用于函数的返回值。
声明内嵌型别的方法：
但是，并不是所有的迭代器都是class type，原生指针就不是。
所以可以使用 偏特化 来进行一个特殊的定义。
偏特化的意思是：提供另一份template定义式，其本身还是templatized。
或者说:针对template参数更进一步的条件限制 设计出来的一个 特化版本。
一个简单的例子：
|
1 2 3 4 5 6 7 8 9 10 11 |
template <class T> class C { //这个泛化版本允许接受T为任何型别 }; template <class T> class C<T*> { //这个特化版本仅适用于 “T为原生指针” 的情况 }; |
这便是从 任何型别->原生指针 的进一步条件限制，即一个特化。
这样我们使用内嵌型别和偏特化的方法，就可以获得相应的特性了
下面这个class template专门用来“萃取”迭代器的特性.以value_type为例：
|
1 2 3 4 5 |
template <class I> struct iterator_traits { typedef typename I::value_type value_type; }; |
这个traits的意义是，如果I定义有自己的value_type，那么通过这个traits的作用，萃取出来的value_type就是I::value_type。
同时，如果I定义有自己的value_type,先前按个func()就可以写成这样：
|
1 2 3 4 5 6 |
template <class I> typename iterator_traits<I>::value_type func(I ite) { return *ite; } |
同时还可以使用偏特化解决原生指针的问题：
|
1 2 3 4 5 |
template <class T> struct iterator_traits<T*> { typedef T value_type; }; |
还有一种是 指向常数对象的原生指针(pointer-to-const)
例如下式:
|
1 |
iterator_traits<const int*>::value_type |
它会获得什么结果呢…是const int 而非int…但是我们可能会需要一个int而非 const int…因为声明一个无法赋值的暂时变量并没有什么用。因此，如果迭代器是一个pointer-to-const ，我们应设法令其value_type为一个 non-const型别。
再设计一个特化版本：
|
1 2 3 4 5 |
template <class T> struct iterator_traits<const T*> { typedef T value_type; }; |
那么现在我们拥有三种版本：
- 泛型版本
- 原生指针
- pointer-to-const
这样无论是迭代器 Iter 还是 原生指针 int* 还是 const int * 我们都可以通过traits取出正确的value_type。
根据经验，最常用到的迭代器型别有五种：
3.4.1 value_type 迭代器所指对象的型别
3.4.2 difference_type 两个迭代器之间的距离
也可以用来表示一个容器的最大容量。如果泛型算法提供计数功能，就必须使用迭代器的这个型别做返回值。
3.4.3 reference_type 引用类型
从迭代器所指的内容是否允许改变来看，可以将迭代器分为两种：
- 不允许改变所指之物的内容，称为constant iterator
- 可以改变所指之物的内容，称为 mutable iterator
他们对应的例子分别是 cosnt int * 和 int *
当我们对 mutable iterator (int *) 进行解引用操作时，获得的不应该是一个右值(rvalue)，应该是一个左值(lvalue)，因为右值不允许赋值操作(assignment)，左值才允许：
|
1 2 3 4 |
int *pi = new int(5); const int *cpi = new int(9); *pi = 7; //获得一个左值，允许赋值 *cpi = 1; //获得一个右值，不允许赋值 |
在C++中，如果函数要传会左值，都是以 by reference 的方式进行，所以当p是一个mutable iterator时，如果其value type是 T，那么 *p 的型别不应该是T，而应该是 T&(T的引用类型)。
同上，如果p是一个constant iterator，其value type是T，那么*p的型别应该是 const T&。
所以，这里讨论的 *p的类型就是引用类型：reference_type.
3.4.4 pointer_type 指针类型
指针和引用在C++中有非常密切的关联。
传回一个左值，令它代表迭代器所指之物是可以的…
那么传回一个左值，令它代表迭代器所指之物的指针也是可以的…
他们俩同样是三个版本：
泛型版本
|
1 2 3 4 5 6 7 |
template <class I> struct iterator_traits { //... typedef typename I::pointer pointer; typedef typename I::reference reference; }; |
原生指针偏特化版
|
1 2 3 4 5 6 7 |
template <class T> struct iterator_traits<T*> { //... typedef T* pointer; typedef T& reference; }; |
原生的const-to-pointer偏特化版本
|
1 2 3 4 5 6 7 |
template <class T> struct iterator_traits<const T*> { //... typedef const T* pointer; typedef const T& reference; } |
3.4.5 iterator_category 迭代器类型
根据移动与施行操作，迭代器被分为以下五类：
只读，唯写，前向，双向，随机存取。
- Input Iterator：这种迭代器所指的对象，不允许外界改变；只读(Read Only)
- Output Iterator：这种迭代器所指的对象，只可以写入；唯写(Write Only)
- Forward Iterator：允许“写入型”算法在此种迭代器形成的区间上读写操作。
- Bidirectional Iterator：可双向移动。
- Random Access Iterator：涵盖了所有的算数能力，比如p+n,p-n,p[n],p1-p2,p1<p2等等…
迭代器的从属关系，可以用下图表示：
这里的箭头并非是继承关系，而是 概念与强化 的的关系
以 advance() 为例
既可以使用多个版本的函数由运行时根据不同类型的迭代器来决定调用的函数，也可以使用重载函数在编译时决定调用的版本，这里考虑用迭代器型别作为参数来进行重载。
首先设计五种迭代器类型：
|
1 2 3 4 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 : public bidirectional_iterator_tag { }; |
这里的 struct 只作为标记使用，所以不需要任何成员。
然后设计__advance()函数
STL源码里面给出的四个版本，我这里只有三个，Forward是直接调用的input…
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
template<typename _InputIterator , typename _Distance> inline void __advance( _InputIterator& __i , _Distance __n , input_iterator_tag ) { // concept requirements glibcxx_function_requires( _InputIteratorConcept<_InputIterator> ) _GLIBCXX_DEBUG_ASSERT( __n >= 0 ); while(__n--) ++__i; } template<typename _BidirectionalIterator , typename _Distance> inline void __advance( _BidirectionalIterator& __i , _Distance __n , bidirectional_iterator_tag ) { // concept requirements __glibcxx_function_requires( _BidirectionalIteratorConcept<_BidirectionalIterator> ) if(__n > 0) while(__n--) ++__i; else while(__n++) --__i; } template<typename _RandomAccessIterator , typename _Distance> inline void __advance( _RandomAccessIterator& __i , _Distance __n , random_access_iterator_tag ) { // concept requirements __glibcxx_function_requires( _RandomAccessIteratorConcept <_RandomAccessIterator > ) __i += __n; } |
这里第三个参数只作为标记使用，函数内并没有使用它们。
然后接下来是 advance 函数：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
template<typename _Iter> inline typename iterator_traits<_Iter>::iterator_category __iterator_category( const _Iter& ) { return typename iterator_traits<_Iter>::iterator_category(); } template<typename _InputIterator , typename _Distance> inline void advance( _InputIterator& __i , _Distance __n ) { // concept requirements -- taken care of in __advance typename iterator_traits<_InputIterator>::difference_type __d = __n; std::__advance( __i , __d , std::__iterator_category( __i ) ); } |
以上源码都是我直接从STL文件内拷贝过来的…慢慢看
因此，为了满足上述的萃取迭代器型别 的行为，应该在traits内再增加一个型别：
这样所有的五个型别是：
|
1 2 3 4 5 6 7 8 9 |
template<typename _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; }; |
然后分别有 原生指针 和 原生const-to-pointer 的偏特化版：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
/// Partial specialization for pointer types. template<typename _Tp> struct iterator_traits < _Tp* > { typedef random_access_iterator_tag iterator_category; typedef _Tp value_type; typedef ptrdiff_t difference_type; typedef _Tp* pointer; typedef _Tp& reference; }; /// Partial specialization for const pointer types. 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; }; |
同时讲一下迭代器的归属和函数接受型别的规则：
任何一个迭代器，其类型永远归属于该迭代器隶属的所有类型中最强化的那个。
任何一个函数，以算法所能接受的最低阶迭代器类型来为其迭代器型别参数命名。
总结：
设计适当的相应型别，是迭代器的责任；设计适当的迭代器，则是容器的责任。
因为只有容器(的设计者)才知道该设计一个怎样的迭代器来遍历自己，并执行迭代器的各种行为。
至于算法，可以完全独立于容器与迭代器之外，只要设计时以迭代器为对外接口即可。