向量容器與泛型算法

1、向量容器與泛型算法在數(shù)組生存期內(nèi)，數(shù)組的大小是不會(huì)改變的，向量容器則可以在運(yùn)行時(shí)動(dòng)態(tài)地增長(zhǎng)或縮小。向量是類模板，具有成員函數(shù)，例如可以使用size()方法動(dòng)態(tài)地獲得vector的當(dāng)前大小。面向?qū)ο蟮南蛄縱ector是使用最廣泛的一個(gè)容器。vector是同一種類型的對(duì)象的集合，每個(gè)對(duì)象都有一個(gè)對(duì)應(yīng)的整數(shù)索引值。和string對(duì)象一樣，標(biāo)準(zhǔn)庫(kù)負(fù)責(zé)管理存儲(chǔ)元素的相關(guān)內(nèi)存。我們把vector稱為容器，是因?yàn)樗梢园渌麑?duì)象。一個(gè)容器中的所有對(duì)象都必須是同一種類型的。使用vector之前，必須包含相應(yīng)的頭文件。#include using std:vector; vector是一個(gè)類模板（class

2、template）。模板允許程序員編寫單個(gè)類或函數(shù)定義，這個(gè)類和函數(shù)定義可用于不同的數(shù)據(jù)類型上。因此，我們可以定義保存string對(duì)象的vector，或保存int值的vector，又或是保存自定義的類類型對(duì)象（如Sales_item對(duì)象）的vector。聲明從類模板產(chǎn)生的某種類型的對(duì)象，需要提供附加信息，信息的種類取決于模板。以vector為例，必須說(shuō)明vector保存何種對(duì)象的類型，通過(guò)將類型放在類模板名稱后面的尖括號(hào)中來(lái)指定類型：vector ivec; / ivec holds objects of type intvector Sales_vec; / holds Sales_item

3、s和其他變量定義一樣，定義vector對(duì)象要指定類型和一個(gè)變量的列表。上面的第一個(gè)定義，類型是vector，該類型即是含有若干int類型對(duì)象的vector，變量名為ivec。第二個(gè)定義的變量名是Sales_vec，它所保存的元素是Sales_item類型的對(duì)象。vector對(duì)象的定義和初始化vector類定義了好幾種構(gòu)造函數(shù)，用來(lái)定義和初始化vector對(duì)象。下面列出了這些構(gòu)造函數(shù)：vector v1; vector保存類型為T的對(duì)象。默認(rèn)構(gòu)造函數(shù)v1為空。vector v2(v1);v2是v1的一個(gè)副本。vector v3(n, i);v3包含n個(gè)值為i的元素。vector v4(n);v4

4、含有值初始化的元素的n個(gè)副本。1. 創(chuàng)建確定個(gè)數(shù)的元素若要?jiǎng)?chuàng)建非空的vector對(duì)象，必須給出初始化元素的值。當(dāng)把一個(gè)vector對(duì)象復(fù)制到另一個(gè)vector對(duì)象時(shí)，新復(fù)制的vector中每一個(gè)元素都初始化為原vector中相應(yīng)元素的副本。但這兩個(gè)vector對(duì)象必須保存同一種元素類型:vector ivec1; / ivec1 holds objects of type intvector ivec2(ivec1); / ok: copy elements of ivec1 into ivec2vector svec(ivec1); / error: svec holds strings,

5、not ints可以用元素個(gè)數(shù)和元素值對(duì)vector對(duì)象進(jìn)行初始化。構(gòu)造函數(shù)用元素個(gè)數(shù)來(lái)決定vector對(duì)象保存元素的個(gè)數(shù)，元素值指定每個(gè)元素的初始值：vector ivec4(10, -1); / 10 elements, each initialized to -1vector svec(10, hi!); / 10 strings, each initialized to hi!關(guān)鍵概念：vector對(duì)象動(dòng)態(tài)增長(zhǎng) vector對(duì)象（以及其他標(biāo)準(zhǔn)庫(kù)容器對(duì)象）的重要屬性就在于可以在運(yùn)行時(shí)高效地添加元素。因?yàn)関ector增長(zhǎng)的效率高，在元素值已知的情況下，最好是動(dòng)態(tài)地添加元素。雖然可以對(duì)給定元

6、素個(gè)數(shù)的vector對(duì)象預(yù)先分配內(nèi)存，但更有效的方法是先初始化一個(gè)空vector對(duì)象，然后再動(dòng)態(tài)地增加元素（我們隨后將學(xué)習(xí)如何進(jìn)行這樣的操作）。2. 值初始化如果沒(méi)有給出元素的初始化式，那么標(biāo)準(zhǔn)庫(kù)將提供一個(gè)值初始化的（value initialized）元素初始化式。這個(gè)由庫(kù)生成的初始值用于初始化容器中的每個(gè)元素。而元素初始化式的值取決于存儲(chǔ)在vector中元素的數(shù)據(jù)類型。如果vector保存內(nèi)置類型（如int類型）的元素，那么標(biāo)準(zhǔn)庫(kù)將用0值創(chuàng)建元素初始化值：vector fvec(10); / 10 elements, each initialized to 0如果向量保存類類型（如stri

7、ng）的元素，標(biāo)準(zhǔn)庫(kù)將用該類型的默認(rèn)構(gòu)造函數(shù)創(chuàng)建元素初始值：vector svec(10); / 10 elements, each an empty string還有第三種可能性：元素類型可能是沒(méi)有定義任何構(gòu)造函數(shù)的類類型。這種情況下，標(biāo)準(zhǔn)庫(kù)仍產(chǎn)生一個(gè)帶初始值的對(duì)象，這個(gè)對(duì)象的每個(gè)成員進(jìn)行了值初始化。vector的操作v.empty()如果v為空，則返回true,否則返回false。v.size()返回v中元素的個(gè)數(shù)。v.push_back(t)在v的末尾增加一個(gè)值為t的元素。vn返回v中位置為n的元素。v1 = v2把v1的元素替換為v2中元素的副本。v1 = v2如果v1與v2相等，則返

8、回true。!=, , , =保持這些操作符慣有的含義。v.front()返回向量中的第一個(gè)對(duì)象v.back()返回向量中的最后一個(gè)對(duì)象1. vector對(duì)象的sizeempty和size操作類似于string類型的相關(guān)操作（節(jié)）。成員函數(shù)size返回相應(yīng)vector類定義的size_type的值。 使用size_type類型時(shí)，必須指出該類型是在哪里定義的。vector類型總是包括vector的元素類型：vector:size_type / okvector:size_type / error2. 向vector添加元素push_back()操作接受一個(gè)元素值，并將它作為一個(gè)新的元素添加到v

9、ector對(duì)象的后面，也就是“插入（push）”到vector對(duì)象的“后面(back)”：/ read words from the standard input and store them as elements in a vectorstring word;vector text; / empty vectorwhile (cin word) text.push_back(word); / append word to text該循環(huán)從標(biāo)準(zhǔn)輸入讀取一系列string對(duì)象，逐一追加到vector對(duì)象的后面。首先定義一個(gè)空的vector對(duì)象text。每循環(huán)一次就添加一個(gè)新元素到vector對(duì)

10、象，并將從輸入讀取的word值賦予該元素。當(dāng)循環(huán)結(jié)束時(shí)，text就包含了所有讀入的元素。3. vector的下標(biāo)操作vector中的對(duì)象是沒(méi)有命名的，可以按vector中對(duì)象的位置來(lái)訪問(wèn)它們。通常使用下標(biāo)操作符來(lái)獲取元素。vector的下標(biāo)操作類似于string類型的下標(biāo)操作(節(jié))。vector的下標(biāo)操作符接受一個(gè)值，并返回vector中該對(duì)應(yīng)位置的元素。vector元素的位置從0開(kāi)始。下例使用for循環(huán)把vector中的每個(gè)元素值都重置為0:/ reset the elements in the vector to zerofor (vector:size_type ix = 0; ix !

11、= ivec.size(); +ix) ivecix = 0;和string類型的下標(biāo)操作符一樣，vector下標(biāo)操作的結(jié)果為左值，因此可以像循環(huán)體中所做的那樣實(shí)現(xiàn)寫入。另外，和string對(duì)象的下標(biāo)操作類似，這里用size_type類型作為vector下標(biāo)的類型。 在上例中，即使ivec為空，for循環(huán)也會(huì)正確執(zhí)行。ivec為空則調(diào)用size返回0，并且for中的測(cè)試比較ix和0。第一次循環(huán)時(shí)，由于ix本身就是0，則條件測(cè)試失敗，for循環(huán)體一次也不執(zhí)行。4. 下標(biāo)操作不添加元素初學(xué)C+的程序員可能會(huì)認(rèn)為vector的下標(biāo)操作可以添加元素，其實(shí)不然：vector ivec; / empty

12、vectorfor (vector:size_type ix = 0; ix != 10; +ix) ivecix = ix; / disaster: ivec has no elements上述程序試圖在ivec中插入10個(gè)新元素，元素值依次為0到9的整數(shù)。但是，這里ivec是空的vector對(duì)象，而且下標(biāo)只能用于獲取已存在的元素。這個(gè)循環(huán)的正確寫法應(yīng)該是：for (vector:size_type ix = 0; ix != 10; +ix) ivec.push_back(ix); / ok: adds new element with value ix 必須是已存在的元素才能用下標(biāo)操作符

13、進(jìn)行索引。通過(guò)下標(biāo)操作進(jìn)行賦值時(shí)，不會(huì)添加任何元素。警告：僅能對(duì)確知已存在的元素進(jìn)行下標(biāo)操作 對(duì)于下標(biāo)操作符(操作符)的使用有一點(diǎn)非常重要，就是僅能提取確實(shí)已存在的元素，例如：vector ivec; / empty vectorcout ivec0; / Error: ivec has no elements!vector ivec2(10); / vector with 10 elementscout ivec10; / Error: ivec has elements 0.9試圖獲取不存在的元素必然產(chǎn)生運(yùn)行時(shí)錯(cuò)誤。和大多數(shù)同類錯(cuò)誤一樣，不能確保執(zhí)行過(guò)程可以捕捉到這類錯(cuò)誤，運(yùn)行程序的結(jié)果是

14、不確定的。由于取不存在的元素的結(jié)果是未定義的，因而不同的實(shí)現(xiàn)會(huì)導(dǎo)致不同的結(jié)果，但程序運(yùn)行時(shí)幾乎肯定會(huì)以某種有趣的方式失敗。本警告適用于任何使用下標(biāo)操作的時(shí)候，如string類型的下標(biāo)操作，以及將要簡(jiǎn)要介紹的內(nèi)置數(shù)組的下標(biāo)操作。不幸的是，試圖對(duì)不存在的元素進(jìn)行下標(biāo)操作是程序設(shè)計(jì)過(guò)程中經(jīng)常會(huì)犯的嚴(yán)重錯(cuò)誤。所謂的“緩沖區(qū)溢出”錯(cuò)誤就是對(duì)不存在的元素進(jìn)行下標(biāo)操作的結(jié)果。這樣的缺陷往往導(dǎo)致PC機(jī)和其他應(yīng)用中最常見(jiàn)的安全問(wèn)題。除了使用下標(biāo)來(lái)訪問(wèn)vector對(duì)象的元素外，標(biāo)準(zhǔn)庫(kù)還提供了另一種檢測(cè)元素的方法：使用迭代器（iterator）。迭代器是一種允許程序員檢查容器內(nèi)元素，并實(shí)現(xiàn)元素遍歷的數(shù)據(jù)類型。標(biāo)準(zhǔn)庫(kù)

15、為每一種標(biāo)準(zhǔn)容器（包括vector）定義了一種迭代器類型。迭代器類型提供了比下標(biāo)操作更一般化的方法：所有的標(biāo)準(zhǔn)庫(kù)容器都定義了相應(yīng)的迭代器類型，而只有少數(shù)的容器支持下標(biāo)操作。因?yàn)榈鲗?duì)所有的容器都適用，現(xiàn)代C+程序更傾向于使用迭代器而不是下標(biāo)操作訪問(wèn)容器元素，即使對(duì)支持下標(biāo)操作的vector類型也這樣。1. 容器的iterator類型每種容器類型都定義了自己的迭代器類型，如vector：vector:iterator iter;這條語(yǔ)句定義了一個(gè)名為iter的變量，它的數(shù)據(jù)類型是由vector定義的iterator類型。每個(gè)標(biāo)準(zhǔn)庫(kù)容器類型都定義了一個(gè)名為iterator的成員，這里的itera

16、tor與迭代器實(shí)際類型的含義相同。術(shù)語(yǔ)：迭代器和迭代器類型 程序員首次遇到有關(guān)迭代器的術(shù)語(yǔ)時(shí)可能會(huì)困惑不解，產(chǎn)生困惑的原因之一是由于本書中同一個(gè)術(shù)語(yǔ)iterator表示兩個(gè)不同的事物。一般性提及的是迭代器的概念；而特別提及的則是由容器定義的具體的iterator類型，如vector。重點(diǎn)要理解的是，定義了許多用作迭代器的類型，這些類型在概念上是相關(guān)的。若一種類型支持一組確定的行為（這些行為允許程序員遍歷容器內(nèi)的元素，并允許程序員訪問(wèn)這些元素值），我們就稱這種類型為迭代器。不同的容器類定義了自己的iterator類型，用于訪問(wèn)容器內(nèi)的元素。換句話說(shuō)，每個(gè)容器定義了一種名為iterator的類型，

17、而這種類型支持（概念上的）迭代器的各種行為。 2. begin和end操作每種容器都定義了一對(duì)命名為begin和end的函數(shù)，用于返回迭代器。如果容器中有元素的話，由begin返回的迭代器指向第一個(gè)元素：vector:iterator iter = ivec.begin();上述語(yǔ)句把iter初始化為由名為begin的vector操作返回的值。假設(shè)vector不空，初始化后，iter即指該元素為ivec0。由end操作返回的迭代器指向vector的“末端元素的下一個(gè)”。通常稱為超出末端迭代器(off-the-end iterator)，表明它指向了一個(gè)不存在的元素。如果vector為空，beg

18、in返回的迭代器與end返回的迭代器相同。 由end操作返回的迭代器并不指向vector中任何實(shí)際的元素，相反，它只是起一個(gè)哨兵（sentinel）的作用，表示我們已處理完vector中所有元素。3. vector迭代器的自增和解引用運(yùn)算迭代器類型定義了一些操作來(lái)獲取迭代器所指向的元素，并允許程序員將迭代器從一個(gè)元素移動(dòng)到另一個(gè)元素。迭代器類型可使用解引用操作符（*操作符）來(lái)訪問(wèn)迭代器所指向r 元素：*iter = 0;解引用操作符返回迭代器當(dāng)前所指向的元素。假設(shè)iter指向vector對(duì)象ivec的第一個(gè)元素，那么*iter和ivec0就是指向同一個(gè)元素。上面這個(gè)語(yǔ)句的效果就是把這個(gè)元素的值

19、賦為0。迭代器使用自增操作符（節(jié)）向前移動(dòng)迭代器指向容器中下一個(gè)元素。從邏輯上說(shuō)，迭代器的自增操作和int型對(duì)象的自增操作類似。對(duì)int對(duì)象來(lái)說(shuō)，操作結(jié)果就是把int型值“加1”，而對(duì)迭代器對(duì)象則是把容器中的迭代器“向前移動(dòng)一個(gè)位置”。因此，如果iter指向第一個(gè)元素，則+iter指向第二個(gè)元素。 由于end操作返回的迭代器不指向任何元素，因此不能對(duì)它進(jìn)行解引用或自增操作。4. 迭代器的其他運(yùn)算另一對(duì)可執(zhí)行于迭代器的操作就是比較：用=或!=操作符來(lái)比較兩個(gè)迭代器，如果兩個(gè)迭代器對(duì)象指向同一個(gè)元素，則它們相等，否則就不相等。5. 迭代器應(yīng)用的程序示例假設(shè)已聲明了一個(gè)vector型的ivec變量，

20、要把它所有元素值重置為0，可以用下標(biāo)操作來(lái)完成：/ reset all the elements in ivec to 0for (vector:size_type ix = 0; ix != ivec.size(); +ix) ivecix = 0;上述程序用for循環(huán)遍歷ivec的元素，for循環(huán)定義了一個(gè)索引ix，每循環(huán)迭代一次ix就自增1。for循環(huán)體將ivec的每個(gè)元素賦值為0。更典型的做法是用迭代器來(lái)編寫循環(huán)：/ equivalent loop using iterators to reset all the elements in ivec to 0for (vector:ite

21、rator iter = ivec.begin(); iter != ivec.end(); +iter) *iter = 0; / set element to which iter refers to 0for循環(huán)首先定義了iter，并將它初始化為指向ivec的第一個(gè)元素。for循環(huán)的條件測(cè)試iter是否與end操作返回的迭代器不等。每次迭代iter都自增1，這個(gè)for循環(huán)的效果是從ivec第一個(gè)元素開(kāi)始，順序處理vector中的每一元素。最后，iter將指向ivec中的最后一個(gè)元素，處理完最后一個(gè)元素后，iter再增加1，就會(huì)與end操作的返回值相等，在這種情況下，循環(huán)終止。for循環(huán)體

22、內(nèi)的語(yǔ)句用解引用操作符來(lái)訪問(wèn)當(dāng)前元素的值。和下標(biāo)操作符一樣，解引用操作符的返回值是一個(gè)左值，因此可以對(duì)它進(jìn)行賦值來(lái)改變它的值。上述循環(huán)的效果就是把ivec中所有元素都賦值為0。通過(guò)上述對(duì)代碼的詳細(xì)分析，可以看出這段程序與用下標(biāo)操作符的版本達(dá)到相同的操作效果：從vector的第一個(gè)元素開(kāi)始，把vector中每個(gè)元素都置為0。 本節(jié)給出的例子程序和 vector的下標(biāo)操作的程序一樣，如果vector為空，程序是安全的。如果ivec為空，則begin返回的迭代器不指向任何元素，由于沒(méi)有元素，所以它不能指向任何元素在這種情況下，從begin操作返回的迭代器與從end操作返回的迭代器的值相同，因此for

23、語(yǔ)句中的測(cè)試條件立即失敗。6. const_iterator前面的程序用vector:iterator改變vector中的元素值。每種容器類型還定義了一種名為const_iterator的類型，該類型只能訪問(wèn)容器內(nèi)元素，但不能改變其值。當(dāng)我們對(duì)普通iterator類型解引用時(shí)，得到對(duì)某個(gè)元素的非const引用（2.5節(jié)）。而如果我們對(duì)const_iterator類型解引用時(shí)，則可以得到一個(gè)指向const對(duì)象的引用（2.4節(jié)），如同任何常量一樣，該對(duì)象不能進(jìn)行重寫。例如，如果text是vector類型，程序員想要遍歷它，輸出每個(gè)元素,可以這樣編寫程序：/ use const_iterator b

24、ecause we wont change the elementsfor (vector:const_iterator iter = text.begin(); iter != text.end(); +iter) cout *iter endl; / print each element in text除了是從迭代器讀取元素值而不是對(duì)它進(jìn)行賦值之外，這個(gè)循環(huán)與前一個(gè)相似。由于這里只需要借助迭代器進(jìn)行讀，不需要寫，這里把iter定義為const_iterator類型。當(dāng)對(duì)const_iterator類型解引用時(shí)，返回的是一個(gè)const值。不允許用const_iterator進(jìn)行賦值：for

25、(vector:const_iterator iter = text.begin(); iter != text.end(); + iter) *iter = ; / error: *iter is const使用const_iterator類型時(shí)，我們可以得到一個(gè)迭代器，它自身的值可以改變，但不能用來(lái)改變其所指向的元素的值?？梢詫?duì)迭代器進(jìn)行自增以及使用解引用操作符來(lái)讀取值，但不能對(duì)該元素值賦值。不要把const_iterator對(duì)象與const的iterator對(duì)象混淆起來(lái)。聲明一個(gè)const迭代器時(shí)，必須初始化迭代器。一旦被初始化后，就不能改變它的值：vector nums(10); /

26、nums is nonconstconst vector:iterator cit = nums.begin();*cit = 1; / ok: cit can change its underlying element+cit; / error: cant change the value of citconst_iterator對(duì)象可以用于const vector或非const vector，因?yàn)椴荒芨膶懺刂?。const迭代器這種類型幾乎沒(méi)什么用處：一旦它被初始化后，只能用它來(lái)改寫其指向的元素，但不能使它指向任何其他元素：const vector nines(10, 9); / cann

27、ot change elements in nines/ error: cit2 could change the element it refers to and nines is constconst vector:iterator cit2 = nines.begin();/ ok: it cant change an element value, so it can be used with a const vectorvector:const_iterator it = nines.begin();*it = 10; / error: *it is const+it; / ok: it isnt const so we can change its va