3.4迭代器介紹

我們已經知道可以使用下標運算符來訪問string對象的字符或vector對象的元素，還有另外一種更通用的機制也可以實現同樣的目的，這就是迭代器（iterator）。在第II部分中將要介紹，除了vector之外，標準庫還定義了其他幾種容器。所有標準庫容器都可以使用迭代器，但是其中只有少數幾種才同時支持下標運算符。嚴格來說，string對象不屬于容器類型，但是string支持很多與容器類型類似的操作。vector支持下標運算符，這點和string-樣；string支持迭代器，這也和vector是一樣的。類似于指針類型（參見2.3.2節，第47頁），迭代器也提供了對對象的間接訪問。就迭代器而言，其對象是容器中的元素或者string對象中的字符。使用迭代器可以訪問某個元素，迭代器也能從一個元素移動到另外一個元素。迭代器有有效和無效之分，這一點和指針差不多。有效的迭代器或者指向某個元素，或者指向容器中尾元素的下一位置：其他所有情況都屬于無效。

3.4.1使用迭代器

和指針不一樣的是，獲取迭代器不是使用取地址符，有迭代器的類型同時擁有返回迭代器的成員。比如，這些類型都擁有名為begin和end的成員，其中begin成員負責返回指向第一個元素（或第一個字符）的迭代器。如有下述語句：
/ / 由編譯器決定b 和 e 的類型；參見2.5.2節（第 61頁）
// b 表示v 的第一個元素，e 表示v 尾元素的下一位置
auto b = v.begin （） , e = v.end （） ; //b 和 e 的類型相同
end成員則負責返回指向容器（或string對象）“尾元素的下一位置（onepasttheend）”的迭代器，也就是說，該迭代器指示的是容器的一個本不存在的“尾后（offtheend）”元素。這樣的迭代器沒什么實際含義，僅是個標記而已，表示我們已經處理完了容器中的所有元素。end成員返舊]的迭代器常被稱作尾后迭代器（off^the-enditerator）或者簡稱為尾迭代器（enditerator特殊情況下如果容器為空，則begin和end返回的是同一個迭代器。
如果容器為空，則begin和 end返回的是同一個迭代器，都是尾后迭代器。?
一般來說，我們不清楚（不在意）迭代器準確的類型到底是什么。在上面的例子中，使用auto關鍵字定義變量b 和 e （參見2.5.2節，第 61頁），這兩個變量的類型也就是 begin 和 end的返回值類型，第 97頁將對相關內容做更詳細的介紹。

迭代器運算符

表3.6列舉了迭代器支持的一些運算。使用==和=來比較兩個合法的迭代器是否相等，如果兩個迭代器指向的元素相同或者都是同一個容器的尾后迭代器，則它們相等；否則就說這兩個迭代器不相等

iter->mem? 等效于（*item).mem
指針類似，也能通過解引用迭代器來獲取它所指示的元素，執行解引用的迭代器必須合法并確實指示著某個元素（參見2.3.2節，第48頁）。試圖解引用一個非法迭代器或者尾后迭代器都是未被定義的行為。舉個例子，3.2.3節（第84頁）中的程序利用下標運算符把string對象的第一個字母改為了大寫形式，下面利用迭代器實現同樣的功能：

本例和原來的程序一樣，首先檢查S 是否為空，顯然通過檢查begin和 end返回的結果是否一致就能做到這一點。如果返回的結果一樣，說明s為空；如果返回的結果不一樣，說明s不為空，此時s 中至少包含一個字符。我們在if內部，聲明了一個迭代器變量it并把begin返回的結果賦給它，這樣就得到了指示s 中第一個字符的迭代器，接下來通過解引用運算符將第一個字符更改為大寫形式。

將迭代器從一個元素移動到另外一個元素

迭代器使用遞增（++）運算符（參見1.4.1節，第11頁）來從一個元素移動到下一個元素。從邏輯上來說，迭代器的遞增和整數的遞增類似，整數的遞增是在整數值上“加1”,迭代器的遞增則是將迭代器“向前移動一個位置”。
因為end返回的迭代器并不實際指示某個元素，所以不能對其進行遞增或解引用的操作

和 3.2.3節（第 84頁）的那個程序一樣，上面的循環也是遍歷s 的字符直到遇到空白字符為止，只不過之前的程序用的是下標運算符，現在這個程序用的是迭代器。
循環首先用s .begin的返回值來初始化it,意味著it指示的是s 中的第一個字符（如果有的話）。條件部分檢查是否已到達s 的尾部，如果尚未到達，則將it解引用的結果傳入isspace函數檢查是否遇到了空白。每次迭代的最后,執行++it令迭代器平移一個位置以訪問s 的下一個字符。循環體內部和上一個程序if語句內的最后一句話一樣，先解引用it,然后將結果傳入 toupper函數得到該字母對應的大寫形式，再把這個大寫字母重新賦值給it所指示的字符。

for循環使用 != 進行比較，<這個支持的沒有!= 廣泛

迭代器類型

就像不知道string和vector的size_type成員（參見3.2.2節，第79頁）到底是什么類型一樣，一般來說我們也不知道（其實是無須知道）迭代器的精確類型。而實際上，
那些擁有迭代器的標準庫類型使用iterator和const_iterator來表示迭代器的類型：
iterator??參考鏈接

const_iterator和常量指針（參見2.4.2節，第56頁）差不多，能讀取但不能修改它所指的元素值。相反iterator的對象可讀可寫。如果vector對象或string對象是-個常量，只能使用const_iterator；如果vector對象或string對象不是常量，那么既能使用iterator也能使用const_iterator

begin和end運算符

begin和end返回的具體類型由對象是否是常量決定，如果對象是常量，begin和end返回const_iterator；如果對象不是常量，返回iterator：
vector<int>v;

有時候這種默認的行為并非我們所要。在6.2.3節(第191頁)中將會看到，如果對象只需讀操作而無須寫操作的話最好使用常量類型(比如const_iterator)。為了便于專門得到const_iterator類型的返回值,C++11新標準引入了兩個新函數，分別是cbegin和cend：
auto it3 = v . cbegin () ; // it3 的類型是 vector<int>: : const_iterator
類似于begin和end,上述兩個新函數也分別返回指示容器第一個元素或最后元素下一位置的迭代器。有所不同的是，不論vector對象(或string對象)本身是否是常量，返回值是const_iterator

結合解引用和成員訪問操作

解引用迭代器可獲得迭代器所指的對象，如果該對象的類型恰好是類，就有可能希望進一步訪問它的成員。例如，對于一個由字符串組成的vector對象來說，要想檢查其元素是否為空，令it是該vector對象的迭代器，只需檢查it所指字符串是否為空就可以了，其代碼如下所示：
(*it).empty()
注意，(*it).empty()中的圓括號必不可少，具體原因將在4.1.2節(第121頁)介紹，該表達式的含義是先對it解引用，然后解引用的結果再執行點運算符(參見1.5.2節，第20頁)。如果不加圓括號，點運算符將由it來執行，而非it解引用的結果：

上面第二個表達式的含義是從名為it的對象中尋找其em pty成員，顯然it是一個迭代器，它沒有哪個成員是叫empty的，所以第二個表達式將發生錯誤。?
為了簡化上述表達式，C++語言定義了箭頭運算符(->)箭頭運算符把解引用和成員訪問兩個操作結合在一起，也就是說，it->mem和表達的意思相同。例如，假設用一個名為text的字符串向量存放文本文件中的數據，其中的元素或者是一句話或者是一個用于表示段落分隔的空字符串。如果要輸出text中第一段的內容，可以利用迭代器寫一個循環令其遍歷text,直到遇到空字符串的元素為止：

我們首先初始化it令其指向text的第-個元素，循環重復執行直至處理完了text的所有元素或者發現某個元素為空。每次迭代時只要發現還有元素并且尚未遇到空元素，就輸出當前正在處理的元素。值得注意的是，因為循環從頭到尾只是讀取text的元素而未向其中寫值，所以使用了cbegin和cend來控制整個迭代過程。

某些對vector對象的操作會使迭代器失效

3.3.2節 (第 90頁)曾經介紹過，雖然vector對象可以動態地增長，但是也會有一些副作用。已知的一個限制是不能在范圍for循環中向vector對象添加元素。另外一個限制是任何一種可能改變vector對象容量的操作，比如push_back,都會使該vector對象的迭代器失效。9.3.6節（第315頁）將詳細解釋迭代器是如何失效的。迭代器是指end 和 cend尾后迭代器
謹記，但凡是使用了迭代器的循環體，都不要向迭代器所屬的容器添加元素

3.4.2迭代器運算

迭代器的遞增運算令迭代器每次移動一個元素，所有的標準庫容器都有支持遞增運算的迭代器。類似的，也能用==和=對任意標準庫類型的兩個有效迭代器（參見3.4節，第95頁）進行比較。string和vector的迭代器提供了更多額外的運算符，一方面可使得迭代器的每次移動跨過多個元素，另外也支持迭代器進行關系運算。所有這些運算被稱作迭代器運算>其細節由表3.7列出。

迭代器的算術運算

可以令迭代器和一個整數值相加（或相減），其返回值是向前（或向后）移動了若干個位置的迭代器。執行這樣的操作時，結果迭代器或者指示原vector對象（或 string 對象）內的一個元素，或者指示原vector對象（或 string對象）尾元素的下一位置。
舉個例子，下面的代碼得到一個迭代器，它指向某vector對象中間位置的元素：
auto mid = vi.begin() + vi.size() / 2;? ?/ / 計算得到最接近vi中間元素的一個迭代器
如果vi有20個元素，vi.size()/2得10,此例中即令mid等于vi.begin()+10。已知下標從0開始，則迭代器所指的元素是vi[10],也就是從首元素開始向前相隔10個位置的那個元素。
只要兩個迭代器指向的是同一個容器中的元素或者尾元素的下一位置，就能將其相減，所得結果是兩個迭代器的距離。所謂距離指的是右側的迭代器向前移動多少位置就能追上左側的迭代器，其類型是名為difference_type的帶符號整型數。string和vector都定義了difference_type,因為這個距離可正可負，所以difference_type是帶符號類型的。

使用迭代器運算

使用迭代器運算的一個經典算法是二分搜索。二分搜索從有序序列中尋找某個給定的值。二分搜索從序列中間的位置開始搜索，如果中間位置的元素正好就是要找的元素，搜索完成；如果不是，假如該元素小于要找的元素，則在序列的后半部分繼續搜素；假如該元素大于要找的元素，則在序列的前半部分繼續搜索。在縮小的范圍中計算一個新的中間元素并重復之前的過程，直至最終找到目標或者沒有元素可供繼續搜索。

程序的一開始定義了三個迭代器：beg指向搜索范圍內的第一個元素、end指向尾元素的下一位置、mid指向中間的那個元素。初始狀態下，搜索范圍是名為text的vector＜string＞的全部范圍。
循環部分先檢查搜索范圍是否為空，如果mid和end的當前值相等，說明已經找遍了所有元素。此時條件不滿足，循環終止。當搜索范圍不為空時，可知mid指向了某個元素，檢查該元素是否就是我們所要搜索的，如果是，也終止循環。
當進入到循環體內部后，程序通過某種規則移動beg或者end來縮小搜索的范圍。如果mid所指的元素比要找的元素sought大，可推測若text含有sought,則必出現在mid所指元素的前面。此時，可以忽略mid后面的元素不再查找，并把mid賦給end即可。另一種情況，如果*mid比soughtZJS＞則要找的元素必出現在mid所指兀素的后面。此時，通過令beg指向mid的下一個位置即可改變搜索范圍。因為已經驗證過mid不是我們要找的對象，所以在接下來的搜索中不必考慮它。
循環過程終止時，mid或者等于end或者指向要找的元素。如果mid等于end,說明text中沒有我們要找的元素。