vector容器与iterator迭代器
vector容器
vector是同一種類型的對象的集合，每個對象都有一個對應的整數索引值。和string對象一樣，標準庫負責管理存儲元素的相關內存。我們把vector稱為容器，是因為它可以包含其他對象。一個容器中的所有對象都必須是同一種類型的。
使用vector之前，必須包含相應的頭文件。
#include <vector>
using std::vector;
vector是一個類模板（class?template）。模板允許程序員編寫單個類或函數定義，這個類和函數定義可用于不同的數據類型上。因此，我們可以定義保存string對象的vector，或保存int值的vector，又或是保存自定義的類類型對象（如Sales_item對象）的vector。
聲明從類模板產生的某種類型的對象，需要提供附加信息，信息的種類取決于模板。以vector為例，必須說明vector保存何種對象的類型，通過將類型放在類模板名稱后面的尖括號中來指定類型：
vector<int> ivec;?????????????? ? //?ivec?holds objects of type?int
vector<Sales_item> Sales_vec;? //?holds?Sales_items
和其他變量定義一樣，定義vector對象要指定類型和一個變量的列表。上面的第一個定義，類型是vector<int>，該類型即是含有若干int類型對象的vector，變量名為ivec。第二個定義的變量名是Sales_vec，它所保存的元素是Sales_item類型的對象。
vector不是一種數據類型，而只是一個類模板，可用來定義任意多種數據類型。vector類型的每一種都指定了其保存元素的類型。因此，vector<int>和vector <string>都是數據類型。
vector對象的定義和初始化
vector類定義了好幾種構造函數，用來定義和初始化vector對象。下表3-4列出了這些構造函數：
| vector<T>??v1; | vector保存類型為T的對象。默認構造函數v1為空。 |
| vector<T>?v2(v1); | v2是v1的一個副本。 |
| vector<T>?v3(n,?i); | v3包含n個值為i的元素。 |
| vector<T>?v4(n); | v4含有值初始化的元素的n個副本。 |
?創建確定個數的元素
若要創建非空的vector對象，必須給出初始化元素的值。當把一個vector對象復制到另一個vector對象時，新復制的vector中每一個元素都初始化為原vector中相應元素的副本。但這兩個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
可以用元素個數和元素值對vector對象進行初始化。構造函數用元素個數來決定vector對象保存元素的個數，元素值指定每個元素的初始值：
vector<int> ivec4(10, -1);???? //?10?elements, each initialized to?-1
vector<string> svec(10, "hi!"); //?10?strings, each initialized to "hi!"
關鍵概念：vector對象動態增長???????????????????????????????????????????????????????
vector對象（以及其他標準庫容器對象）的重要屬性就在于可以在運行時高效地添加元素。因為vector增長的效率高，在元素值已知的情況下，最好是動態地添加元素。這種增長方式不同于C語言中的內置數據類型，也不同于大多數其他編程語言的數據類型。特別地，如果讀者習慣了C或Java的風格，由于vector元素連續存儲，可能希望最好是預先分配合適的空間。但事實上，為了達到連續性，C++的做法恰好相反。
雖然可以對給定元素個數的vector對象預先分配內存，但更有效的方法是先初始化一個空vector對象，然后再動態地增加元素。?
值初始化
如果沒有給出元素的初始化式，那么標準庫將提供一個值初始化的（value?initialized）元素初始化式。這個由庫生成的初始值用于初始化容器中的每個元素。而元素初始化式的值取決于存儲在vector中元素的數據類型。
如果vector保存內置類型（如int類型）的元素，那么標準庫將用0值創建元素初始化值：
vector<string> fvec(10); //?10?elements, each initialized to?0
如果向量保存類類型（如string）的元素，標準庫將用該類型的默認構造函數創建元素初始值：
vector<string> svec(10); //?10?elements, each an empty string
對于有自定義構造函數但沒有默認構造函數的類，在初始化這種類型的Vector對象時，程序員就不能僅提供元素個數，還需要提供元素初始值。
元素類型可能是沒有定義任何構造函數的類類型。這種情況下，標準庫仍產生一個帶初始值的對象，這個對象的每個成員進行了值初始化。
vector的操作
vector標準庫提供許多類似于string對象的操作，下表列出了幾種最重要的vector操作。
| v.empty() | 如果v為空，則返回true,否則返回false。 |
| v.size() | 返回v中元素的個數。 |
| v.push_back(t) | 在v的末尾增加一個值為t的元素。 |
| v[n] | 返回v中位置為n的元素。 |
| v1?=?v2 | 把v1的元素替換為v2中元素的副本。 |
| v1?==?v2 | 如果v1與v2相等，則返回true。 |
| !=, <, <=, >, >= | 保持這些操作符慣有的含義。 |
?vector對象的size
empty和size操作類似于string類型的相關操作。成員函數size返回相應vector類定義的size_type的值。
使用size_type類型時，必須指出該類型是在哪里定義的。vector類型總是包括vector的元素類型：
vector<int>::size_type??? ??? //?ok
vector::size_type????????? //?error
?向vector添加元素
push_back()操作接受一個元素值，并將它作為一個新的元素添加到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
}
該循環從標準輸入讀取一系列string對象，逐一追加到vector對象的后面。首先定義一個空的vector對象text。每循環一次就添加一個新元素到vector對象，并將從輸入讀取的word值賦予該元素。當循環結束時，text就包含了所有讀入的元素。
vector的下標操作
vector中的對象是沒有命名的，可以按vector中對象的位置來訪問它們。通常使用下標操作符來獲取元素。vector的下標操作類似于string類型的下標操作。
vector的下標操作符接受一個值，并返回vector中該對應位置的元素。vector元素的位置從0開始。下例使用for循環把vector中的每個元素值都重置為0:
//?reset the elements in the?vector?to zero
for (vector<int>::size_type ix = 0; ix != ivec.size(); ++ix)
??? ivec[ix] = 0;
和string類型的下標操作符一樣，vector下標操作的結果為左值，因此可以像循環體中所做的那樣實現寫入。另外，和string對象的下標操作類似，這里用size_type類型作為vector下標的類型。
在上例中，即使ivec為空，for循環也會正確執行。ivec為空則調用size返回0，并且for中的測試比較ix和0。第一次循環時，由于ix本身就是0，則條件測試失敗，for循環體一次也不執行。
關鍵概念：安全的泛型編程???????????????????????????????????????????????????????
習慣于C或Java編程的C++程序員可能會覺得難以理解，for循環的判斷條件用!=而不是用<來測試vector下標值是否越界。C程序員難以理解的還有，上例中沒有在for循環之前就調用size成員函數并保存其返回的值，而是在for語句頭中調用size成員函數。C++程序員習慣于優先選用!=而不是<來編寫循環判斷條件。調用size成員函數而不保存它返回的值，在這個例子中同樣不是必需的，但這反映了一個良好的編程習慣。在C++中，有些數據結構（如vector）可以動態增長。上例中循環僅需要讀取元素，而不需要增加新的元素。但是，循環可以容易地增加新元素，如果確實增加了新元素的話，那么測試已保存的size值作為循環的結束條件就會有問題，因為沒有將新加入的元素計算在內。所以我們傾向于在每次循環中測試size的當前值，而不是在進入循環時，存儲size值的副本。
我們知道，C++中有些函數可以聲明為內聯（inline）函數。編譯器遇到內聯函數時就會直接擴展相應代碼，而不是進行實際的函數調用。像size這樣的小庫函數幾乎都定義為內聯函數，所以每次循環過程中調用它的運行時代價是比較小的。
?
下標操作不添加元素
初學C++的程序員可能會認為vector的下標操作可以添加元素，其實不然：
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個新元素，元素值依次為0到9的整數。但是，這里ivec是空的vector對象，而且下標只能用于獲取已存在的元素。
這個循環的正確寫法應該是：
for (vector<int>::size_type ix = 0; ix != 10; ++ix)
???? ivec.push_back(ix);? //?ok: adds new element with value?ix
必須是已存在的元素才能用下標操作符進行索引。通過下標操作進行賦值時，不會添加任何元素。
警告：僅能對確知已存在的元素進行下標操作???????????????????????????????????????????
對于下標操作符([]操作符)的使用有一點非常重要，就是僅能提取確實已存在的元素，例如：
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
試圖獲取不存在的元素必然產生運行時錯誤。和大多數同類錯誤一樣，不能確保執行過程可以捕捉到這類錯誤，運行程序的結果是不確定的。由于取不存在的元素的結果是未定義的，因而不同的實現會導致不同的結果，但程序運行時幾乎肯定會以某種有趣的方式失敗。
本警告適用于任何使用下標操作的時候，如string類型的下標操作，以及將要簡要介紹的內置數組的下標操作。
不幸的是，試圖對不存在的元素進行下標操作是程序設計過程中經常會犯的嚴重錯誤。所謂的“緩沖區溢出”錯誤就是對不存在的元素進行下標操作的結果。這樣的缺陷往往導致PC機和其他應用中最常見的安全問題。
????????????????????????vector迭代器
除了使用下標來訪問vector對象的元素外，標準庫還提供了另一種檢測元素的方法：使用迭代器（iterator）。迭代器是一種允許程序員檢查容器內元素，并實現元素遍歷的數據類型。
標準庫為每一種標準容器（包括vector）定義了一種迭代器類型。迭代器類型提供了比下標操作更一般化的方法：所有的標準庫容器都定義了相應的迭代器類型，而只有少數的容器支持下標操作。因為迭代器對所有的容器都適用，現代C++程序更傾向于使用迭代器而不是下標操作訪問容器元素，即使對支持下標操作的vector類型也這樣。
容器的iterator類型
每種容器類型都定義了自己的迭代器類型，如vector：
vector<int>::iterator iter;
這條語句定義了一個名為iter的變量，它的數據類型是由vector<int>定義的iterator類型。每個標準庫容器類型都定義了一個名為iterator的成員，這里的iterator與迭代器實際類型的含義相同。
不同的容器類定義了自己的iterator類型，用于訪問容器內的元素。換句話說，每個容器定義了一種名為iterator的類型，而這種類型支持（概念上的）迭代器的各種行為。
?
begin和end操作
每種容器都定義了一對命名為begin和end的函數，用于返回迭代器。如果容器中有元素的話，由begin返回的迭代器指向第一個元素：
vector<int>::iterator iter = ivec.begin();
上述語句把iter初始化為由名為begin的vector操作返回的值。假設vector不空，初始化后，iter即指該元素為ivec[0]。
由end操作返回的迭代器指向vector的“末端元素的下一個”。通常稱為超出末端迭代器(off-the-end?iterator)，表明它指向了一個不存在的元素。如果vector為空，begin返回的迭代器與end返回的迭代器相同。
由end操作返回的迭代器并不指向vector中任何實際的元素，相反，它只是起一個哨兵（sentinel）的作用，表示我們已處理完vector中所有元素。
vector迭代器的自增和解引用運算
迭代器類型定義了一些操作來獲取迭代器所指向的元素，并允許程序員將迭代器從一個元素移動到另一個元素。
迭代器類型可使用解引用操作符（*操作符）來訪問迭代器所指向r?元素：
*iter = 0;
解引用操作符返回迭代器當前所指向的元素。假設iter指向vector對象ivec的第一個元素，那么*iter和ivec[0]就是指向同一個元素。上面這個語句的效果就是把這個元素的值賦為0。
迭代器使用自增操作符向前移動迭代器指向容器中下一個元素。從邏輯上說，迭代器的自增操作和int型對象的自增操作類似。對int對象來說，操作結果就是把int型值“加1”，而對迭代器對象則是把容器中的迭代器“向前移動一個位置”。因此，如果iter指向第一個元素，則++iter指向第二個元素。
由于end操作返回的迭代器不指向任何元素，因此不能對它進行解引用或自增操作。
?迭代器的其他運算
另一對可執行于迭代器的操作就是比較：用==或!=操作符來比較兩個迭代器，如果兩個迭代器對象指向同一個元素，則它們相等，否則就不相等。
迭代器應用的程序示例
假設已聲明了一個vector<int>型的ivec變量，要把它所有元素值重置為0，可以用下標操作來完成：
//?reset all the elements in?ivec?to?0
for (vector<int>::size_type ix = 0; ix != ivec.size(); ++ix)
?????? ivec[ix] = 0;
上述程序用for循環遍歷ivec的元素，for循環定義了一個索引ix，每循環迭代一次ix就自增1。for循環體將ivec的每個元素賦值為0。
更典型的做法是用迭代器來編寫循環：
//?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循環首先定義了iter，并將它初始化為指向ivec的第一個元素。for循環的條件測試iter是否與end操作返回的迭代器不等。每次迭代iter都自增1，這個for循環的效果是從ivec第一個元素開始，順序處理vector中的每一元素。最后，iter將指向ivec中的最后一個元素，處理完最后一個元素后，iter再增加1，就會與end操作的返回值相等，在這種情況下，循環終止。
for循環體內的語句用解引用操作符來訪問當前元素的值。和下標操作符一樣，解引用操作符的返回值是一個左值，因此可以對它進行賦值來改變它的值。上述循環的效果就是把ivec中所有元素都賦值為0。
通過上述對代碼的詳細分析，可以看出這段程序與用下標操作符的版本達到相同的操作效果：從vector的第一個元素開始，把vector中每個元素都置為0。
如果vector為空，程序是安全的。如果ivec為空，則begin返回的迭代器不指向任何元素，由于沒有元素，所以它不能指向任何元素——在這種情況下，從begin操作返回的迭代器與從end操作返回的迭代器的值相同，因此for語句中的測試條件立即失敗。
const_iterator
前面的程序用vector::iterator改變vector中的元素值。每種容器類型還定義了一種名為const_iterator的類型，該類型只能訪問容器內元素，但不能改變其值。
當我們對普通iterator類型解引用時，得到對某個元素的非const引用。而如果我們對const_iterator類型解引用時，則可以得到一個指向const對象的引用，如同任何常量一樣，該對象不能進行重寫。
例如，如果text是vector<string>類型，程序員想要遍歷它，輸出每個元素,可以這樣編寫程序：
//?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
除了是從迭代器讀取元素值而不是對它進行賦值之外，這個循環與前一個相似。由于這里只需要借助迭代器進行讀，不需要寫，這里把iter定義為const_iterator類型。當對const_iterator類型解引用時，返回的是一個const值。不允許用const_iterator進行賦值：
for (vector<string>::const_iterator iter = text.begin();
?????????????????????????????????? iter != text.end(); ++ iter)
??? *iter = " ";???? //?error:?*iter is const
使用const_iterator類型時，我們可以得到一個迭代器，它自身的值可以改變，但不能用來改變其所指向的元素的值。可以對迭代器進行自增以及使用解引用操作符來讀取值，但不能對該元素值賦值。
不要把const_iterator對象與const的iterator對象混淆起來。聲明一個const迭代器時，必須初始化迭代器。一旦被初始化后，就不能改變它的值：
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
迭代器的算術操作
除了一次移動迭代器的一個元素的增量操作符外，vector的迭代器（很少有其他標準庫容器迭代器）也支持其他的算術操作。這些操作稱為迭代器算術操作（iterator arithmetic），包括：
l?iter + n
? iter - n
可以對迭代器對象加上或減去一個整型值。這樣做將產生一個新的迭代器，其位置在iter所指元素之前（加）或之后（減）n個元素的位置。加或減之后的結果必須指向iter所指vector中的某個元素，或者是vector末端的后一個元素。加上或減去的值的類型應該是vector的size_type或difference_type類型（參考下面的解釋）。
l?iter1?-?iter2??????????????????????????????????????????????????????
該表達式用來計算兩個迭代器對象的距離，該距離是名為difference_type的signed整數類型的值，這里的difference_type類型類似于size_type類型，也是由vector定義的。difference_type是signed類型，因為減法運算可能產生負數的結果。該類型可以保證足夠大以存儲任何兩個迭代器對象間的距離。iter1與iter2兩者必須都指向同一vector中的元素，或者指向vector末端之后的下一個元素。
可以用迭代器算術操作來移動迭代器直接指向某個元素，例如，下面語句直接定位于vector的中間元素：
vector<int>::iterator mid = vi.begin() + vi.size()/2;
上述代碼用來初始化mid，使其指向vi中最靠近正中間的元素。這種直接計算迭代器的方法，與用迭代器逐個元素自增操作到達中間元素的方法是等價的，但前者的效率要高得多。
任何改變vector長度的操作都會使已存在的迭代器失效。例如，在調用push_back之后，就不能再信賴指向vector的迭代器的值了。
轉自：http://www.cppblog.com/totti1006/archive/2009/09/01/94955.html
總結
以上是生活随笔為你收集整理的vector容器与iterator迭代器的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 剑指offer 算法 （知识迁移能力）
- 下一篇： 剑指offer 算法 （知识迁移能力2）