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

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

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

• 函數(shù)第一行的意思是，以算式new動(dòng)態(tài)配置一個(gè)初值為"jjhou” 的 string 對(duì)象，并將所得結(jié)果(一個(gè)原生指針)作為aUtoj>tr<Strin g > 對(duì)象的初值。注意, auto_ptr角括號(hào)內(nèi)放的是“原生指針?biāo)笇?duì)象”的型別，而不是原生指針的型別.?

迭代器相 應(yīng) 型 別 ( associated types )

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

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

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

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

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

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

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

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

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

?3.4.2 迭 代 器 相應(yīng)型別之二：difference type

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

• ?針對(duì)相應(yīng)型別difference type, traits的如下兩個(gè)(針對(duì)原生指針而寫的)特 化版本，以 C++內(nèi)建的ptrdiff_t (定義于<cstddef>頭文件)作為原生指針的 difference type：
• ptrdiff_t是C/C++標(biāo)準(zhǔn)庫(kù)中定義的一個(gè)與機(jī)器相關(guān)的數(shù)據(jù)類型。ptrdiff_t類型變量通常用來保存兩個(gè)指針減法操作的結(jié)果

?3.4.3 迭代器相應(yīng)型別之三：reference type

• 從 “迭代器所指之物的內(nèi)容是否允許改變”的角度觀之，迭代器分為兩種：不 允 許 改 變 “所指對(duì)象之內(nèi)容”者，稱為constant iterators,例 如 const int*pic； 允許改變"所指對(duì)象之內(nèi)容”者，稱 為 mutable iterators, 例 如 int* pio當(dāng)我們對(duì) 一 個(gè) mutable iterators進(jìn)行提領(lǐng)操作時(shí)，獲得的不應(yīng)該是一個(gè)右值(rvalue), 應(yīng)該是一個(gè)左值(lvalue), 因?yàn)橛抑挡辉试S賦值操作(assignm ent), 左值才允許：

• ?在 C ++中，函數(shù)如果要傳回左值，都是以by reference的方式進(jìn)行，所以當(dāng)p 是 個(gè) mutable iterators時(shí),如果其value type 是 T,那 么 * p 的型別不應(yīng)該是T, 應(yīng)該是T&
• 將此道理擴(kuò)充，如果p 是 一 個(gè) constant iterators,其 value type 是 t ,那 么 * p 的型別不應(yīng)該是const T , 而應(yīng)該是const T&。這里所討論的* p 的型 別，即所謂的reference type

迭代器相應(yīng)型別之四：pointer type

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

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

?迭代器 相 應(yīng) 型 別 之 五 ：iterator_category

• 最后一個(gè)（第五個(gè)）迭代器的相應(yīng)型別會(huì)引發(fā)較大規(guī)模的寫代碼工程。在那之前，我必須先討論迭代器的分類
• 根據(jù)移動(dòng)特性與施行操作，迭代器被分為五類：

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

以 advanced。 為例

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

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

?

• ?注意上述語法，每個(gè)— advanced 的最后一個(gè)參數(shù)都只聲明型別，并未指定 參數(shù)名稱，因?yàn)樗兇庵皇怯脕砑せ钪剌d機(jī)制，函數(shù)之中根本不使用該參數(shù)。如果硬要加上參數(shù)名稱也可以，畫蛇添足罷了。
• 行進(jìn)至此，還需要一個(gè)對(duì)外開放的上層控制接口，調(diào)用上述各個(gè)重載的_advance()。這一上層接口只需兩個(gè)參數(shù)，當(dāng)它準(zhǔn)備將工作轉(zhuǎn)給上述的 _advance ()時(shí)，才自行加上第三參數(shù)：迭代器類型。因此，這個(gè)上層函數(shù)必須有 能力從它所獲得的迭代器中推導(dǎo)出其類型—— 這份工作自然是交給traits機(jī)制：

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

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

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

• ?distance使用 category動(dòng)態(tài)適配 InputIterator和randomAccessiterator，分別調(diào)用與之匹配的__distance函數(shù)，但是這個(gè) distance使用的時(shí)候 <> 需要指定最小的迭代器類型，來為迭代器進(jìn)行命名

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

std::iterator 的保證

• 了符合規(guī)范，任何迭代器都應(yīng)該提供五個(gè)內(nèi)嵌相應(yīng)型別，以利于traits萃取，否則便是自別于整個(gè)STL架構(gòu)，可能無法與其它STL組件順利搭配。然而寫代碼難免掛一漏萬，誰也不能保證不會(huì)有粗心大意的時(shí)候。如果能夠?qū)⑹虑楹?jiǎn)化，就好多了。STL提供了一個(gè)iterators class如下，如果每個(gè)新設(shè)計(jì)的迭代器都 繼承自它，就可保證符合STL所需之規(guī)范：

• ?設(shè)計(jì)適當(dāng)?shù)南鄳?yīng)型別(associated types) , 是迭代器的責(zé)任。設(shè)計(jì)適當(dāng)?shù)牡?器，則是容器的責(zé)任.唯容器本身，才知道該設(shè)計(jì)出怎樣的迭代器來遍歷自己，并執(zhí)行迭代器該有的各種行為(前進(jìn)、后退、取值、取用成員…) 。至于算法，完全可以獨(dú)立于容器和迭代器之外自行發(fā)展，只要設(shè)計(jì)時(shí)以迭代器為對(duì)外接口就行。

ite ra to r源代碼完整重列

• SGI STL<stl_iterator.h>頭文件內(nèi)與本章相關(guān)的程序代碼。該頭文件還有其它內(nèi)容，是關(guān)于 iostream iterators, inserter iterators 以及 reverse iterators 的實(shí)現(xiàn)，將于第8 章討論。

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

?SGI STL 的 私 房 菜 ：__type_traits

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

• ?我們希望上述式子響應(yīng)我們“真”或 “假”(以便我們決定采取什么策略)，但其結(jié)果不應(yīng)該只是個(gè)bool值，應(yīng)該是個(gè)有著真/假性質(zhì)的“對(duì)象”，因?yàn)槲覀?希望利用其響應(yīng)結(jié)果來進(jìn)行參數(shù)推導(dǎo)，而編譯器只有面對(duì)Class object形式的參數(shù), 才會(huì)做參數(shù)推導(dǎo)。為此，上述式子應(yīng)該傳回這樣的東西：

• ?為了達(dá)成上述五個(gè)式子，— type_traits內(nèi)必須定義一些typedefs,其值不是 _ true_type 就是 _ false_type下面是 SGI 的做法：

POD

?

例子

?

?

?

?

?

?

?

?

總結(jié)

以上是生活随笔為你收集整理的STL源码剖析 迭代器iterator的概念 和 traits编程技法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。