vector容器
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 <vector>
using std::vector;
vector是一個(gè)類模板（class template）。模板允許程序員編寫(xiě)單個(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<int> ivec; // ivec holds objects of type int
vector<Sales_item> Sales_vec; // holds Sales_items
和其他變量定義一樣，定義vector對(duì)象要指定類型和一個(gè)變量的列表。上面的第一個(gè)定義，類型是vector<int>，該類型即是含有若干int類型對(duì)象的vector，變量名為ivec。第二個(gè)定義的變量名是Sales_vec，它所保存的元素是Sales_item類型的對(duì)象。
vector不是一種數(shù)據(jù)類型，而只是一個(gè)類模板，可用來(lái)定義任意多種數(shù)據(jù)類型。vector類型的每一種都指定了其保存元素的類型。因此，vector<int>和vector <string>都是數(shù)據(jù)類型。
vector對(duì)象的定義和初始化
vector類定義了好幾種構(gòu)造函數(shù)，用來(lái)定義和初始化vector對(duì)象。下表3-4列出了這些構(gòu)造函數(shù)：
|
vector<T> v1;
|
vector保存類型為T的對(duì)象。默認(rèn)構(gòu)造函數(shù)v1為空。
|
|
vector<T> v2(v1);
|
v2是v1的一個(gè)副本。
|
|
vector<T> v3(n, i);
|
v3包含n個(gè)值為i的元素。
|
|
vector<T> v4(n);
|
v4含有值初始化的元素的n個(gè)副本。
|
創(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<int> ivec1; // ivec1 holds objects of type int
vector<int> ivec2(ivec1); // ok: copy elements of ivec1 into ivec2
vector<string> svec(ivec1); // error: svec holds strings, not ints
可以用元素個(gè)數(shù)和元素值對(duì)vector對(duì)象進(jìn)行初始化。構(gòu)造函數(shù)用元素個(gè)數(shù)來(lái)決定vector對(duì)象保存元素的個(gè)數(shù)，元素值指定每個(gè)元素的初始值：
vector<int> ivec4(10, -1); // 10 elements, each initialized to -1
vector<string> 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)?/span>vector增長(zhǎng)的效率高，在元素值已知的情況下，最好是動(dòng)態(tài)地添加元素。這種增長(zhǎng)方式不同于C語(yǔ)言中的內(nèi)置數(shù)據(jù)類型，也不同于大多數(shù)其他編程語(yǔ)言的數(shù)據(jù)類型。特別地，如果讀者習(xí)慣了C或Java的風(fēng)格，由于vector元素連續(xù)存儲(chǔ)，可能希望最好是預(yù)先分配合適的空間。但事實(shí)上，為了達(dá)到連續(xù)性，C++的做法恰好相反。
雖然可以對(duì)給定元素個(gè)數(shù)的vector對(duì)象預(yù)先分配內(nèi)存，但更有效的方法是先初始化一個(gè)空vector對(duì)象，然后再動(dòng)態(tài)地增加元素。
值初始化
如果沒(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<string> fvec(10); // 10 elements, each initialized to 0
如果向量保存類類型（如string）的元素，標(biāo)準(zhǔn)庫(kù)將用該類型的默認(rèn)構(gòu)造函數(shù)創(chuàng)建元素初始值：
vector<string> svec(10); // 10 elements, each an empty string
對(duì)于有自定義構(gòu)造函數(shù)但沒(méi)有默認(rèn)構(gòu)造函數(shù)的類，在初始化這種類型的Vector對(duì)象時(shí)，程序員就不能僅提供元素個(gè)數(shù)，還需要提供元素初始值。
元素類型可能是沒(méi)有定義任何構(gòu)造函數(shù)的類類型。這種情況下，標(biāo)準(zhǔn)庫(kù)仍產(chǎn)生一個(gè)帶初始值的對(duì)象，這個(gè)對(duì)象的每個(gè)成員進(jìn)行了值初始化。
vector的操作
vector標(biāo)準(zhǔn)庫(kù)提供許多類似于string對(duì)象的操作，下表列出了幾種最重要的vector操作。
|
v.empty()
|
如果v為空，則返回true,否則返回false。
|
|
v.size()
|
返回v中元素的個(gè)數(shù)。
|
|
v.push_back(t)
|
在v的末尾增加一個(gè)值為t的元素。
|
|
v[n]
|
返回v中位置為n的元素。
|
|
v1 = v2
|
把v1的元素替換為v2中元素的副本。
|
|
v1 == v2
|
如果v1與v2相等，則返回true。
|
|
!=, <, <=, >, >=
|
保持這些操作符慣有的含義。
|
vector對(duì)象的size
empty和size操作類似于string類型的相關(guān)操作。成員函數(shù)size返回相應(yīng)vector類定義的size_type的值。
使用size_type類型時(shí)，必須指出該類型是在哪里定義的。vector類型總是包括vector的元素類型：
vector<int>::size_type // ok
vector::size_type // error
向vector添加元素
push_back()操作接受一個(gè)元素值，并將它作為一個(gè)新的元素添加到vector對(duì)象的后面，也就是“插入（push）”到vector對(duì)象的“后面(back)”：
// read words from the standard input and store them as elements in a vector
string word;
vector<string> text; // empty vector
while (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ì)象，并將從輸入讀取的word值賦予該元素。當(dāng)循環(huán)結(jié)束時(shí)，text就包含了所有讀入的元素。
vector的下標(biāo)操作
vector中的對(duì)象是沒(méi)有命名的，可以按vector中對(duì)象的位置來(lái)訪問(wèn)它們。通常使用下標(biāo)操作符來(lái)獲取元素。vector的下標(biāo)操作類似于string類型的下標(biāo)操作。
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 zero
for (vector<int>::size_type ix = 0; ix != ivec.size(); ++ix)
ivec[ix] = 0;
和string類型的下標(biāo)操作符一樣，vector下標(biāo)操作的結(jié)果為左值，因此可以像循環(huán)體中所做的那樣實(shí)現(xiàn)寫(xiě)入。另外，和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í)行。
關(guān)鍵概念：安全的泛型編程
習(xí)慣于C或Java編程的C++程序員可能會(huì)覺(jué)得難以理解，for循環(huán)的判斷條件用!=而不是用<來(lái)測(cè)試vector下標(biāo)值是否越界。C程序員難以理解的還有，上例中沒(méi)有在for循環(huán)之前就調(diào)用size成員函數(shù)并保存其返回的值，而是在for語(yǔ)句頭中調(diào)用size成員函數(shù)。C++程序員習(xí)慣于優(yōu)先選用!=而不是<來(lái)編寫(xiě)循環(huán)判斷條件。
調(diào)用size成員函數(shù)而不保存它返回的值，在這個(gè)例子中同樣不是必需的，但這反映了一個(gè)良好的編程習(xí)慣。在C++中，有些數(shù)據(jù)結(jié)構(gòu)（如vector）可以動(dòng)態(tài)增長(zhǎng)。上例中循環(huán)僅需要讀取元素，而不需要增加新的元素。但是，循環(huán)可以容易地增加新元素，如果確實(shí)增加了新元素的話，那么測(cè)試已保存的size值作為循環(huán)的結(jié)束條件就會(huì)有問(wèn)題，因?yàn)闆](méi)有將新加入的元素計(jì)算在內(nèi)。所以我們傾向于在每次循環(huán)中測(cè)試size的當(dāng)前值，而不是在進(jìn)入循環(huán)時(shí)，存儲(chǔ)size值的副本。
我們知道，C++中有些函數(shù)可以聲明為內(nèi)聯(lián)（inline）函數(shù)。編譯器遇到內(nèi)聯(lián)函數(shù)時(shí)就會(huì)直接擴(kuò)展相應(yīng)代碼，而不是進(jìn)行實(shí)際的函數(shù)調(diào)用。像size這樣的小庫(kù)函數(shù)幾乎都定義為內(nèi)聯(lián)函數(shù)，所以每次循環(huán)過(guò)程中調(diào)用它的運(yùn)行時(shí)代價(jià)是比較小的。
下標(biāo)操作不添加元素
初學(xué)C++的程序員可能會(huì)認(rèn)為vector的下標(biāo)操作可以添加元素，其實(shí)不然：
vector<int> ivec; // empty vector
for (vector<int>::size_type ix = 0; ix != 10; ++ix)
ivec[ix] = ix; // disaster: ivec has no elements
上述程序試圖在ivec中插入10個(gè)新元素，元素值依次為0到9的整數(shù)。但是，這里ivec是空的vector對(duì)象，而且下標(biāo)只能用于獲取已存在的元素。
這個(gè)循環(huán)的正確寫(xiě)法應(yīng)該是：
for (vector<int>::size_type ix = 0; ix != 10; ++ix)
ivec.push_back(ix); // ok: adds new element with value ix
必須是已存在的元素才能用下標(biāo)操作符進(jìn)行索引。通過(guò)下標(biāo)操作進(jìn)行賦值時(shí)，不會(huì)添加任何元素。
警告：僅能對(duì)確知已存在的元素進(jìn)行下標(biāo)操作
對(duì)于下標(biāo)操作符([]操作符)的使用有一點(diǎn)非常重要，就是僅能提取確實(shí)已存在的元素，例如：
vector<int> ivec; // empty vector
cout << ivec[0]; // Error: ivec has no elements!
vector<int> ivec2(10); // vector with 10 elements
cout << ivec[10]; // Error: ivec has elements 0...9
試圖獲取不存在的元素必然產(chǎn)生運(yùn)行時(shí)錯(cuò)誤。和大多數(shù)同類錯(cuò)誤一樣，不能確保執(zhí)行過(guò)程可以捕捉到這類錯(cuò)誤，運(yùn)行程序的結(jié)果是不確定的。由于取不存在的元素的結(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)題。
vector迭代器
除了使用下標(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ù)為每一種標(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類型也這樣。
容器的iterator類型
每種容器類型都定義了自己的迭代器類型，如vector：
vector<int>::iterator iter;
這條語(yǔ)句定義了一個(gè)名為iter的變量，它的數(shù)據(jù)類型是由vector<int>定義的iterator類型。每個(gè)標(biāo)準(zhǔn)庫(kù)容器類型都定義了一個(gè)名為iterator的成員，這里的iterator與迭代器實(shí)際類型的含義相同。
不同的容器類定義了自己的iterator類型，用于訪問(wèn)容器內(nèi)的元素。換句話說(shuō)，每個(gè)容器定義了一種名為iterator的類型，而這種類型支持（概念上的）迭代器的各種行為。
begin和end操作
每種容器都定義了一對(duì)命名為begin和end的函數(shù)，用于返回迭代器。如果容器中有元素的話，由begin返回的迭代器指向第一個(gè)元素：
vector<int>::iterator iter = ivec.begin();
上述語(yǔ)句把iter初始化為由名為begin的vector操作返回的值。假設(shè)vector不空，初始化后，iter即指該元素為ivec[0]。
由end操作返回的迭代器指向vector的“末端元素的下一個(gè)”。通常稱為超出末端迭代器(off-the-end iterator)，表明它指向了一個(gè)不存在的元素。如果vector為空，begin返回的迭代器與end返回的迭代器相同。
由end操作返回的迭代器并不指向vector中任何實(shí)際的元素，相反，它只是起一個(gè)哨兵（sentinel）的作用，表示我們已處理完vector中所有元素。
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和ivec[0]就是指向同一個(gè)元素。上面這個(gè)語(yǔ)句的效果就是把這個(gè)元素的值賦為0。
迭代器使用自增操作符向前移動(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)行解引用或自增操作。
迭代器的其他運(yùn)算
另一對(duì)可執(zhí)行于迭代器的操作就是比較：用==或!=操作符來(lái)比較兩個(gè)迭代器，如果兩個(gè)迭代器對(duì)象指向同一個(gè)元素，則它們相等，否則就不相等。
迭代器應(yīng)用的程序示例
假設(shè)已聲明了一個(gè)vector<int>型的ivec變量，要把它所有元素值重置為0，可以用下標(biāo)操作來(lái)完成：
// reset all the elements in ivec to 0
for (vector<int>::size_type ix = 0; ix != ivec.size(); ++ix)
ivec[ix] = 0;
上述程序用for循環(huán)遍歷ivec的元素，for循環(huán)定義了一個(gè)索引ix，每循環(huán)迭代一次ix就自增1。for循環(huán)體將ivec的每個(gè)元素賦值為0。
更典型的做法是用迭代器來(lái)編寫(xiě)循環(huán)：
// equivalent loop using iterators to reset all the elements in ivec to 0
for (vector<int>::iterator iter = ivec.begin();
iter != ivec.end(); ++iter)
*iter = 0; // set element to which iter refers to 0
for循環(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)體內(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。
如果vector為空，程序是安全的。如果ivec為空，則begin返回的迭代器不指向任何元素，由于沒(méi)有元素，所以它不能指向任何元素——在這種情況下，從begin操作返回的迭代器與從end操作返回的迭代器的值相同，因此for語(yǔ)句中的測(cè)試條件立即失敗。
const_iterator
前面的程序用vector::iterator改變vector中的元素值。每種容器類型還定義了一種名為const_iterator的類型，該類型只能訪問(wèn)容器內(nèi)元素，但不能改變其值。
當(dāng)我們對(duì)普通iterator類型解引用時(shí)，得到對(duì)某個(gè)元素的非const引用。而如果我們對(duì)const_iterator類型解引用時(shí)，則可以得到一個(gè)指向const對(duì)象的引用，如同任何常量一樣，該對(duì)象不能進(jìn)行重寫(xiě)。
例如，如果text是vector<string>類型，程序員想要遍歷它，輸出每個(gè)元素,可以這樣編寫(xiě)程序：
// use const_iterator because we won't change the elements
for (vector<string>::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)行讀，不需要寫(xiě)，這里把iter定義為const_iterator類型。當(dāng)對(duì)const_iterator類型解引用時(shí)，返回的是一個(gè)const值。不允許用const_iterator進(jìn)行賦值：
for (vector<string>::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<int> nums(10); // nums is nonconst
const vector<int>::iterator cit = nums.begin();
*cit = 1; // ok: cit can change its underlying element
++cit; // error: can't change the value of cit
const vector<int> nines(10, 9); // cannot change elements in nines
// error: cit2 could change the element it refers to and nines is const
const vector<int>::iterator cit2 = nines.begin();
// ok: it can't change an element value, so it can be used with a const vector<int>
vector<int>::const_iterator it = nines.begin();
*it = 10; // error: *it is const
++it; // ok: it isn't const so we can change its value
// an iterator that cannot write elements
vector<int>::const_iterator
// an iterator whose value cannot change
const vector<int>::iterator
迭代器的算術(shù)操作
除了一次移動(dòng)迭代器的一個(gè)元素的增量操作符外，vector的迭代器（很少有其他標(biāo)準(zhǔn)庫(kù)容器迭代器）也支持其他的算術(shù)操作。這些操作稱為迭代器算術(shù)操作（iterator arithmetic），包括：
l iter + n
iter - n
可以對(duì)迭代器對(duì)象加上或減去一個(gè)整型值。這樣做將產(chǎn)生一個(gè)新的迭代器，其位置在iter所指元素之前（加）或之后（減）n個(gè)元素的位置。加或減之后的結(jié)果必須指向iter所指vector中的某個(gè)元素，或者是vector末端的后一個(gè)元素。加上或減去的值的類型應(yīng)該是vector的size_type或difference_type類型（參考下面的解釋）。
l iter1 - iter2
該表達(dá)式用來(lái)計(jì)算兩個(gè)迭代器對(duì)象的距離，該距離是名為difference_type的signed整數(shù)類型的值，這里的difference_type類型類似于size_type類型，也是由vector定義的。difference_type是signed類型，因?yàn)闇p法運(yùn)算可能產(chǎn)生負(fù)數(shù)的結(jié)果。該類型可以保證足夠大以存儲(chǔ)任何兩個(gè)迭代器對(duì)象間的距離。iter1與iter2兩者必須都指向同一vector中的元素，或者指向vector末端之后的下一個(gè)元素。
可以用迭代器算術(shù)操作來(lái)移動(dòng)迭代器直接指向某個(gè)元素，例如，下面語(yǔ)句直接定位于vector的中間元素：
vector<int>::iterator mid = vi.begin() + vi.size()/2;
上述代碼用來(lái)初始化mid，使其指向vi中最靠近正中間的元素。這種直接計(jì)算迭代器的方法，與用迭代器逐個(gè)元素自增操作到達(dá)中間元素的方法是等價(jià)的，但前者的效率要高得多。
任何改變vector長(zhǎng)度的操作都會(huì)使已存在的迭代器失效。例如，在調(diào)用push_back之后，就不能再信賴指向vector的迭代器的值了。