自從C++中引入了template后，以泛型技術(shù)為中心的設(shè)計得到了長足的進步。STL就是這個階段杰出的產(chǎn)物。STL的目標(biāo)就是要把數(shù)據(jù)和算法分開，分別對其進行設(shè)計，之后通過一種名為iterator的東西，把這二者再粘接到一起。設(shè)計模式中，關(guān)于iterator的描述為：一種能夠順序訪問容器中每個元素的方法，使用該方法不能暴露容器內(nèi)部的表達方式。可以說，類型萃取技術(shù)就是為了要解決和iterator有關(guān)的問題的，下面，我們就來看看整個故事。
應(yīng)該說，迭代器就是一種智能指針，因此，它也就擁有了一般指針的所有特點——能夠?qū)ζ溥M行*和->操作。但是在遍歷容器的時候，不可避免的要對遍歷的容器內(nèi)部有所了解，所以，設(shè)計一個迭代器也就自然而然的變成了數(shù)據(jù)結(jié)構(gòu)開發(fā)者的一個義務(wù)，而這些iterators的表現(xiàn)都是一樣的，這種內(nèi)外的差異，對用戶來說，是完全透明的，
第一部分 為什么要有萃取技術(shù)
既然是一種智能指針，iterator也要對一個原生指針進行封裝，而問題就源于此，當(dāng)我們需要這個原生指針?biāo)笇ο蟮念愋偷臅r候（例如聲明變量），怎么辦呢？
Case1 對于函數(shù)的局部變量
這種情況我們可以采用模版的參數(shù)推導(dǎo)，例如：
template <class T> void func(T iter)
如果T是某個指向特定對象的指針，那么在func中需要指針?biāo)赶驅(qū)ο箢愋偷淖兞康臅r候，怎么辦呢？這個還比較容易，模板的參數(shù)推導(dǎo)機制可以完成任務(wù)，如下：
template <class T, class U>
void func_impl(T t, U u) {
U temp; // OK, we’ve got the type
// The rest work of func…
}
template <class T>
void func(T t) {
func_impl(t, *t); // forward the task to func_impl
}
通過模板的推導(dǎo)機制，我們輕而易舉的或得了指針?biāo)赶虻膶ο蟮念愋停鞘虑橥荒敲春唵巍＠纾绻蚁氚褌鬟f給func的這個指針參數(shù)所指的類型作為返回值，顯然這個方法不能湊效了，這就是我們的case 2。
Case2 對于函數(shù)的返回值
盡管在func_impl中我們可以把U作為函數(shù)的返回值，但是問題是用戶需要調(diào)用的是func，于是，你不可能寫出下面的代碼：
template <class T, class U>
U func_impl(T t, U u) {
U temp; // OK, we’ve got the type
// The rest work of func…
}
template <class T>
(*T) func(T t) { // !!!Wrong code
return func_impl(t, *t); // forward the task to func_impl
}
int i =10;
cout<<func(&i)<<endl; // !!! Can’t pass compile
紅色的部分概念上如此正確，不過所有的編譯器都會讓你失望。這個問題解決起來也不難，只要做一個iterator，然后在定義的時候為其指向的對象類型制定一個別名，就好了，像下面這樣：
template <class T>
struct MyIter {
typedef T value_type; // A nested type declaration, important!!!
T* ptr;
MyIter(T* p = 0) : ptr(p) {}
T& operator*() const { return *ptr; }
};
而后只要需要其指向的對象的類型，只要直接引用就好了，例如：
template <class I>
typename I::value_type func(I iter) { return *iter; }
很漂亮的解決方案，看上去一切都很完美。但是，實際上還是有問題，因為func如果是一個泛型算法，那么它也絕對要接受一個原生指針作為迭代器，但是顯然，你無法讓下面的代碼編譯通過：
int *p = new int(52);
cout<<func(p)<<endl; // !!!Is there a int::value_type?? Wrong Code here
我們的func無法支持原生指針，這顯然是不能接受的。此時，template partial specialization就派上了用場。
Solution ：template partial specialization是救世主
既然剛才的設(shè)計方案仍不完美，那我們就再加一個間接層，把智能指針和原生指針統(tǒng)統(tǒng)的封裝起來。在討論之前，先要澄清一下template partial specialization的含義。所謂的partial specialization和模板的默認(rèn)參數(shù)是完全不同的兩件事情，前者指的是當(dāng)參數(shù)為某一類特定類型的時候，采用特殊的設(shè)計，也就是說是“針對template參數(shù)更進一步的條件限制所設(shè)計出來的一個特化版本”；而默認(rèn)參數(shù)則是當(dāng)不提供某些參數(shù)的時候，使用的一個缺省。
參考：partial specialization的語法
Template <typename T> class C<T*> {} // 為所有類型為T*的參數(shù)而準(zhǔn)備的特殊版本
好了，下面我們就找一個專職的負(fù)責(zé)人，用來封裝迭代器封裝的對象類型。首先，把我們剛才的MyIter重新包裝一下：
template <class I>
struct iterator_traits {
Typedef I::value_type value_type;
}
現(xiàn)在，我們的func又有了新的面貌：
template <class I>
typename iterator_traits<I>::value_type func(I ite) {
return *ite;
}
盡管這次我們的函數(shù)返回值的長度有些嚇人，但是，我們的確為原生指針找到了好的解決方案。只要為原生指針提供一個偏特化的iterator_traits就OK了。如下：
template <class I>
struct iterator_traits<T*> {
typedef T value_type;
};
下面，我們終于可以讓func同時支持智能指針和原生指針了：
template <class I>
struct iterator_traits {
Typedef I::value_type value_type;
}
template <class T>
struct iterator_traits<T*> {
typedef T value_type;
};
template <class I>
typename iterator_traits<I>::value_type func(I ite) {
return *ite;
}
int main() {
MyIter<int> iter = new int(520);
int *p = new int(520);
// This time the following two statements will success
cout<<func(iter)<<endl;
cout<<func(p)<<endl;
return 0;
}
但是，我們離最后的成功還有最后一步，如果，我們需要聲明一個value_type類型的左值，但是卻給iterator_traits傳遞了一個const int*，顯然結(jié)果有問題，于是，為const T*也另起爐灶，準(zhǔn)備一份小炒：
template<class T>
struct iterator_traits<const T*> {
typedef T value_type;
}
OK ，現(xiàn)在萬事大吉，無論是正宗迭代器，原生指針，const原生指針，我們都可以利用iterator_traits萃取出其封裝的對象的類型，萃取技術(shù)由此而來。
第二部分 基于泛型的類型萃取技術(shù)
總結(jié)一下，我們之所以要萃取迭代器相關(guān)的類型，無非是要把迭代器相關(guān)的類型用于聲明局部變量、用作函數(shù)的返回值等一系列行為。對于原生指針和point-to-const類型的指針，采用模板偏特化技術(shù)對其進行特殊處理，另外，對于point-to-const類型的指針，為了保證聲明左值時語義正確，特化時按照普通原生指針處理。
實際上，把我們剛才的例子提煉一下，迭代器相應(yīng)類型不僅僅有迭代器封裝的對象類型，STL中對這些類型作了整理，有如下幾種：
template <class I>
struct iterator_traits {
typedef typename I::iterator_category iterator_category;
typedef typename I::value_type value_type;
typedef typename I::difference_type difference_type;
typedef typename I::pointer pointer;
typedef typename I::reference reference;
}
當(dāng)然，也如你所想，對于原生pointer和pointer-to-const這兩種情況，STL分別對其進行了特化處理。如果你看了上面的代碼卻不知所云，也屬正常，在去了解特化版本之前，我們先來看看這五種類型的含義。
Type 1 value_type
這個類型和我們在第一部分談到的vlaue_type的含義是一樣的，不多說了。
Type 2 difference_type
用來表示兩個迭代器之間的最大距離。這個類型用來對某種算法提供計數(shù)功能，例如：
template <class I, class T>
typename iterator_traits<I>::difference_type
count(I first, I last, const T& value){
typename iterator_traits<I>::difference_type n = 0;
for(; first != last; first++) {
if(*first == value)
n++;
}
return n;
}
也許這個例子最足以說明問題，任何的解釋都沒必要了。這里需要說明的是。對于原生指針，由于不存在int::difference_type的情況，所以，iterator_traits對其進行特化：
template <class I>
class iterator_traits<I*> {
typedef ptrdiff_t difference_type;
}
這里，ptrdiff_t是定義在cstddef中的一個C++內(nèi)置類型，在GNU gcc中，定義如下：
typedef long int ptrdiff_t;
同樣，對于pointer-to-const，也要入法炮制：
template <class I>
class iterator_traits<const I*> {
typedef ptrdiff_t difference_type;
}
再一次，偏特化技術(shù)幫了大忙，現(xiàn)在count可以處理所有類型迭代器的difference_type了。
Type 3 reference
這里，reference type指的是迭代器封裝對象的類型的引用。這個類型的出現(xiàn)主要是為了解決對指針進行解引用的時候，返回什么樣的對象的問題。我們希望：
MyIter<int> iter(new int(10));
*iter = 52;
和
Int *p = new int(10);
*p = 52;
是一樣的。于是，reference_type一般用在迭代器的*運算符重載上，讓所有的“指針家族”有同樣的表現(xiàn)形式。于是，如果value_type是T，那么reference_type就是T&，如果value_type是const T，reference_type就是const T&。
Type 4 pointer
C++ 中指針和引用總是有著密切的關(guān)系。如果我們想返回迭代器封裝的對象的地址，就需要用到這里的pointer_type，主要用在迭代器中對->運算符重載的問題。對于一個智能指針來說，通常我們都需要下面的兩個運算符重載：
T& operator*() const { return *ptr; } // T& is reference type
T* operator->() const { return ptr; } // T* is pointer type
同樣，為了能夠?qū)Φ骱驮羔樁寄軌蛟谒惴ㄉ嫌薪y(tǒng)一的表現(xiàn)形式，在iterator_traits中加入了下面的類型
template <class T>
struct iterator_traits {
typedef typename I::pointer pointer;
typedef typename I::reference reference;
}
同樣，對于原生指針和point-to-const類型的指針作了特化：
template<class T>
struct iterator_traits<T*> {
typedef typename T* pointer;
typedef typename T& reference;
}
而這次，對于point-to-const類型的指針，則有些特別：
template<class T>
struct iterator_traits<const T*> {
typedef typename const T* pointer;
typedef typename const T& reference;
}
也就是說，當(dāng)我們解引用一個封裝了常量對象的迭代器的時候，返回的類型應(yīng)該是const T&，取一個封裝了常量對對象的迭代器中的元素的地址，返回的應(yīng)該是const T*。最終的結(jié)果，就是所有的算法都有了一個統(tǒng)一的表達方式：
template <class T>
typename iterator_traits<T>::reference func() {}
template <class T>
typename iterator_traits<T>::pointer func() {}
Type 5 iterator_category
這個類型的作用是按照迭代器的移動特性和能夠在該迭代器上實施的操作對迭代器進行分類，之所以這樣做，完全是為了效率的考量。不過，在我看來，對其分類的因素實際上只有迭代器的移動特性，而分類，也非常簡單：一步步向前挪的類型和一步跨到位的類型。
在STL中，共有以下5種迭代器類型：
l 單向移動只讀迭代器 Input Iterator
l 單向移動只寫迭代器 Output Iterator
l 單向移動讀寫迭代器 Forward Iterator
l 雙向移動讀寫迭代器 Bidirectional Iterator
以上4種屬于單步向前挪型的迭代器，還有一種雙向移動讀寫迭代器屬于一步跨到位型：
l 隨機訪問迭代器 Random Access Iterator
按照強化關(guān)系，上面5種迭代器的關(guān)系如下：
Input Iterator Output Iterator
| |
+-----------+----------+
|
Forward Iterator
|
Bidirectional Iterator
|
Random Access Iterator
在STL的各種算法中，遍歷元素是很常用的，于是我們就用advance()這個函數(shù)作個例子，看看每個迭代器的類型，這個函數(shù)負(fù)責(zé)把迭代器移動特定的長度：
// The input iterator version, an O(N) algorithm
template <class InputIterator, class Distance>
void Advance_II(InputIteraotr& i, Distance n) {
while(n--) i++; // This is step by step moving
}
其實，Output和Forward類型的迭代器在移動上和Input類型是一樣的。不再熬述，來看看Bidirectional類型：
// The bidirectional iterator version, an O(N) algorithm
template <class BidirectionalIterator, class Distance>
void Advance_BI(BidirectionalIterator& i, Distance n) {
if(n >= 0)
while(n--) i++;
else
while(n++) i++;
}
加入了雙向移動，但仍然要單步進行。最后，看看隨機訪問類型：
// The random access version, an O(1) algorithm
template <class RandomAccessIterator, class Distance>
void Advance_RAI(RandomAccessIterator& i, Distance n) {
i += n;
}
最后，我們可以構(gòu)想一個把這3個函數(shù)封裝起來的函數(shù)advance，專門負(fù)責(zé)迭代器的移動。
template <class InputIterator, class Distance>
void advance(InputIterator& I, Distance n) {
if(is_ramdom_access_iterator(i)) // How to judge?
advance_RAI(I, i);
else if(is_bidirectional_iterator(i)) // How to judge?
Advance_BI(I, i);
else
Advance_II(I, i);
}
但是，在程序運行時決定函數(shù)調(diào)用，顯然效率不彰，最好能夠讓編譯器在程序編譯的時候決定函數(shù)調(diào)用，于是，我們要想方設(shè)法利用函數(shù)重載，讓編譯器幫助我們決策函數(shù)調(diào)用。這樣，就需要我們對于迭代器的類型做一個統(tǒng)一的規(guī)劃，OO正好能幫助我們解決這個問題，設(shè)計下面的繼承結(jié)構(gòu)，這和我們上面畫的那張圖是一樣的：
// five tag classes
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_tag : public bidirectional_iterator_tag { }
之后，重新設(shè)計__advance，給它加上第3個參數(shù)——用以表明此迭代器類型的標(biāo)簽，根據(jù)此標(biāo)簽來決定不同的__advance操作（此時，type_traits技術(shù)派上了用場）。而對外開放的advance仍然不變:
template <class InputIterator, class Distance>
void advance(InputIterator& i, Distance n) {
// Forward the correct messages
__advance(i, n, type_traits<i>::iterator_category());
}
說到這里，你也就應(yīng)該明白iterator_category的作用了，同樣，為poiner準(zhǔn)備了兩個特化版本：
template <class T>
struct iterator_traits<T*> {
typedef random_access_iterator_tag iterator_category;
}
template <class T>
struct iterator_traits<const T*> {
typedef random_access_iterator_tag iterator_category;
}
道理很簡單，所有的原生指針都支持隨機訪問。
第三部分 雜項
在STL中，所有的迭代器都遵從上面的設(shè)計原則，都要提供上面說過的五種類型，但是，人總會有掛一漏萬的時候，為了設(shè)計上的方便，STL提供了一個標(biāo)準(zhǔn)的迭代器殼：
template <class Category,
class T,
class Distance = ptrdiff_t
class Pointer = T*
class Reference = T&>
struct iterator {
typedef Category iterator_category;
typedef T value_type;
typedef Distance difference_type;
typedef Pointer pointer;
typedef Reference reference;
};
這樣就免去了聲明這些類型的麻煩，當(dāng)你想自定義一個迭代器的時候：
template <class Item>
struct MyIter : public std::iterator<std::forward_iterator_tag, Item> { … }
就萬事大吉了。