vector(向量)类

声明

#include <vector>
vector<int> v;//相当于长度动态变化的一维(int)数组
vector<int> v(10);//相当于长度现在为10但仍然动态变化的一维(int)数组
vector<int> v[Max];//相当于长度动态变化的二维数组
struct node{
    int v,w;
};
vector<node> v;//相当于长度动态变化的自定义数组
vector<int>::iterator it;//一个保存int的vector的迭代器
//迭代器就像STL容器的指针,并可以用"*"(星号)操作解除引用

特点

支持随机访问
节省空间

用法

函数	用途	时间复杂度
size()	返回 vector 的实际长度,即元素个数	(Theta(1))
empty()	返回 bool 型判断 vector 是否为空	(Theta(1))
push_back(x)	把元素 x 插入vector 的尾部	(Theta(1))
pop_back()	删除 vector 最后一个元素	(Theta(1))
begin()	返回第一个元素迭代器若 vector 非空 *a.begin()等效于a[0]	(Theta(1))
end()	返回最后一个元素迭代器若 vector 非空 *a.end()等效于a[a.size()] 此时二者越界访问	(Theta(1))
front()	返回第一个元素等效于a[0]和*a.begin()	(Theta(1))
back()	返回最后一个元素等效于*--a.end()和a[a.size()-1]	(Theta(1))
clear()	清空所有元素	(Theta(n))

用途

用 vector 代替邻接表存图

const int N=100010;
vector<int> v[N],edge[N];

void add(int x,int y,int z) {
    v[x].push_back(y);
    edge[x].push)back(z);
}

for (int i=0; i<v[x}.size(); i++) {
    int y=v[x][i],z=edge[x][i];
}