前言

std::advance函数是一个工具模板函数，用于将一个迭代器移动给定距离。本条款讲述了如何利用C++和编译器特性实现std::advance，其中最核心的问题便是如何在编译器得到一个类的类型信息。

函数实现

advance声明如下：

template<typename IterT, typename DistT>
void advance(IterT& iter, DistT d);

对advance最直接的实现便是iter+=d，但是只有支持随机访问的iterator才支持+=操作，其他不那么强大的iterator需要循环调用iter++或者iter–。
迭代器依据其支持的操作可以分为5类：

1. input迭代器。只能向前移动，只支持读。如istream_iterator
2. output迭代器。只能向前移动，只支持写。如ostream_iterator
3. forward迭代器。只能向前移动，可读可写。如单向链表
4. biderectional迭代器。可向前后移动，可读可写。如list
5. random access迭代器。比起上一种迭代器，可以执行迭代器算术，即常量时间内移动任意距离。如vector,deque,string

C++定义了几个tag struct（即用于标记的struct）来表示这五类迭代器。

struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : input_iterator_tag {};
struct bidirectional_iterator_tag : forward_iterator_tag {};
struct random_access_iterator_tag : bidirectional_iterator_tag {};

回到实现的问题上，我们需要根据不同的迭代器类型来决定是使用+=的方式移动还是使用循环++或--的方式移动。伪代码类似如下：

template<typename IterT, typename DistT>
void advance(IterT& iter, DistT d)
{
	if (iter is a random acess iterator)
		iter += d;
	else {
		if (d>=0) {
			while (d--) ++iter; 
		} else {
			while (d++) --iter;
		}
	}
}

我们要知道一个iter的类型信息，这就是由traits提供的，它允许你在编译期得到类型的信息。
traits并不是C++关键字，而是一种技术，一种C++程序员共同遵守的协议，这个技术的要求是要求内置类型和用户自定义类型表现必须一样好，例如advance(char*, int)也必须能够执行。
对内置类型traits技术也能起作用意味着类型信息必须存在于类型之外，因为不可能在内置类型中保存类型信息。
标准技术是把类型信息放到一个template及其特化版本中（？），这样的template在标准库中有若干，其中针对迭代器的template如下：

template<typename IterT>
struct iterator_traits {
	typedef typename IterT::iterator_category iterator_category;
	...
}

iterator_traits内部声明了iterator_category类型，其类型即IterT::iterator_category
而在用户自定义的迭代器类型中必须也嵌套一个typedef ：

template<...>//省略
class deque {
public:
	class iterator {
	public:
		typedef random_access_iterator_tag iterator_category;
		...
	}
}

到此我们建立了这样一种关系：
deque::iterator::iterator_category类型是random_access_iterator_tag的类型别名，而iterator_traits<IterT>::iterator_category是IterT::iterator_category的类型别名。当IterT为deque::iterator时，iterator_traits<deque::iterator>::iterator_category就代表了deque::iterator::iterator_category，也即random_access_iterator_tag

这里通过在自定义类内声明tag struct的类型别名iterator_category，标识自定义类的某个特性（traits）,通过模板类取得名称为iterator_category的类型，从而得到tag struct。实现代码可以改成如下：

template<typename IterT, typename DistT>
void advance(IterT& iter, DistT d)
{
	if (typeid(typename std::iterator_traits<IterT>::iterator_category)
	== typeid(std::random_access_iterator_tag))
		iter += d;
	...
}

这里存在的问题是，IterT类型在编译期获知，所以iterator_traits<IterT>::iterator_category也能在编译器确定，但if语句是在运行时判断，编译期能确定的类型不应在运行时才判定。
这里我们将用到C++的另一种技术：函数重载（overloading）。当调用函数f时，编译器为我们寻找与最匹配的函数重载，如果参数是类型A，那么调用这个，如果参数类型是B，那么调用那个，这就是我们所寻求的“编译期条件语句”，改写实现函数，我们新增函数doAdvance，有多个重载，每个重载接受不同的iterator_traits<IterT>::iterator_category参数：

template<typename IterT, typename DistT>
void doAdvance(IterT& iter, DistT d, 
		std::random_access_iterator_tag)//第三个参数，无参数名，因为只是用于选择合适的重载函数
{
	iter+=d;
}

template<typename IterT, typename DistT>
void doAdvance(IterT& iter, DistT d, 
		std::bidirectional_iterator_tag)
{
	if (d>=0) {
		while (d--) ++iter; 
	} else {
		while (d++) --iter;
	}
}
...
template<typename IterT, typename DistT>
void advance(IterT& iter, DistT d)
{
	doAdvance(iter, d, 
		typename iterator_traits<IterT>::iterator_category());//传入临时变量
}

利用编译器的重载解析机制，我们只要传入一个tag struct对象即可调用适当的函数，并且由于tag struct有继承关系，适用于派生类的重载也会适用于基类。

总结

1. 设计并实现trait class
   a. 确认要获取的类型相关信息。如迭代器类型信息
   b. 为信息取个名字。如iterator_category
   c. 定义tag struct，用于表现信息。如random_access_iterator_tag
   d. 在类内声明tag struct类型别名为b步骤中信息名
   e. 提供一个template和一组偏特化版本，其中包含b步骤中信息名成员。如iterator_traits模板类
2. 建立一组重载函数（劳工），彼此的差异仅仅在于traits参数，函数实现体现traits信息不同时各自的处理方式
3. 建立控制函数（工头），调用上述重载函数，并传递traits信息