iterator_traits

reference from STL源碼剖析 -- 從老闆辦公室書櫃幹來的

一圖蔽之請看下圖:

文字說明: 

Container必須要遵守對應iterator的型態，例如array的容器可以支援random access但link list只能支援forward iterator.對不同程度的iterator的支援將影響該容器是否可以跟相映演算法相接合。

例如有支援random access的容器才能支援binary search。 取max的演算法只要支援forward iterator可以traverse整個容器一次即可。

所以iterator對演算法來說是一種抽象化資料結構的介面。

不過如果說iterator是類似指標的存在，那當演算法撰寫時必須要取得指標(iterator)內所儲存的形態時該如何處理呢? 舉例像下列交換兩個iterator內容物的演算法:

template<typename I>

void swap(I i, I i2)

{

    iterator內存形態 tmp = *i;

    *i = *i2;

    *i2 = tmp;

}

此例中需要宣告一個暫存變數其型態是iterator內存的instance的型態。

其實原本iterator就需要遵守某種可以取得原形態、及相關形態的規範，即利用iterator範圍內對應的5個typedef。其中一個value_type就是上例中所需要的內存instance型態。

其在iterator內宣告長得像:

template<class T>

struct MyIterator

{

    typedef T value_type;

};

存取時寫法有點像是:

typename I::value_type;

但為支援原生型別的指標(e.g. int*, char*)

STL設計上多作了一層iterator_traits的class template來做萃取特性的動作。
如此一來就可以用C++的partial template specialization(樣板特化)的功能，針對原生指標寫一個特化版的trait來處理相關動作。
一般iterator_traits寫法如下:
template<typename I>
struct iterator_traits
{
    typedef typename I::value_type value_type;
};
特化版的iterator如下:
template<typename T>
struct iterator_traits<T*>
{
    typedef T value_type;
};