前言

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

本篇博客将会介绍迭代器与 traits 编程技法的由来，这部分强烈推荐看侯捷老师的书，叙述的十分清晰明了。

iterators

迭代器是将算法和容器两个独立的泛型进行调和的一个接口。使我们不需要关系中间的转化是怎么样的就都能直接使用迭代器进行数据访问。而迭代器最重要的就是对operator *和operator->进行重载，使它表现的像一个指针。STL 的每种容器都有自己独特的指针，它们具体的行为模式不同，但都对外暴露出相同的接口对所属容器进行遍历。

traits 编程技法

在算法中运用迭代器时，很可能会用到其相应型别（associated type）。什么是相应型别？迭代器所指之物的型别便是其一。但 C++ 只支持 sizeof()，并不支持 typeof()，因此需要设计一种能够拿到迭代器相应型别的手段，这便是 traits 编程技法的由来。

参数推导

利用函数模板的参数推导机制可以部分地解决这个问题，例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template <class I, class T>
void func_impl(I iter, T t) {
    T tmp;  // 这里解决了问题。T 就是迭代器所指之物的型别，本例为int

    // ... 这里做原本 func() 应该做的全部工作
}

template <class I> inline
void func(I iter) {
    func_impl(iter, *iter);  // func 的工作全部移往 func_impl
}

int main() {
    int i;
    func(&i);
}

我们以 func() 为对外接口，却把实际操作全部置于 func_impl() 之中。由于 func_impl() 是一个 function template，一旦被调用，编译器会自动进行 template 参数推导。于是导出型别 T，顺利解决了问题。

内嵌型别声明

但当我们需要将 T 作为返回值时，上述的方法就束手无策了，毕竟函数的模板参数推导机制推而导之的只是参数，无法推导函数的返回值型别。利用内嵌型别声明可以解决这个问题，例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <class T>
struct MyIter {
    typedef T value_type;  // 内嵌型别声明
    T* ptr;
    MyIter(T* p = 0) : ptr(p) {}
    T& operator*() const { return *ptr }
};

template <class I>
typename I::value_type   // 这一整行是 func 的返回值型别
func(I ite) { return *ite }

// ...
MyIter<int> ite(new int(8));
cout << func(ite);  // 输出：8

如果没有在 MyIter 中定义内嵌型别的话，那么 func() 返回值的类型便无法获得，这就是内嵌型别声明的意义。

注意，func() 的回返型别必须加上关键词 typename，因为 T 是一个 template 参数，在它被编译器具现化之前，编译器对 T 一无所悉，换句话说，编译器此时并不知道 MyIter<T>::value_type 代表的是一个型别或是一个 member function 或是一个 data member。关键词 typename 的用意在于告诉编译器这是一个型别，如此才能顺利通过编译。

这也是 class 与 typename 这两个关键词在定义 template 时的区别，typename 可以定义嵌套依赖类型，如上面的例子，而 class 关键词则不行。
需要注意的是，在非模板代码中使用typename是非法的。如果在非模板代码中使用typename，编译器会报错。

偏特化

看起来似乎利用参数推导机制加上内嵌型别声明就可以解决所有的问题了，但是有个隐晦的陷阱：并不是所有迭代器都是 class type。原生指针就不是！如果不是 class type，就无法为它定义内嵌型别。但 STL（以及整个泛型思维）绝对必须接受原生指针作为一种迭代器，所以上面这样还不够。有没有办法可以让上述的一般化概念针对特定情况（例如针对原生指针）做特殊化处理呢?

这就要引出今天的第三个知识点 ———— 偏特化（Partial Specialization）。

偏特化的大致意思是：如果 class template 拥有一个以上的 template 参数，我们可以针对其中某个（或数个，但非全部）template 参数进行特化工作。换句话说，我们可以在泛化设计中提供一个特化版本（也就是将泛化版本中的某些 template 参数赋予明确的指定）。
《泛型思维》一书对 partial specialization 的定义是：“针对（任何）template 参数更进一步的条件限制所设计出来的一个特化版本”。例如，针对下面的这个 class template：

1
2
template <class T>
class C { ... };  // 这个泛化版本允许（接受）T 为任何型别

针对原生指针的偏特化为：

1
2
3
template <class T>
class C<T*> { ... };  // 这个特化版本仅适用于 “ T 为原生指针” 的情况
// “ T 为原生指针” 便是 “ T 为任何型别” 的一个更进一步的条件限制

如此一来，假设我们有一个 class template 专门用于萃取迭代器的特性：

1
2
3
4
template <class I>
struct iterator_traits {
    typedef typename I::value_type value_type;
}

为了让其能够适用于原生指针，我们可以设计一个偏特化的版本如下：

1
2
3
4
template <class T>
struct iterator_traits <T*> {
    typedef T value_type;
}

这样，iterator_traits 也能够萃取出原生指针的特性了。似乎我们再一次解决了所有的问题，但还有最后一个坑，那就是当 T 的类型为 “指向常数对象的指针（pointer-to-const）” 时。例如，当 T 为 const int* 时，使用上面的 iterator_traits 我们会萃取出什么结果？答案是 const int。显然，萃取出一个无法赋值的变量是没什么用的。因此，我们应该再为 iterator_traits 设计一个针对 pointer-to-const 的偏特化版本。

1
2
3
4
template <class T>
struct iterator_traits <const T*> {
    typedef T value_type;
}

现在，不论面对的是迭代器 MyIter，或是原生指针 int* 或 const int*，都可以通过 tralts 取出正确的（我们所期望的）value type。