//<vector>
template < class T, class Alloc = allocator<T> > class vector;

向量（Vector）是一個(gè)封裝了動(dòng)態(tài)大小數(shù)組的順序容器（Sequence container）。跟任意其它類(lèi)型容器一樣，它能夠存放各種類(lèi)型的對(duì)象。可以簡(jiǎn)單的認(rèn)為，向量是一個(gè)能夠存放任意類(lèi)型的動(dòng)態(tài)數(shù)組。

vector類(lèi)為內(nèi)置數(shù)組提供了一種替代表示，與string類(lèi)一樣 vector 類(lèi)是隨標(biāo)準(zhǔn) C++引入的標(biāo)準(zhǔn)庫(kù)的一部分 ，為了使用vector 我們必須包含相關(guān)的頭文件  ：

#include <vector>

容性特性：

1.順序序列

順序容器中的元素按照嚴(yán)格的線性順序排序?？梢酝ㄟ^(guò)元素在序列中的位置訪問(wèn)對(duì)應(yīng)的元素。

2.動(dòng)態(tài)數(shù)組

支持對(duì)序列中的任意元素進(jìn)行快速直接訪問(wèn)，甚至可以通過(guò)指針?biāo)闶鲞M(jìn)行該操作。操供了在序列末尾相對(duì)快速地添加/刪除元素的操作。

3.能夠感知內(nèi)存分配器的（Allocator-aware）

容器使用一個(gè)內(nèi)存分配器對(duì)象來(lái)動(dòng)態(tài)地處理它的存儲(chǔ)需求。

使用：

使用vector有兩種不同的形式，即所謂的數(shù)組習(xí)慣和 STL習(xí)慣。

一、數(shù)組習(xí)慣用法
1. 定義一個(gè)已知長(zhǎng)度的 vector ：

vector< int > ivec( 10 ); //類(lèi)似數(shù)組定義int ia[ 10 ];

可以通過(guò)ivec[索引號(hào)] 來(lái)訪問(wèn)元素

使用 if ( ivec.empty() ) 判斷是否是空，ivec.size()判斷元素個(gè)數(shù)。

2. vector的元素被初始化為與其類(lèi)型相關(guān)的缺省值：算術(shù)和指針類(lèi)型的缺省值是 0，對(duì)于class 類(lèi)型，缺省值可通過(guò)調(diào)用這類(lèi)的缺省構(gòu)造函數(shù)獲得，我們還可以為每個(gè)元素提供一個(gè)顯式的初始值來(lái)完成初始化，例如 
vector< int > ivec( 10, -1 );
定義了 ivec 它包含十個(gè)int型的元素 每個(gè)元素都被初始化為-1

對(duì)于內(nèi)置數(shù)組 我們可以顯式地把數(shù)組的元素初始化為一組常量值，例如 ：

int ia[ 6 ] = { -2, -1, 0, 1, 2, 1024 };

我們不能用同樣的方法顯式地初始化 vector ，但是可以將 vector 初始化為一個(gè)已有數(shù)組的全部或一部分，只需指定希望被用來(lái)初始化 vector 的數(shù)組的開(kāi)始地址以及數(shù)組最末元的下一位置來(lái)實(shí)現(xiàn)，例如：  

// 把 ia 的 6 個(gè)元素拷貝到 ivec 中 
vector< int > ivec( ia, ia+6 ); 

被傳遞給ivec 的兩個(gè)指針標(biāo)記了用來(lái)初始化對(duì)象的值的范圍，第二個(gè)指針總是指向要拷貝的末元素的下一位置，標(biāo)記出來(lái)的元素范圍也可以是數(shù)組的一個(gè)子集，例如 :

// 拷貝 3 個(gè)元素 ia[2], ia[3], ia[4] 
vector< int > ivec( &ia[ 2 ], &ia[ 5 ] );

3. 與內(nèi)置數(shù)組不同 vector 可以被另一個(gè) vector 初始化 或被賦給另一個(gè) vector 例如 

vector< string > svec; 
void init_and_assign() 
{ 
  // 用另一個(gè) vector 初始化一個(gè) vector 
  vector< string > user_names( svec ); 
  // ... 
 
  // 把一個(gè) vector 拷貝給另一個(gè) vector 
  svec = user_names; 
}

二、STL習(xí)慣用法
在 STL9中對(duì)vector 的習(xí)慣用法完全不同。我們不是定義一個(gè)已知大小的 vector，而是定義一個(gè)空 vector 
vector< string > text;

1. 我們向 vector 中插入元素，而不再是索引元素，以及向元素賦值，例如 push_back()操作，就是在 vector 的后面插入一個(gè)元素下面的 while 循環(huán)從標(biāo)準(zhǔn)輸入讀入一個(gè)字符串序列并每次將一個(gè)字符串插入到 vector 中 

string word; 
while ( cin >> word ) { 
text.push_back( word ); 
// ... 
}

雖然我們?nèi)钥梢杂孟聵?biāo)操作符來(lái)迭代訪問(wèn)元素 

cout << "words read are: \n"; 
 
for ( int ix = 0; ix < text.size(); ++ix ) 
   cout << text[ ix ] << ' '; 
 
cout << endl; 

但是 更典型的做法是使用 vector 操作集中的begin()和 end()所返回的迭代器 iterator 
對(duì) ：

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)庫(kù)中的類(lèi)，它具有指針的功能

向前移動(dòng)迭代器 it 使其指向下一個(gè)元素 

2. 注意 不要混用這兩種習(xí)慣用法， 例如，下面的定義 

vector< int > ivec; 

定義了一個(gè)空vector 再寫(xiě)這樣的語(yǔ)句 

ivec[ 0 ] = 1024; 

就是錯(cuò)誤的 ，因?yàn)?ivec 還沒(méi)有第一個(gè)元素，我們只能索引 vector 中已經(jīng)存在的元素 size()操作返回 vector 包含的元素的個(gè)數(shù) 。

3. 類(lèi)似地 當(dāng)我們用一個(gè)給定的大小定義一個(gè) vector 時(shí)，例如  ：

vector<int> ia( 10 ); 

任何一個(gè)插入操作都將增加vector 的大小，而不是覆蓋掉某個(gè)現(xiàn)有的元素，這看起來(lái)好像是很顯然的，但是 下面的錯(cuò)誤在初學(xué)者中并不少見(jiàn) ：

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é)束時(shí)ivec 包含 14 個(gè)元素, ia 的元素從第八個(gè)元素開(kāi)始插入。

深入理解
在向量中，所有元素都是連續(xù)存儲(chǔ)的。也就是說(shuō)，不僅可以通過(guò)迭代器（Iterators）訪問(wèn)各個(gè)元素，也可以通過(guò)指向元素的指針加上偏移來(lái)訪問(wèn)。還意味著，當(dāng)向任意函數(shù)傳遞向量的一個(gè)元素的指針時(shí)，這個(gè)指針可以直接被認(rèn)為指向了一個(gè)數(shù)組中的某個(gè)元素。
向量?jī)?nèi)部的存儲(chǔ)調(diào)整是自動(dòng)處理的，按需擴(kuò)展或壓縮。通常，相比靜態(tài)數(shù)組（Static arrays），向量將會(huì)占用更多的存儲(chǔ)空間，因?yàn)轭~外的內(nèi)存將被未來(lái)增長(zhǎng)的部分所使用。就因?yàn)檫@點(diǎn)，當(dāng)插入元素時(shí)，向量不需要太頻繁地重分配（Reallocate）內(nèi)存。當(dāng)前最大容量可以通過(guò)函數(shù) capacity() 查詢。額外的內(nèi)存可以通過(guò)調(diào)用 shrink_to_fit() 函數(shù)返還給操作系統(tǒng)。
當(dāng)增加向量對(duì)象中的序列的長(zhǎng)度時(shí)，如果超出當(dāng)前存儲(chǔ)容量上限，就會(huì)發(fā)生內(nèi)存重分配（Reallocation），即內(nèi)部將會(huì)重新分配一個(gè)數(shù)組，然后按順序逐個(gè)拷貝元素。其它的插入及刪除操作將會(huì)修改序列中部分元素的內(nèi)存地址。在上述所有情況下，指向序列中被修改部分的迭代器或引用將會(huì)失效。當(dāng)未發(fā)生內(nèi)存重分配，僅指向插入或刪除點(diǎn)之前元素的迭代器或引用才會(huì)保持有效性。

標(biāo)準(zhǔn)庫(kù)可以執(zhí)行不同的增長(zhǎng)策略來(lái)平衡內(nèi)存的使用量與重分配所耗的性能。但不管哪種情況下，重分配內(nèi)存的大小必須以指數(shù)方式增長(zhǎng)，只有這樣，才能將在向量末尾逐個(gè)插入元素所需的時(shí)間復(fù)雜度整體分?jǐn)偅ˋmortized）為一個(gè)恒定值。

內(nèi)存重分配就性能而言是一個(gè)高代價(jià)操作。如果在使用向量前知道元素的數(shù)量，可以通過(guò) reserve() 消除內(nèi)存重分配。

向量支持在序列末尾恒定耗時(shí)的插入及刪除元素。而在向量的中間插入或刪除元素則需要線性的時(shí)間。在只涉及向序列起始或未尾插入及刪除元素操作時(shí)，std::deque​ 容器的性能將會(huì)高出很多。當(dāng)涉及向序列中的任意位置進(jìn)行插入及刪除操作時(shí)，std::list 容器的性能將會(huì)高出很多。
常用操作的算法復(fù)雜度（性能相關(guān)）如下：

• 隨機(jī)訪問(wèn)，時(shí)間復(fù)雜度為 O(1)
• 在未尾插入或刪除元素，整體分?jǐn)偟臅r(shí)間復(fù)雜度為 O(1)
• 其它位置插入或刪除元素，與當(dāng)前位置至向量末尾的距離有關(guān)，時(shí)間復(fù)雜度 O(n)​​

最新評(píng)論