#include

vector可理解为变长数组，它的内部实现基于倍增思想。按照下列思路可以大致实现一个vector: 设 n,m 为vector 的实际长度和最长长度。向vector加入元素前，若 $n=m$ ,则在内存中申请 $2m$ 的连续空间，并把内容转移到新的地址上（同时释放旧的空间），再执行插入。 从 vector 中删除元素后，若 $n \leq \frac{m}{4}$,则释放一半的空间。

vector 支持随机访问，即对于任意的下标 $0\leq i < n$，就可以像数组一样用 $[i]$ 取值。但它不是链表，不支持在任意位置 $O(1)$ 插入。为了保证效率，元素的增删一般应该在末尾进行。

声明

#include<vector>  //头文件
vector<int> a;    //相当于一个长度动态变化的int数组
vector<int> b[101]; //相当于第一维长度101，第二维长度动态变化的int数组
struct node{...};
vector<node> c;  //自定义的结构体类型也可以保存在vector中

size()/empty()

size 函数返回vector的实际长度（包含的元素个数），empty函数返回一个bool类型，表明vector是否为空。二者的时间复杂度都是$O(1)$.

所有的STL容器都支持这两个方法，含义也都相同，之后我们就不再重复给出。

clear()

clear函数把vector清空。

迭代器

迭代器就像STL容器的"指针"，可以用星号“*”操作符解除引用。

一个保存int的vector的迭代器声明方法为：

vector<int>::iterator it;

vector 的迭代器是“随机访问迭代器”，可以把vector的迭代器与一个整数相加减，其行为和指针的移动类似。可以把vector的两个迭代器相减，其结果也和指针相减类似，得到两个迭代器对应下标之间的距离。

begin()/end()

begin函数返回指向vector中第一个元素的迭代器。例如 a 是一个非空的vector，则*a.begin()与a[0]的作用相同。

所有容器都可以视作一个“前闭后开”的结构，end 函数返回 vector 的尾部，即第 n 个元素再往后的“边界”。*a.end() 与 a[n] 都是越界访问，其中 n=a.size()

下面两份代码都遍历了 vector<int>a ,并输出它的所有元素。

for(int i=0;i<a.size();i++)
      cout<<a[i]<<'\n';
for(vector<int>::iterator it=a.begin();it!=a.end();it++)
      cout<<*it<<'\n';
//C++11之后
for(int x : a )
     cout<<x<<'\n';
for(auto x=a.begin();x!=a.end();x++)
     cout<<*x<<'\n';

front()/back()

front 函数返回 vector 的第一个元素，等价于 *a.begin() 和 a[0].

back 函数返回 vector 的最后一个元素，等价于 *--a.end() 和 a[a.size()-1]

push_back()/pop_back()

a.push_back(x) 把元素 x 插入到 vector a 的尾部。

a.pop_back() 删除 vector a 的最后一个元素。

【实例】用 vector 代替邻接表保存有向图

const int MAX_EDGES=100010; //边数量
vector<int>ver[MAX_EDGES],dis[MAX_EDGES];   //ver 保存顶点编号 dis保存边权
//保存从 from 到 to 边权为 d 的有向边 
void add(int from,int to,int d)
{
	ver[from].push_back(to);
	dis[from].push_back(d); 
}
//遍历从x出发的所有边
for(int i=0;i < ver[x].size();i++)
{
	int y=ver[x][i],d=dis[x][i];
	//有向边(x,y,d)...
	
}

学习完毕

{{ select(1) }}

• YES
• NO