STL主要由“用以表现容器，迭代器和算法”的模板组成，但是也有一些功能模板。其中之一叫做advance。advance将一个指定的迭代器移动指定的距离：

template<typename IterT, typename DistT> // move iter d units forward;
void advance(IterT& iter, DistT d); // if d < 0, 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结构体”：

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

这些结构体之间的继承关系是有效的“is-a”关系（Item32）：所有的前向迭代器同样是输入迭代器，等等。我们很快会看到这种继承的效用。

2. 如何实现advance简析

回到advance。考虑到不同的迭代器功能，实现advance的一种方法是使用循环的最小公分母策略：对迭代器进行反复加或者减。然而，这个方法会花费线性的时间。随机访问迭代器支持常量时间的迭代器算法，在我们需要的时候会使用它的这种能力。

我们真正想要的是像下面这样去实现advance:

template<typename IterT, typename DistT>
void advance(IterT& iter, DistT d) {
    if (iter is a random access iterator) {
        iter += d;                           // use iterator arithmetic
    }                                        // for random access iters
    else {
        if (d >= 0) {
            while (d--)
                ++iter;
        } // use iterative calls to
        else {
            while (d++)
                --iter;
        } // ++ or -- for other
    } // iterator categories
}

这需要决定iter是不是一个随机访问迭代器，也就是需要知道它的类型，IterT，是不是随机访问迭代器类型。换句话说，我们需要获取一个类型的相关信息。这也是Traits让你所做的：它们允许你在编译期间获取一个类型的相关信息。

3. Traits技术分析

3.1 使用traits技术的要求

Traits不是C++中的关键字或者一个预定义的概念；它们是一种技术，也是一个C++程序员需要遵守的约定。使用这项技术的一个要求是它必须使内建类型同用户自定义类型一样能够很好的工作。例如，如果advance的入参为一个指针（像const char*）和一个Int，advance必须能够工作，但是这就意味着Traits技术必须能够使用在像指针一样的内建类型上。

Traits必须能够同内建类型一块工作就意味着不能在类型内部嵌入一些信息，因为没有方法在指针内部嵌入信息。于是对于一种类型的traits信息，必须是放在类型外部的。标准的技术是将其放在模板和模板的一个或多个特化实例中。对于迭代器来说，标准库中的模板被命名为iterator_traits:

template<typename IterT> // template for information about
struct iterator_traits; // iterator types

正如你所见的，iterator_traits是一个结构体。是的，习惯上traits总是被实现为structs，但他们却又往往被成为traits classes。

Iterator_traits的工作方式是对于每个类型IterT，在结构体iterator_traits<IterT>中声明一个叫做iterator_category的typedef。这个typedef唯一确认了IterT的迭代器类别。

3.2 实现traits class需要处理用户自定义类型

Iterator_traits会在两部分中实现它。首先，它强制任何用户自定义的迭代器类型必须包含一个叫做iterator_category的内嵌typedef，它能够识别合适的tag结构体。举个例子，deque的迭代器是随机访问的，因此一个deque迭代器的类会像是下面这个样子：

template < ... >    // template params elided
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;
        ...
    };
    ...
};

iterator_traits只是重复使用iterator类的内嵌typedef:

// the iterator_category for type IterT is whatever IterT says it is;
// see Item 42 for info on the use of “typedef typename”
template<typename IterT>
struct iterator_traits<IterT>{
    typedef typename IterT::iterator_category iterator_category;
        ...
};

3.3 实现traits class需要处理指针类型

这对用户自定义类型来说会工作的很好，但是对于指针迭代器来说就不工作了，因为指针中没有内嵌的typedef。Iterator_trait实现的第二部分需要处理指针迭代器。

为了支持这种迭代器，iterator_traits为指针类型提供了一种部分模板特化（partial template specialization）。指针的行为表现同随机访问迭代器类似，所以iterator_trait为它们指定了随机访问类别：

template<typename T> // partial template specialization
struct iterator_traits<T*> // for built-in pointer types
{
    typedef random_access_iterator_tag iterator_category;
    ...
};

3.4 实现traits class总结

到现在你应该了解了如何设计和实现一个traits class：

• 确认你想要支持的类型的一些信息(例如，对于迭代器来说，它们的迭代器类别)。
• 为了确认信息，你需要选择一个名字（例如，iterator_category）
• 为你想支持的类型提供包含相关信息的一个模板和一些特化（例如，iterator_traits）

4. 使用traits class实现advance

4.1 类别判断不应该在运行时进行

考虑iterator_traits——实际上是std::iterator_traits，既然它是C++标准库的一部分——我们能为advance的实现精炼成我们自己的伪代码：

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))
    ...
}

虽然这看上去很有希望，但它不会如我们所愿。第一，它会导致编译问题，这个问题我们将在Item 48研究；现在，有更加基本的问题需要考虑。IterT的类型在编译期被确认，所以iterator_traits<IterT>::iterator_category同样能够在编译期被确定。但是if语句会在运行时被评估（除非你的优化器足够疯狂，把if语句去掉）。为什么将本来可以在编译期做的事情挪到运行时去做呢？它会浪费时间，并且会造成执行代码膨胀。

4.2 将条件评估提前到编译期——使用重载

我们真正想要的是为类型提供一个能够在编译期进行评估的条件结构（也就是一个if…else语句）。C++已经有一种方法来实现这种行为。她叫做重载。

当你重载某个函数f的时候，你为不同的重载函数指定不同的参数类型。当你调用f时，编译器会根据你所传递的参数选择最佳匹配重载函数。编译器会说：“如果这个重载对于传递过来的参数来说是最佳匹配，那么调用这个f；如果另外一个重载函数是最佳匹配，那么调用另外一个函数；如果第三个函数是最佳匹配，调用第三个”等等，看到了么？这是一个与类型相关的编译期条件结构。为了让advance表现出我们想要的行为，所有我们必须要做的是创建一个重载函数的多个版本，它们包含了advance的“内脏”，每个函数都带有一个不同类型的iterator_category对象。我将这些函数命名为doAdvance：

template<typename IterT, typename DistT> // use this impl for
void doAdvance(IterT& iter, DistT d, // random access
        std::random_access_iterator_tag) // iterators
        {
    iter += d;
}
template<typename IterT, typename DistT> // use this impl for
void doAdvance(IterT& iter, DistT d, // bidirectional
        std::bidirectional_iterator_tag) // iterators
        {
    if (d >= 0) {
        while (d--)
            ++iter;
    } else {
        while (d++)
            --iter;
    }
}
template<typename IterT, typename DistT> // use this impl for
void doAdvance(IterT& iter, DistT d, // input iterators
        std::input_iterator_tag) {
    if (d < 0) {
        throw std::out_of_range("Negative distance"); // see below
    }
    while (d--)
        ++iter;
}

因为forward_iterator_tag继承自input_iterator_tag，为input_iterator_tag提供的doAdvance版本同样能够处理forward迭代器。这是在不同iterator_tag结构体之间引入继承的动机。（事实上，这也是所有的使用public继承的动机：为基类类型实现的代码对于派生类类型来说同样适用。）

对于随机访问迭代器和双向迭代器来说，advance的特化版本同时能够做正向或者负向的移动，但是对于forward迭代器或者input迭代器来说，如果你想进行一个负向的移动就会出现未定义行为。实现中如果简单的假设d是非负的，当传递一个负参数时，你就会进入一个很长的循环中，直到d变为0为止。在上面的代码中，我所使用的替代方法是抛出一个异常。两种实现都是有效的。这就是未定义行为的诅咒：你不能预测出来会发成什么。

考虑为doAdvance所重载的不同版本，所有advance需要做的就是调用它们，传递一个额外的合适的迭代器类别对象，最后编译器就能够使用重载方案来调用合适的实现：

template<typename IterT, typename DistT>
void advance(IterT& iter, DistT d) {
    doAdvance( // call the version
            iter, d, // of doAdvance
            typename // that is
            std::iterator_traits<IterT>::iterator_category() // appropriate for
            ); // iter’s iterator
} // category

5. traits class使用总结

我们可以总结一下如何使用traits class:

• 创建一系列重载的”worker”函数或者函数模板（例如，doAdvance），通过使用traits 参数来进行区分。根据传递的traits信息来对应的实现每个函数。
• 创建一个“master”函数或者函数模板（例如，advance）来调用worker，将traits class提供的信息传递进去。

Traits被广泛使用在标准库中。对于iterator_traits来说，除了iterator_category，还为迭代器提供了四种其它的信息（最有用的就是value_type—Item 42中给出了一个例子。）还有char_traits，存储了字符类型的信息，numeric_limits,提供数字类型信息，例如，它们能够表示的最大和最小值等等。（numeric_limits这个名字可能让你感到意外，因为传统的命名方式是以“traits”结尾，但是numeric_limits没有遵守。）

TR1（Item 54）为了为类型提供信息引入了大量的新的traits class，包括is_fundamental<T>(判断T是否为内建类型)，is_array<T>(判断T是否为数组)，和is_base_of<T1,T2>（判断T1和T2是否相同或者是T2的基类）。TR1向标准C++中添加了大概有50个traits classes。

6. 本条款总结

• Traits classes使得在编译期就能够获得类型信息。它们用模板和模板特化版本来进行实现。
• 利用重载，traits classes使得在类型上执行编译期if-else测试成为可能。

7. 网友完成的一个完整的代码

我们知道容器的许多操作都是通过迭代器展开的。其中容器类似于数组，迭代器类似于指针。我们用数组来写个例子：

int arr[5] = {1,2,3,4,5}; 
int *p;
p = &arr[2];

假设，我将第1、2遮挡起来，问你p所指向的对象arr[2]是什么类型，你恐怕无法回答。因为它可以是int，char，float甚至你自己定义的类型。假设我们现在是个容器：

list<int> lit(5,3);
list<int>::iterator it1，it2; 
it1 = lit.begin(); 
it2 = lit.end();

其中lit是个容器对象，it1和it2都是容器的迭代器。假设现在有个函数，他接受两个迭代器作为参数，并且返回类型是迭代器所指的类型：

template<class iterator>
返回类型 fun(iterator first,iterator last) 
{
    //函数体 
}

问题来了，现在我的返回类型假设是iterator所指向的类型。我们无法进行下去了……别怕，我们接着往下看：

如果我们将迭代器定义成一个类：

template<class T>
class My_iterator
{ public:
    T* ptr;
    typedef T value_type;
    My_iterator(T* p = 0):ptr(p){} //... 
};

也就是说如果我们的list的迭代器的类型也是上面那种形式，那么我们的fun函数就可以这样写了：

template<class iterator> 
typename iterator::value_type　　//返回类型
fun(iterator first,iterator last)
{ 
    //函数体 
}

这样，迭代器所指的容器元素的类型就可以取出来了。怎么样，是不是很cool！但是不是所有的迭代器都是一个类啊，比如我们的原生指针也是迭代器的一种。vector的迭代器就是原生指针。那么用上面的那种方法似乎就不行了。但是STL的编写者创造了一个很好的方法---迭代器类型萃取模板，可以萃取原生指针所指向的元素的类型。对了，什么是原生指针？就是那种真正的是一个指针，我们的许多容器（list，deque）的迭代器是模拟指针但实际上它不是真正意义上的指针，他是一个类里面封装了原生指针。上面的My_iterator是迭代器，My_iterator里面的成员ptr就是原生指针。现在，是Traits编程技法发挥作用的时候了：

如果我们有个迭代器类型萃取模板，如下：

template<clas iterator>    //专门用来萃取迭代器iterator指向的元素的类型
class My_iterator_traits
{
    typedef typename iterator::value_type value_type; //...
};

于是，我们的fun()函数就可以写成这样：

template<class iterator>
typename My_iterator_traits<iterator>::value_type　　//返回类新
fun(iterator first,iterator last)
{
    //函数体 
}

明眼人一眼就能看出这个代码跟原来的相比除了多一层包装，好像什么实质意义也没有，别急。我们这样写并不是做无用功，是为了应付上面说的原生指针而设计的。这时，我们的偏特化要派上用场了，针对原生指针的迭代器类型萃取偏特化模板如下：

template<clas iterator>    //专门用来萃取迭代器iterator指向的类型的
class My_iterator_traits<iterator*> { //typedef typename iterator::value_type value_type;
    typedef T value_type;  //注意与上面的区别 //...
};

怎么样，这样一个迭代器类型萃取模板就这样诞生了。它可以萃取自定义的iterator类型和原生指针类型。

#include <iostream>
using namespace std;

/*先定义一些tag*/
struct A {
};
struct B: A {
};

/*假设有一个未知类*/
template<class AorB>
struct unknown_class {
    typedef AorB return_type;
};

/*特性萃取器*/
template<class unknown_class>
struct unknown_class_traits {
    typedef typename unknown_class::return_type return_type;
};

/*特性萃取器 —— 针对原生指针*/
template<class T>
struct unknown_class_traits<T*> {
    typedef T return_type;
};

/*特性萃取器 —— 针对指向常数*/
template<class T>
struct unknown_class_traits<const T*> {
    typedef const T return_type;
};

template<class unknown_class>
inline typename unknown_class_traits<unknown_class>::return_type __func(unknown_class, A)
{
    cout << "use A flag" << endl;
    return A();
}

template<class unknown_class>
inline typename unknown_class_traits<unknown_class>::return_type __func(unknown_class, B)
{
    cout << "use B flag" << endl;
    return B();
}

template<class unknown_class, class T>
T __func(unknown_class, T) {
    cout << "use origin ptr" << endl;
    return T();
}

/*决定使用哪一个类型*/
template<class unknown_class>
inline typename unknown_class_traits<unknown_class>::return_type return_type(unknown_class)
{
    typedef typename unknown_class_traits<unknown_class>::return_type RT;
    return RT();
}

template<class unknown_class>
inline typename unknown_class_traits<unknown_class>::return_type func(unknown_class u)
{
    typedef typename unknown_class_traits<unknown_class>::return_type return_type;
    return __func(u, return_type());
}

int main() {
    unknown_class<B> b;
    unknown_class<A> a;
    //unknown_class<int> i;
    int value = 1;
    int *p = &value;

    A v1 = func(a);
    B v2 = func(b);
    int v3 = func(p);
}