目录
引入
常见用法介绍
1. vector的定义
2. vector容器内元素的访问
3. vector常用函数实例解析
1）push_back()
2）pop_back()
3）size()
4）clear()
5）insert()
6）erase()
vector的常见用途
1. 存储数据
2. 用邻接表存储图
引入
vector翻译为向量，但你可以理解为“变长数组”，即vector会根据长度需要而自动改变。在算法题目中，会碰到只用普通数组会超内存的情况，这个时候vector的运用会使问题的解决便捷很多。另外，vector还可以用来以邻接表的方式存储图，这对无法使用邻接矩阵的题目（结点数太多）、以及害怕用指针实现邻接表的读者十分友好。
如果要使用vector，需要添加vector头文件，即#include<vector>。如果你之前只有C语言编程经验，记得在头文件下面添加一句using namespace std;
常见用法介绍
1. vector的定义
单独定义一个vector：
vector<typename> name;
上面这个定义相当于是一维数组name[SIZE]，不过其长度可以根据需要进行变化，比较节省空间。说白了就是“变长数组”。
关于typename，可以是任何基本类型，如int, char, double, 结构体，也可以是其他STL容器。
需要注意的是，如果typename是STL容器（带<>），定义的时候需要在>>之间加上空格，因为一些使用C++11之前标准的编译器会将它当成移位操作，导致编译错误。
示例如下：
vector<int> name;
vector<char> name;
//如果typename是STL容器，>>需要加空格
vector<vector<int> >name;
读者不难发现，示例三给出了vector二维数组的定义，你可以简单理解为两个维度都可以变长的二维数组。
然后来看定义vector数组的方法：
vector<typename> Arrayname[arraySize];
这样Arrayname[0]~Arrayname[arraySize-1]中每一个都是一个vector容器。
与vector<vector<int> > name不同的是，这种写法的一位长度已经固定为arraySize，另一维才是“变长”的。
2. vector容器内元素的访问
这里引入一个概念——迭代器。迭代器（iterator）可以理解为一种类似指针的东西，定义为：
vector<typename>::iterator it;
这样it就是一个vector<typename>::iterator型的变量，typename为定义vector时填写的类型。
vector<int>::iterator it;
//typename为int
vector<double>::iterator it;
//typename为double
这样，我们就得到了迭代器it，并且可以通过*it来访问vector里的元素。
例如，有这样定义的一个vector容器：
vector<int>vi;
for(int i = 1; i <= 5; i++){
vi.push_back(i);
//push_back(i)在vi的末尾添加元素i
}
//循环结束后vi中元素有1 2 3 4 5
那我们可以通过类似下标和指针访问数组的方式来访问容器内的元素：
#include <iostream>
#include <vector>
using namespace std;
int main(){
vector<int> vi;
for(int i = 1; i <= 5; i++){
vi.push_back(i);
}
//vi.begin()为取vi的首元素地址，而it指向这个地址
vector<int>::iterator it = vi.begin();
for(int i = 0; i < 5; i++){
printf("%d ", *(it+i));
}
return 0;
}
/*
result:
1 2 3 4 5
*/
从这里看出，vi[i]和*(vi.begin()+i)是等价的。
既然上面说到了begin()函数的作用为取vi的首元素地址，那么还需要提到end()函数。与begin()不同的是，end()并不是取vi的尾元素地址，而是取尾元素地址的下一个地址。end()作为迭代器末尾标志，不存储任何元素。
除此之外，迭代器还实现了两种自加操作：++it和it++（自减操作同理），于是有了另一种遍历vector元素的方法。
#include <iostream>
#include <vector>
using namespace std;
int main(){
vector<int> vi;
for(int i = 1; i <= 5; i++){
vi.push_back(i);
}
//vector的迭代器不支持it < vi.end()写法，改用!=作为循环条件
for(vector<int>::iterator it = vi.begin(); it != vi.end(); it++){
printf("%d ", *it);
}
return 0;
}
/*
result:
1 2 3 4 5
*/
最后需要指出，在常见STL容器中，只有在vector和string中，才允许使用vi.begin() + 3这种迭代器加上整数的做法。
3. vector常用函数实例解析
1）push_back()
顾名思义，push_back(i)就是在vector后面加一个元素i，时间复杂度为O(1)。
示例如下：
#include <iostream>
#include <vector>
using namespace std;
int main(){
vector<int> vi;
for(int i = 1; i <= 3; i++)
vi.push_back(i);
for(int i = 0; i < vi.size(); i++)
cout<<vi[i]<<" ";
//size()函数会给出vi中元素的个数
return 0;
}
/*
result: 1 2 3
*/
2）pop_back()
有添加就会有删除，pop_back()用于删除vector的尾元素，时间复杂度为O(1)。
示例如下：
#include <iostream>
#include <vector>
using namespace std;
int main(){
vector<int> vi;
for(int i = 1; i <= 3; i++)
vi.push_back(i); //将1 2 3依次插入vi末尾
vi.pop_back(); //删除vi的尾元素3
for(int i = 0; i < vi.size(); i++)
cout<<vi[i]<<" ";
//size()函数会给出vi中元素的个数
return 0;
}
/*
result: 1 2
*/
3）size()
size()用来获得vector中元素的个数，时间复杂度为O(1)。size()返回的是unsigned类型，不过一般来说用%d问题不大，这一点对于所有STL容器都是一样的。
示例如下：
#include <iostream>
#include <vector>
using namespace std;
int main(){
vector<int> vi;
for(int i = 1; i <= 3; i++)
vi.push_back(i); //将1 2 3依次插入vi末尾
cout<<vi.size()<<endl;
return 0;
}
/*
result: 3
*/
4）clear()
clear()用于清空vector中所有的元素，时间复杂度为O(N)，N为vector中元素的个数。
示例如下：
#include <iostream>
#include <vector>
using namespace std;
int main(){
vector<int> vi;
for(int i = 1; i <= 3; i++)
vi.push_back(i); //将1 2 3依次插入vi末尾
vi.clear();
cout<<vi.size()<<endl;
return 0;
}
/*
result: 0
*/
5）insert()
insert(it, x)用来向vector的任意一个迭代器it处插入一个元素x，时间复杂度为O(N)。
示例如下：
#include <iostream>
#include <vector>
using namespace std;
int main(){
vector<int> vi;
for(int i = 1; i <= 5; i++)
vi.push_back(i); //将1 2 3 4 5依次插入vi末尾
vi.insert(vi.begin() + 2, -1); //将-1插入vi[2]的位置
for(int i = 0; i < vi.size(); i++)
cout<<vi[i]<<" ";
return 0;
}
/*
result: 1 2 -1 3 4 5
*/
6）erase()
erase()有两种用法：删除单个元素，删除一个区间内的所有元素。时间复杂度均为O(N)。
删除单个元素：
erase(it)即为删除迭代器为it处的元素。
示例如下：
#include <iostream>
#include <vector>
using namespace std;
int main(){
vector<int> vi;
for(int i = 1; i <= 5; i++)
vi.push_back(i); //将1 2 3 4 5依次插入vi末尾
vi.erase(vi.begin() + 2); //删除位于vi[2]处的元素
for(int i = 0; i < vi.size(); i++)
cout<<vi[i]<<" ";
return 0;
}
/*
result: 1 2 4 5
*/
删除一个区间内的所有元素：
erase(first, last)即删除[first, last)内的所有元素。
示例如下：
#include <iostream>
#include <vector>
using namespace std;
int main(){
vector<int> vi;
for(int i = 1; i <= 5; i++)
vi.push_back(i); //将1 2 3 4 5依次插入vi末尾
vi.erase(vi.begin() + 2, vi.begin() + 4);
//删除vi[2], vi[3]
for(int i = 0; i < vi.size(); i++)
cout<<vi[i]<<" ";
return 0;
}
/*
result: 1 2 5
*/
由上面的说法可以知道，如果要删除这个vector内的所有元素，正确的写法是vi.erase(vi.begin(), vi.end())，正如前面所说，vi.end()指向尾元素地址的下一个地址。（当然，更简便的操作是使用vi.clear()）。
vector的常见用途
1. 存储数据
vector本身可以作为变长数组来使用，而且在一些元素不确定的场合可以很好的节省空间
2. 用邻接表存储图
使用vector实现邻接表可以避免使用指针
