歡迎閱讀我的 【C++Primer】專欄

專欄簡介：本專欄主要面向C++初學者，解釋C++的一些基本概念和基礎語言特性，涉及C++標準庫的用法，面向對象特性，泛型特性高級用法。通過使用標準庫中定義的抽象設施，使你更加適應高級程序設計技術。希望對讀者有幫助！

3.4迭代器介紹

我們已經知道可以使用下標運算符來訪問string對象的字符或vector對象的元素,還有另外一種更通用的機制也可以實現同樣的目的,這就是迭代器(iterator)。除了vector之外,標準庫還定義了其他幾種容器。所有標準庫容器都可以使用逄代器,但是其中只有少數幾種才同時支持下標運算符。嚴格來說,string對象不屬于容器類型,但是string支持很多與容器類型類似的操作。vector支持下標運算符,這點和string一樣;string支持迭代器,這也和vector是一樣的。

類似于指針類型,迭代器也提供了對對象的間接訪問。就迭代器而言,其對象是容器中的元素或者string對象中的字符。使用迭代器可以訪問某個元素,迭代器也能從一個元素移動到另外一個元素。迭代器有有效和無效之分,這一點和指針差不多。有效的迭代器或者指向某個元素,或者指向容器中尾元素的下一位置;其他所有情況都屬于無效。

使用迭代器

和指針不一樣的是,獲取迭代器不是使用取地址符,有迭代器的類型同時擁有返回迭代器的成員。比如,這些類型都擁有名為begin和end的成員,其中begin成員負責返回指向第一個元素(或第一個字符)的迭代器。如有下述語句:

//由編譯器決定b和e的類型;
//b表示v的第一個元素,e表示y尾元素的下一位置
auto b=v.begin(),e=v.end();//b和e的類型相同

end成員則負責返回指向容器(或string對象)尾元素的下一位置(one past the end) 的迭代器,也就是說,該迭代器指示的是容器的一個本不存在的“尾后(off the end)“元
素。這樣的迭代器沒什么實際含義,僅是個標記而己,表示我們已經處理完了容器中的所有元素。end成員返回的迭代器常被稱作尾后迭代器(off-the-end iterator)或者簡稱為尾
迭代器(end iterator)。特殊情況下如果容器為空,則begin和end返回的是同一個迭代器。

如果容器為空,則begin和end返回的是同一個迭代囂,都是尾后迭代器

一般來說,我們不清楚(不在意)迭代器準確的類型到底是什么。在上面的例子中,使用auto關鍵字定義變量b和e(參見2.5.2節,第61頁),這兩個變量的類型也就是begin和end的返回值類型,第97頁將對相關內容做更詳細的介紹。

迭代器運算符

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

表3.6:標準容器迭代器的運算符

*iter	返回迭代器iter所指元素的引用
iter->mem	解引用ttez并獲取該元素的名為mem的成員,等價于(*iter).mem
++iter	令iter指示容器中的下一個元素
–iter	令iter指示容器中的上一個元素
iter1==iter2	判斷兩個迭代器是否相等(不相等),如果兩個迪代器指示的是同一個元
iter1 != iter2	素或者它們是同一個容器的尾后追代器,則相等;反之,不相等

和指針類似,也能通過解引用迭代器來獲取它所指示的元素,執行解引用的選代器必須合法并確實指示著樹個元素。試圖解引用一個非法迢代器或者尾后迭代器都是未被定義的行為。
舉個例子,程序利用下標運算符把string對象的第一個字母改為了大寫形式:

strings(“some string“);
if(s.begin()!s.end())〔//確保s非空auto it=s.begin();//it表示s的第一個字符*it= toupper(*it);//將當前字符改成大寫形式
)

本例首先檢查s是否為空,顯然通過檢查begin和end返回的結果是否一致就能做到這一點。如果返回的結果一樣,說明s為空;如果返回的結果不一樣,說明s不為空,此時s中至少包含一個字符。

我們在i內部,聲明了一個迭代器變量it并把begin返回的結果賦給它,這樣就得到了指示s中第一個字符的迭代器,接下來通過解引用運算符將第一個字符更改為大寫形式。和原來的程序一樣,輸出結果將是:

Some string

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

迭代器使用遞增(++)運算符來從一個元素移動到下一個元素。從邏輯上來說,迭代器的遞增和整數的遞增類似,整數的遞增是在整數值上“加1迭代器的遞增則是將迭代器“向前移動一個位置“。

因為end 返回的迭代器并不實際指示某個元素，所以不能對其進行遞增或解引用操作。

之前有一個程序把string對象中第一個單詞改寫為大寫形式,現在利用迭代器及其遞增運算符可以實現相同的功能:

//依次處理s的字符直至我們處理完全部字符或者遙到空白
for(auto it=s.begin();it!=s.end()&&!isspace(*it);++it)*it=toupper(*it);//將當前字符改成大寫形式

上面的循環遍歷s的字符直到遇到空白字符為止。

循環首先用s.begin的返回值來初始化it,意味著it指示的是s中的第一個字符(如果有的話)。條件部分檢查是否已到達s的尾部,如果尚未到達,則將it解引用的結果傳入isspace函數檢查是否遇到了空白。每次迭代的最后,執行++it令迭代器前移-個位置以訪問s的下一個字符。

循環體內部和上一個程序if語句內的最后一句話一樣,先解引用it,然后將結果傳入toupper函數得到該字母對應的大寫形式,再把這個大寫字母重新賦值給it所指示的字符。

迭代器類型

就像不知道string和vector的size_type成員到底是什么類型一樣,一般來說我們也不知道(其實是無須知道)迭代器的精確類型。而實際上,那些擁有迭代器的標準庫類型使用iterator和const iterator來表示迭代器的類型:

vector<int>::iterator it;//it能讀寫vector<itnt>的元素
string::iterator it2;//it2能讀寫string對象中的字符vector<int>::const_iterator it3;//it3只能讀元素,不能寫元素
string::const_iterator it4;//it4只能讀字符,不能寫字符

const_iterator和常量指針差不多,能讀取但不能修改它所指的元素值。相反,iterator的對象可讀可寫。如果vector對象或string對象是一個常量,只能使const iterator;如果vector對象或string對象不是常量, 那么既能使用iterator也能使用const_iterator。

begin和end運算符

begin和end返回的具體類型由對象是否是常量決定,如果對象是常量,begin和end返回const_iterator;如果對象不是常量,返回iterator:

vector<int> v;
const vector<int> cv;
auto it1 = v.begin();//it1的類型是vector<int>::tterator
auto it2 = cv.begin();//it2的類型是vector<int>::const_iterator

有時候這種默認的行為些非我們所要。如果對象只需讀操作而無須寫操作的話最好使用常量類型(比如const_iterator)。為了便于專門得到const_iterator類型的返回值,C++11新標準引入了兩個新函數,分別是cbegin：

auto it3 = v.cpegin();//it3的類型是vector<int>::const_tterator

類似于begin和end,上述兩個新函數也分別返回指示容器第一個元素或最后元素下一位置的迭代器。有所不同的是,不論vector對象(或string對象)本身是否是常量,返回值都是const_iterator。

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

解引用迭代器可獲得迭代器所指的對象,如果該對象的類型恰好是類,就有可能希望進一步訪問它的成員。例如,對于一個由字符串組成的vector對象來說,要想檢查其元素是否為空,令it是該vector對象的迭代器,只需檢查it所指宇符串是否為空就可以了,其代碼如下所示:

(*it).empty()

注意,(*it).empty()中的圓括號必不可少,該表達式的含義是先對it解引用,然后解引用的結果再執行點運算符。如果不加圓括號,點運算符將由it來執行,而非it解引用的結果:

(*it).empty() //解引用it,然后調用結果對象的empty成員
*it.empty()// 錯誤:試圖訪問it的名為empty的成員,但it是個選代器,
// 沒有empty成員

上面第二個表達式的含義是從名為it的對象中尋找其empty成員,顯然it是一個迭代器,它沒有哪個成員是叫empty的,所以第二個表達式將發生錯誤。

為了簡化上述表達式,C++語言定義了箭頭運算符(->)。箭頭運算符把解引用和成員訪問兩個操作結合在一起,也就是說,it->mem和(*it).mem表達的意思相同。

例如,假設用一個名為text的字符串向量存放文本文件中的數據,其中的元素或者是一句話或者是一個用于表示段落分隔的空字符串。如果要輸出text中第一段的內容,可以利用迭代器寫一個循環令其遍歷text,直到遇到穿字符串的元素為止:

//依次輸出text的每一行直至遇到第一個空白行為止
for(auto it=text.cbegin();it != text.cend()&& it->empty();++it)
cout<< *it << endl;

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

某些對vector對象的操作會使迭代器失效
雖然vector對象可以動態地增長,但是也會有些副作用。已知的一個限制是不能在范圍for循環中向vector對象添加元素。另外一個限制是任何一種可能改變vector對象容量的操作,比如push_back,都會使該vector對象的迭代器失效。

迭代器運算

迭代器的遞增運算令迭代器每次移動一個元素,所有的標準庫容器都有支持遞增運算的迭代器。類似的,也能用==和!=對任意標準庫類型的兩個有效迭代器進行比較。

string和vector的迭代器提供了更多額外的運算符,一方面可使得迭代器的每次移動跨過多個元素,另外也支持迭代器進行關系運算。所有這些運算被稱作迭代器運算
(iterator arithmetic,其細節由表3.7列出。

表3.7:vector和string迭代器支持的運算

iter + n	迭代器加上一個整數值仍得一個迪代器,迭代器指示的新位置與原米相比向前移動了若干個元素。結果迪代器或者指示容器內的一個元素,或者指示容器尾元素的下一位置
itter-n	迭代器湊去一個整數值仍得一個迪代器,迭代器指示的新位置與原來相比向后移動了若干個元素。結果迭代器或者指示容器內的一個元素,或者指示容器尾元素的下一位置
iter1+=n	迭代器加法的復合賦值語句,將iter1加n的結果賦給iter1
iter1-=n	迭代器減法的復合賦值語句,將iter1減n的結果賦給iter1
iter1-iter2	兩個迭代器相減的結果是它們之間的距離,也就是說,將運算符右側的迭代器向前移動差值個元素后將得到左側的迭代器。參與運算的兩個迭代器必須指向的是同一個容器中的元素或尾元素的下一個位置
>,>=,<,<=	迭代囂的關系運算符,如果某迭代器指向的容器位置在另一個迭代器所指位置之前,則說前者小于后者。參與運算的兩個迭代器必須指向的是同一個容器中的元素或者尾元素的下一位置

迭代器的算術運算

可以令迭代器和一個整數值相加〔或相減),其返回值是向前〔或向后)移動了若干個位置的迭代器。執行這樣的操作時,結果迭代器或者指示原vector對象(或string對象)內的一個元素,或者指示原vector對象(或string對象)尾元素的下一位置。

舉個例子,下面的代碼得到一個迭代器,它指向vector對象中間位置的元素:

//計算得到最接近vi中間元素的一個選代器
auto mid=vi.begin()+vi.size()/2;

如果vi有20個元素,vi.size()/2得10,此例中即令mid等于vi.begin(1+10)。已知下標從0開始,則迭代器所指的元素是vi[10],也就是從首元素開始向前相隔10個位置的那個元素。

對于string或vector的迭代器來說,除了判斷是否相等,還能使用關系運算符(<=、>、>=)對其進行比較。參與比較的兩個迭代器必須合法而且指向的是同一個容器的元素(或者尾元素的下一位置)。例如,假設it和mid是同一個vector對象的兩個迭代器,可以用下面的代碼來比較它們所指的位置孰前孰后:
if(it<mid)
//處理vi前半部分的元素

只要兩個迭代器指向的是同一個容器中的元素或者尾元素的下一位置,就能將其相減,所得結果是兩個迭代器的距離。所謂距離指的是右側的迭代器向前移動多少位置就能追上左側的迭代器,其類型是名為adifference_type的帶符號整型數。string和vector都定義了adifference_type,因為這個距離可正可負,所以difference_type是帶符號類型的。

使用迭代器運算

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

下面的程序使用迭代器完成了二分搜索:

//text必須是有序的
//beg和end表示我們搜索的范國
auto beg=text.begin(), end=text.end();
auto mid=text.begin()+(end-beg)/2; //初始狀態下的中間點
//當還有元素尚未格查并且我們還沒有找到sought時執行循環while(mid!=end&&*mid!=sought){if(sought<*mid)//我們要找的元素在前半部分嗎?end=mid;//如果是,調整搜索范圍使得忽略掉后半部分else//我們要找的元素在后半部分beg=mid+1;//在mid之后尋找mid=beg+(end-beg)/2;//新的中間點
}

程序的一開始定義了三個迭代器:beg指向搜索范圍內的第一個元素、end指向尾元素的下一位置、mid指向中間的那個元素。初始狀態下,搜索范圍是名為text的vector的全部范圍。

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

循環過程終止時,mid或者等于end或者指向要找的元素。如果mid等于end,說明text中沒有我們要找的元素。