vector容器
vector是同一種類型的對象的集合，每個(gè)對象都有一個(gè)對應(yīng)的整數(shù)索引值。和string對象一樣，標(biāo)準(zhǔn)庫負(fù)責(zé)管理存儲(chǔ)元素的相關(guān)內(nèi)存。我們把vector稱為容器，是因?yàn)樗梢园渌麑ο蟆Ｒ粋€(gè)容器中的所有對象都必須是同一種類型的。
使用vector之前，必須包含相應(yīng)的頭文件。
#include <vector>
using std::vector;
vector是一個(gè)類模板（class template）。模板允許程序員編寫單個(gè)類或函數(shù)定義，這個(gè)類和函數(shù)定義可用于不同的數(shù)據(jù)類型上。因此，我們可以定義保存string對象的vector，或保存int值的vector，又或是保存自定義的類類型對象（如Sales_item對象）的vector。
聲明從類模板產(chǎn)生的某種類型的對象，需要提供附加信息，信息的種類取決于模板。以vector為例，必須說明vector保存何種對象的類型，通過將類型放在類模板名稱后面的尖括號中來指定類型：
vector<int> ivec; // ivec holds objects of type int
vector<Sales_item> Sales_vec; // holds Sales_items
和其他變量定義一樣，定義vector對象要指定類型和一個(gè)變量的列表。上面的第一個(gè)定義，類型是vector<int>，該類型即是含有若干int類型對象的vector，變量名為ivec。第二個(gè)定義的變量名是Sales_vec，它所保存的元素是Sales_item類型的對象。
vector不是一種數(shù)據(jù)類型，而只是一個(gè)類模板，可用來定義任意多種數(shù)據(jù)類型。vector類型的每一種都指定了其保存元素的類型。因此，vector<int>和vector <string>都是數(shù)據(jù)類型。
vector對象的定義和初始化
vector類定義了好幾種構(gòu)造函數(shù)，用來定義和初始化vector對象。下表3-4列出了這些構(gòu)造函數(shù)：
|
vector<T> v1;
|
vector保存類型為T的對象。默認(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對象，必須給出初始化元素的值。當(dāng)把一個(gè)vector對象復(fù)制到另一個(gè)vector對象時(shí)，新復(fù)制的vector中每一個(gè)元素都初始化為原vector中相應(yīng)元素的副本。但這兩個(gè)vector對象必須保存同一種元素類型:
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ù)和元素值對vector對象進(jìn)行初始化。構(gòu)造函數(shù)用元素個(gè)數(shù)來決定vector對象保存元素的個(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對象動(dòng)態(tài)增長
vector對象（以及其他標(biāo)準(zhǔn)庫容器對象）的重要屬性就在于可以在運(yùn)行時(shí)高效地添加元素。因?yàn)?/span>vector增長的效率高，在元素值已知的情況下，最好是動(dòng)態(tài)地添加元素。這種增長方式不同于C語言中的內(nèi)置數(shù)據(jù)類型，也不同于大多數(shù)其他編程語言的數(shù)據(jù)類型。特別地，如果讀者習(xí)慣了C或Java的風(fēng)格，由于vector元素連續(xù)存儲(chǔ)，可能希望最好是預(yù)先分配合適的空間。但事實(shí)上，為了達(dá)到連續(xù)性，C++的做法恰好相反。
雖然可以對給定元素個(gè)數(shù)的vector對象預(yù)先分配內(nèi)存，但更有效的方法是先初始化一個(gè)空vector對象，然后再動(dòng)態(tài)地增加元素。
值初始化
如果沒有給出元素的初始化式，那么標(biāo)準(zhǔn)庫將提供一個(gè)值初始化的（value initialized）元素初始化式。這個(gè)由庫生成的初始值用于初始化容器中的每個(gè)元素。而元素初始化式的值取決于存儲(chǔ)在vector中元素的數(shù)據(jù)類型。
如果vector保存內(nèi)置類型（如int類型）的元素，那么標(biāo)準(zhǔn)庫將用0值創(chuàng)建元素初始化值：
vector<string> fvec(10); // 10 elements, each initialized to 0
如果向量保存類類型（如string）的元素，標(biāo)準(zhǔn)庫將用該類型的默認(rèn)構(gòu)造函數(shù)創(chuàng)建元素初始值：
vector<string> svec(10); // 10 elements, each an empty string
對于有自定義構(gòu)造函數(shù)但沒有默認(rèn)構(gòu)造函數(shù)的類，在初始化這種類型的Vector對象時(shí)，程序員就不能僅提供元素個(gè)數(shù)，還需要提供元素初始值。
元素類型可能是沒有定義任何構(gòu)造函數(shù)的類類型。這種情況下，標(biāo)準(zhǔn)庫仍產(chǎn)生一個(gè)帶初始值的對象，這個(gè)對象的每個(gè)成員進(jìn)行了值初始化。
vector的操作
vector標(biāo)準(zhǔn)庫提供許多類似于string對象的操作，下表列出了幾種最重要的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對象的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對象的后面，也就是“插入（push）”到vector對象的“后面(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對象，逐一追加到vector對象的后面。首先定義一個(gè)空的vector對象text。每循環(huán)一次就添加一個(gè)新元素到vector對象，并將從輸入讀取的word值賦予該元素。當(dāng)循環(huán)結(jié)束時(shí)，text就包含了所有讀入的元素。
vector的下標(biāo)操作
vector中的對象是沒有命名的，可以按vector中對象的位置來訪問它們。通常使用下標(biāo)操作符來獲取元素。vector的下標(biāo)操作類似于string類型的下標(biāo)操作。
vector的下標(biāo)操作符接受一個(gè)值，并返回vector中該對應(yīng)位置的元素。vector元素的位置從0開始。下例使用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)寫入。另外，和string對象的下標(biāo)操作類似，這里用size_type類型作為vector下標(biāo)的類型。
在上例中，即使ivec為空，for循環(huán)也會(huì)正確執(zhí)行。ivec為空則調(diào)用size返回0，并且for中的測試比較ix和0。第一次循環(huán)時(shí)，由于ix本身就是0，則條件測試失敗，for循環(huán)體一次也不執(zhí)行。
關(guān)鍵概念：安全的泛型編程
習(xí)慣于C或Java編程的C++程序員可能會(huì)覺得難以理解，for循環(huán)的判斷條件用!=而不是用<來測試vector下標(biāo)值是否越界。C程序員難以理解的還有，上例中沒有在for循環(huán)之前就調(diào)用size成員函數(shù)并保存其返回的值，而是在for語句頭中調(diào)用size成員函數(shù)。C++程序員習(xí)慣于優(yōu)先選用!=而不是<來編寫循環(huán)判斷條件。
調(diào)用size成員函數(shù)而不保存它返回的值，在這個(gè)例子中同樣不是必需的，但這反映了一個(gè)良好的編程習(xí)慣。在C++中，有些數(shù)據(jù)結(jié)構(gòu)（如vector）可以動(dòng)態(tài)增長。上例中循環(huán)僅需要讀取元素，而不需要增加新的元素。但是，循環(huán)可以容易地增加新元素，如果確實(shí)增加了新元素的話，那么測試已保存的size值作為循環(huán)的結(jié)束條件就會(huì)有問題，因?yàn)闆]有將新加入的元素計(jì)算在內(nèi)。所以我們傾向于在每次循環(huán)中測試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這樣的小庫函數(shù)幾乎都定義為內(nèi)聯(lián)函數(shù)，所以每次循環(huán)過程中調(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對象，而且下標(biāo)只能用于獲取已存在的元素。
這個(gè)循環(huán)的正確寫法應(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)行索引。通過下標(biāo)操作進(jìn)行賦值時(shí)，不會(huì)添加任何元素。
警告：僅能對確知已存在的元素進(jìn)行下標(biāo)操作
對于下標(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í)行過程可以捕捉到這類錯(cuò)誤，運(yùn)行程序的結(jié)果是不確定的。由于取不存在的元素的結(jié)果是未定義的，因而不同的實(shí)現(xiàn)會(huì)導(dǎo)致不同的結(jié)果，但程序運(yùn)行時(shí)幾乎肯定會(huì)以某種有趣的方式失敗。
本警告適用于任何使用下標(biāo)操作的時(shí)候，如string類型的下標(biāo)操作，以及將要簡要介紹的內(nèi)置數(shù)組的下標(biāo)操作。
不幸的是，試圖對不存在的元素進(jìn)行下標(biāo)操作是程序設(shè)計(jì)過程中經(jīng)常會(huì)犯的嚴(yán)重錯(cuò)誤。所謂的“緩沖區(qū)溢出”錯(cuò)誤就是對不存在的元素進(jìn)行下標(biāo)操作的結(jié)果。這樣的缺陷往往導(dǎo)致PC機(jī)和其他應(yīng)用中最常見的安全問題。
vector迭代器
除了使用下標(biāo)來訪問vector對象的元素外，標(biāo)準(zhǔn)庫還提供了另一種檢測元素的方法：使用迭代器（iterator）。迭代器是一種允許程序員檢查容器內(nèi)元素，并實(shí)現(xiàn)元素遍歷的數(shù)據(jù)類型。
標(biāo)準(zhǔn)庫為每一種標(biāo)準(zhǔn)容器（包括vector）定義了一種迭代器類型。迭代器類型提供了比下標(biāo)操作更一般化的方法：所有的標(biāo)準(zhǔn)庫容器都定義了相應(yīng)的迭代器類型，而只有少數(shù)的容器支持下標(biāo)操作。因?yàn)榈鲗λ械娜萜鞫歼m用，現(xiàn)代C++程序更傾向于使用迭代器而不是下標(biāo)操作訪問容器元素，即使對支持下標(biāo)操作的vector類型也這樣。
容器的iterator類型
每種容器類型都定義了自己的迭代器類型，如vector：
vector<int>::iterator iter;
這條語句定義了一個(gè)名為iter的變量，它的數(shù)據(jù)類型是由vector<int>定義的iterator類型。每個(gè)標(biāo)準(zhǔn)庫容器類型都定義了一個(gè)名為iterator的成員，這里的iterator與迭代器實(shí)際類型的含義相同。
不同的容器類定義了自己的iterator類型，用于訪問容器內(nèi)的元素。換句話說，每個(gè)容器定義了一種名為iterator的類型，而這種類型支持（概念上的）迭代器的各種行為。
begin和end操作
每種容器都定義了一對命名為begin和end的函數(shù)，用于返回迭代器。如果容器中有元素的話，由begin返回的迭代器指向第一個(gè)元素：
vector<int>::iterator iter = ivec.begin();
上述語句把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)算
迭代器類型定義了一些操作來獲取迭代器所指向的元素，并允許程序員將迭代器從一個(gè)元素移動(dòng)到另一個(gè)元素。
迭代器類型可使用解引用操作符（*操作符）來訪問迭代器所指向r 元素：
*iter = 0;
解引用操作符返回迭代器當(dāng)前所指向的元素。假設(shè)iter指向vector對象ivec的第一個(gè)元素，那么*iter和ivec[0]就是指向同一個(gè)元素。上面這個(gè)語句的效果就是把這個(gè)元素的值賦為0。
迭代器使用自增操作符向前移動(dòng)迭代器指向容器中下一個(gè)元素。從邏輯上說，迭代器的自增操作和int型對象的自增操作類似。對int對象來說，操作結(jié)果就是把int型值“加1”，而對迭代器對象則是把容器中的迭代器“向前移動(dòng)一個(gè)位置”。因此，如果iter指向第一個(gè)元素，則++iter指向第二個(gè)元素。
由于end操作返回的迭代器不指向任何元素，因此不能對它進(jìn)行解引用或自增操作。
迭代器的其他運(yùn)算
另一對可執(zhí)行于迭代器的操作就是比較：用==或!=操作符來比較兩個(gè)迭代器，如果兩個(gè)迭代器對象指向同一個(gè)元素，則它們相等，否則就不相等。
迭代器應(yīng)用的程序示例
假設(shè)已聲明了一個(gè)vector<int>型的ivec變量，要把它所有元素值重置為0，可以用下標(biāo)操作來完成：
// 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。
更典型的做法是用迭代器來編寫循環(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)的條件測試iter是否與end操作返回的迭代器不等。每次迭代iter都自增1，這個(gè)for循環(huán)的效果是從ivec第一個(gè)元素開始，順序處理vector中的每一元素。最后，iter將指向ivec中的最后一個(gè)元素，處理完最后一個(gè)元素后，iter再增加1，就會(huì)與end操作的返回值相等，在這種情況下，循環(huán)終止。
for循環(huán)體內(nèi)的語句用解引用操作符來訪問當(dāng)前元素的值。和下標(biāo)操作符一樣，解引用操作符的返回值是一個(gè)左值，因此可以對它進(jìn)行賦值來改變它的值。上述循環(huán)的效果就是把ivec中所有元素都賦值為0。
通過上述對代碼的詳細(xì)分析，可以看出這段程序與用下標(biāo)操作符的版本達(dá)到相同的操作效果：從vector的第一個(gè)元素開始，把vector中每個(gè)元素都置為0。
如果vector為空，程序是安全的。如果ivec為空，則begin返回的迭代器不指向任何元素，由于沒有元素，所以它不能指向任何元素——在這種情況下，從begin操作返回的迭代器與從end操作返回的迭代器的值相同，因此for語句中的測試條件立即失敗。
const_iterator
前面的程序用vector::iterator改變vector中的元素值。每種容器類型還定義了一種名為const_iterator的類型，該類型只能訪問容器內(nèi)元素，但不能改變其值。
當(dāng)我們對普通iterator類型解引用時(shí)，得到對某個(gè)元素的非const引用。而如果我們對const_iterator類型解引用時(shí)，則可以得到一個(gè)指向const對象的引用，如同任何常量一樣，該對象不能進(jìn)行重寫。
例如，如果text是vector<string>類型，程序員想要遍歷它，輸出每個(gè)元素,可以這樣編寫程序：
// 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
除了是從迭代器讀取元素值而不是對它進(jìn)行賦值之外，這個(gè)循環(huán)與前一個(gè)相似。由于這里只需要借助迭代器進(jìn)行讀，不需要寫，這里把iter定義為const_iterator類型。當(dāng)對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è)迭代器，它自身的值可以改變，但不能用來改變其所指向的元素的值。可以對迭代器進(jìn)行自增以及使用解引用操作符來讀取值，但不能對該元素值賦值。
不要把const_iterator對象與const的iterator對象混淆起來。聲明一個(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)庫容器迭代器）也支持其他的算術(shù)操作。這些操作稱為迭代器算術(shù)操作（iterator arithmetic），包括：
l iter + n
iter - n
可以對迭代器對象加上或減去一個(gè)整型值。這樣做將產(chǎn)生一個(gè)新的迭代器，其位置在iter所指元素之前（加）或之后（減）n個(gè)元素的位置。加或減之后的結(jié)果必須指向iter所指vector中的某個(gè)元素，或者是vector末端的后一個(gè)元素。加上或減去的值的類型應(yīng)該是vector的size_type或difference_type類型（參考下面的解釋）。
l iter1 - iter2
該表達(dá)式用來計(jì)算兩個(gè)迭代器對象的距離，該距離是名為difference_type的signed整數(shù)類型的值，這里的difference_type類型類似于size_type類型，也是由vector定義的。difference_type是signed類型，因?yàn)闇p法運(yùn)算可能產(chǎn)生負(fù)數(shù)的結(jié)果。該類型可以保證足夠大以存儲(chǔ)任何兩個(gè)迭代器對象間的距離。iter1與iter2兩者必須都指向同一vector中的元素，或者指向vector末端之后的下一個(gè)元素。
可以用迭代器算術(shù)操作來移動(dòng)迭代器直接指向某個(gè)元素，例如，下面語句直接定位于vector的中間元素：
vector<int>::iterator mid = vi.begin() + vi.size()/2;
上述代碼用來初始化mid，使其指向vi中最靠近正中間的元素。這種直接計(jì)算迭代器的方法，與用迭代器逐個(gè)元素自增操作到達(dá)中間元素的方法是等價(jià)的，但前者的效率要高得多。
任何改變vector長度的操作都會(huì)使已存在的迭代器失效。例如，在調(diào)用push_back之后，就不能再信賴指向vector的迭代器的值了。