迭代器是一种抽象的设计概念，现实程序语言中并没有直接对应于这个概念的实物。
在设计模式中，迭代器模式是指：提供一种方法，使之能够依序巡防某个聚合物(容器)所含的各个元素，而又无须暴露该聚合物的内部表述方式。

迭代器是STL的关键所在：将数据容器和算法分开，彼此独立设计，最后再用桥梁将它们联系在一起，这个桥梁就是迭代器。
比如泛型算法 find 的实现

template <typename InputIterator, typename T>
InputIterator find(InputIterator first, InputIterator last, const T& value)
{
    for (; first != last; ++first)
    {
        if (*first == value)
            return first;
    }

    return first;
}

我们不需要关心容器的具体类型，也不需要关心T的具体实现，就能够对不同的容器进行查找操作。

迭代器榨汁机

template<typename I>
struct iterator_traits
{
    typedef typename I::iterator_category
    typedef typename I::value_type;
    typedef typename I::difference_type;
    typedef typename I::pointer;
    typedef typename I::reference;
}

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

迭代器型别

• 迭代器型别之一：value_type
  value_type 是指对象的型别，每一个打算与STL算法完美搭配的class，都应该定义自己的value_type内嵌型别。

• 迭代器型别之二：difference_type
  difference_type用来表示2个迭代器的距离，因此它可以用来表示容器的最大容量。通常用于STL中泛型算法提供的计数功能，例如STL中的count()。

  template <typename I, typename T>
  typename iterator_traits<I>::difference_type count
  (I first, I last, count T& value)
  {
      typename iterator_traits<I>::difference_type n = 0;
      for (; first != last; first++)
        if (*first == value)
            ++n;
  
      return n;
  }
  

• 迭代器相应型别之三：reference_type
  迭代器所指之物的内容是否允许改变， 迭代器分为2类，

  • 不允许改变“所指对象之内容者”称为constant iterators 例如 const int* pic。
  • 允许改变“所指对象之内容者” 称为mutable iterators，例如int *pi。

• 迭代器相应型别之四：pointer type
  reference_type 表示迭代器所指之物，那么pointer type则表示迭代器所指之物的地址。

  // 针对原生指针而设计的"偏特化版"
  template <typename T>
  struct iterator_traits<T*> {
      ......
      typedef T* pointer;
      typedef T& reference;
  }
  
  // 针对原生的pointer-to-const而设计的"偏特化"
  template <typename T>
  struct iterator_traits<const T*> {
      ......
      typedef T* pointer;
      typedef T& reference;
  }
  

• 迭代器相应型别之五：Iterator_category
  根据移动特性与施行操作迭代器被分为5类：

  • Input Iterator：这种迭代器所指的对象，不允许外界改变，只读。
  • Output Iterator：只写。
  • Forward Iterator：允许写入型算法在此种迭代器所形成的区间上进行读写操作。
  • Bidirectional Iterator：可双向移动，某些算法需要逆向走访某个区间。
  • Random Access Iterator：前4种迭代器只提供一部分指针算术能力，(前3种支持operator++，第4种支持operator--)，第5种则涵盖所有指针算术能力。

  为什么需要区分这么多的迭代器种类？因为我们在设计算法时，应该针对某种强化的迭代器提供另一种定义，这样才能提供最大的效率。

迭代器类型.jpg

任何一个迭代器，其类型应该落在 "该迭代器所隶属的各种类型中，最强化的那个"，例如，int* 既是 RandomAccess Iterator，又是 Bidirectional Iterator，同时也是 Forward Iterator，而且也是 Input Iterator，那么其类型应该归属为RandomAccess iterator。

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

比如以 advanced() 为例，它的目的是使迭代器向前移动n步。

/* 适合Input Iterator */
template <typename InputIterator, typename Distance>
void advance_II(InputIterator& i, Distance n)
{
   while(n--)
     ++i;
}

/* 适合Bidirectional Iterator */
template <typename BidirectionalIterator, typename Distance>
void advance_BI(BidirectionalIterator& i, Distance n)
{
   if (n >= 0)
     while(n--)
       ++i; 
   else
     while(n++)
        --i;
}

 /* 适合Random Access Iterator */
template <typename RandomAccessIterator, typename Distance>
void advance_RAI(RandomAccessIterator& i, Distance n)
{
   i += n;
}

template <typename InputIterator, typename Distance>
void advance(InputIterator& i, Distance n)
{
    if (is_random_access_iterator(i))    // 有待实现。
        advanced_RAI(i, n);
    else if (is_bidirectional_iterator(i))    // 有待实现。
        advance_BI(i, n)
    ......
}

像在advanced中，通过判断不同迭代器类型来调用不同的函数以达到最大的效率。
那怎么判断出不同类型呢？
第一种方法是多态，但运行期才确定未免成本太高，同时胡乱继承多态也是把问题复杂化。
第二种就是函数重载，我们可以事先标记不同迭代器类型，并将其作为第3个参数传给advanced。

template <typename InputIterator, typename Distance>
inline void advance(InputIterator &iter, Distance n)
{
    typedef typename iterator_traits<InputIterator>::iterator_category category;
    __advance(iter, n, category());
}

template <typename RandomAccessIterator, typename Distance>
void __advance(RandomAccessIterator iter, Distance n, random_access_iterator_tag)
{
    iter += n;
}

template <typename InputIterator, typename Distance>
void __advance(InputIterator iter, Distance n, input_iterator_tag)
{
    while(n--)
        iter++;
}

template <typename BidirectionalIterator, typename Distance>
void __advance(BidirectionalIterator iter, Distance n, bidirectional_iterator_tag)
{
    if (n >= 0)
        while(n--)
            iter++;
    else
        while(n++)
            iter--;
}

__advanced中的第三个参数仅仅是激活重载。但我们还需要一个提供上层统一的接口，在这一层中通过traits机制，将迭代器类型推导出来。

参考资料
[1]《STL源码剖析》侯捷