//<vector>template < class T, class Alloc = allocator<T> > class vector;
向量（Vector）是一個封裝了動態(tài)大小數(shù)組的順序容器（Sequence container）。跟任意其它類型容器一樣，它能夠存放各種類型的對象。可以簡單的認(rèn)為，向量是一個能夠存放任意類型的動態(tài)數(shù)組。
vector類為內(nèi)置數(shù)組提供了一種替代表示，與string類一樣 vector 類是隨標(biāo)準(zhǔn) C++引入的標(biāo)準(zhǔn)庫的一部分 ，為了使用vector 我們必須包含相關(guān)的頭文件 ：
#include <vector>
容性特性：
1.順序序列
順序容器中的元素按照嚴(yán)格的線性順序排序。可以通過元素在序列中的位置訪問對應(yīng)的元素。
2.動態(tài)數(shù)組
支持對序列中的任意元素進行快速直接訪問，甚至可以通過指針?biāo)闶鲞M行該操作。操供了在序列末尾相對快速地添加/刪除元素的操作。
3.能夠感知內(nèi)存分配器的（Allocator-aware）
容器使用一個內(nèi)存分配器對象來動態(tài)地處理它的存儲需求。
使用：
使用vector有兩種不同的形式，即所謂的數(shù)組習(xí)慣和 STL習(xí)慣。
一、數(shù)組習(xí)慣用法
1. 定義一個已知長度的 vector ：
vector< int > ivec( 10 ); //類似數(shù)組定義int ia[ 10 ];
可以通過ivec[索引號] 來訪問元素
使用 if ( ivec.empty() ) 判斷是否是空，ivec.size()判斷元素個數(shù)。
2. vector的元素被初始化為與其類型相關(guān)的缺省值：算術(shù)和指針類型的缺省值是 0，對于class 類型，缺省值可通過調(diào)用這類的缺省構(gòu)造函數(shù)獲得，我們還可以為每個元素提供一個顯式的初始值來完成初始化，例如
vector< int > ivec( 10, -1 );
定義了 ivec 它包含十個int型的元素 每個元素都被初始化為-1
對于內(nèi)置數(shù)組 我們可以顯式地把數(shù)組的元素初始化為一組常量值，例如 ：
int ia[ 6 ] = { -2, -1, 0, 1, 2, 1024 }; 我們不能用同樣的方法顯式地初始化 vector ，但是可以將 vector 初始化為一個已有數(shù)組的全部或一部分，只需指定希望被用來初始化 vector 的數(shù)組的開始地址以及數(shù)組最末元的下一位置來實現(xiàn)，例如：
// 把 ia 的 6 個元素拷貝到 ivec 中 vector< int > ivec( ia, ia+6 );
被傳遞給ivec 的兩個指針標(biāo)記了用來初始化對象的值的范圍，第二個指針總是指向要拷貝的末元素的下一位置，標(biāo)記出來的元素范圍也可以是數(shù)組的一個子集，例如 :
// 拷貝 3 個元素 ia[2], ia[3], ia[4] vector< int > ivec( &ia[ 2 ], &ia[ 5 ] );
3. 與內(nèi)置數(shù)組不同 vector 可以被另一個 vector 初始化 或被賦給另一個 vector 例如
vector< string > svec; void init_and_assign() { // 用另一個 vector 初始化一個 vector vector< string > user_names( svec ); // ... // 把一個 vector 拷貝給另一個 vector svec = user_names; }
二、STL習(xí)慣用法
在 STL9中對vector 的習(xí)慣用法完全不同。我們不是定義一個已知大小的 vector，而是定義一個空 vector
vector< string > text;
1. 我們向 vector 中插入元素，而不再是索引元素，以及向元素賦值，例如 push_back()操作，就是在 vector 的后面插入一個元素下面的 while 循環(huán)從標(biāo)準(zhǔn)輸入讀入一個字符串序列并每次將一個字符串插入到 vector 中
雖然我們?nèi)钥梢杂孟聵?biāo)操作符來迭代訪問元素
cout << "words read are: /n"; for ( int ix = 0; ix < text.size(); ++ix ) cout << text[ ix ] << ' '; cout << endl;
但是 更典型的做法是使用 vector 操作集中的begin()和 end()所返回的迭代器 iterator
對 ：
cout << "words read are: /n"; for ( vector<string>::iterator it = text.begin(); it != text.end(); ++it ) cout << *it << ' '; cout << endl
iterator 是標(biāo)準(zhǔn)庫中的類，它具有指針的功能
對迭代器解引用，并訪問其指向的實際對象
向前移動迭代器 it 使其指向下一個元素
2. 注意 不要混用這兩種習(xí)慣用法， 例如，下面的定義
vector< int > ivec;
定義了一個空vector 再寫這樣的語句
ivec[ 0 ] = 1024;
就是錯誤的 ，因為 ivec 還沒有第一個元素，我們只能索引 vector 中已經(jīng)存在的元素 size()操作返回 vector 包含的元素的個數(shù) 。
3. 類似地 當(dāng)我們用一個給定的大小定義一個 vector 時，例如 ：
vector<int> ia( 10 );
任何一個插入操作都將增加vector 的大小，而不是覆蓋掉某個現(xiàn)有的元素，這看起來好像是很顯然的，但是 下面的錯誤在初學(xué)者中并不少見 ：
const int size = 7; int ia[ size ] = { 0, 1, 1, 2, 3, 5, 8 }; vector< int > ivec( size ); for ( int ix = 0; ix < size; ++ix ) ivec.push_back( ia[ ix ]); 程序結(jié)束時ivec 包含 14 個元素, ia 的元素從第八個元素開始插入。
深入理解
在向量中，所有元素都是連續(xù)存儲的。也就是說，不僅可以通過迭代器（Iterators）訪問各個元素，也可以通過指向元素的指針加上偏移來訪問。還意味著，當(dāng)向任意函數(shù)傳遞向量的一個元素的指針時，這個指針可以直接被認(rèn)為指向了一個數(shù)組中的某個元素。
向量內(nèi)部的存儲調(diào)整是自動處理的，按需擴展或壓縮。通常，相比靜態(tài)數(shù)組（Static arrays），向量將會占用更多的存儲空間，因為額外的內(nèi)存將被未來增長的部分所使用。就因為這點，當(dāng)插入元素時，向量不需要太頻繁地重分配（Reallocate）內(nèi)存。當(dāng)前最大容量可以通過函數(shù) capacity() 查詢。額外的內(nèi)存可以通過調(diào)用 shrink_to_fit() 函數(shù)返還給操作系統(tǒng)。
當(dāng)增加向量對象中的序列的長度時，如果超出當(dāng)前存儲容量上限，就會發(fā)生內(nèi)存重分配（Reallocation），即內(nèi)部將會重新分配一個數(shù)組，然后按順序逐個拷貝元素。其它的插入及刪除操作將會修改序列中部分元素的內(nèi)存地址。在上述所有情況下，指向序列中被修改部分的迭代器或引用將會失效。當(dāng)未發(fā)生內(nèi)存重分配，僅指向插入或刪除點之前元素的迭代器或引用才會保持有效性。
標(biāo)準(zhǔn)庫可以執(zhí)行不同的增長策略來平衡內(nèi)存的使用量與重分配所耗的性能。但不管哪種情況下，重分配內(nèi)存的大小必須以指數(shù)方式增長，只有這樣，才能將在向量末尾逐個插入元素所需的時間復(fù)雜度整體分?jǐn)偅ˋmortized）為一個恒定值。
內(nèi)存重分配就性能而言是一個高代價操作。如果在使用向量前知道元素的數(shù)量，可以通過 reserve() 消除內(nèi)存重分配。
向量支持在序列末尾恒定耗時的插入及刪除元素。而在向量的中間插入或刪除元素則需要線性的時間。在只涉及向序列起始或未尾插入及刪除元素操作時，std::deque? 容器的性能將會高出很多。當(dāng)涉及向序列中的任意位置進行插入及刪除操作時，std::list 容器的性能將會高出很多。
常用操作的算法復(fù)雜度（性能相關(guān)）如下：
- 隨機訪問，時間復(fù)雜度為 O(1)
- 在未尾插入或刪除元素，整體分?jǐn)偟臅r間復(fù)雜度為 O(1)
- 其它位置插入或刪除元素，與當(dāng)前位置至向量末尾的距離有關(guān)，時間復(fù)雜度 O(n)??
