C++ 頭文件系列(iterator)

簡介

該頭文件圍繞迭代器展開，定義了一系列與迭代器有關的概念，但最最最重要的一點就是----它和其它容器一起實現了C++容器的Iterator設計模式。

Iterators are a generalization of pointers that allow a C++ program to work with different data structures(containers) in a uniform manner.

上述文字摘自C++14標准草案，簡而言之，迭代器就是對指針的一層封裝，提供了統一的接口。

使用迭代器有很多好處：

• 訪問數據內容，同時不暴露其內部結構，降低耦合性。
• 支持multiple traversal（即同時有多個遍歷發生）。
• 提供統一的訪問接口和多態遍歷（該多態為靜態多態，發生在編譯期）。

詳細請見設計模式。

迭代器類別

迭代器主要有5類（[iterator-class]代指該類迭代器支持的操作集）：

這裡有兩點需要特別說明：

• multi-pass：它的意思是支持同時多次個遍歷 （這個概念有待驗證）。
• 解引用：該操作是有限制的，只能出現在賦值語句的左邊。

不難看出，這幾類迭代器有如下關系:

迭代器 與 指針

因為迭代器實際上是指針的抽象，很多功能概念都是從指針身上“扒”下來的，所以它的語義跟指針是一致的。

這意味著什麼呢？ 這意味著可以傳入指針作為迭代器， 因為指針上的操作集（遞增、遞減、算數運算等）是迭代器的超集，模版定義對迭代器所做出的操作要求放在指針上完全適用。

這在操縱內置數組的時候，可以省去不少麻煩(不用再去敲多余的代碼來生成iterators)：

int numbers[] = { 1,2,3,4 };
std::find(numbers, numbers + 4, 2); 

迭代器基礎設施

標准庫提供了以下4個方面的設施來幫助用戶使用iterator。

iterator_traits類

“traits”是特性的意思，所以“iterator_traits”是迭代器特性的意思。 從代碼角度看，這裡的traits就是types，因為這個類只包含了五個類型定義：

• difference_type
• value_type
• reference

• pointer

• iterator_category

因為algorithm在C++是單獨的一塊，是iterator將容器與算法溝通在一起。 也就是說，標准庫的算法只是通過迭代器來進行數據操作。 必然而然的，一些操作需要有對應的類型： 1) 例如，應用distance庫函數計算迭代器的距離，應該返回“距離”類型的值。 2) 例如，獲取迭代器指向的對象，應該返回“對象值”類型的對象。 等等...

所以，標准庫的算法需要我們定義這些類型，好讓它在應用算法的時候使用正確的類型。

需要注意的是，當迭代器為output iterators時，上面的4個類型可能被定義為void（可能對於output iterator來說，這四個類型都沒有多大意義，它支持的操作非常有限）。

iterator類

上面這個iterator_traits類取自某個庫的iterator實現，可以看到，默認的iterator_traits模版內的類型定義都取自迭代器中相應的類型，即_Iter迭代器類。 所以我們在定義自己的迭代器的時候，如果定義了這些類，就不用再顯示實例化iterator_traits模版了，它能自動提取出這些類型。

這時候就輪到我們的iterator類來大顯身手啦！ 用戶只要繼承這個base class並指定兩個參數，就可以獲得剩余的三個類型定義，因為它的定義是這樣的：

iterator category tags

對應迭代器類別，這裡也有5類標簽（tag），名稱為XXX_tag，XXX對應迭代器名稱。

這個標簽的作用主要是實現標簽派發功能，提供迭代器類型信息，從而讓C++庫算法可以選擇合適的、高效的操作來完成算法（可參見下一小節）。

iterator functions

頭文件還提供了一些方便的操縱迭代器的函數供用戶使用：

• advance（步進）
• distance（距離）
• next（下一個）
• prev（上一個）：只支持雙向迭代器以上（因為單向迭代器不支持“--”操作符）。

對於不同類型的迭代器，上述四個函數采用不同的方法進行計算，例如：

• 隨機訪問迭代器支持算數運算，故使用“+”和“-”操作符進行運算（若兩個迭代器分別為first和last，則計算他們之間的距離只需要last - first）。
• 單向迭代器只支持遞增運算，故使用++運算符進行運算（若兩個迭代器分別為first和last，計算他們之間的距離需要重復對first進行遞增，知道first == last）

迭代器適配器

類

標准庫包含了三種迭代器適配器：

1. Reverse iterator：這種迭代器對元素進行反向迭代。 注意，當從某個迭代器構造出reverse iterator時，新的迭代器不再指向先前的元素，而是指向前一個元素（按舊迭代器的順序），因為end iterator逆轉過來才是begin iterator。

1. Insert iterator：通過迭代器進行元素的插入時，操作略有不同。 指針通常是指向已有的內存，因此迭代器一般也只是對指向地址的元素進行賦值；而插入元素是需要先分配內存，再賦值。 為了能讓使用者像使用一般迭代器那樣進行元素的插入，標准庫提供了3種插入迭代器：

   • back_insert_iterator
   • front_insert_iterator
   • insert_iterator

2. Move iterator：移動迭代器會將內部的迭代器的操作返回值全部轉換成右值（rvalue）。

生成函數（Generators）

• back_inserter
• front_inserter
• inserter
• make_move_inserter

這些都是全局模版函數，利用類型推導幫助用戶構造上述的三種迭代器適配器。

流迭代器

輸入輸出一直是語言非常重要的部分，對於C++迭代器來說，操縱流（stream）中數據的輸入輸出的重要性毋庸置疑。 Stream Iterator則是針對stream的一套迭代器，包括istream，ostream，istreambuf 和 ostreambuf。

以下兩種是input iterator：

• istream_iterator
• istreambuf_iterator

以下兩種是output iterator：

• ostream_iterator
• ostreambuf_iterator