STL为什么需要迭代器？看下面实例：

//对于int类的求和函数
int sum(int *a , int n)
{
    int sum = 0 ;
    for (int i = 0 ; i < n ; i++) {
        sum += *a++;
    }
    return sum;
}
//对于listNode类的求和函数
struct ListNode {
    int val;
    ListNode * next;
};
int sum(ListNode * head) {
    int sum = 0;
    ListNode *p = head;
    while (p != NULL) {
        sum += p->val;
        p=p->next;
    }
    return sum;
}

上面两个函数存在如下设计缺陷：

I 遍历int数组和单链表listNode时，需要设计两份不一样的sum求和函数，对于STL这样含有大量容器的代码库，针对每一种容器都设计sum的话，过于冗杂。

II 在sum函数中暴露了太多设计细节，如ListNode的节点值类型int，和指向下一个节点的指针next。

III 对于int数组来说，还必须知道数组的大小，以免越界访问。

IV 算法的设计过多的依赖容器，容器的改动会造成大量算法函数的随之改动。

那么，如何设计才能使得算法摆脱特定容器？如何让算法和容器各自独立设计，互不影响又能统一到一起？

STL 迭代器是一种抽象的设计概念，在设计模式中是这么定义迭代器模式的，即提供一种方法，使之能够巡访某个聚合物所含的每一个元素，而无需暴露该聚合物的内部表述方式。

不论是泛型思维或STL的实际运用，迭代器都扮演着重要的角色，STL的中心思想就在于：将数据容器和算法分开，彼此独立设计，最后再以一帖胶着剂将它们撮合在一起。

谈到迭代器需要遍历容器就想到指针，的确，迭代器就是一种类似指针的对象，而指针的各种行为中最常见也最重要的就是内容提领(dereference)和成员访问(member access)，因此，迭代器最重要的编程工作就是对operator*和operator->进行重载工作。

我们先回过头去看看sum函数，在sum函数中，我们必须知道容器的元素类型（型别），这关系到函数返回值。

1 函数模板参数推导机制

看下面的代码：

#include <stdio.h>
#include <iostream>
using namespace std;

// 此函数中并不知道iter所指的元素型别，而是通过模板参数 T 来获取的
template <class I, class T1 ,class T> // 这里要用 T 来表示 I 的型别，T用*I 赋值
T sum_impl(I iter ,T1 n , T t) {
    T sum = 0; // 通过模板的特性，可以获取I所指之物的型别，此处为int

    // 这里做func应该做的工作
    for(int i = 0 ; i < n ;i++){
        sum+=*iter++;
    } 
    return sum;
}

template <class I , class T1>
inline T1 sum(I iter , T1 n) {// 此处暴露了template参数推导机制的缺陷，iv 型别用于返回值时便束手无策
    return sum_impl(iter , n ,*iter);
}

int main() {
    int a[5] = {1,2,3,4,5};
    int sum1 = sum(a , 5);
    cout<<sum1<<endl;
}

通过函数模板的参数推导机制推导出了iter所指之物的型别(int)，于是可以定义T sum变量。

对于返回值类型，template参数推导机制也束手无策。

2 类模板内嵌型别机制

在类中可以进行型别声明。

看下面的代码：

#include <stdio.h>
#include <iostream>
using namespace std;

// 定义一个简单的iterator类模板
template <class T>
struct MyIter{
    typedef T value_type; // 内嵌型别声明
    T* ptr;
    MyIter(T* p =0):ptr(p){}
    T& operator*() const {return *ptr;}
};

// 这样当我们使用myIter类型时，可以通过 myIter::value_type来
// 获得相应的myIter所指向的类型（型别）
template <class I>
typename I::value_type // func返回值型别，也是定义的value_type的类型I的型别
func(I iter){
    return *iter;
}

int main(){
    MyIter<int> iter(new int(8));
    cout<<func(iter)<<endl;  // 8
}

注意，func()函数的返回值型别必须加上关键词typename，因为T是一个template参数，在它被编译器具现化之前，编译器对其一无所知，关键词typename的用意在于告诉编译器这是一个型别，如此才能通过编译。

内嵌型别看起来不错，可以很顺利的提取出迭代器所指型别并克服了template参数推导机制不能用于函数返回值的缺陷。

如果不是class type，那么就无法声明内嵌型别。但是STL绝对必须接受原生指针（如vector）作为一个迭代器。因此，必须另行它法！

3 类模板偏特化机制

针对原生指针这类特殊情况，我们很容易想到利用模板偏特化的机制来实现特殊声明，在泛化设计中提供一个特化版本。偏特化的定义是：针对任何template参数更进一步的条件限制所设计出来的一个特化版本。这里，针对上面的MyIter设计出一个适合原生指针的特化版本，如下：

template <class T>
struct MyIter <T*>{   // T*代表T为原生指针，这便是T为任意型别的一个更进一步的条件限制
    typedef T value_type; // 内嵌型别声明
    T* ptr;
    MyIter(T* p =0):ptr(p){}
    T& operator*() const {return *ptr;}
};

这样，函数func()就可以写为：

template <class I>
I func(I* iter){
    return *iter;
}

以上针对类模板内嵌型别机制与偏特化机制要分别实现模板函数func()，太繁杂，太不优雅了。

4 iterator_traits中间层机制

我们可以不直接使用myIter的value_type，而是通过另一个类来把这个信息提取出来：

// 用于traits出迭代器所指对象的型别
template <class I> // 这里的 I 可以是任意类型的迭代器
struct iterator_traits
{
  typedef typename I::value_type value_type;
};

这样，我们可以通过 iterator_traits<myIter>::value_type 来获得myIter的value_type，于是我们把func函数改写成：

template <class I> // 这里的I可以是任意类型的迭代器
typename iterator_traits<I>::value_type // 通过iterator_traits类萃取I的型别
func(I iter){
    return *iter;
}

从表面上来看，这么做只是多了一个间接层，但是带来的好处是极大的！iterator_traits类可以拥有特化版本，如下：

// 原生指针特化版本
template <class T>
struct iterator_traits <T*>
{
  typedef T  value_type;
}
// const指针特化版本
template <class T>
struct iterator_traits <const T*>
{
  typedef T  value_type;
}

于是，原生指针int*虽然不是一种class type，也可以通过traits取其value，到这里traits的思想就基本明了了，以下是测试代码：

#include <iostream>

template <class T>   // iterator_traits萃取机
struct iterator_traits {
    typedef typename T::value_type value_type;
};

template <class T>    // iterator_traits萃取机特化T*
struct iterator_traits<T*> {
    typedef T value_type;
};

template <class T>    // iterator_traits萃取机特化const T*
struct iterator_traits<const T*> { 
    typedef T value_type;
};

template <class T>  // iterator迭代器
struct MyIter {
    typedef T value_type;
    T * ptr;
    MyIter(T * p = 0) : ptr (p) {};
    T& operator* () const { return *ptr;}
};

template <class I>  // 算法（函数模板）定义
typename iterator_traits<I>::value_type
func (I ite) {
    return *ite;
}

int main() {
    int i = 3;
    const int k = 3;
    MyIter<int> v(&i);
    std::cout << func(v) << std::endl;    // 3
    std::cout << func(&i) << std::endl;  // 3
    std::cout << func(&k) << std::endl;  // 3
    return 0;
}

通过定义内嵌类型，我们获得了知晓iterator所指元素类型的方法，通过封装中间层（iterator_traits类模板），我们将函数模板对于原生指针和自定义iterator的定义都统一起来了。

这就是traits技法的妙处所在。

下面就来看看STL中”萃取机“的源码：

/**
 * 用于标记迭代器类型
 */
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 {};

/**
 * 用于traits出迭代其所指对象的型别
 */
template <class Iterator>
struct iterator_traits
{
  // 迭代器类型, STL提供五种迭代器
  typedef typename Iterator::iterator_category iterator_category;

  // 迭代器所指对象的型别
  // 如果想与STL算法兼容, 那么在类内需要提供value_type定义
  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 <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;
};
/**
 * 针对指向常对象的指针提供特化
 */
template <class T>
struct iterator_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;
};
/**
 *  返回迭代器类别
 */
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);
}
/**
 * 返回迭代器所指对象的类型
 */
template <class Iterator>
inline typename iterator_traits<Iterator>::value_type*
value_type(const Iterator&)
{
  return static_cast<typename iterator_traits<Iterator>::value_type*>(0);
}

萃取型别的运行机制：

上述萃取类不但能萃取出了迭代器的型别value_type，还有：

iterator_category;

difference_type;

pointer;

reference;

iterator与iterator_traits的整体运行机制：

各式各样的traits以及对应的头文件（GNU C++）：

type traits : .../c++/type_traits

iterator traits: .../c++/bits/stl_iterator.h

char traits: .../c++/bits/char_traits.h

allocator traits:.../c++/bits/alloc_traits.h

pointer traits: .../c++/bits/ptr_traits.h

array traits:.../c++/bits/array.h

算法（algorithms）在操作容器（Container）中的数据时需要通过Iterator知道的如下信息：

iterator_category：Iterator的类别，五种类型之一；

difference_type：两个Iterator之间的距离的type（int、unsigned int），决定了容器可以容纳多少元素；

value_type：容器元素本身的type；

reference：引用；

pointer：指针；

为了符合规范，任何迭代器都应该提供五个内嵌型别，以利于Traits萃取。STL提供了一份iterator class如下：

// 为避免挂一漏万，每个新设计的迭代器都必须继承自它
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;
};

还有与迭代器相关的函数：

distance()用来计算两个迭代器之前的距离。
Advance()有两个参数，迭代器p和n，函数内部将p前进n次。

STL有了迭代器、迭代器萃取器，其算法便可以独立并作用于容器了：

ref：

ZeeCoder：带你深入理解STL之迭代器和Traits技法

OriginalS_TZ：C++ STL之Traits

-End-