本文主要关注STL的迭代器，浅谈迭代器在STL中扮演什么样的角色，以及它是怎么起作用的。

1 没有迭代器的日子

刚学数据结构与算法的时候，我们写一个数组容器array，写一个链表容器list，如果要写一个查找算法find，我们的做法是：
为array写一个array_find，为list写一个list_find。当有更多不同的数据结构，我们就要为不同的数据结构都分别写一个
find算法。无比繁琐。

反观find算法，它无非是从容器的第一个节点开始，每次往前走一个节点，然后进行比对。关键的不同在于不同的容器每向前走
一步的行为方式是不同的，对数组是直接往前走一个元素的尺寸；对于链表，需要找到下一个节点的地址，然后跳转到那个地址。

怎么样才能让一个find，可以操作各种不同的容器呢？让算法只关心它自己的核心行为，也就是算法行为本身（find: 从第一个元素，比对一次，找下一个元素，再比对，再找下一个，直到找到或到达容器尾部）。而具体在容器上的行为，算法不关心。

2 引入迭代器

为了让算法和容器之间解耦，我们引入一个“中间人”角色。我们为每个容器设计一个中间人，这个中间人代表着容器，对外它们有着一样的接口，对内，不同容器的中间人是不一样的。承接上文，这个“中间人”就是让算法“驱使”的。算法让“中间人”往前走一步，它就走一步。但是具体是怎么前进的，中间人知道就可以了，算法不理会。而这个中间人，就是所谓的迭代器。

迭代器其实是23种设计模式中的一种，模式定义如下：

提供一种方法，使之能够依序巡访某个聚合物（容器）所含的各个元素，而又无需暴露该聚合物的内部表述方式。

另一方面，STL的中心思想在于：将数据容器和算法分开、彼此独立设计，最后再用迭代器联系在一起，完美！

3 作为一个代表，迭代器需要知道容器哪些属性

迭代器最终是被算法所使用的。因此，迭代器需要知道容器的哪些信息，完全是由算法决定的。

最基本的，算法需要知道容器元素的类型T。
算法可能需要获取容器元素类型的引用，获知其是否可以修改。迭代器要提供。
算法可能需要获取容器元素类型的指针，迭代器要提供。
算法需要在容器元素之间移动，所以迭代器需要提供在容器元素之间移动的方式。比如++，–，+n，-n等。
等等。。。

STL设计者归纳起来，作为迭代器，需要记录容器的五种信息，这五个信息作为迭代器的属性：

value_type: 迭代器所指对象之类型，一般可以直接理解为容器元素的类型。
different_type: 两个迭代器之间的距离类型。
reference_type: 迭代器是const还是非const，表征是否可在相应容器元素上做修改。
pointer_type: 迭代器所指对象的指针类型。
iterator_category: 反映迭代器的移动特性和实施操作。比如最基本的++行为在不同容器的迭代器是不同的。（STL设计者在此做了很多巧妙的设计）

// std::iterator
template <class Category, class T, class Distance = ptrdiff_t, 
        class Pointer = T*, class Reference = T&>
struct iterator {
    typedef Category    iterator_category;
    typedef T           value_type;
    typedef Distance    difference_type;
    typedef Pointer     pointer;
    typedef Reference   reference;
};

此外，迭代器还要记录容器的操作方式和移动方式，这有点像智能指针。比如：

operator*
operator->
operator++
operator--

也就是说，如果一个独立设计的容器能够提供符合其特点、同时满足上述定义的迭代器，那么这个容器就能加入到STL算法的大家庭中。

4 迭代器设计的工作

针对特定的容器，设计迭代器所要做的工作就是分析并精确定义前面描述五种类型，以及各种操作，比如operator++，operator–,operator->,operator*等等。

比如，容器list的迭代器

template <class T, class Ref, class Ptr>
struct list_iterator {
    //五种迭代器的属性，使用内嵌类型的方式声明，用于萃取
    typedef bidirectional_iterator_tag  iterator_category;
    typedef T   value_type;
    typedef Ptr pointer;
    typedef Ref reference;
    typedef ptrdiff_t  difference_type;

    // 各种移动方式和操作方式
    bool operator==(const self& x) const { return node == x.node; } // 类似指针比较
    bool operator!=(const self& x) const { return node != x.node; } // 

    reference operator*() const { return (*node).data; } //迭代器取值，取的是节点的值

    pointer operator->() const { return &(operator*()); } 

    self& operator++() {} //前置++
    self operator++(int n) {} //后置++
    self& operator--() {} //前置--
    self operator--(int n) {} //后置--
};

另外，因为原生指针T*满足vector迭代器该有的属性，所以vector的迭代器直接使用T*

template <class T, class Alloc = alloc>
class vector {
public:
    typedef T*  iterator;
};

5 算法怎么获取迭代器的属性

STL设计者使用了一种很巧妙的方法：内嵌型别 + iterator_traits萃取。

内嵌型别指的是：直接在迭代器类的内部声明五种属性的类型（见前面list）。

iterator_traits萃取即：

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;
};

iterator_traits是个模板类，通过模板参数（迭代器的类型）Iterator，萃取出迭代器的五种属性。而算法根据萃取出来的五种属性类型，而选择不同的策略。

比如：根据萃取出来的距离类型声明返回值类型

template<class Iterator>
typename iterator_traits<Iterator>::difference_type
distance(Iterator first, Iterator last){
    typedef typename iterator_traits<Iterator>::iterator_category iterator_category;
    return _distance(first, last, iterator_category());
}

然而，问题来了，像vector这种直接把原生指针T*作为迭代器，并没有专门设计一个vector_iterator类，并在类内内嵌各种声明blablabla。怎么办？

答案：模板偏特化

比如，为原生指针而设计的traits偏特化版

template <class T>
struct iterator_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*设计偏特化版本。具体可参考侯捷《STL源码剖析》

讨论到此，我们对迭代器为何存在于STL中有了一定的认识。要深入认识，可以阅读源码。

本文完。