向量容器與泛型算法

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

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

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

4、含有值初始化的元素的n個副本。1. 創(chuàng)建確定個數(shù)的元素若要創(chuàng)建非空的vector對象，必須給出初始化元素的值。當把一個vector對象復(fù)制到另一個vector對象時，新復(fù)制的vector中每一個元素都初始化為原vector中相應(yīng)元素的副本。但這兩個vector對象必須保存同一種元素類型: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可以用元素個數(shù)和元素值對vector對象進行初始化。構(gòu)造函數(shù)用元素個數(shù)來決定vector對象保存元素的個數(shù)，元素值指定每個元素的初始值：vector ivec4(10, -1); / 10 elements, each initialized to -1vector svec(10, hi!); / 10 strings, each initialized to hi!關(guān)鍵概念：vector對象動態(tài)增長 vector對象（以及其他標準庫容器對象）的重要屬性就在于可以在運行時高效地添加元素。因為vector增長的效率高，在元素值已知的情況下，最好是動態(tài)地添加元素。雖然可以對給定元

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

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

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

9、ector對象的后面，也就是“插入（push）”到vector對象的“后面(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)從標準輸入讀取一系列string對象，逐一追加到vector對象的后面。首先定義一個空的vector對象text。每循環(huán)一次就添加一個新元素到vector對

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

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

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

13、進行索引。通過下標操作進行賦值時，不會添加任何元素。警告：僅能對確知已存在的元素進行下標操作 對于下標操作符(操作符)的使用有一點非常重要，就是僅能提取確實已存在的元素，例如：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)生運行時錯誤。和大多數(shù)同類錯誤一樣，不能確保執(zhí)行過程可以捕捉到這類錯誤，運行程序的結(jié)果是

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

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

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

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

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

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

20、要把它所有元素值重置為0，可以用下標操作來完成：/ 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)定義了一個索引ix，每循環(huán)迭代一次ix就自增1。for循環(huán)體將ivec的每個元素賦值為0。更典型的做法是用迭代器來編寫循環(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的第一個元素。for循環(huán)的條件測試iter是否與end操作返回的迭代器不等。每次迭代iter都自增1，這個for循環(huán)的效果是從ivec第一個元素開始，順序處理vector中的每一元素。最后，iter將指向ivec中的最后一個元素，處理完最后一個元素后，iter再增加1，就會與end操作的返回值相等，在這種情況下，循環(huán)終止。for循環(huán)體

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

23、語句中的測試條件立即失敗。6. const_iterator前面的程序用vector:iterator改變vector中的元素值。每種容器類型還定義了一種名為const_iterator的類型，該類型只能訪問容器內(nèi)元素，但不能改變其值。當我們對普通iterator類型解引用時，得到對某個元素的非const引用（2.5節(jié)）。而如果我們對const_iterator類型解引用時，則可以得到一個指向const對象的引用（2.4節(jié)），如同任何常量一樣，該對象不能進行重寫。例如，如果text是vector類型，程序員想要遍歷它，輸出每個元素,可以這樣編寫程序：/ 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除了是從迭代器讀取元素值而不是對它進行賦值之外，這個循環(huán)與前一個相似。由于這里只需要借助迭代器進行讀，不需要寫，這里把iter定義為const_iterator類型。當對const_iterator類型解引用時，返回的是一個const值。不允許用const_iterator進行賦值：for

25、(vector:const_iterator iter = text.begin(); iter != text.end(); + iter) *iter = ; / error: *iter is const使用const_iterator類型時，我們可以得到一個迭代器，它自身的值可以改變，但不能用來改變其所指向的元素的值?？梢詫Φ鬟M行自增以及使用解引用操作符來讀取值，但不能對該元素值賦值。不要把const_iterator對象與const的iterator對象混淆起來。聲明一個const迭代器時，必須初始化迭代器。一旦被初始化后，就不能改變它的值：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對象可以用于const vector或非const vector，因為不能改寫元素值。const迭代器這種類型幾乎沒什么用處：一旦它被初始化后，只能用它來改寫其指向的元素，但不能使它指向任何其他元素：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