前言

迭代器（iterators）是一种抽象的设计概念，现实程序语言中并没有直接对应于这个概念的实物。《Designt Patterns》一书提供有 23 个设计模式（design patterns）的完整描述，其中iterator 模式定义如下：提供一种方法，使之能够依序巡访某个聚合物（容器）所含的各个元素，而又无需暴露该聚合物的内部表述方式。
不论是泛型思维或 STL 的实际运用，迭代器（iterators）都扮演着重要的角色。STL 的中心思想在于：将数据容器（containers）和算法（algorithms）分开，彼此独立设计，最后再以一帖胶着剂将它们撮合在-起。容器和算法的泛型化，从技术角度来看并不困难，C++的class templates 和 function templates 可分别达成目标。如何设计出两者之间的良好胶着剂，才是大难题。
———— 《STL源码剖析》侯捷

本篇博客将会讲解 STL 中迭代器的相应型别。

迭代器相应型别

根据经验，最常用到的迭代器相应型别有五种:value type，difference type，pointor，reference，iterator category。

1
2
3
4
5
6
7
8
template <class I>
struct iterator_traits {
    typedef typename I::iterator_category iterator_category;  // 迭代器类型
    typedef typename I::value_type        value_type;         // 迭代器所指对象的类型
    typedef typename I::pointer           pointer;            // 迭代器之间的距离类型
    typedef typename I::reference         reference;          // 指向迭代器所指对象的指针类型
    typedef typename I::difference_type   difference_type;    // 迭代器所指对象的引用类型
}

iterator_traits结构体就是使用typename对参数类型的提取(萃取)，并且对参数类型在进行一次命名，看上去对参数类型的使用有了一层间接性。在五类迭代器对模板对象的类型重新定义一次。这里提取(萃取)出来的参数类型名都是统一的，也就说明每个要使用traits编程的类必须以此类型名为标准，而且需要自己对类定义这些类型名。

除此之外，还需要为原生指针做偏特化版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 针对原生指针(native pointer)而设计的 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 native pointer)而设计的 traits 偏特化版本
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;
};

iterator_category

在迭代器的相应型别中，最重要也是最复杂的就是 iterator_category，这一型别代表了迭代器的类型。

根据迭代器的移动特性与实行操作，可以将迭代器分为如下的五类：

  • Input Iterator：这种迭代器所指的对象，不允许外界改变。只读（read only）。
  • Output Iterator：只写（write only）。
  • Forward Iterator：允许 “写人型” 算法（例如 replace()）在此种迭代器所形成的区间上进行读写操作。
  • Bidirectonal Iterator：可双向移动。某些算法需要逆向走访某个迭代器区间（例如逆向拷贝某范围内的元素），可以使用Bidirectional lterators。
  • Random Access Iterator：前四种迭代器都只供应一部分指针算术能力（前三种支持 operator++，第四种再加上 operator--），第五种则涵盖所有指针算术能力，包括 p+n，p-n，p[n]，p1-p2， p1 < p2。

五种迭代器之间的关系如下图所示，虽然图中所表达的意思并非是继承关系，但在实际的实现过程中却实在地以继承的关系来构造这些迭代器类型。

3.png

STL 中，同一个函数针对不同的迭代器类型往往有不同的重载版本，如 distance()（计算两个迭代器之间的距离）。为了执行时的效率最佳，需要能够在编译时期就获取到迭代器的类型信息，以依据不同的迭代器类型进行函数的重载决议(overloaded resolution)，这时就有需要利用到模板参数推导机制，通过推导出的迭代器类型来在编译时期就选择正确的函数版本，提高运行时的效率。

为此，STL 中定义了以下的五种迭代器类型，这些 class 只作为标记使用，不需要任何成员。

1
2
3
4
5
6
// 五种迭代器类型
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 {};  // 随机访问

了解了这些的基础上，我们来看一下 distance() 的设计：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/// @brief distance 的重载版本，用于 input_iterator_tag 类型的迭代器
template <class InputIterator>  // 以算法所能接受的最低阶迭代器类型，来为其迭代器类别参数命名
typename iterator_traits<InputIterator>::difference_type __distance(InputIterator first, 
    InputIterator last, input_iterator_tag) {
    typename iterator_traits<InputIterator>::difference_type n = 0;
    // input_iterator_tag 类型的迭代器只能使用 ++ 操作符
    while (first != last) {
        ++first; ++n;
    }
    return n;
}

/// @brief distance 的重载版本，用于 random_access_iterator_tag 类型的迭代器
template <class RandomAccessIterator>  // 以算法所能接受的最低阶迭代器类型，来为其迭代器类别参数命名
typename iterator_traits<RandomAccessIterator>::difference_type __distance(RandomAccessIterator first, 
    RandomAccessIterator last, random_access_iterator_tag) {
    return last - first;  // 随机访问迭代器可以直接相减
}

/// @brief 计算两个迭代器之间的距离，根据迭代器的类型调用不同的函数
template <class InputIterator>
typename iterator_traits<InputIterator>::difference_type distance(InputIterator first, 
    InputIterator last) {
    typedef typename iterator_traits<InputIterator>::iterator_category category;
    return __distance(first, last, category());  // 通过迭代器的类别来调用不同的函数
}

在 distance() 中，真正操作交由 __distance() 实行，distance() 只是根据不同的迭代器类型来选择不同的函数。注意, distance() 可接受任何类型的迭代器；其 template 型别参数之所以命名为 Inputlterator，是为了遵循 STL 算法的命名规则：以算法所能接受之最初级类型来为其迭代器型别参数命名。此外也请注意，由于迭代器类型之间存在着继承关系，因此存在着 “传递调用”，当客端调用 distance() 并使用 Output lterators 或 Forward lterators 或 Biclirectional lterators 时，统统都会传递调用 Input lterator 版的那个 _distance() 函数。