【原创】C++ 动态数组 vector 详解

一、引入

引入：略

vector收录在STL里，是一种特殊的数据结构。它的中文名字叫做“动态数组”或者“不定长数组”，有时也被翻译成“容器”。

说白了，vector就是一个功能强大的数组。下面让我们来体验它强大的功能吧！

二、vector的头文件

vector收录在std库里，所以调用vector需要

#include

using namespace std;

这两个头文件。

三、vector的声明与构造函数

既然是“动态数组”，vector是一个什么数组呢，int？double？或者结构体数组？

我们可以这样声明一个vector：

vector
<数据类型>
动态数组名;

比如：

vector

i;//一个int的动态数组

vector

c;//一个char的动态数组

vector

n;//一个node的动态数组（node是结构体名）

如果你想赋初值，你可以：

vector

M(a,b);//在M里装a个b

vector

N(a); //在N里装a个0

当然你也可以：

vector

A;

vector

B(A);//一个和A一模一样的动态数组

vector

C(B.begin()+l,B.end()-r);//继承B动态数组
下标[l,B.end()-r)的值，注意，
下标从0开始，begin()，end()，size()三个函数见下文

四、vector的析构函数

很简单，你可以vector B;//A是某种数据结构，B是动态数组名

如果你想析构它，只需调用B.~vector (); 即可。

也就是说，vector的析构函数是：动态数组名.~vector
<该数组的数据结构>
();

五、vector的基本操作

以vector

v为例：

① v[i]或v.at(i)//返回v[i]的值

② v.size();//返回v数组元素总个数

③ v.front();//返回v数组第一个元素的值

④ v.back();//返回v数组最后一个元素的值

⑤ v.clear();//清空v数组

⑥ v.begin();//返回v数组第一个数的地址

⑦ v.end();//返回v数组最后一个数之后的地址

⑧ v.empty();//判断v数组是否为空，是空则返回1(true)，非空（有元素）则返回0(false)

⑨ v.swap(v1);//v1是另一个动态数组，将v和v1元素互换

⑩ swap(v,v1);//同⑨

注意：再次重申，vector的下标是从0开始的！

注意：除v[i]外，其余都是vector的自带函数，因此必须添上括号！

五、vector的插入

std库提供了好几种插入，这里讲最为常用的三种。

① v.push_back(a);//在v数组的尾部插入数a

比如：

有一个动态数组x:2017 2333

调用x.push_back(666);

则x:2017 2333 666

② v.insert(v.begin()+k,a);//在下标k的前面插入数a，k之后的数依次后退一位

//记住，下标是从0开始的！

比如：

动态数组x:1 2 3 4 5 6 

调用x.insert(x.begin()+2,100);

则x:1 2 100 3 4 5 6 

③ x.insert(x.begin()+k,p,a);//在下标k前面插入p个a

六、vector的删除

也有三种，

① v.pop_back()//删除最后一个元素

② v.erase(v.begin()+k);//删除下标为k的数，返回下一个位置的下标

③ v.erase(v.begin()+l,v.end()-r);//删除下标[l,v.end()-r)的元素

七、vector的内存机制

vector能装多少个元素呢？它的长度是多长呢？接下来就要简单地介绍一下vector的内存机制。

先介绍几个函数吧：

v.capacity();//返回v数组的长度，就相当于int v[20000];的20000

v.resize(k);//将v数组的长度设为k

现在让我们来研究一下vector的内存机制。

#include 
  
    #include 
   
     #include 
    
      using namespace std; const unsigned int maxn=; vector 
     
       v; int main() { //printf("%d\n",v.capacity()); //v.resize(1000); unsigned int last=v.capacity(); printf("%d\n",last); for(unsigned int i=1;i<=maxn;i++) { v.push_back(i); unsigned int a=v.capacity(); if(a!=last) { printf("%d\n",a); last=a; } } } 
      
     
    
  

这个验证程序测试了vector的长度上限，现在让我们来看看输出结果：

最后程序输出了这一行英文，然后就会崩溃。这句话的大概意思是：程序运行时申请以某种非正常的方式结束它，请联系开发团队以取得更多信息。

（也就是说，我们把vector玩爆了。）

我们来看看它的规律，我们可以发现，每一次，它的内存都翻了一倍！！

我们再来看看它什么时候翻倍。

在printf(“%d\n”,a);时，再输出此时的v.size();

此时的程序：

#include 
  
    #include 
   
     #include 
    
      using namespace std; const unsigned int maxn=; vector 
     
       v; int main() { //printf("%d\n",v.capacity()); //v.resize(1000); unsigned int last=v.capacity(); printf("%d\n",last); for(unsigned int i=1;i<=maxn;i++) { v.push_back(i); unsigned int a=v.capacity(); if(a!=last) { printf("size()=%d -> capacity()=%d\n",v.size(),a); last=a; } } } 
      
     
    
  

此时的输出结果：

（结尾还是那句英文。。。。）

我们可以看到：

设当前v.capacity()=c,v.size()=s;如果s=c+1，那么c就会加倍。

这是一个初始长度为0的动态数组，接着我们来看看初始长度不为0的情况。

此时代码：

#include 
  
    #include 
   
     #include 
    
      using namespace std; const unsigned int maxn=; const unsigned int beg=1250;//这是可修改的 vector 
     
       v; int main() { v.resize(beg); unsigned int last=v.capacity(); printf("At first , capacity() = %d\n",last); for(unsigned int i=1;i<=maxn;i++) { v.push_back(1); unsigned int a=v.capacity(); if(a!=last) { printf("size()=%d -> capacity()=%d\n",v.size(),a); last=a; } } } 
      
     
    
  

结果（只保留了一部分）：

①

②

③

多次试验后，我们可以得出结论：

当动态数组内的元素比动态数组长度多一时，动态数组长度翻倍！

也就是说：if(v.size()-1==v.capacity()) v.resize(v.capacity()*2);

而长度翻倍是很花时间的。所以说做题的时候，记得事先把vector的长度拉得足够长，以免运行的时候，vector长度翻倍浪费时间。

最后一个问题，vector最多能装多少个元素呢？

我们可以用函数：

v.max_size();

来得到。

下列是一个常用的数据结构对应的max_size();

bool ->

char ->

int->

unsigned int ->

float ->

double->

long long ->

unsigned long long ->