STL主要由“用以表現(xiàn)容器，迭代器和算法”的模板組成，但是也有一些功能模板丧叽。其中之一叫做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并不是用這種方式實現(xiàn)的，因為只有隨機訪問迭代器支持+=操作陕靠。其他一些更加弱的迭代器類型必須通過反復(fù)的++或者--d次來實現(xiàn)advance迂尝。

1. 五種迭代器種類回顧

你不記得STL迭代器的種類了？沒問題剪芥，我們現(xiàn)在做一些簡單的回顧垄开。總共有5類迭代器税肪，對應(yīng)著它們支持的五種操作溉躲。輸入迭代器（input iterator）只能向前移動，一次只能移動一步益兄，只能讀取它們指向的內(nèi)容锻梳，并且只能讀一次。這種迭代器模擬的是輸入文件的讀指針净捅；C++庫的istream_iterator是這種迭代器的代表唱蒸。輸出迭代器（output iterator）同輸入迭代器類似，但是對于輸出迭代器來說：它們只能向前移動灸叼，每次只能移動一步神汹，只能對它們指向的內(nèi)存進(jìn)行寫操作，并且只能寫一次古今。它們模擬的是輸出文件的寫指針屁魏；ostream_iterator代表了這種迭代器。這是兩類功能最弱的迭代器捉腥。因為輸入和輸出迭代器只能向前移動氓拼，只能對它們所指向的內(nèi)容進(jìn)行讀寫最多一次，它們只能為one-pass算法所使用抵碟。

一個更加強大的迭代器種類由前向迭代器（forward iterator）組成桃漾。這種迭代器能做輸入和輸出迭代器能做的所有事情，并且它們能對它們指向的內(nèi)容進(jìn)行多次的讀寫拟逮。這就使得它們能被multi-pass算法所使用撬统。STL沒有提供單鏈表，但是一些庫卻提供了（通常叫做slist）敦迄，這種容器中的迭代器為前向迭代器恋追。TR1中的哈希容器（Item 54）迭代器也可能是前向迭代器凭迹。

雙向迭代器（bidirectional iterators）和前向迭代器相比添加了向后移動的能力。為STL中的list提供的迭代器就屬于這種類別苦囱，為set嗅绸，multiset，map和multimap提供的迭代器也是這種類別撕彤。

最強大的迭代器類別叫做隨機訪問迭代器（random access iterator）鱼鸠。這種類型的迭代器和雙向迭代器相比添加了執(zhí)行“迭代器運算（iterator arithmetic）”的能力，也就是在常量時間內(nèi)向前或者向后跳躍任意的距離羹铅。這種運算同指針運算類似蚀狰，不要吃驚，因為隨機訪問迭代器模擬的就是內(nèi)建類型的指針睦裳，內(nèi)建類型指針的行為表現(xiàn)就如同隨機訪問迭代器。Vector撼唾，deque和string迭代器都是隨機訪問迭代器廉邑。

為了識別這五種迭代器類型，C++在標(biāo)準(zhǔn)庫中為五種迭代器類型提供了一個“tag結(jié)構(gòu)體”：

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

這些結(jié)構(gòu)體之間的繼承關(guān)系是有效的“is-a”關(guān)系（Item32）：所有的前向迭代器同樣是輸入迭代器倒谷，等等蛛蒙。我們很快會看到這種繼承的效用。

2. 如何實現(xiàn)advance簡析

回到advance渤愁∏Ｋ睿考慮到不同的迭代器功能，實現(xiàn)advance的一種方法是使用循環(huán)的最小公分母策略：對迭代器進(jìn)行反復(fù)加或者減抖格。然而诺苹，這個方法會花費線性的時間。隨機訪問迭代器支持常量時間的迭代器算法雹拄，在我們需要的時候會使用它的這種能力收奔。

我們真正想要的是像下面這樣去實現(xiàn)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坪哄，是不是隨機訪問迭代器類型。換句話說势篡，我們需要獲取一個類型的相關(guān)信息翩肌。這也是Traits讓你所做的：它們允許你在編譯期間獲取一個類型的相關(guān)信息。

3. Traits技術(shù)分析

3.1 使用traits技術(shù)的要求

Traits不是C++中的關(guān)鍵字或者一個預(yù)定義的概念禁悠；它們是一種技術(shù)念祭，也是一個C++程序員需要遵守的約定。使用這項技術(shù)的一個要求是它必須使內(nèi)建類型同用戶自定義類型一樣能夠很好的工作碍侦。例如棒卷，如果advance的入?yún)橐粋€指針（像const char*）和一個Int顾孽，advance必須能夠工作，但是這就意味著Traits技術(shù)必須能夠使用在像指針一樣的內(nèi)建類型上比规。

Traits必須能夠同內(nèi)建類型一塊工作就意味著不能在類型內(nèi)部嵌入一些信息若厚，因為沒有方法在指針內(nèi)部嵌入信息。于是對于一種類型的traits信息蜒什，必須是放在類型外部的测秸。標(biāo)準(zhǔn)的技術(shù)是將其放在模板和模板的一個或多個特化實例中。對于迭代器來說灾常，標(biāo)準(zhǔn)庫中的模板被命名為iterator_traits:

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

正如你所見的霎冯，iterator_traits是一個結(jié)構(gòu)體。是的钞瀑，習(xí)慣上traits總是被實現(xiàn)為structs沈撞，但他們卻又往往被成為traits classes。

Iterator_traits的工作方式是對于每個類型IterT雕什，在結(jié)構(gòu)體iterator_traits<IterT>中聲明一個叫做iterator_category的typedef缠俺。這個typedef唯一確認(rèn)了IterT的迭代器類別。

3.2 實現(xiàn)traits class需要處理用戶自定義類型

Iterator_traits會在兩部分中實現(xiàn)它贷岸。首先壹士，它強制任何用戶自定義的迭代器類型必須包含一個叫做iterator_category的內(nèi)嵌typedef，它能夠識別合適的tag結(jié)構(gòu)體偿警。舉個例子躏救，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只是重復(fù)使用iterator類的內(nèi)嵌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 實現(xiàn)traits class需要處理指針類型

這對用戶自定義類型來說會工作的很好盒使，但是對于指針迭代器來說就不工作了，因為指針中沒有內(nèi)嵌的typedef七嫌。Iterator_trait實現(xiàn)的第二部分需要處理指針迭代器忠怖。

為了支持這種迭代器，iterator_traits為指針類型提供了一種部分模板特化（partial template specialization）抄瑟。指針的行為表現(xiàn)同隨機訪問迭代器類似凡泣，所以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 實現(xiàn)traits class總結(jié)

到現(xiàn)在你應(yīng)該了解了如何設(shè)計和實現(xiàn)一個traits class：

• 確認(rèn)你想要支持的類型的一些信息(例如，對于迭代器來說皮假，它們的迭代器類別)鞋拟。
• 為了確認(rèn)信息，你需要選擇一個名字（例如惹资，iterator_category）
• 為你想支持的類型提供包含相關(guān)信息的一個模板和一些特化（例如贺纲，iterator_traits）

4. 使用traits class實現(xiàn)advance

4.1 類別判斷不應(yīng)該在運行時進(jìn)行

考慮iterator_traits——實際上是std::iterator_traits，既然它是C++標(biāo)準(zhǔn)庫的一部分——我們能為advance的實現(xiàn)精煉成我們自己的偽代碼：

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

雖然這看上去很有希望褪测，但它不會如我們所愿猴誊。第一潦刃，它會導(dǎo)致編譯問題，這個問題我們將在Item 48研究懈叹；現(xiàn)在乖杠，有更加基本的問題需要考慮。IterT的類型在編譯期被確認(rèn)澄成，所以iterator_traits<IterT>::iterator_category同樣能夠在編譯期被確定胧洒。但是if語句會在運行時被評估（除非你的優(yōu)化器足夠瘋狂，把if語句去掉）墨状。為什么將本來可以在編譯期做的事情挪到運行時去做呢卫漫？它會浪費時間，并且會造成執(zhí)行代碼膨脹肾砂。

4.2 將條件評估提前到編譯期——使用重載

我們真正想要的是為類型提供一個能夠在編譯期進(jìn)行評估的條件結(jié)構(gòu)（也就是一個if…else語句）列赎。C++已經(jīng)有一種方法來實現(xiàn)這種行為。她叫做重載镐确。

當(dāng)你重載某個函數(shù)f的時候包吝，你為不同的重載函數(shù)指定不同的參數(shù)類型。當(dāng)你調(diào)用f時辫塌，編譯器會根據(jù)你所傳遞的參數(shù)選擇最佳匹配重載函數(shù)漏策。編譯器會說：“如果這個重載對于傳遞過來的參數(shù)來說是最佳匹配派哲，那么調(diào)用這個f臼氨；如果另外一個重載函數(shù)是最佳匹配，那么調(diào)用另外一個函數(shù)芭届；如果第三個函數(shù)是最佳匹配储矩，調(diào)用第三個”等等，看到了么褂乍？這是一個與類型相關(guān)的編譯期條件結(jié)構(gòu)持隧。為了讓advance表現(xiàn)出我們想要的行為，所有我們必須要做的是創(chuàng)建一個重載函數(shù)的多個版本逃片，它們包含了advance的“內(nèi)臟”屡拨，每個函數(shù)都帶有一個不同類型的iterator_category對象。我將這些函數(shù)命名為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結(jié)構(gòu)體之間引入繼承的動機。（事實上损离，這也是所有的使用public繼承的動機：為基類類型實現(xiàn)的代碼對于派生類類型來說同樣適用哥艇。）

對于隨機訪問迭代器和雙向迭代器來說，advance的特化版本同時能夠做正向或者負(fù)向的移動僻澎，但是對于forward迭代器或者input迭代器來說貌踏，如果你想進(jìn)行一個負(fù)向的移動就會出現(xiàn)未定義行為十饥。實現(xiàn)中如果簡單的假設(shè)d是非負(fù)的，當(dāng)傳遞一個負(fù)參數(shù)時祖乳，你就會進(jìn)入一個很長的循環(huán)中逗堵，直到d變?yōu)?為止。在上面的代碼中凡资，我所使用的替代方法是拋出一個異常砸捏。兩種實現(xiàn)都是有效的。這就是未定義行為的詛咒：你不能預(yù)測出來會發(fā)成什么隙赁。

考慮為doAdvance所重載的不同版本垦藏，所有advance需要做的就是調(diào)用它們，傳遞一個額外的合適的迭代器類別對象伞访，最后編譯器就能夠使用重載方案來調(diào)用合適的實現(xiàn)：

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使用總結(jié)

我們可以總結(jié)一下如何使用traits class:

• 創(chuàng)建一系列重載的”worker”函數(shù)或者函數(shù)模板（例如掂骏，doAdvance），通過使用traits 參數(shù)來進(jìn)行區(qū)分厚掷。根據(jù)傳遞的traits信息來對應(yīng)的實現(xiàn)每個函數(shù)弟灼。
• 創(chuàng)建一個“master”函數(shù)或者函數(shù)模板（例如，advance）來調(diào)用worker冒黑，將traits class提供的信息傳遞進(jìn)去田绑。

Traits被廣泛使用在標(biāo)準(zhǔn)庫中。對于iterator_traits來說抡爹，除了iterator_category掩驱，還為迭代器提供了四種其它的信息（最有用的就是value_type—Item 42中給出了一個例子。）還有char_traits冬竟，存儲了字符類型的信息欧穴，numeric_limits,提供數(shù)字類型信息，例如泵殴，它們能夠表示的最大和最小值等等涮帘。（numeric_limits這個名字可能讓你感到意外，因為傳統(tǒng)的命名方式是以“traits”結(jié)尾笑诅，但是numeric_limits沒有遵守调缨。）

TR1（Item 54）為了為類型提供信息引入了大量的新的traits class，包括is_fundamental<T>(判斷T是否為內(nèi)建類型)吆你，is_array<T>(判斷T是否為數(shù)組)弦叶，和is_base_of<T1,T2>（判斷T1和T2是否相同或者是T2的基類）。TR1向標(biāo)準(zhǔn)C++中添加了大概有50個traits classes早处。

6. 本條款總結(jié)

• Traits classes使得在編譯期就能夠獲得類型信息湾蔓。它們用模板和模板特化版本來進(jìn)行實現(xiàn)。
• 利用重載砌梆，traits classes使得在類型上執(zhí)行編譯期if-else測試成為可能默责。

7. 網(wǎng)友完成的一個完整的代碼

我們知道容器的許多操作都是通過迭代器展開的贬循。其中容器類似于數(shù)組，迭代器類似于指針桃序。我們用數(shù)組來寫個例子：

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

假設(shè)杖虾，我將第1、2遮擋起來媒熊，問你p所指向的對象arr[2]是什么類型奇适，你恐怕無法回答。因為它可以是int芦鳍，char嚷往，float甚至你自己定義的類型。假設(shè)我們現(xiàn)在是個容器：

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

其中l(wèi)it是個容器對象皮仁，it1和it2都是容器的迭代器。假設(shè)現(xiàn)在有個函數(shù)菲宴，他接受兩個迭代器作為參數(shù)贷祈，并且返回類型是迭代器所指的類型：

template<class iterator>
返回類型 fun(iterator first,iterator last) 
{
    //函數(shù)體 
}

問題來了，現(xiàn)在我的返回類型假設(shè)是iterator所指向的類型喝峦。我們無法進(jìn)行下去了……別怕势誊，我們接著往下看：

如果我們將迭代器定義成一個類：

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

也就是說如果我們的list的迭代器的類型也是上面那種形式，那么我們的fun函數(shù)就可以這樣寫了：

template<class iterator> 
typename iterator::value_type　　//返回類型
fun(iterator first,iterator last)
{ 
    //函數(shù)體 
}

這樣谣蠢，迭代器所指的容器元素的類型就可以取出來了粟耻。怎么樣，是不是很cool漩怎！但是不是所有的迭代器都是一個類啊勋颖，比如我們的原生指針也是迭代器的一種嗦嗡。vector的迭代器就是原生指針勋锤。那么用上面的那種方法似乎就不行了。但是STL的編寫者創(chuàng)造了一個很好的方法---迭代器類型萃取模板侥祭，可以萃取原生指針?biāo)赶虻脑氐念愋腿础α耍裁词窃羔槹烤褪悄欠N真正的是一個指針谈宛，我們的許多容器（list，deque）的迭代器是模擬指針但實際上它不是真正意義上的指針胎署，他是一個類里面封裝了原生指針吆录。上面的My_iterator是迭代器，My_iterator里面的成員ptr就是原生指針∏砟粒現(xiàn)在恢筝，是Traits編程技法發(fā)揮作用的時候了：

如果我們有個迭代器類型萃取模板哀卫，如下：

template<clas iterator>    //專門用來萃取迭代器iterator指向的元素的類型
class My_iterator_traits
{
    typedef typename iterator::value_type value_type; //...
};

于是，我們的fun()函數(shù)就可以寫成這樣：

template<class iterator>
typename My_iterator_traits<iterator>::value_type　　//返回類新
fun(iterator first,iterator last)
{
    //函數(shù)體 
}

明眼人一眼就能看出這個代碼跟原來的相比除了多一層包裝撬槽，好像什么實質(zhì)意義也沒有此改，別急。我們這樣寫并不是做無用功侄柔，是為了應(yīng)付上面說的原生指針而設(shè)計的共啃。這時，我們的偏特化要派上用場了暂题，針對原生指針的迭代器類型萃取偏特化模板如下：

template<clas iterator>    //專門用來萃取迭代器iterator指向的類型的
class My_iterator_traits<iterator*> { //typedef typename iterator::value_type value_type;
    typedef T value_type;  //注意與上面的區(qū)別 //...
};

怎么樣移剪，這樣一個迭代器類型萃取模板就這樣誕生了。它可以萃取自定義的iterator類型和原生指針類型薪者。

#include <iostream>
using namespace std;

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

/*假設(shè)有一個未知類*/
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;
};

/*特性萃取器 —— 針對指向常數(shù)*/
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);
}