本文原创

迭代器在概念上分为五种，分别是输入迭代器、输出迭代器、正向迭代器、双向迭代器、随机访问迭代器。各种迭代器的类型只是一种概念性描述，表明的是一系列要求而不是具体的类型，使用 concept 来描述这一系列要求，概念可以具有类似继承的关系，例如双向迭代器继承了正向迭代器的功能，但不能将继承机制用于迭代器，例如可以将正向迭代器实现为一个类，而将双向迭代器实现为一个常规指针，此时，该双向迭代器为内置类型，无法从类派生而来，然而从概念上，它确实能够继承，可用 refinement 来表示这种概念上的继承，因此双向迭代器是对正向迭代器概念的一种改进。概念的具体实现称为 model，因此指向 int 类型的指针是一个随机访问迭代器模型。

头文件 stl_iterator_base.h 描述了五类迭代器的概念模型。

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

template <class _Tp, class _Distance>
struct input_iterator
{
    typedef input_iterator_tag iterator_category;
    typedef _Tp                value_type;
    typedef _Distance          difference_type;
    typedef _Tp*               pointer;
    typedef _Tp&               reference;
};

struct output_iterator
{
  typedef output_iterator_tag iterator_category;
  typedef void                value_type;
  typedef void                difference_type;
  typedef void                pointer;
  typedef void                reference;
};

template <class _Tp, class _Distance>
struct forward_iterator
{
    typedef forward_iterator_tag iterator_category;
    typedef _Tp                  value_type;
    typedef _Distance            difference_type;
    typedef _Tp*                 pointer;
    typedef _Tp&                 reference;
};

template <class _Tp, class _Distance>
struct bidirectional_iterator
{
    typedef bidirectional_iterator_tag iterator_category;
    typedef _Tp                        value_type;
    typedef _Distance                  difference_type;
    typedef _Tp*                       pointer;
    typedef _Tp&                       reference;
};

template <class _Tp, class _Distance>
struct random_access_iterator
{
    typedef random_access_iterator_tag iterator_category;
    typedef _Tp                        value_type;
    typedef _Distance                  difference_type;
    typedef _Tp*                       pointer;
    typedef _Tp&                       reference;
};

不同类型迭代器的 iterator_category 表明其所属种类，输出迭代器无值类型、指针类型、引用类型。

各类容器中使用的 iterator 的原型如下：

template <class _Category, class _Tp, class _Distance = ptrdiff_t,
          class _Pointer = _Tp*, class _Reference = _Tp&>
struct iterator
{
    typedef _Category     iterator_category;
    typedef _Tp           value_type;
    typedef _Distance     difference_type;
    typedef _Pointer      pointer;
    typedef _Reference    reference;
};

后三个模板形参都有默认参数，后两个模板形参根据第二个模板形参进行设置，那么如何获取一个迭代器对象的类型呢，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;
};

template <class _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;
};

template <class _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;
};

类定义好了，可使用函数来方便调用：

template <class _Iter>
inline typename iterator_traits<_Iter>::iterator_category
__iterator_category(const _Iter&)
{
    typedef typename iterator_traits<_Iter>::iterator_category _Category;
    return _Category();
}

template <class _Iter>
inline typename iterator_traits<_Iter>::difference_type*
__distance_type(const _Iter&)
{
    return static_cast<typename iterator_traits<_Iter>::difference_type*>(0);
}

template <class _Iter>
inline typename iterator_traits<_Iter>::value_type*
__value_type(const _Iter&)
{
    return static_cast<typename iterator_traits<_Iter>::value_type*>(0);
}

template <class _Iter>
inline typename iterator_traits<_Iter>::iterator_category
iterator_category(const _Iter& __i) { return __iterator_category(__i); }

template <class _Iter>
inline typename iterator_traits<_Iter>::difference_type*
distance_type(const _Iter& __i) { return __distance_type(__i); }

template <class _Iter>
inline typename iterator_traits<_Iter>::value_type*
value_type(const _Iter& __i) { return __value_type(__i); }

#define __ITERATOR_CATEGORY(__i) __iterator_category(__i)
#define __DISTANCE_TYPE(__i)     __distance_type(__i)
#define __VALUE_TYPE(__i)        __value_type(__i)

注意上面的 __distance_type 和 __value_type 调用返回的是对应的指针类型。该处定义为宏是为了处理编译器不支持类模板局部特化时选用另一种全局特化实现方式的需要。

distance 实现有引用传递和返回值两种方式，两种方式对随机访问迭代器做了高效处理：

/* 引用传递 __n */
template <class _InputIterator, class _Distance>
inline void __distance(_InputIterator __first, _InputIterator __last,
                       _Distance& __n, input_iterator_tag)
{
    while (__first != __last) { ++__first; ++__n; }
}

template <class _RandomAccessIterator, class _Distance>
inline void __distance(_RandomAccessIterator __first, 
                       _RandomAccessIterator __last, 
                       _Distance& __n, random_access_iterator_tag)
{
    __n += __last - __first;
}

template <class _InputIterator, class _Distance>
inline void distance(_InputIterator __first, 
                     _InputIterator __last, _Distance& __n)
{
    __distance(__first, __last, __n, iterator_category(__first));
}

/* 返回 __n */
template <class _InputIterator>
inline typename iterator_traits<_InputIterator>::difference_type
__distance(_InputIterator __first, _InputIterator __last, input_iterator_tag)
{
    typename iterator_traits<_InputIterator>::difference_type __n = 0;
    while (__first != __last) { ++__first; ++__n; }
    return __n;
}

template <class _RandomAccessIterator>
inline typename iterator_traits<_RandomAccessIterator>::difference_type
__distance(_RandomAccessIterator __first, _RandomAccessIterator __last,
           random_access_iterator_tag)
{
    return __last - __first;
}

template <class _InputIterator>
inline typename iterator_traits<_InputIterator>::difference_type
distance(_InputIterator __first, _InputIterator __last)
{
    typedef typename iterator_traits<_InputIterator>::iterator_category _Category;
    return __distance(__first, __last, _Category());
}

advance 则根据输入迭代器及正向迭代器、双向迭代器、随机访问迭代器设置了三种实现：

template <class _InputIter, class _Distance>
inline void __advance(_InputIter& __i, _Distance __n, input_iterator_tag)
{
    while (__n--) ++__i;
}

template <class _BidirectionalIterator, class _Distance>
inline void __advance(_BidirectionalIterator& __i, _Distance __n, 
                      bidirectional_iterator_tag)
{
    if (__n >= 0)
        while (__n--) ++__i;
    else
        while (__n++) --__i;
}

template <class _RandomAccessIterator, class _Distance>
inline void __advance(_RandomAccessIterator& __i, _Distance __n, 
                      random_access_iterator_tag)
{
    __i += __n;
}

template <class _InputIterator, class _Distance>
inline void advance(_InputIterator& __i, _Distance __n)
{
    __advance(__i, __n, iterator_category(__i)); // 由iterator_category返回的迭代器类型选择调用上述哪一种实现
}