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