在 STL 源码中，到处可见 Traits 的身影，其实 Traits 不是一种语法，更确切地说是一种技术。
STL库中，有一个函数叫做 advance， 用来将某个迭代器（具有指针行为的一种 class）移动
某个给定的距离。声明如下：
template <typename IterT, typename DistT> // 将迭代器向前移动 d 单位
void advance(IterT& iter, DistT d); // 如果 d < 0, 则向后移动
通常来说, iter += d 即可。但是其实不是。因为只有随机迭代器才支持算数运算。
而其他的迭代器种类，advance 只能一步步 ++ iter，走 d 步。
STL 库共有 5 种迭代器：
1. Input 迭代器
2. Output 迭代器
3. forward 迭代器
4. Bidirectional 迭代器
5. random 迭代器
对于这五种迭代器，STL 定义了五个专属的卷标结构（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 bidirectional_iterator_tag { };
他们的用途我在稍微会讲到。
现在回到 advance 函数。为了让 advance 满足不同迭代器的需要， 并且效率达到最高，
我们期望它以如下的方式定义：
template <typename IterT, typename DistT>
void advance(IterT& iter, DistT d)
{
if ( iter is a random access iterator) {
iter += d; // 针对 random_access 迭代器采用迭代器算数运算，复杂度是 O（1）
}
else {
if (d > 0) { while (d--) ++iter; }
else { while (d++) --iter; }
}
}
难点在于如何判断 iter 是否是 random_access 迭代器这种类型？？ 这里就是 traits 所做之事。
traits 技术让你能够 萃取 出迭代器的某些性质： 比如，迭代器类型，所指向元素的类型等等。
下面开始详细讲解 traits：
可以说它主要由两部分组成：
1. stl 中定义的 iterator_traits 的模板类：
template <typename IterT>
struct iterator_traits;
这个模板类里面包含了许多的 typedef， 其中有一个 typedef 名为 iterator_category，就是用来确认迭代器分类。
2. 要求用户自定义的迭代器类型中，必须定义一个 iterator_category 的 typedef.
举个例子：加入下面是 list 迭代器的定义，注意 list 是有双链表实现的，所以迭代器应该是 bidirectional 迭代器。
class iterator { // for list
public:
typedef bidirectional_iterator_tag iterator_category;
...
};
之前所说的 tag struct 就是用在这里，用来标识随机迭代器这种类型。
而 iterator_traits 里面有一个typedef 如下：
template<typename IterT>
struct iterator_traits {
typedef typename IterT::iterator_category iterator_category;
};
大家明白了吗？ 这个其实就是 在迭代器中定义一个public 的 typedef, 告诉外界，我是一个什么迭代器类型。
然后 iterator_traits 仅仅是鹦鹉学舌般地响应 迭代器类的嵌套式 typedef 而已。
截取一种 STL 源码分析上的图：
大家先消化以下。。。。
。。。。。。。。。。。。。。。。。。。。。。。。。
二、
大家可能立刻想到一个问题，这对于 指针行不通。。因为我们不能在指针的内部定义一个 typedef.
怎么办？？ 这时候，模板的偏特化技术就派上了用途。
我们可以提供一个 iterator_traits 的针对指针的偏特化版本：
template <typename IterT>
struct iterator_traits <IterT*>
{
typedef random_access_iterator_tag iterator_category; // 一般的指针是随机访问迭代器
....
}
讲了一堆难懂的技术，现在来说说具体是如何用的。。
给出一段 advance 函数的代码，但是会有编译问题并且效率不高。。因此，STL 其实并没有采用。
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) )
....
}
typeid 是 C++ 中用于辨别类型的。。具体参考 C++ primer.
大家知道， IterT 的类型在编译期已经获知，所以 iterator_traits<IterT>::iterator_category
在编译期也可确定。但是 if 语句得到执行期才执行，所以只有到执行期才能判断 iter 是否是随机迭代器。
如何能够在编译期就是判断 iter 是否是随机迭代器呢？？（效率更高）
我们需要一个“执行”于编译期的类似 if, else 的语句，
Bingo ! 重载（overloading)
直接上代码。。
template<typename IterT, typename DistT>
void advance(IterT iter, DistT d)
{
doAdvance(iter, d,
std::iterator_traits<IterT>::iterator_category());
// 用 iterator_category 定义一个临时对象，作为参数
} // for random_access iterator
template<typename IterT, typename DistT>
void doAdvance(IterT iter, DistT d,
std::random_access_iterator_tag)
{
iter += d;
} // overload
// for bidirectional iterators
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;
}
} // overload
// for input iterators
template<typename IterT, typename DistT>
void doAdvance(IterT iter, DistT d,
std::input_iterator_tag)
{
if(d < 0){
throw std::out_of_range("Negative distance");
}
while(d--) ++iter;
}
通过定义不同迭代器的 doAdvance 函数的重载版本，
参数唯一不同的是 之前说用来标识迭代器的 tag_struct：
input_iterator_tag
bidirectional_iterator_tag
random_access_iterator_tag
有没有觉得这种技术很酷？？
利用重载函数完美地将执行期判断类型是否是某个迭代器，提前到了编译期，
极大地提高了速度。
参考书籍：
Stanley, B. Lippman, C++ Primer 第四版，
Scott, Meyers, Effective C++,
侯捷， STL 源码分析