C++ vector類詳解

轉自http://blog.csdn.net/whz_zb/article/details/6827999

?

vector簡介

?????? vector是STL中最常見的容器，它是一種順序容器，支持隨機訪問。vector是一塊連續分配的內存，從數據安排的角度來講，和數組極其相似，不同的地方就是：數組是靜態分配空間，一旦分配了空間的大小，就不可再改變了；而vector是動態分配空間，隨著元素的不斷插入，它會按照自身的一套機制不斷擴充自身的容量。

??????? vector的擴充機制：按照容器現在容量的一倍進行增長。vector容器分配的是一塊連續的內存空間，每次容器的增長，并不是在原有連續的內存空間后再進行簡單的疊加，而是重新申請一塊更大的新內存，并把現有容器中的元素逐個復制過去，然后銷毀舊的內存。這時原有指向舊內存空間的迭代器已經失效，所以當操作容器時，迭代器要及時更新。

vector的數據結構

??????? vector數據結構，采用的是連續的線性空間，屬于線性存儲。他采用3個迭代器_First、_Last、_End來指向分配來的線性空間的不同范圍，下面是聲明3個迭代器變量的源代碼。

template<class _Ty, class _A= allocator< _Ty> > 

class vector{ 

    ... 

    protected: 

    iterator _First, _Last, _End; 

};

_First指向使用空間的頭部，_Last指向使用空間大小（size）的尾部，_End指向使用空間容量（capacity）的尾部。例如：

int data[6]={3,5,7,9,2,4}; 

vector<int> vdata(data, data+6); 

vdata.push_back(6); 

...

vector初始化時，申請的空間大小為6，存放下了data中的6個元素。當向vdata中插入第7個元素“6”時，vector利用自己的擴充機制重新申請空間，數據存放結構如圖1所示：

?

圖1 擴充后的vector內存結構

??????? 簡單描述一下。當插入第7個元素“6”時，vector發現自己的空間不夠了，于是申請新的大小為12的內存空間（自增一倍），并將前面已有數據復制到新空間的前部，然后插入第7個元素。此時_Last迭代器指向最后一個有效元素，而_End迭代器指向vector的最后有效空間位置。我們利用vector的成員函數size可以獲得當前vector的大小，此時為7；利用capacity成員函數獲取當前vector的容量，此時為12。

vector容器類型

vector容器是一個模板類，可以存放任何類型的對象（但必須是同一類對象）。vector對象可以在運行時高效地添加元素，并且vector中元素是連續存儲的。

vector的構造

函數原型：

template<typename T>
?? explicit vector();???????????????????????????????? // 默認構造函數，vector對象為空
?? explicit vector(size_type n, const T& v = T());??? // 創建有n個元素的vector對象
?? vector(const vector& x);
?? vector(const_iterator first, const_iterator last);

注：vector容器內存放的所有對象都是經過初始化的。如果沒有指定存儲對象的初始值，那么對于內置類型將用0初始化，對于類類型將調用其默認構造函數進行初始化（如果有其它構造函數而沒有默認構造函數，那么此時必須提供元素初始值才能放入容器中）。

舉例：
vector<string> v1;???????? // 創建空容器，其對象類型為string類
vector<string> v2(10);???? // 創建有10個具有初始值（即空串）的string類對象的容器
vector<string> v3(5, "hello"); // 創建有5個值為“hello”的string類對象的容器
vector<string> v4(v3.begin(), v3.end());? // v4是與v3相同的容器（完全復制）

vector的操作（下面的函數都是成員函數）
?
bool empty() const;??????????????????? // 如果為容器為空，返回true；否則返回false
size_type max_size() const;??????????? // 返回容器能容納的最大元素個數
size_type size() const;??????????????? // 返回容器中元素個數??
size_type capacity() const;??????????? // 容器能夠存儲的元素個數，有：capacity() >= size()??
void reserve(size_type n);???????????? // 確保capacity() >= n
void resize(size_type n, T x = T());?? // 確保返回后，有：size() == n；如果之前size()<n，那么用元素x的值補全。

reference front();???????????????????? // 返回容器中第一個元素的引用（容器必須非空）
const_reference front() const;???????????????????
reference back();????????????????????? // 返回容器中最后一個元素的引用（容器必須非空）
const_reference back() const;

reference operator[](size_type pos);?? // 返回下標為pos的元素的引用（下標從0開始；如果下標不正確，則屬于未定義行為。
const_reference operator[](size_type pos) const;?
reference at(size_type pos);?????????? // 返回下標為pos的元素的引用；如果下標不正確，則拋出異常out_of_range
const_reference at(size_type pos) const;
????????????
void push_back(const T& x);??????????? // 向容器末尾添加一個元素??????????
void pop_back();?????????????????????? // 彈出容器中最后一個元素（容器必須非空）

// 注：下面的插入和刪除操作將發生元素的移動（為了保持連續存儲的性質），所以之前的迭代器可能失效
iterator insert(iterator it, const T& x = T());??????? // 在插入點元素之前插入元素（或者說在插入點插入元素）
void insert(iterator it, size_type n, const T& x);???? // 注意迭代器可能不再有效（可能重新分配空間）
void insert(iterator it, const_iterator first, const_iterator last);

iterator erase(iterator it);?????????? // 刪除指定元素，并返回刪除元素后一個元素的位置（如果無元素，返回end()）
iterator erase(iterator first, iterator last); // 注意：刪除元素后，刪除點之后的元素對應的迭代器不再有效。

void clear() const;??????????????????? // 清空容器，相當于調用erase( begin(), end())

void assign(size_type n, const T& x = T());?? // 賦值，用指定元素序列替換容器內所有元素
void assign(const_iterator first, const_iterator last);

const_iterator begin() const;????????? // 迭代序列
iterator begin();
const_iterator end() const;
iterator end();

const_reverse_iterator rbegin() const;
reverse_iterator rbegin();
const_reverse_iterator rend() const;?
reverse_iterator rend();

vector對象的比較（非成員函數）

針對vector對象的比較有六個比較運算符：operator==、operator!=、operator<、operator<=、operator>、operator>=。

其中，對于operator==和operator!=，如果vector對象擁有相同的元素個數，并且對應位置的元素全部相等，則兩個vector對象相等；否則不等。

對于operator<、operator<=、operator>、operator>=，采用字典排序策略比較。

注：其實只需要實現operator==和operator!=就可以了，其它可以根據這兩個實現。因為，operator!= (lhs, rhs) 就是 !(lhs == rhs)，operator<=(lhs, rhs) 就是 !(rhs < lhs)，operator>(lhs, rhs) 就是 (rhs < lhs)，operator>=（lhs, rhs) 就是 !(lhs, rhs)。

vector類的迭代器

?? vector類的迭代器除了支持通用的前綴自增運算符外，還支持算術運算：it + n、it - n、it2 - it1。注意it2 - it1返回值為difference_type（signed類型）。

注意，任何改變容器大小的操作都可能造成以前的迭代器失效。

應用示例

?

1.vector 的數據的存入和輸出：

#include<stdio.h>
#include<vector>
#include <iostream>

using namespace std;

void main()

{

?? int i = 0;

??? vector<int> v;

??? for( i = 0; i < 10; i++ )

?? {

???????????? v.push_back( i );//把元素一個一個存入到vector中

?? }

?? for( i = 0; i < v.size(); i++ )//v.size() 表示vector存入元素的個數

?? {

????????? cout << v[?i ] << "? "; //把每個元素顯示出來

?? }

?? cout << endl;

}?

注：你也可以用v.begin()和v.end() 來得到vector開始的和結束的元素地址的指針位置。你也可以這樣做：

vector<int>::iterator iter;

for( iter = v.begin(); iter != v.end(); iter++ )

{
??? cout << *iter << endl;
}

2. 對于二維vector的定義。

1)定義一個10個vector元素，并對每個vector符值1-10。

#include<stdio.h>
#include<vector>
#include <iostream>

using namespace std;

void main()
{
?int i = 0, j = 0;

//定義一個二維的動態數組，有10行，每一行是一個用一個vector存儲這一行的數據。

所以每一行的長度是可以變化的。之所以用到vector<int>(0)是對vector初始化，否則不能對vector存入元素。
?vector< vector<int> > Array( 10, vector<int>(0) );?

for( j = 0; j < 10; j++ )
?{
??for ( i = 0; i < 9; i++ )
??{
???Array[ j ].push_back( i );
??}
?}

?for( j = 0; j < 10; j++ )
?{
??for( i = 0; i < Array[ j ].size(); i++ )
??{
???cout << Array[ j ][ i ] << "? ";
??}
??cout<< endl;
?}
}

2)定義一個行列都是變化的數組。

#include<stdio.h>
#include<vector>
#include <iostream>

using namespace std;

void main()
{
?int i = 0, j = 0;

?vector< vector<int> > Array;
?vector< int > line;
?for( j = 0; j < 10; j++ )
?{
??Array.push_back( line );//要對每一個vector初始化，否則不能存入元素。
??for ( i = 0; i < 9; i++ )
??{
???Array[ j ].push_back( i );
??}
?}

?for( j = 0; j < 10; j++ )
?{
??for( i = 0; i < Array[ j ].size(); i++ )
??{
???cout << Array[ j ][ i ] << "? ";
??}
??cout<< endl;
?}
}

3.綜合一點的例子。

#include <iostream>
#include <cassert>
#include <vector>


using namespace std;


int main()
{
? ? vector<int> v(5, 1);
? ? vector<int> v2(v.begin(), v.end());
? ??
? ? assert(v == v2);
? ??
? ? cout<<"> Before operation"<<endl;
? ? for(vector<int>::const_iterator it = v.begin(); it < v.end(); ++it)
? ? ? ? cout<<*it<<endl;


? ? //v.insert(v.begin() + 3, 4, 2);


? ? v.insert(v.begin() + 3, 1, 2);
? ? v.insert(v.begin() + 4, 1, 3);
? ? v.insert(v.begin() + 5, 1, 4);

? ? v.insert(v.begin() + 6, 1, 5);

? ? cout<<"> After insert"<<endl;
? ? for(vector<int>::size_type i = 0; i < v.size(); ++i)
? ? ? ? cout<<v[i]<<endl;
? ??
? ? vector<int>::iterator it1 = v.erase(v.begin() + 3, v.begin() + 6);//刪除的是第4，5，6三個元素
? ? assert(*it1 == 5);
? ? cout<<"> After erase"<<endl;
? ? for(vector<int>::size_type j = 0; j != v.size(); ++j)
? ? ? ? cout<<v[j]<<endl;
? ??
? ? assert(v.begin() + v.size() == v.end());
? ? assert(v.end() - v.size() == v.begin());
? ? assert(v.begin() - v.end() == -vector<string>::difference_type(v.size()));
? ??
? ? return 0;
}

程序說明：上面第3個程序中用了三個循環輸出容器中的元素，每個循環的遍歷方式是不一樣的。特別需要說明的是，第二個循環在條件判斷中使用了size() 函數，而不是在循環之前先保存在變量中再使用。之所以這樣做，有兩個原因：其一，如果將來在修改程序時，在循環中修改了容器元素個數，這個循環仍然能很好 地工作，而如果先保存size()函數值就不正確了；其二，由于這些小函數（其實現只需要一條返回語句）基本上都被聲明為inline，所以不需要考慮效率問題。

?

?

附錄1

?

?

vector是一個標準庫中的容器，使用時需要包含#include <vector>頭文件。

?

vector是一個類模板而不是一種數據類型，對它的定義，需要指定類型。

vector(向量)是 C++中的一種數據結構,確切的說是一個類.它相當于一個動態的數組,

當程序員無法知道自己需要的數組的規模多大時,用其來解決問題可以達到最大節約空間的目的.

?

1、vector對象的定義和初始化

vector類定義了好幾種構造函數，并且與string類型相類似，如下所示：

操作調用方式	操作說明
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個副本

?

注：對C++的容器來說，動態添加元素的效率，要比直接靜態初始化元素的效率高

?

例1.1 :聲明一個int向量以替代一維的數組:vector <int> a;(等于聲明了一個int數組a[],大小沒有指定,可以動態的向里面添加刪除)。

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

?

?

備注:

在用vector的過程中我碰到了一個問題,特此列出討論:

???????????????????? 1)

???????????????????? vector <int > a;

???????????????????? int b = 5;

???????????????????? a.push_back(b);

???????????????????? 此時若對b另外賦值時不會影響a[0]的值

???????????????????? 2)

????????????????????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;
????????????????????? }

????????????????????? 此時輸出的值并不是一開始b數組初始化的值,而是一些無法預計的值.

???????????????????? 分析:根據1) 2)的結果,可以想到,在1)中,?? 往a向量中壓入的是b的值,即a[0]=b,此時a[0]和b是存儲在兩個不同的地址中的.因此改變b的值不會影響a[0];而在2)中,因為是把一個地址(指針)壓入向量a,即a[0]=b,因此釋放了b的地址也就釋放了a[0]的地址,因此a[0]數組中存放的數值也就不得而知了. ? ? ??

?

2、vector對象的操作

vector標準庫提供了許多類似于string對象的操作，如下所示是一部分：

操作調用方式	操作說明
v.empty()	判斷v是否為空
v.size()	返回v中元素的個數
v.push_back(t)	向v的末尾添加一個元素
V[n]	返回v中位置為n的元素
V1 = v2	把v1中元素替換為v2中元素副本
V1==v2	判斷是否相等
!=, <, <=, >, >=	直接用于vector對象的相互比較

?

1.push_back?? 在數組的最后添加一個數據
2.pop_back??? 去掉數組的最后一個數據?
3.at??????????????? 得到編號位置的數據
4.begin?????????? 得到數組頭的指針
5.end???????????? 得到數組的最后一個單元+1的指針
6．front??????? 得到數組頭的引用
7.back??????????? 得到數組的最后一個單元的引用
8.max_size???? 得到vector最大可以是多大
9.capacity?????? 當前vector分配的大小
10.size?????????? 當前使用數據的大小
11.resize???????? 改變當前使用數據的大小，如果它比當前使用的大，者填充默認值
12.reserve????? 改變當前vecotr所分配空間的大小
13.erase???????? 刪除指針指向的數據項
14.clear????????? 清空當前的vector
15.rbegin??????? 將vector反轉后的開始指針返回(其實就是原來的end-1)
16.rend????????? 將vector反轉構的結束指針返回(其實就是原來的begin-1)
17.empty??????? 判斷vector是否為空
18.swap???????? 與另一個vector交換數據

注，以下是一些需要注意的地方

??vector和string一樣，長度、下標等類型是size_type，但是vector獲取size_type時，需要指定類型，如vector<int>::size_type這樣的方式

??vector的下標操作，例如v[i]，只能用于操作已經存在的元素，可以進行覆蓋、獲取等，但是不能通過v[i++]這種方式來給一個vector容器添加元素，該功能需要用push_back操作完成，下標不具備該功能

??C++程序員習慣優先使用！=而不是<來編寫循環判斷條件

?

?

附錄2

?

C++ vector 排序

C++中當 vector 中的數據類型為基本類型時我們調用std::sort函數很容易實現 vector中數據成員的升序和降序排序，然而當vector中的數據類型為自定義結構體類型時，我們該怎樣實現升序與降序排列呢？有兩種方法，下面的例子能很好的說明： 方法1：
我們直接來看代碼吧，比較簡單，容易理解：
#include “stdafx.h”
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;
struct AssessTypeInfo
{
unsigned int m_uiType; //類型ID
char m_szName[64]; //類型名稱
unsigned int m_uiTotal; //總分數

bool operator < (const AssessTypeInfo& rhs ) const //升序排序時必須寫的函數
{
return m_uiType < rhs.m_uiType;
}
bool operator > (const AssessTypeInfo& rhs ) const //降序排序時必須寫的函數
{
return m_uiType > rhs.m_uiType;
}
}
int main()
{
vector<AssessTypeInfo > ctn ;

AssessTypeInfo a1;
a1.m_uiType=1;
AssessTypeInfo a2;
a2.m_uiType=2;

AssessTypeInfo a3;
a3.m_uiType=3;

ctn.push_back(a1);
ctn.push_back(a2);
ctn.push_back(a3);
//升序排序
sort(ctn.begin(), ctn.end(),less<AssessTypeInfo>()) ; //或者sort(ctn.begin(), ctn.end()) 默認情況為升序

for ( int i=0; i<3; i++ )
printf(”%d\n”,ctn[i].m_uiType);

//降序排序
sort(ctn.begin(), ctn.end(),greater<AssessTypeInfo>()) ;

for ( int i=0; i<3; i++ )
printf(”%d\n”,ctn[i].m_uiType);

return 0 ;
}
以上方法就可以實現升序排序，輸出結果為 1 2 3
降序排序結果3 2 1。
方法2 ： 不修改結構體或類的定義部分，我們用函數對象來實現：
#include “stdafx.h”
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;
struct AssessTypeInfo
{
unsigned int m_uiType; //類型ID
char m_szName[64]; //類型名稱
unsigned int m_uiTotal; //總分數
};

bool lessmark(const AssessTypeInfo& s1,const AssessTypeInfo& s2)
{
return s1.m_uiType < s2.m_uiType;
}
bool greatermark(const AssessTypeInfo& s1,const AssessTypeInfo& s2)
{
return s1.m_uiType > s2.m_uiType;
}
int main()
{
vector<AssessTypeInfo > ctn ;

AssessTypeInfo a1;
a1.m_uiType=1;
AssessTypeInfo a2;
a2.m_uiType=2;

AssessTypeInfo a3;
a3.m_uiType=3;

ctn.push_back(a1);
ctn.push_back(a2);
ctn.push_back(a3);

sort(ctn.begin(), ctn.end(),lessmark) ; //升序排序

for ( int i=0; i<3; i++ )
printf(”%d\n”,ctn[i].m_uiType);

sort(ctn.begin(), ctn.end(),greatermark) ; //降序排序

return 0 ;
}

以上方法就可以實現升序排序，輸出結果為 1 2 3
降序排序結果3 2 1。
方法2是一種比較簡單的方法。
以上兩種方法您可根據您自己的需求選擇，并且以上兩種方法在VC++6.0環境下編譯通過，也是自己在實踐過程中的總結，如有不妥的地方，歡迎您指出，至于為什么這樣使用，請參考 stl算法中sort 部分。

(6)C++ Vector排序

vector<?int?>?vi?;? ?
vi.push_back(1); ?
vi.push_back(3); ?
vi.push_back(0); ?
sort(vi.begin()?,?vi.end());?///?/小到大 ?
reverse(vi.begin(),vi.end())?///?從大道小?

(7)順序訪問

vector?<?int?>?vi?;? ?
for(?int?i?=?0?;?i?<?10?;?i?++) ?
{ ?
vector.push_back(i); ?
}? ?
for(int?i?=?0?;?i?<?10?;?i?++)?///?第一種調用方法 ?
{ ?
cout?<<vector[i]?<<"?"?;? ?
} ?
for(vector<int>::iterator?it?=?vi.begin()?;?
it?!=vi.end()?;?it++)?///第二種調用方法 ?
{ ?
cout?<<?*it?<<?"?"?; ?
}?

(8)尋找

vector?<?int?>?vi?;? ?
for(?int?i?=?0?;?i?<?10?;?i?++) ?
{ ?
vector.push_back(i); ?
}? ?
vector?<?int?>::interator?it?=?find(vi.begin()?,?vi.end,3)?; ?
cout?<<?*it?<<?endl?;?///返回容器內找到值的位置。?

(9)使用數組對C++ Vector進行初始化

int?i[10]?={1,2,3,4,5,6,7,78,8}?; ?
///第一種? ?
vector<int>?vi(i+1,i+3);?///從第2個元素到第三個元素 ?
for(vector?<int>::interator?it?=?vi.begin()?;?
it?!=?vi.end()?;?it++) ?
{ ?
cout?<<?*it?<<"?"?;? ?
}?

(10) 結構體類型

struct?temp ?
{ ?
public?: ?
string?str?;? ?
public?: ?
int?id?; ?
}tmp ?
int?main() ?
{ ?
vector?<temp>?t?;? ?
temp?w1?;? ?
w1.str?=?"Hellowor"?; ?
w1.id?=?1?;? ?
t.push_back(t1); ?
cout?<<?w1.str?<<?","?<<w1.id?<<endl?;? ?
return?0?;? ?
}?