问题描述

STL主要由“容器、迭代器、算法”的templates构成，但也覆盖了若干工具性templates，其中有一个名为advance，用来将迭代器移动若干距离：

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

理论上来说这种操作肯定是执行iter+=d操作到达指定位置，但事实上，只有random access迭代器才支持+=操作，其它功能略弱的迭代器只能反复执行自增或者自减以达到同样的效果。

迭代器分类

我们首先回顾一下STL中迭代器的分类：

input与output迭代器
它们只能向前移动，一次一步，用户只能读取/涂写它们所指的东西，显然这是在模仿输入输出文件的读写指针。istream_iterator与ostream_iterator是这一类迭代器的代表。
由于这两类都只能向前移动，并且最多读写一次，所以他们只适合“一次性操作算法”。
forward迭代器
这类迭代器能完成input与output迭代器所做的任何事，并且可以读或写其所指物一次以上。所以它们可执行多次性算法。STL并未提供SingleLinked List，但不难想象，这类容器的迭代器就是forward迭代器。
Bidirection迭代器
比上一类更加强大，支持双向移动。STL中list,map,set(以及它们的multi版本）的迭代器就属于这一分类。
random access迭代器
在Bidirection迭代器的基础上支持了算术操作，也就是说可以在常量时间内前后移动任意距离。这种操作类似于指针算术，而它也确实以内置指针为榜样。vector，deque，string的迭代器便是这种类型。

对于这5种分类，C++标准程序库分别提供专属的卷标结构（tag struct）加以确认：

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 bidirection_iterator_tag {};

它们之间的关系是自上而下的标准的public继承，即：forward迭代器都必然是一个input迭代器，诸如此类。

问题实例

将目光拉回至advance函数。既然不同的迭代器具有不同的性质，那我们自然会想到：针对不同的迭代器，advance内部执行不同的操作：

template<typename IterT,typename Dist>
void advance(IterT &it,Dist d){
    if(iter is random accesss iterator){
        it+=d;
    }
    else{
        while(...) ++it;
    }
}

这种做法必须首先判断当前迭代器是否为random access迭代器，也就是说需要取得类型的某些信息。这就是traits的工作：允许你在编译期获取某些类型信息。

Traits

Traits并非是c++的某个关键词或者一个事先定义好的构件；这是一种技术，也是c++程序员共同遵循的协议。其内置要求之一是：对于内置类型与用户自定义类型的表现必须一样好。举例而言，即如果上述advance接受的是一个指针与一个int参数，它必须仍然可以有效运作。

Traits的实现

Traits必须可以施加于内置类型，表明我们不应该使用“在自定义类型里附加信息”的技术，因为原始指针无法附加信息。
标准技术是把它放进一个template及一个或者多个特化版本中。针对迭代器的版本名为iterator_traits:

1 2	template<typename IterT> struct iterator_traits;//处理迭代器分类信息

iterator_traits是一个struct。习惯上我们总是定义traits为structs，但它们又往往被称为traits classes。

Traits的运作方式

仍以迭代器为例，iterator_traits的运作机理是，针对每一个类型IterT，在struct iterator_traits中必然声明了某个typedef名为iterator_category.这个typedef用来确认IterT的迭代器分类。

实现iterator_traits

自定义用户类型

iterator_traits以两个部分来实现上述要求。
首先，它要求每个“用户自定义的迭代器类型”必须嵌套一个typedef，名为iterator_category，用以确认当前的卷标结构。举例而言，deque的迭代器可能如下：

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

而list的迭代器可双向行进，所以它们应当这样：

template<...> 
class list{
public:
    class iterator{
    public:
        typedef bidirectional_iterator_tag iterator_category；
    };
};

至于iterators_traits，则是被动响应iterator class的嵌套式typedef：

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

指针类型

上述设计对自定义类型而言没问题，但对指针则行不通，因为指针不可能嵌套typedef，因此iterators_traits为指针类型提供了一个偏特化版本，如下所示：

template<typename IterT>
struct iterator_traits<IterT *>{//偏特化
    typedef random_access_iterator_tag iterator_cagetory;
}

总结

设计一个traits classes需要以下步骤：

确认若干个你希望将来可以取得的信息（例如对迭代器的分类category）
为该信息提供名称（如iterator_category）
提供一个template与一组特化版本

解决方案

有了iterator_traits后我们似乎可以执行先前的伪代码了：

template<typename IterT,typename Dist>
void advance(IterT& it,Dist d){
    if(typeid(typename std::iterator_traits<IterT>::iterator_cagetory)==
        typeid(std::random_access_iterator_tag))
    ...
}

现在先不去考虑无法编译的问题。正如我们所知，IterT是在编译期获知，所以iterator_traits<IterT>::iterator_category也可以在编译期间确定，关键在于if语句发生在运行期，怎么把它移动到编译期执行呢？

我们所需要的是一个能在编译期完成if…else操作的条件式，C++恰巧有某种特性支持这种行为：重载。

当我们重载某个函数f，我们必须详细叙述各个重载件的参数类型。当你调用f，编译期便根据实参选择最恰当的重载件。这简直为我们的问题量身定制。针对advance函数，我们所需要做的就是产生两版重载函数，内含advance的真正操作，但各自接受不同类型的iterator_category对象。具体如下所示：

template<typename IterT,typename Dist>
void doadvance(IterT &iter,Dist d,std::random_access_iterator_tag){
    iter+=d;
}
template<typename IterT,typename Dist>
void doadvance(IterT &iter,Dist d,std::bidirectional_iterator_tag){
    if(d>=0) {
        while(d--) ++iter;
    }
    else{
        while(d++) --iter;
    }
}
template<typename IterT,typename Dist>
void doadvance(IterT &iter,Dist d,std::input_iterator_tag){
    if(d>=0) {
        throw std::out_of_range("Negative distance");
    }
    else{
        while(d--) ++iter;
    }
}

因为forward_iterator_tag继承自input_iterator_tag，所以无需为它定义一个重载函数，这也是public继承的一大优点：针对base class编写的代码用于derived class身上一样有效。

最终，advance函数的实现如下所示：

template<typename IterT,typename Dist>
void advance(IterT &iter,Dist d){
    doadvance(iter,d,typename std::iterator_traits<IterT>::iterator_category());
}

如何使用traits classes

建立一组重载函数或函数模板（doadvance），彼此之间的差异仅在于各自的traits参数，令每个函数实现码与其接受的traits信息相匹配。
建立一个控制函数或函数模板（advance），它调用上述函数并传递traits class所提供的信息。

总结

traits class使得“类型相关信息”在编译期可用，它们以templates和偏特化完成实现。
整合重载技术后我们可以在编译期执行ifelse测试。