STL源碼剖析迭代器iterator的概念和 traits編程技法

iterator模式定義如下：提供一種方法，使之能夠依序巡訪某個聚合物(容器)所含的各個元素，而又無需暴露該聚合物的內部表述方式.
STL的中心思想在于：將數據容器(containers)和算法(algorithms)分開，彼此獨立設計，最后再以一帖膠著劑將它們撮合在一起。容器和算法的泛型化，從技術角度來看并不困難，C ++的class templates和 function templates可分別達成目標。如何設計出兩者之間的良好膠著劑，才是大難題。

?迭代器 (iterator ) 是一種 smart pointer

迭代器是一種行為類似指針的對象,而指針的各種行為中最常見也最重要的便是內容提領〈dereference)和成員訪問(member access) , 因此，迭代器最重要的編程工作就是對 operator* 和 operator-> 進行重載(overloading) 工作。關于這一點，C++標準程序庫有一個auto_ptr可供我們參考任何一本詳盡的C++ 語法書籍都應該談到auto_ptr 這是一個用來包裝原生指針 (native pointer)的對象，聲名狼藉的內存漏洞(memory leak)問題可藉此獲得解決. auto_ptr用法如下，和原生指針一模一樣：

函數第一行的意思是，以算式new動態配置一個初值為"jjhou” 的 string 對象，并將所得結果(一個原生指針)作為aUtoj>tr<Strin g > 對象的初值。注意, auto_ptr角括號內放的是“原生指針所指對象”的型別，而不是原生指針的型別.?

迭代器相應型別 ( associated types )

?我們以func ()為對外接口，卻把實際操作全部置于func_impl()之中.由于 func_impl ()是一個function template,—旦被調用，編譯器會自動進行template參數推導。于是導出型別T,順利解決了問題。
迭代器相應型別(associatedtypes)不只是 “迭代器所指對象的型別”?種而已。根據經驗，最常用的相應型別有五種，然而并非任何情況下任何一種都可利用上述的template參數推導機制來取得.我們需要更全面的解法。

Traits編程技法— STL源代碼門鑰

迭代器所指對象的型別，稱為該迭代器的value iy p e .上述的參數型別推導技巧雖然可用于value ty p e ,卻非全面可用：萬一 value typ e 必須用于函數的傳回值，就束手無策了，畢竟函數的*"template參數推導機制”推而導之的只是參數，無法推導函數的回返值型別。
我們需要其它方法。聲明內嵌型別似乎是個好主意，像這樣：

注意，func ( ) 的回返型別必須加上關鍵詞typename , 因為 T 是一個 template參數，在它被編譯器具現化之前，編譯器對T 一無所悉，換句話說，編譯器此時并不知道MyIter<T>: : value_type代表的是一個型別或是一個member function或是一個data m e m b e r . 關鍵詞 typename的用意在于告訴編譯器這是一個型別，如此才能順利通過編譯。

?大致的意義是：如果 class template擁有一個以上的 template參數，我們可以針對其中某個(或數個，但非全部)template參數進行特化工作。換句話說，我們可以在泛化設計中提供一個特化版本（也就是將泛化版本中的某些template參數賦予明確的指定）。

?多了一層間接性，先前使用一個T，現在使用了兩個T
但這除了多一層間接性，又帶來什么好處呢？好處是traits可以擁有特化版本。現在，我們令 iterator_traites 擁有一個 partial specializations 如下

?于是，原生指針i n t * 雖然不是一種class type,亦可通過traits取其 value type。這就解決了先前的問題。
但是請注意，針對 “指向常數對象的指針(pointeEo-snst) ”，下面這個式子得到什么結果
iterator_traits<const int*>::value_type
獲得的是const i n t 而非i n t . 這是我們期望的嗎？我們希望利用這種機制來聲明一個暫時變量，使其型別與迭代器的value type相同，而現在，聲明一個無法賦值 (因 c o n s t 之故)的暫時變量，沒什么用！因此，如果迭代器是個pointer-to-const,我們應該設法令其value t y p e 為一個non-const型別。沒問題，只要另外設計一個特化版本，就能解決這個問題：

?現在，不論面對的是迭代器My I t e r , 或是原生指針i n t * 或 const int*,都可以通過traits取出正確的(我們所期望的)value type。?
特性萃取機”角色，萃取各個迭代器的特性。這里所謂的迭代器特性，指的是迭代器的相應型別(associated types)。當然，若要這個 “特性萃取機” traits能夠有效運作，每一個迭代器必須遵循約定，自行以內嵌型別定義(nested typedef)的方式定義出相應型別(associated types) 。這是一個約定，誰不遵守這個約定，誰就不能兼容于S T L 這個大家庭。

?根據經驗，最常用到的迭代器相應型別有五種：value 1ype, difference iype, pointer, reference, iterator catagoly。如果你希望你所開發的容器能與STL水乳交融，一定要為你的容器的迭代器定義這五種相應型別。 “特性萃取機” traits會很 ?實地將原汁原味榨取出來：

?3.4.2 迭代器相應型別之二：difference type

difference type用來表示兩個迭代器之間的距離，因此它也可以用來表示一個容器的最大容量，因為對于連續空間的容器而言，頭尾之間的距離就是其最大容量.
如果一個泛型算法提供計數功能，例如STL的 count(), 其傳回值就必須使用迭代器的 difference type：

?針對相應型別difference type, traits的如下兩個(針對原生指針而寫的)特化版本，以 C++內建的ptrdiff_t (定義于<cstddef>頭文件)作為原生指針的 difference type：
ptrdiff_t是C/C++標準庫中定義的一個與機器相關的數據類型。ptrdiff_t類型變量通常用來保存兩個指針減法操作的結果

?3.4.3 迭代器相應型別之三：reference type

從 “迭代器所指之物的內容是否允許改變”的角度觀之，迭代器分為兩種：不允許改變 “所指對象之內容”者，稱為constant iterators,例如 const int*pic；允許改變"所指對象之內容”者，稱為 mutable iterators, 例如 int* pio當我們對一個 mutable iterators進行提領操作時，獲得的不應該是一個右值(rvalue), 應該是一個左值(lvalue), 因為右值不允許賦值操作(assignm ent), 左值才允許：

?在 C ++中，函數如果要傳回左值，都是以by reference的方式進行，所以當p 是個 mutable iterators時,如果其value type 是 T,那么 * p 的型別不應該是T, 應該是T&
將此道理擴充，如果p 是一個 constant iterators,其 value type 是 t ,那么 * p 的型別不應該是const T , 而應該是const T&。這里所討論的* p 的型別，即所謂的reference type

迭代器相應型別之四：pointer type

pointers和 references在 C + + 中有非常密切的關聯。如果 “傳回一個左值, 令它代表P 所指之物”是可能的，那么 “傳回一個左值，令它代表P 所指之物的地址”也一定可以。也就是說，我們能夠傳回一個pointer,指向迭代器所指之物。

item& 便是 Listlier 的 reference type ,而 item * 便是其 pointer type

?迭代器相應型別之五：iterator_category

最后一個（第五個）迭代器的相應型別會引發較大規模的寫代碼工程。在那之前，我必須先討論迭代器的分類
根據移動特性與施行操作，迭代器被分為五類：

?盡量針對圖3? 2中的某種迭代器提供一個明確定義，并針對更強化的某種迭代器提供另一種定義，這樣才能在不同情況下提供最大效率。在研究STL的過程中，每一分每一秒我們都要謹記在心，效率是個重要課題。假設有個算法可接受Forward Iterator,你以 Random Access Iterator喂給它, 它當然也會接受，因為一個Random Access Iterator必然是一個Forward Iterator（見圖3-2）。但是可用并不代表最佳！

以 advanced。為例

拿 advance （）來說（這是許多算法內部常用的一個函數），該函數有兩個參數，迭代器P 和數值n;函數內部將p 累進n 次（前進n 距離）。下面有三份定義，一份針對 Input Iterator, 一份針對 Bidirectional Iterator,另一份針對 Random Access Iteratoro倒是沒有針對Foiv/ardlterator而設計的版本，因為那和針對 Inputiterator而設計的版本完全~致。
設計考慮如下：如果 traits有能力萃取出迭代器的種類，我們便可利用這個 “迭代器類型”相應型別作為advanced 0 的第三參數。這個相應型別一定必須是一個class type,不能只是數值號碼類的東西，因為編譯器需仰賴它(一個型別)來進行重載決議(overloaded resolution) o 下面定義五個classes,代表五種迭代器類型：

?這些 classes只作為標記用，所以不需要任何成員。至于為什么運用繼承機制，稍后再解釋。現在重新設計— advance。 (由于只在內部使用，所以函數名稱加上特定的前導符)，并加上第三參數，使它們形成重載：

?注意上述語法，每個— advanced 的最后一個參數都只聲明型別，并未指定參數名稱，因為它純粹只是用來激活重載機制，函數之中根本不使用該參數。如果硬要加上參數名稱也可以，畫蛇添足罷了。
行進至此，還需要一個對外開放的上層控制接口，調用上述各個重載的_advance()。這一上層接口只需兩個參數，當它準備將工作轉給上述的 _advance ()時，才自行加上第三參數：迭代器類型。因此，這個上層函數必須有能力從它所獲得的迭代器中推導出其類型—— 這份工作自然是交給traits機制：

?任何一個迭代器，其類型永遠應該落在“該迭代器所隸屬之各種類型中，最強化的那個”。例如,int* 既是 Random Access Iterator，又是 Bidirectional Iterator, 同時也是Forward Iterator,而且也是Input Iterator,那么，其類型應該歸屬為 random_access_iterator_tag?
按說 advanced()既然可以接受各種類型的迭代器，就不應將其型別參數命名為Inputiterator。這其實是STL算法的一個命名規則：以算法所能接受之最低階迭代器類型，來為其迭代器型別參數命名。
消除 "單純傳遞調用的函數
以 class來定義迭代器的各種分類標簽，不僅可以促成重載機制的成功運作 (使編譯器得以正確執行重載決議，overloaded resolution), 另一個好處是，通過繼承，我們可以不必再寫 “單純只做傳遞調用”的函數(例如前述的 advance() Forwarditerator版 ) 。為什么能夠如此？考慮下面這個小例子，從其輸出結果可以看出端倪：

?以 d is ta n c e ()為例

關于 “迭代器類型標簽”的應用，以下再舉一例。distance ()也是常用的一個迭代器操作函數，用來計算兩個迭代器之間的距離。針對不同的迭代器類型，它可以有不同的計算方式，帶來不同的效率。整個設計模式和前述的advance ()如出一轍：

?distance使用 category動態適配 InputIterator和randomAccessiterator，分別調用與之匹配的__distance函數，但是這個 distance使用的時候 <> 需要指定最小的迭代器類型，來為迭代器進行命名

?注意,distanced可接受任何類型的迭代器；其 template型別參數之所以命名為 Inputiterator,是為了遵循STL算法的命名規則：以算法所能接受之最初級類型來為其迭代器型別參數命名.此外也請注意，由于迭代器類型之間存在著繼承關系， “傳遞調用(forwarding) ”的行為模式因此自然存在一一點我已在前一節討論過。換句話說，當客端調用distanced并使用Output Iterators或Forward Iterators 或 BidirectionaI Iterators 時，統統都會傳遞調用 Input Iterator 版
的那個_ distance ( ) 函數。

std::iterator 的保證

了符合規范，任何迭代器都應該提供五個內嵌相應型別，以利于traits萃取，否則便是自別于整個STL架構，可能無法與其它STL組件順利搭配。然而寫代碼難免掛一漏萬，誰也不能保證不會有粗心大意的時候。如果能夠將事情簡化，就好多了。STL提供了一個iterators class如下，如果每個新設計的迭代器都繼承自它，就可保證符合STL所需之規范：

?設計適當的相應型別(associated types) , 是迭代器的責任。設計適當的迭代器，則是容器的責任.唯容器本身，才知道該設計出怎樣的迭代器來遍歷自己，并執行迭代器該有的各種行為(前進、后退、取值、取用成員…) 。至于算法，完全可以獨立于容器和迭代器之外自行發展，只要設計時以迭代器為對外接口就行。

ite ra to r源代碼完整重列

SGI STL<stl_iterator.h>頭文件內與本章相關的程序代碼。該頭文件還有其它內容，是關于 iostream iterators, inserter iterators 以及 reverse iterators 的實現，將于第8 章討論。

?我并不是很懂為啥要再包裝一層

?SGI STL 的私房菜：__type_traits

traits編程技法很棒，適度彌補了 C++語言本身的不足。STL只對迭代器加以規范，制定出itera to r_ tra its這樣的東西。SG I把這種技法進一步擴大到迭代器以外的世界，于是有了所謂的_ type_tra-itso 雙底線前綴詞意指這是SGI STL內部所用的東西，不在STL標準規范之內?
iterator_ traits負責萃取迭代器的特性，—type_ traits則負責萃取型別(type)的特性
此處我們所關注的型別特性是指：這個型別是否具備non-trivial defaltctor ? 是否具備 non-trivial copy ctor ? 是否具備 non-trivial assignment operator?是否具備non-trivial dtor?如果答案是否定的，我們在對這個型別進行構造、析構、拷貝、賦值等操作時，就可以采用最有效率的措施(例如根本不調用身居高位，不謀實事的那些constructor, destructor), 而采用內存直接處理操作如 malloc. memcpy等等，獲得最高效率。這對于大規模而操作頻繁的容器, 有著顯著的效率提升4。