迭代器

iterators是一种抽象的设计概念，iterator模式在《Design Patterns》一书定义如下：提供一种方法，使之能够依序巡防某个聚合物（容器）所含的各个元素，而又无需暴露该聚合物的内部表述方式。
扮演容器与算法之间的桥梁，是所谓的 “泛型指针”，共有五种类型，以及其它衍生变化。从实现的角度来看，迭代器是一种将 operator*，operator->，operator++，operator-- 等指针相关操作予以重载的 class template。 所有 STL 容器都附带有自己专属的迭代器。 native pointer 也是一种迭代器。
STL的中心思想在于：将容器和算法分开，彼此独立设计，最后再以通过迭代器把他们撮合在一起。

迭代器相应类型(associated types)

迭代器所指对象的类型。
利用 function template 的参数推导机制，只能推导出参数的类型，无法推导出函数返回值类型。
迭代器相应类型有五种：
value type
difference type
pointer
reference
iterator category

Traits 编程技术

traits 意为 “特性”，扮演 “特性萃取机” 角色，萃取各个迭代器的特性(相应类型)。
template partial specialization 模板偏特化：针对 template 参数更进一步的条件限制所设计出来的一个特化版本，本身仍然是 template。

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

这个所谓的 traits，其意义是，如果 I 定义有自己的 value type，那么通过这个traits 的作用，萃取出来的 value_type就是 I::value_type。
如果迭代器是原生指针，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;
};

迭代器相应类型之一：value type
value type 就是迭代器所指对象的类型。

template <class T>
typename iterator_traits<I>::value_type func(I ite)
{
    return *ite;
}

迭代器相应类型之二：difference type
difference type 用来表示两个迭代器之间的距离。

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

迭代器相应类型之三：reference type
在 c++ 中，函数如果要传回左值，都是以 by reference 的方式进行，所以如果 p 是一个迭代器，它的 value type 是 T ，那么*p 应该是T& (即reference type)

迭代器相应类型之四：pointer type

迭代器相应类型之五：iterator_category
输入迭代器 (InputIterator) 是能从所指向元素读取的迭代器 (Iterator) 。输入迭代器 (InputIterator) 仅保证单趟算法的合法性。
输出迭代器 (OutputIterator) 是能写入所指元素的迭代器 (Iterator) 。
向前迭代器 (ForwardIterator) 是一种能从所指向元素读取数据的迭代器 (Iterator) 。
双向迭代器 (BidirectionalIterator) 是能双向移动（即自增与自减）的向前迭代器 (ForwardIterator) 。
随机访问迭代器 (RandomAccessIterator) 是能在常数时间内移动到指向任何元素的双向迭代器 (BidirectionalIterator) 。

std::iterator的保证

为了符合规范，任何迭代器都应该提供五个内嵌相应的类型，以利于traits萃取

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

总结

traits 本质是什么？
多一层间接性，换来灵活性。
iterator_traits 负责萃取迭代器的特性，SGI stl还有__type_traits，它负责萃取类型的特性。