STL中实现 iterator trail 的编程技巧
《泛型编程和 STL》笔记及思考。
这篇文章主要记录在 STL 中迭代器设计过程中出现的编程技巧，围绕的 STL 主题为 （迭代器特征） Iterator traits 和 相关类型（Associated Types）。
首先介绍 Associated Types
Associated Types
我们知道，Iterator 是一种泛化的指针，我们有时会这样理解它：
指针（广义的）指向某个序列的一个 item，而每个 item 的类型就是我们想要的 Associated Types。
对于 C 中的指针来说，*ptr 就是他的相关类型。
对于我们之前定义的外覆类（C++ 泛型算法 find 那篇）来说，*int_node （即 Node）是他的相关类型。
现在我们有个问题，我们如何使用这个类型？假设有一个 Iterator type P，P 的相关类型为 value_type。我们想要在一些算法中使用这个类型声明一些临时变量（这很常见，比如在计算数值的算法内），然而 ”P 的 value_type “ 并没有告诉我们 C++ 如何表达这样的概念。比如在之前的外覆类中，我们可以通过外覆类的接口获得他的相关类型的具体引用，但是却没办法使用这个类型信息用于外覆类之外的变量的声明。
技巧一 ：使用 C++ 的类型推断机制
假设有个泛型函数 f() ，需要一个类型为 P 的参数，而且还需要声明一个类型为 P 的 value_type 的临时变量。我们可以令 f() 成为一个单纯的传递函数，并将所有工作委托给内部函数 f_impl():
template <class P,class T>
void f_impl(P iter,T t) {
T tmp;
...
}
template <class T> inline void f(T iter) {
f_impl(iter,*iter);
}
于是，我们可以在函数 f_impl 之中，声明一个类型为 T 也即 P 的 value_type 类型的临时变量。template 参数的 “type inference” 机制是自动自发的，所以在 f_impl 之中，template 的参数 T 和 *iter 是同义的。
这个技巧的确能够解决我们之前提出的问题，但是，他却解决不了另一个问题，这个方案无法用来声明函数的返回类型。通过类型推导得到的 Associated Type 信息是在 f() 方法内获得的，我们无法将这个 Associated Type 用于函数的返回值。所以我们来看一下技巧二。
技巧二 : 嵌套声明
这种方法的核心思想是在每个迭代器类中将具体的 Associated Type 统一定义为一个新的名为value_type（又一次的隐藏了差异性）的类型。
用上一篇定义的外覆类 int_node 为例，为它增加一个新的类型 value_type:
template <class Node> //Node 是类型参数，可能用 T 更好理解
struct node_wrap {
typedef Node value_type;
Node *ptr;
...
};
这样的话，只要我们知道这个迭代器的类名，便可以访问他的 Associated Type 。并且，在每个定义了 value_type 的迭代器都可以换通过相同的方法访问。
对于声明一个 node_wrap 的 Associated Type 类型的变量，我们可以这样：
typename node_wrap :: value_type tmp;
以这种方式来对变量命名。（typename 是为了向编译器指出这是类型名而不是成员方法名或其他）
声明函数的返回类型：
typename node_wrap:: value_type f(...) {
...
}
这样做相当于我们再次将差异性隐藏，向外提供了一个统一的接口。
看起来这种方式解决了我们的问题。但是我们忽略了一些情况。上述成立的前提是迭代器是一个类，所以我们可以在它们内部增加一个新的类型，并从外部访问它。但是 C 中的指针也是一个迭代器，而且我们一直是在以 C 指针的行为来指导迭代器的行为。显然我们无法为 C 指针提供这种操作。为了解决这个问题，为指针也提供合适的操作，我们再次提出了新的方案。
技巧三 : 增加中间层和模板偏特化
我们可以增加一个中间层来解决这个问题。具体的做法是定义一个辅助用的 class，iterator_traits:
template <class Iterator>
struct iterator_traits {
typedef typename Iterator::value_type value_type;
};
这么一来我们就可以以这样的写法来取用 Iterator 的 value_type（以声明变量为例）：
typename iterator_traits<node_wrap>::value_type tmp;
这看起来没有任何改进，因为 Iterator_traits 仍然假设它的 template 参数 Iterator 有一个嵌套类型。（指针仍然没有）
不过，现在我们可以使用另一种技术来解决这个问题了。我们将利用 “对某种 template 参数提供另一种定义” 的方法，将 Iterator_traits class 特化。