STL主要由为容器，迭代器和算法创建的模板组成，但是也有一些功能模板。其中之一叫做advance。Advance将一个指定的迭代器移动指定的距离：
1 template<typename IterT, typename DistT> // move iter d units
2 void advance(IterT& iter, DistT d); // forward; if d < 0,
3 // move iter backward
从概念上来说，advance仅仅做了iter += d，但是advance并不是用这种方式实现的，因为只有随机访问迭代器支持+=操作。其他一些更加弱的迭代器类型必须通过反复的++或者--d次来实现advance。
1. 五种迭代器种类回顾
你不记得STL迭代器的种类了？没问题，我们现在做一些简单的回顾。总共有5类迭代器，对应着它们支持的五种操作。输入迭代器（input iterator）只能向前移动，一次只能移动一步，只能读取它们指向的内容，并且只能读一次。这种迭代器模拟的是输入文件的读指针；C++库的istream_iterator是这种迭代器的代表。输出迭代器（output iterator）同输入迭代器类似，但是对于输出迭代器来说：它们只能向前移动，每次只能移动一步，只能对它们指向的内存进行写操作，并且只能写一次。它们模拟的是输出文件的写指针；ostream_iterator代表了这种迭代器。这是两类功能最弱的迭代器。因为输入和输出迭代器只能向前移动，只能对它们所指向的内容进行读写最多一次，它们只能为one-pass算法所使用。
一个更加强大的迭代器种类由前向迭代器（forward iterator）组成。这种迭代器能做输入和输出迭代器能做的所有事情，并且它们能对它们指向的内容进行多次的读写。这就使得它们能被multi-pass算法所使用。STL没有提供单链表，但是一些库却提供了（通常叫做slist），这种容器中的迭代器为前向迭代器。TR1中的哈希容器（Item 54）迭代器也可能是前向迭代器。
双向迭代器（bidirectional iterators）和前向迭代器相比添加了向后移动的能力。为STL中的list提供的迭代器就属于这种类别，为set,multiset，map和multimap提供的迭代器也是这种类别。
最强大的迭代器类别叫做随机访问迭代器（random access iterator）。这种类型的迭代器和双向迭代器相比添加了执行“迭代器运算（iterator arithmetic）”的能力，也就是在常量时间内向前或者向后跳跃任意的距离。这种运算同指针运算类似，不要吃惊，因为随机访问迭代器模拟的就是内建类型的指针，内建类型指针的行为表现就如同随机访问迭代器。Vector,deque和string迭代器都是随机访问迭代器。
为了识别这五种迭代器类型，C++在标准库中为五种迭代器类型提供了一个“tag结构体”：
1 struct input_iterator_tag {};
2 struct output_iterator_tag {};
3 struct forward_iterator_tag: public input_iterator_tag {};
4 struct bidirectional_iterator_tag: public forward_iterator_tag {};
5 struct random_access_iterator_tag: public bidirectional_iterator_tag {};
这些结构体之间的继承关系是有效的“is-a”关系（Item32）：所有的前向迭代器同样是输入迭代器，等等。我们很快会看到这种继承的效用。
2. 如何实现advance简析
回到advance。考虑到不同的迭代器功能，实现advance的一种方法是使用循环的最小公分母策略：对迭代器进行反复加或者减。然而，这个方法会花费线性的时间。随机访问迭代器支持常量时间的迭代器算法，在我们需要的时候会使用它的这种能力。
我们真正想要的是像下面这样去实现advance:
1 template<typename IterT, typename DistT>
2 void advance(IterT& iter, DistT d)
3 {
4 if (iter is a random access iterator) {
5
6 iter += d; // use iterator arithmetic
7
8 } // for random access iters
9
10 else {
11
12
13 if (d >= 0) { while (d--) ++iter; } // use iterative calls to
14 else { while (d++) --iter; } // ++ or -- for other
15 } // iterator categories
16 }
这需要决定iter是不是一个随机访问迭代器，也就是需要知道它的类型，IterT，是不是随机访问迭代器类型。换句话说，我们需要获取一个类型的相关信息。这也是trait让你所做的：它们允许你在编译期间获取一个类型的相关信息。
3. Traits技术分析
3.1 使用traits技术的要求
Traits不是C++中的关键字或者一个预定义的概念；它们是一种技术，也是一个C++程序员需要遵守的约定。使用这项技术的一个要求是它必须使内建类型同用户自定义类型一样能够很好的工作。例如，如果advance的入参为一个指针（像const char*）和一个Int,advance必须能够工作，但是这就意味着trait技术必须能够使用在像指针一样的内建类型上。
Traits必须能够同内建类型一块工作就意味着不能在类型内部嵌入一些信息，因为没有方法在指针内部嵌入信息。于是对于一种类型的traits信息，必须是放在类型外部的。标准的技术是将其放在模板和模板的一个或多个特化实例中。对于迭代器来说，标准库中的模板被命名为iterator_traits:
1 template<typename IterT> // template for information about
2 struct iterator_traits; // iterator types
正如你所见的，iterator_traits是一个结构体。按照惯例，traits经常被实现为一个结构体。另外一种常用手法是将实现traits的结构体替换为traits class(这不是我说的)。
Iterator_traits的工作方式是对于每个类型IterT，在结构体iterator_traits<IterT>中声明一个叫做iterator_category的typedef。这个typedef唯一确认了IterT的迭代器类别。
3.2 实现traits class需要处理用户自定义类型
Iterator_traits会在两部分中实现它。首先，它强制任何用户自定义的迭代器类型必须包含一个叫做iterator_category的内嵌typedef，它能够识别合适的tag结构体。举个