最近看侯杰老師的《STL源碼剖析》有一點收獲，特把我對STL iterator設計的認識草草記錄下來，大部分內容來自那本書(看原書更好)。歡迎大家跟我討論，里面也有問題希望您能提供寶貴看法！
一. Iterator認識
如果需要構造一組通用容器，提供一套統一的算法，構造底層數據結構類庫，iterator的設計無疑是非常重要的。iterator可以方便容器元素的遍歷，提供算法的統一參數接口。怎么說？首先，讓我們考慮一個算法。
Template <class T> ptrdiff_t
distance(T p1, T p2)
{
? //計算p1和p2之間的距離
}
顯然這個函數是想計算兩個“位置”之間距離。這里表示“位置”的類型T，可以是指向數組中某個元素的（原生）指針，可以是指向鏈表節點的指針，也可以是用來記錄位置的任何對象（例如我們要談的iterator）。不管這兩個位置是對應在數組，vector，鏈表或是其他任何容器，我們當然希望設計好的類庫中最好只要一個這樣的distance函數，而不需要每種容器都有不同的“位置”記錄方式，從而導致需要很多個這樣的distance算法。對，我們完全可以抽象出一種表示“位置”的概念，它像游標，像智能的指針，可以方便的遍歷容器中的元素，記錄位置，而不用管你作用的是什么類型的容器，這就是現在被容器設計者普遍接受的iterator概念。
二. STL iterator的設計：
為什么不用繼承構造iterator？
容器抽象出5種iterator 類型，input<--forward<--bidrectional<--random access iterator加上output iterator，我們能不能通過refinement關系設計出具有繼承關系的幾個iterator類？然后各個容器的iterator類去繼承這些基類。那么上面的disatance函數可以設計兩個版本
ptrdiff_t distance(InputIterator p1, InputIterator p2)
{
?//InputIterator只能一個一個前進,例如鏈表
? ptrdiff_t n=0;
? while(p1 != p2)
? {
? ?++p1; ++n;? ?
? }
? return n;
}
ptrdiff_t distance(RandomAccessIterator p1, RandomAccessIterator p2)
{
?//RandomAccessIterator可以直接計算差距，例如數組，vector等
?return p2-p1;
}
這樣看來是可行的對嗎？但為什么STL不采用這種方式呢？（各位幫我想想啊，我實在是菜，想不出很好的理由啊）我所能想到的有：iterator可以是原生指針的類型，而原生指針是不會繼承InputIterator基類的。（是不是還有效率問題？)
不討論STL為什么不這么作，還是看看它漂亮的處理方法吧：先提醒你，它用的是函數模板（function template）的參數推導機制來確定函數返回值和參數類型的。
(1)? 通過不同的iterator概念，先作幾個表明iterator類型的tag類。input_iterator_tag<--forward_iterator_tag<--bidrectonal_iterator_tag<--random_access_iterator_tag。還有output_iterator_tag，這幾個類都是空的，前面4個有繼承關系。
(2)? STL設計的iterator類都需要typedef一個重要的類型iterator_category用來表明這個iterator是什么類型的iterator，它必須是上面tag類中的一個。例如list<T>的iterator類有：
??? typedef bidrectonal_iterator_tag iterator_category;
???
??? 另外需要有一個value_type類型表明iterator是指向什么類型的元素。例如list<T>的iterator類有：
??? typedef T value_type;
(3)? 設計iterator_traits<class Iterator>類，這個類的作用是可以提取出模板參數Iterator類的類型。也是通過typedef實現的。如下：
template <class Iterator>
struct iterator_traits {
? typedef typename Iterator::iterator_category iterator_category;
? typedef typename Iterator::value_type??????? value_type;
? //.....
};
本來第二步中，我們設計的iterator類已經可以通過typedef別名來標志類型了，為什么要這層中間轉換？原因是通常我們可以寫Iterator::iterator_category作為一個typename，但如果Iterator是一個原生指針T*，我們寫T*::iterator_category就得不到啦。利用partial specialization（模板偏特化）技術，可以通過中間層iterator_traits自己指定并得到原生指針的iterator_category類型，代碼如下。（這么復雜的編譯技術，真不知他們咋整的...吾輩只能望洋興嘆55）
template <class T>
struct iterator_traits<T*> {
? typedef random_access_iterator_tag iterator_category;
? typedef T????????????????????????? value_type;
? //........
};
(4)? 設想要設計一個算法template <class Iterator> RET_TYPE gen_fun(Iterator p1, Iterator p2, ...)。
一般這么處理：
template <class Iterator> RET_TYPE gen_fun(Iterator p1, Iterator p2, ...)
{
??? typedef iterator_traits<Iterator>::iterator_category category;???
??? typedef iterator_traits<Iterator>::value_type type;? //這個type用于實際運算中得知iterator指向的對象(*運算符返回類型)
?? __gen_fun(Iterator p1, Iterator p2, ..., category());
}
category()構造一個iterator_tag類型的臨時變量，該臨時變量只用于區分調用函數，不參與實際算法實現。具體實現方法如下：(注意最后的參數不用變量名)
template <class Iterator> RET_TYPE __gen_fun(Iterator p1, Iterator p2, ..., input_iterator_tag)
{
?? //input_iterator類型的實際實現方法
?? //并且由于tag類繼承機制，forward_iterator類型也會調用本方法
}
?
template <class Iterator> RET_TYPE __gen_fun(Iterator p1, Iterator p2, ..., bidrectonal_iterator_tag)
{
?? //bidrectonal_iterator類型的實際實現方法
}
template <class Iterator> RET_TYPE __gen_fun(Iterator p1, Iterator p2, ..., random_access_iterator_tag)
{
?? //random_access_iterator類型的實際實現方法
}
這樣通過定義iterator tag和函數模板的參數推導機制，就實現了參數類型識別，達到了構造繼承關系的iterator類實現的功能。并且沒有繼承要求那么嚴格，而且typedef是在編譯時候完成的工作，絲毫不影響程序運行速度。如果增加iterator中typedef的類型，如pointer等，可以增強參數類型識別的功能。
另外需要提醒的是，在STL代碼中，如果是random_access_iterator類型的方法，它通常寫
template <class RandomAccessIterator> RET_TYPE __gen_fun(RandomAccessIterator p1, RandomAccessIterator p2, ..., random_access_iterator_tag)
是input_iterator類型的方法，它通常寫
template <class InputIterator> RET_TYPE __gen_fun(InputIterator p1, InputIterator p2, ..., input_iterator_tag)
但是，別被這里的RandomAccessIterator和InputIterator迷惑了，它們只是模板參數而已，并沒有繼承關系，也不存在這樣的類！（我就被這個迷惑了好久:( ）也不是我開頭提的構造一組繼承關系的Iterator類。模板參數寫成RandomAccessIterator并不能表示該RandomAccessIterator類型就是random_access_iterator的，它寫成T，Type，Iter都沒有關系。只有通過iterator_traits得到iterator_tag才能表明iterator的真正類型。我想它那樣寫，只是為了提醒你調用函數的iterator類型吧。
三. 最后看看開頭提的distance()算法實際實現：
template <class Iterator> inline
?typename iterator_traits<Iterator>::iterator_category
? iterator_category(const Iterator&)?
? //提取Iterator的iterator_category類型
{
? typedef typename iterator_traits<Iterator>::iterator_category category;
? return category();
}
template <class InputIterator, class Distance>
inline void distance(InputIterator first, InputIterator last, Distance& n)?
{
? __distance(first, last, n, iterator_category(first));
? //根據提取的iterator_category類型選擇實際執行函數
? //Distance是通過引用傳遞，相當于函數返回值
}
template <class InputIterator, class Distance>
inline void __distance(InputIterator first, InputIterator last, Distance& n,
?????????????????????? input_iterator_tag)
{
? //input_iterator類型的實現，根據input_iterator_tag的繼承關系，forward_iterator
??//和bidrectonal_iterator也會調用此實現函數。
? while (first != last) { ++first; ++n; }
}
template <class RandomAccessIterator, class Distance>
inline void __distance(RandomAccessIterator first, RandomAccessIterator last,
?????????????????????? Distance& n, random_access_iterator_tag)
{
? //random_access_iterator類型的實現
? n += last - first;
}
????????????????????????????????????????????????????????????????????????????? 2004.11.10
from: http://www.zahui.com/html/9/35875.htm