1.前言

STL主要由“用以表現(xiàn)容器，迭代器和算法”的template構(gòu)成，但也覆蓋若干工具性templates，其中一個名為advance，用來將某個迭代器移動某個給定距離：

tempalte<typename IterT,typename DistT>//將迭代器向前移動d單位
void advance(IterT& iter,DistT d);//如果d<0，則向后移動

觀念上advance只是做iter+=d動作，但其實不可以全然是那樣，因為只有random access(隨機訪問)迭代器才支持+=操作。面對其它迭代器種類，advance必須反復(fù)施行++或--，共d次。

先回顧下STL迭代器的分類：STL共有5種迭代器分類，inpiut迭代器只能向前移動，一次一步，客戶可只讀取它們所指的變量，而且只讀取一次，他們模仿指向輸入文件的閱讀指針(read pointer)；c++程序庫中的istream_iterators是這一分類的代表。output迭代器情況類似，但一切只為輸出：它們只向前移動，一次一步，客戶只涂寫一次。它們模仿指向輸出文件的涂寫指針（write pointer）；ostream_iterators是這一分類的代表。這是功能最小的兩個迭代器分類。由于這；兩類都只能向前移動，而且只能讀或?qū)懫渌肝镒疃嘁淮?#xff0c;所以它們只適合“一次性操作”（one-pass algorithms）。另一個功能比較強大的分類是forward迭代器。這種迭代器可以做前述兩種分類所能做的每一件事，而且可以讀或?qū)懫渌肝镆淮我陨?。這使得它們可以施行于多次性操作算法(multi-pass algorithms)。STL并未提供單向linked list,但某些程序庫有slit,而置入這種容器的迭代器就是屬于forward迭代器。指入TR1 hashed容器的也可能是這一分類。

Bidirectional迭代器比上一個功能更大：它除了可以向前移動，還可以向后移動。STL的list迭代器就屬于這一類，set,multiset,map和multimap的迭代器也都是這一分類。

最強大的迭代器當屬random access迭代器。這種迭代器功能強大之處再與它可以執(zhí)行“迭代器算術(shù)”，即可以在常量時間內(nèi)向前或向后跳躍任意距離。

對這5種分類，c++標準程序庫分別提供專屬的卷標結(jié)構(gòu)（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 biairectional_iterator_tag{};

這些struct之間的繼承關(guān)系是有效的is-a。

現(xiàn)在回到advance函數(shù)，我們知道STL迭代器有著不同的能力，實現(xiàn)advance的策略之一是采用“最低但最普及”的迭代能力，以循環(huán)往復(fù)遞增或遞減迭代器。然而這種做法耗費線性時間，我們知道random access迭代器支持迭代器算術(shù)運算，只耗費常量時間，如果面對這種迭代器，我們希望運用其優(yōu)勢：

然而我們真正希望的是以這種方式實現(xiàn)advance：

template<typename IterT,typename DistT>
void advance(IterT& iter,DistT d)
{if(iterT& iter,DistT d){if(iter is a random access iterator){iter+=d;//針對random access迭代器使用迭代器算術(shù)運算}else{if(d>=0){while(d--) ++iter;}else{if(d>=0){while(d--) ++iter;}else {while(d++) --iter;}//針對其它迭代器分類，反復(fù)調(diào)用++或--}}}}

這種做法首先是必須判斷iter是否未random access迭代器，也就是說需要知道類型IterT是否為random access迭代器。換句話說我們需要取得類型的某些信息。那就是traits讓你得以進行的事情：它們允許你在編譯期間取得某些類型信息。。

2.實例分析

traits并不是c++關(guān)鍵自或一個預(yù)先定義好的構(gòu)件；他們是一種技術(shù)，也是一個c++程序員共同遵守的協(xié)議。這個技術(shù)的要求之一是他對內(nèi)置(built-in)類型或用戶自定義類型的表現(xiàn)必須一樣好。舉個例子，如果上述advance仍然必須有效運作，那意味這traits技術(shù)必須i能夠施行于內(nèi)置類型如指針上。

”traits必須能夠施行于內(nèi)置類型“意味”類型內(nèi)的嵌套信息（nesting information）“這種東西必須出局了，因為我們無法將信息嵌套于原始指針內(nèi)。因此類型的traits信息必須位于類型自身之外。標準技術(shù)時把它放進一個template及其一個被命名為iterator_traits:

template<typename iterT>//template，用來處理
struct iterator_traits;//迭代器分類的相關(guān)信息

正如所看到的，iterattor_traits是個struct。習(xí)慣上traits總是被實現(xiàn)為structs,但它們又往往被稱為traits classes。

iterator_traits的運作方式是針對每一個類型IterT,針對每一個類型IterT,在struct iterator_traits<IterT>內(nèi)一定聲明某個typedef名為iiterator_category，這個typedef用來確認IterT的迭代器分類。

iterator_traits以兩個部分實現(xiàn)上述所言。首先它要求每一個“用戶自定義的迭代器類型”必須嵌套一個typedef，名為iterator_category，用來確認適當?shù)木順私Y(jié)構(gòu)。例如deque的迭代器可隨機訪問，所以一個針對deque迭代器而設(shè)計的class看起來會是這個樣子：

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

list的迭代器可雙向行進，所以它們應(yīng)該是這樣的：

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

至于iterator_traits，只是相應(yīng)iterator class的嵌套式typedef:

//類型IterT的iterator_category其實是用來表現(xiàn)“IterT說它自己是什么”
//關(guān)于“typedef typename”的運用，見條款42
template<typename IterT>
struct iterator_traits{typedef typename IterT::iterator_category iterator_category;...
};

這對用戶自定義類型行得通，但對指針（也是一種迭代器）行不通，因為指針不可能嵌套tepedef。iterator_traits的第二部分如下，專門用來對付指針：

為了支持指針迭代器，iterator_traits特別針對指針類型提供一個偏特化版本（partial template specialization）。由于指針的行徑與random access迭代器類似，所以iterator_traits為指針指定的迭代器類型是：

template<typename IterT>//template偏特化
struct iterator_traits<IterT*>//針對內(nèi)置指針
{typedef random_access_iterator_tag  iterator_category;....
};

現(xiàn)在，我們應(yīng)該了解了如何設(shè)計并實現(xiàn)一個traits class了：

（1）確認若干你希望可取的的類型相關(guān)信息。例如對迭代器而言，我們希望將來可取其分類（category）;

(2)為該信息選擇一個名稱（比如iterator_category）

(3)提供一個template和一組特化版本，內(nèi)含你希望支持的類型相關(guān)信息。

現(xiàn)在有了iterator_traits（實際上是std::iterator_traits，因為它是c++標準程序的一部分），我們可以對advance實踐先前的偽碼（pseudocode）:

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)致編譯問題。IterT類型在編譯器間獲知，所以iterator_traits<IterT>::iterator_category也可以在編譯器間確定。但if語句卻是在運行期才會核定。

我們真正想要的是一個條件式，判斷“編譯器核定成功”之類型。恰巧c++有一個取得這種行為的辦法，那就是重載(overloading)。

當我們重載某個函數(shù)f，必須詳細描述各個重載建房的參數(shù)類型。當你調(diào)用f，編譯器便根據(jù)傳來的實參選擇最適合的重載件。編譯器的態(tài)度是“如果這個重載件最匹配傳遞過來的實參，就調(diào)用這個f；如果那個重載件最匹配，就調(diào)用那個f；如果第三個f最匹配，就調(diào)用第三個f”。依次類推。這正是一個針對類型而發(fā)生的“編譯器條件句”。為了讓advance的行為如我們所期望的那樣，我們需要做的是產(chǎn)生兩版重載函數(shù)，內(nèi)含advance的本質(zhì)內(nèi)容，但各自接受不同類型的iterator_category對象。我將這兩個函數(shù)取名為doAdvance:

template<typename IterT,typename DistT>//用于random access 迭代器
void doAdvance(IterT& iter,typename Dist,std::random_access_iterator_tag)
{iter+=d;
}template<typename IterT,typename DistT，std::bidirectional_iterator_tag>//這份
{                                   //實現(xiàn)用于bidirectional迭代器if(d>=0){while(d--)++iter;}else{while(d++) --iter;}}
template<typename IterT,typename DistT>//這份用于實現(xiàn)input迭代器
void doAdvance(IterT& iter,DistT d,std::input_iterator_tag)
{if(d<0){throw std::out_of_range("Negative distance");}while(d--) ++iter;
}

由于forward_iterator繼承自input_iterator_tag，所以上述doAdvance的input_iterator_tag版本也能夠處理forward迭代器。這是iterator_tag structs繼承關(guān)系帶來的一項紅利。實際上這也是public繼承帶來的部分好處：針對base class編寫的代碼用于derived class身上行得通。

advance函數(shù)規(guī)范說，如果面對的是random access和bidirectional迭代器，則接受正距離和負距離；但如果面對的是forward或input迭代器，則移動負距離會導(dǎo)致不明確（未定義）行為。我所檢驗過的實現(xiàn)碼都假設(shè)d不為負，于是直接進入一個冗長的循環(huán)迭代，等待計數(shù)器降為0。上述異常我以拋出異常取而代之。

有了這些doAdvance重載版本，advance需要做的是調(diào)用它們并額外傳遞一個對象，后者必須帶有適當?shù)牡鞣诸?。于是編譯器運用重載解析機制（overloading resolution）調(diào)用適當?shù)膶崿F(xiàn)代碼：

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

現(xiàn)在我們可以總結(jié)如何使用一個traits class了：

（1）建立一組重載函數(shù)或函數(shù)模板，，彼此間的差異只在于各自的traits參數(shù)。令每個函數(shù)實現(xiàn)碼與其接受之traits信息相應(yīng)和。

（2）建立一個控制函數(shù)或函數(shù)模板，它調(diào)用上述那些勞工函數(shù)并傳遞traits class所提供的信息。

traits廣泛用于標準程序庫，其中當然有上述討論的iterator_traits，除了供應(yīng)iterator_category還供應(yīng)另四分迭代器相關(guān)信息。此外還有char_traits用來保存字符類型相關(guān)信息，以及numeric_limits用來保存數(shù)值類型的相關(guān)信息，例如某些數(shù)值類型可表現(xiàn)之最小值和最大值等等；命名為numeric_limits有點讓人驚訝，因為traits classes的名稱以"traits"結(jié)束，但numeric_limits卻沒有遵守這種風(fēng)格。

3.總結(jié)

（1）Traits classes使得“類型相關(guān)信息”在編譯器可用。它們以template和“templates特化”完成實現(xiàn)。

（2）整合重載技術(shù)后，traits classes有可能在編譯器對類型執(zhí)行if...else 測試。