vector(向量)

C++中的一種數(shù)據(jù)結(jié)構(gòu)，確切的說是一個(gè)類。它相當(dāng)于一個(gè)動(dòng)態(tài)的數(shù)組，當(dāng)程序員無法知道自己需要的數(shù)組的規(guī)模多大時(shí)，用其來解決問題可以達(dá)到最大節(jié)約空間的目的.

1. 文件包含:

首先在程序開頭處加上 #include <vector> 以包含所需要的類文件vector
還有一定要加上 using namespace std;

#include <iostream>
#include <vector>

using namespace std;

2. 變量聲明:

• 例:聲明一個(gè)int向量以替代一維的數(shù)組: vector <int> a;
  (等于聲明了一個(gè)int數(shù)組a[],大小沒有指定,可以動(dòng)態(tài)的向里面添加刪除)。

• 例:用vector代替二維數(shù)組.
  其實(shí)只要聲明一個(gè)一維數(shù)組向量即可,而一個(gè)數(shù)組的名字其實(shí)代表的是它的首地址,所以只要聲明一個(gè)地址的向量即可,即:vector <int > a.同理想用向量代替三維數(shù)組也是一樣,vector <int*>a;再往上面依此類推.

// 一維數(shù)組
vector <int> a;
// 二維
vector <int*> b;
// 三維
vector <int**> c;

3. 具體的用法以及函數(shù)調(diào)用:

3.1函數(shù)列表

方法名 | 描述
-- |
push_back | 在數(shù)組的最后添加一個(gè)數(shù)據(jù)
pop_back | 去掉數(shù)組的最后一個(gè)數(shù)據(jù)
at | 得到編號(hào)位置的數(shù)據(jù)
begin | 返回一個(gè)迭代器iterator，它指向容器的第一個(gè)元素
end | 返回一個(gè)迭代器iterator，它指向容器的最后一個(gè)元素的下一個(gè)位置
front | 得到數(shù)組頭的引用
back | 得到數(shù)組的最后一個(gè)單元的引用
max_size | 得到vector最大可以是多大
capacity | 當(dāng)前vector分配的大小
size | 當(dāng)前使用數(shù)據(jù)的大小
resize | 改變當(dāng)前使用數(shù)據(jù)的大小，如果它比當(dāng)前使用的大，填充默認(rèn)值
reserve | 改變當(dāng)前vecotr所分配空間的大小
erase | 刪除指針指向的數(shù)據(jù)項(xiàng)
clear | 清空當(dāng)前的vector
rbegin | 返回一個(gè)逆序迭代器reverse_iterator，它指向容器的最后一個(gè)元素
rend | 返回一個(gè)逆序迭代器reverse_iterator，它指向容器c的第一個(gè)元素前面的位置
empty | 判斷vector是否為空
swap | 與另一個(gè)vector交換數(shù)據(jù)

3.2 參考代碼

• 基本用法:

    int b = 5;
    a.push_back(b);
    a.push_back(8);
    a.push_back(10);
    a.push_back(22);
    cout << "a's capacity : " << a.capacity() << endl;
    cout << "a[0] : " << a[0] << endl;
    cout << "--------------------------------" << endl << endl;

• 打印vector中的所有數(shù)字

p_vec(vector <int> *vec)
{
    cout << "vec's capacity : " << vec->capacity() << endl;
    cout << "vec's size : " << vec->size() << endl;
    
    //方法一 
    vector<int>::iterator iter = vec->begin();  
    while (iter != vec->end())  
    {
        cout << *iter << "\t";
        iter++;
    }
    
//    //方法二 
//  for(vector<int>::iterator iter=vec->begin(); iter!=vec->end(); iter++)
//  {
//      cout << *iter ;
//  }

    cout << endl << endl; 
}

• 詳細(xì)實(shí)現(xiàn)

    dump_vec(&a);
    
    cout << "a.push_back(2)" << endl;
    a.push_back(2);
    dump_vec(&a);
    
    cout << "a.pop_back()" << endl;
    a.pop_back();
    dump_vec(&a);
    
    cout << "a.at(0): " << a.at(0) << endl; 
    cout << "a.back(): " << a.back() << endl; 
    cout << "a.front(): " << a.front() << endl; 
    cout << endl;
    
    cout << "a.max_size(): " << a.max_size() << endl; 
    cout << "a.capacity(): " << a.capacity() << endl; 
    cout << "a.size(): " << a.size() << endl; 
    cout << endl;

    cout << "a.resize(2)" << endl;
    a.resize(2);
    dump_vec(&a);
    
    cout << "a.resize(4)" << endl;
    a.resize(4);
    dump_vec(&a);
    
    cout << "a.resize(9)" << endl;
    a.resize(9);
    dump_vec(&a);
    
    cout << "a.reserve(6)" << endl;
    a.reserve(6);
    dump_vec(&a);
    
    cout << "a.reserve(10)" << endl;
    a.reserve(10);
    dump_vec(&a);
    
    //a.insert(pos,elem);  在pos位置插入一個(gè)elem拷貝
    cout << "a.insert(a.begin() + 4, 9)" << endl;
    //不能在這里取值，因?yàn)関ector的capacity增加會(huì)重新分配內(nèi)存 
    vector<int>::iterator pos = a.begin() + 3;
    for(int i=0; i<3; i++)
    {   
        pos = a.begin() + 3;
        a.insert(pos + i, 9);
    }
    dump_vec(&a);
    
    //a.erase(beg,end)-刪除[beg,end)區(qū)間的數(shù)據(jù) 
    cout << "a.erase(pos)" << endl;
    a.erase(pos);
    dump_vec(&a);
    
    cout << "a.erase(pos, pos+2)" << endl;
    a.erase(pos, pos+2);
    dump_vec(&a);
    
    //a.rbegin() 返回一個(gè)逆序迭代器，它指向容器c的最后一個(gè)元素
    //a.rend() 返回一個(gè)逆序迭代器，它指向容器c的第一個(gè)元素前面的位置
    cout << "a.rbegan() & a.rend()" << endl;
    for(vector<int>::reverse_iterator r_iter=a.rbegin(); r_iter!=a.rend(); r_iter++)
    {
        cout << *r_iter << "\t";
    }
    cout << endl;
    dump_vec(&a);
    
    //a.swap(b) 與另一個(gè)vector交換數(shù)據(jù)
    vector <int> m;
    m.push_back(1);
    m.push_back(2);
    m.swap(a);
    dump_vec(&a);
    
    //a.empty() 判斷vector是否為空
    cout << "a.empty() : " << a.empty() << endl;
    cout << endl;
    
    //a.clear() 清空當(dāng)前的vector
    cout << "a.clear()" << endl;
    a.clear();
    cout << "a.empty() : " << a.empty() << endl;

4. 內(nèi)存管理與效率

4.1 使用reserve()函數(shù)提前設(shè)定容量大小，避免多次容量擴(kuò)充導(dǎo)致效率低下

關(guān)于STL（Standard Template Library 標(biāo)準(zhǔn)模板庫）容器，最令人稱贊的特性之一就是是只要不超過它們的最大大小，它們就可以自動(dòng)增長到足以容納你放進(jìn)去的數(shù)據(jù)。（要知道這個(gè)最大值，只要調(diào)用名叫max_size的成員函數(shù)。）

對于vector和string，如果需要更多空間，就以類似realloc的思想來增長大小。vector容器支持隨機(jī)訪問，因此為了提高效率，它內(nèi)部使用動(dòng)態(tài)數(shù)組的方式實(shí)現(xiàn)的。在通過 reserve() 來申請?zhí)囟ù笮〉臅r(shí)候總是按指數(shù)邊界來增大其內(nèi)部緩沖區(qū)。

當(dāng)進(jìn)行insert或push_back等增加元素的操作時(shí)，如果此時(shí)動(dòng)態(tài)數(shù)組的內(nèi)存不夠用，就要?jiǎng)討B(tài)的重新分配當(dāng)前大小的1.5~2倍的新內(nèi)存區(qū)，再把原數(shù)組的內(nèi)容復(fù)制過去。所以，在一般情況下，其訪問速度同一般數(shù)組，只有在重新分配發(fā)生時(shí)，其性能才會(huì)下降。正如上面的代碼告訴你的那樣。

而進(jìn)行pop_back操作時(shí)，capacity并不會(huì)因?yàn)関ector容器里的元素減少而有所下降，還會(huì)維持操作之前的大小。對于vector容器來說，如果有大量的數(shù)據(jù)需要進(jìn)行push_back，應(yīng)當(dāng)使用reserve()函數(shù)提前設(shè)定其容量大小，否則會(huì)出現(xiàn)許多次容量擴(kuò)充操作，導(dǎo)致效率低下。

reserve成員函數(shù)允許你最小化必須進(jìn)行的重新分配的次數(shù)，因而可以避免真分配的開銷和迭代器/指針/引用失效。但在我解釋reserve為什么可以那么做之前，讓我簡要介紹有時(shí)候令人困惑的四個(gè)相關(guān)成員函數(shù)。在標(biāo)準(zhǔn)容器中，只有vector和string提供了所有這些函數(shù)。

• size()告訴你容器中有多少元素。它沒有告訴你容器為它容納的元素分配了多少內(nèi)存。

• capacity()告訴你容器在它已經(jīng)分配的內(nèi)存中可以容納多少元素。那是容器在那塊內(nèi)存中總共可以容納多少元素，而不是還可以容納多少元素。如果你想知道一個(gè)vector或string中有多少?zèng)]有被占用的內(nèi)存，你必須從capacity()中減去size()。如果size和capacity返回同樣的值，容器中就沒有剩余空間了，而下一次插入（通過insert或push_back等）會(huì)引發(fā)上面的重新分配步驟。

• resize(Container::size_type n)強(qiáng)制把容器改為容納n個(gè)元素。調(diào)用resize之后，size將會(huì)返回n。如果n小于當(dāng)前大小，容器尾部的元素會(huì)被銷毀。如果n大于當(dāng)前大小，新默認(rèn)構(gòu)造的元素會(huì)添加到容器尾部。如果n大于當(dāng)前容量，在元素加入之前會(huì)發(fā)生重新分配。

• reserve(Container::size_type n)強(qiáng)制容器把它的容量改為至少n，提供的n不小于當(dāng)前大小。這一般強(qiáng)迫進(jìn)行一次重新分配，因?yàn)槿萘啃枰黾?。（如果n小于當(dāng)前容量，vector忽略它，這個(gè)調(diào)用什么都不做，string可能把它的容量減少為size()和n中大的數(shù)，但string的大小沒有改變。在我的經(jīng)驗(yàn)中，使用reserve來從一個(gè)string中修整多余容量一般不如使用“交換技巧”，那是條款17的主題。）

這個(gè)簡介表示了只要有元素需要插入而且容器的容量不足時(shí)就會(huì)發(fā)生重新分配（包括它們維護(hù)的原始內(nèi)存分配和回收，對象的拷貝和析構(gòu)和迭代器、指針和引用的失效）。所以，避免重新分配的關(guān)鍵是使用reserve盡快把容器的容量設(shè)置為足夠大，最好在容器被構(gòu)造之后立刻進(jìn)行。

例如，假定你想建立一個(gè)容納1-1000值的vector<int>。沒有使用reserve，你可以像這樣來做：

vector<int> v;
for (int i = 1; i <= 1000; ++i)
{ 
 v.push_back(i);
}

在大多數(shù)STL實(shí)現(xiàn)中，這段代碼在循環(huán)過程中將會(huì)導(dǎo)致2到10次重新分配。（10這個(gè)數(shù)沒什么奇怪的。記住vector在重新分配發(fā)生時(shí)一般把容量翻倍，而1000約等于2^10。）

把代碼改為使用reserve，我們得到這個(gè)：

vector<int> v;
v.reserve(1000);
for (int i = 1; i <= 1000; ++i)
{
  v.push_back(i);
}

這在循環(huán)中不會(huì)發(fā)生重新分配。

在大小和容量之間的關(guān)系讓我們可以預(yù)言什么時(shí)候插入將引起vector或string執(zhí)行重新分配，而且，可以預(yù)言什么時(shí)候插入會(huì)使指向容器中的迭代器、指針和引用失效。例如，給出這段代碼，

string s;
...
if (s.size() < s.capacity()) 
{
  s.push_back('x');
}

push_back的調(diào)用不會(huì)使指向這個(gè)string中的迭代器、指針或引用失效，因?yàn)閟tring的容量保證大于它的大小。如果不是執(zhí)行push_back，代碼在string的任意位置進(jìn)行一個(gè)insert，我們?nèi)匀豢梢员ＷC在插入期間沒有發(fā)生重新分配，但是，與伴隨string插入時(shí)迭代器失效的一般規(guī)則一致，所有從插入位置到string結(jié)尾的迭代器/指針/引用將失效。

回到本條款的主旨，通常有兩情況使用reserve來避免不必要的重新分配。

• 第一個(gè)可用的情況是當(dāng)你確切或者大約知道有多少元素將最后出現(xiàn)在容器中。那樣的話，就像上面的vector代碼，你只是提前reserve適當(dāng)數(shù)量的空間。
• 第二種情況是保留你可能需要的最大的空間，然后，一旦你添加完全部數(shù)據(jù)，修整掉任何多余的容量。

4.2 使用“交換技巧”來修整vector過?？臻g/內(nèi)存

有一種方法來把它從曾經(jīng)最大的容量減少到它現(xiàn)在需要的容量。這樣減少容量的方法常常被稱為“收縮到合適（shrink to fit）”。該方法只需一條語句：vector<int>(ivec).swap(ivec);

表達(dá)式vector<int>(ivec)建立一個(gè)臨時(shí)vector，它是ivec的一份拷貝：vector的拷貝構(gòu)造函數(shù)做了這個(gè)工作。但是，vector的拷貝構(gòu)造函數(shù)只分配拷貝的元素需要的內(nèi)存，所以這個(gè)臨時(shí)vector沒有多余的容量。然后我們讓臨時(shí)vector和ivec交換數(shù)據(jù)，這時(shí)我們完成了，ivec只有臨時(shí)變量的修整過的容量，而這個(gè)臨時(shí)變量則持有了曾經(jīng)在ivec中的沒用到的過剩容量。在這里（這個(gè)語句結(jié)尾），臨時(shí)vector被銷毀，因此釋放了以前ivec使用的內(nèi)存，收縮到合適。

4.3 用swap方法強(qiáng)行釋放STL Vector所占內(nèi)存

template < class T> void ClearVector( vector<T>& v )
{ 
    vector<T> vtTemp;
    vtTemp.swap( v );
} 

如:

vector<int> v ;
v.push_back(1);
v.push_back(3);
v.push_back(2);
v.push_back(4);
vector<int>().swap(v);

//
v.swap(vector<int>()); 

//加大括號(hào){ }是讓tmp退出{ }時(shí)自動(dòng)析構(gòu)
{ std::vector<int> tmp = v;   v.swap(tmp);   }; 

5. Vector 內(nèi)存管理成員函數(shù)的行為測試

C++ STL的vector使用非常廣泛，但是對其內(nèi)存的管理模型一直有多種猜測，下面用實(shí)例代碼測試來了解其內(nèi)存管理方式，測試代碼如下：

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<int> iVec;
    cout << "容器 大小為: " << iVec.size() << endl;
    cout << "容器 容量為: " << iVec.capacity() << endl; //0個(gè)元素， 容器容量為0

    iVec.push_back(1);
    cout << "容器 大小為: " << iVec.size() << endl;
    cout << "容器 容量為: " << iVec.capacity() << endl; //1個(gè)元素， 容器容量為1

    iVec.push_back(2);
    cout << "容器 大小為: " << iVec.size() << endl;
    cout << "容器 容量為: " << iVec.capacity() << endl; //2個(gè)元素， 容器容量為2

    iVec.push_back(3);
    cout << "容器 大小為: " << iVec.size() << endl;
    cout << "容器 容量為: " << iVec.capacity() << endl; //3個(gè)元素， 容器容量為4

    iVec.push_back(4);
    cout << "容器 大小為: " << iVec.size() << endl;
    cout << "容器 容量為: " << iVec.capacity() << endl; //4個(gè)元素， 容器容量為4

    iVec.push_back(5);
    cout << "容器 大小為: " << iVec.size() << endl;
    cout << "容器 容量為: " << iVec.capacity() << endl; //5個(gè)元素， 容器容量為8

    iVec.push_back(6);
    cout << "容器 大小為: " << iVec.size() << endl;
    cout << "容器 容量為: " << iVec.capacity() << endl; //6個(gè)元素， 容器容量為8

    iVec.push_back(7);
    cout << "容器 大小為: " << iVec.size() << endl;
    cout << "容器 容量為: " << iVec.capacity() << endl; //7個(gè)元素， 容器容量為8

    iVec.push_back(8);
    cout << "容器 大小為: " << iVec.size() << endl;
    cout << "容器 容量為: " << iVec.capacity() << endl; //8個(gè)元素， 容器容量為8

    iVec.push_back(9);
    cout << "容器 大小為: " << iVec.size() << endl;
    cout << "容器 容量為: " << iVec.capacity() << endl; //9個(gè)元素， 容器容量為16
    /* vs2005/8 容量增長不是翻倍的，1.5 如 
       9個(gè)元素   容量9 
       10個(gè)元素 容量13
    */

    /* 測試effective stl中的特殊的交換 swap() */
    cout << "當(dāng)前vector 的大小為: " << iVec.size() << endl;
    cout << "當(dāng)前vector 的容量為: " << iVec.capacity() << endl;
    vector<int>(iVec).swap(iVec);

    cout << "臨時(shí)的vector<int>對象 的大小為: " 
        << (vector<int>(iVec)).size() << endl;
    cout << "臨時(shí)的vector<int>對象 的容量為: " 
        << (vector<int>(iVec)).capacity() << endl;
    cout << "交換后，當(dāng)前vector 的大小為: " << iVec.size() << endl;
    cout << "交換后，當(dāng)前vector 的容量為: " << iVec.capacity() << endl;

    return 0;
}

6. vector的其他成員函數(shù)

• c.assign(beg, end)：將[beg; end)區(qū)間中的數(shù)據(jù)賦值給c。
• c.assign(n, elem)：將n個(gè)elem的拷貝賦值給c。
• get_allocator：使用構(gòu)造函數(shù)返回一個(gè)拷貝。
• c.~ vector <Elem>()：銷毀所有數(shù)據(jù)，釋放內(nèi)存。

7. 備注:在用vector的過程中的一些問題，特此列出討論:

1. 此時(shí)若對b另外賦值時(shí)不會(huì)影響a[0]的值

vector <int > a;
int b = 5;
a.push_back(b);

往a向量中壓入的是b的值,即a[0]=b,此時(shí)a[0]和b是存儲(chǔ)在兩個(gè)不同的地址中的.因此改變b的值不會(huì)影響a[0]。

2. 此時(shí)輸出的值并不是一開始b數(shù)組初始化的值,而是一些無法預(yù)計(jì)的值.

vector <int*> a;
int *b;
b = new int[4];
b[0]=0;
b[1]=1;
b[2]=2;
a.push_back(b);
delete b;  //釋放b的地址空間
for(int i=0 ; i <3 ; i++)
{
   cout<<a[0][i]<<endl;
}

因?yàn)槭?strong>把一個(gè)地址(指針)壓入向量a,即a[0]=b,因此釋放了b的地址也就釋放了a[0]的地址,因此a[0]數(shù)組中存放的數(shù)值也就不得而知了.