vector容器

$vector$是种容器，类似数组一样，但它可以动态改变长度。
$vector$上的常见操作复杂度（效率）如下：

• 随机访问元素->常数$O(1)$
• 在末尾插入或移除元素->均摊常数$O(1)$
• 非末尾插入或移除元素->与到$vector$结尾的距离成线性$O(n)$，跟数组一样，插入删除会造成大量数据移动。

不罗列所有的用法，只学习常用的方法。

一、vector初始化

1.当成数组用法

vector<int> a(20); //定义20个元素
for(int i = 0; i < a.size(); i++) //输入
	cin>>a[i];

for(int i = 0; i < a.size(); i++) //输出
	cout<<a[i]<<" ";

2.初始化为固定值

vector<int> a(5,1);

3.从其他vector复制一段

vector<int> b(5,1);
vector<int> a(b.begin(),b.begin()+3);

其中b.begin()表示b容器的第一个元素地址，b.begin()+3表示选取$3$个。
相应的，end()表示最后一个元素的后一个地址，一般表示结束。
4.动态用法

//假设a容器保存偶数
vector<int> a;
cin>>n;
for(int i = 1; i <= n; i++){
	int x;
	cin>>x;
	if(x%2==0) a.push_back(x);
}

二、遍历写法

前面已经有一种遍历写法了，$vector$容器下标从0开始，所以类似$string$写法。
1.下标遍历写法1

for(int i = 0; i < a.size(); i++)

2.c++11写法

for(auto x: a){
	cout<<x<<" ";
}

如果不需要用到下标，建议用$c++11$用法。

三、二维vector容器

图论中模拟链接表可以用二维$vector$容器保存。

vector<int> G[10005];  //比如有10000个顶点

无向图保存

for(int i = 1; i <= m; i++){
	cin>>x>>y;
	G[x].push_back(y);
	G[y].push_back(x);
}

属性及操作 (简单了解即可)

Iterators

Capacity

Element access

Modifiers

Allocator