NOIP学习小站一、vector简介
STL容器中的vector是一种顺序性容器。vector和数组相似，但其大小可以不预先指定，并且能自动扩展。vector容器内存储的元素可以像数组元素一样访问和赋值，可以将vector看作是“动态数组”。
在创建一个vector后，会自动在内存中分配一块连续的内存空间存储它的元素，初始的空间大小可以预先指定也可以由vector默认指定。当存储的数据超过分配的空间时，vector会重新分配一块内存块来存储数据（扩容），但这样的分配会额外耗费时间，在重新分配空间时会自动执行下面的操作：
- 首先，vector会申请一块更大的内存块；
- 然后，将原来的数据拷贝到新的内存块中；
- 其次，销毁掉原内存块中的对象（调用对象的析构函数）；
- 最后，将原来的内存空间释放掉。
如果vector保存的数据量很大时，这样的操作会降低性能。所以说，vector不是在什么情况下性能都好，只有在预先知道它大小的情况下，vector的性能才是最优的。
vector的特点：
- vector的元素在内存中是连续存储的，并且vectore的空间可以动态扩展。可以在vector的内部或者末尾插入、删除元素，在内部进行插入、删除操作效率低，在末尾进行追加和删除操作效率高；
- 随机访问方便， vector的元素可以像数组元素一样随机访问，支持 [ ] 操作符，还支持at()成员函数；
- 节省空间，相比开一个很大的数组，vector的数据存储区域没有浪费情况（其实vector 大多情况下并不是满存的，未存储的区域也存在浪费情况，但是比起开大数组存储效率高）；
- 当动态添加的数据超过vector默认分配的大小时要进行内存的重新分配、拷贝与释放，这个操作会消耗性能。
二、vector基本使用方法
可以将vector看作动态数组，解决问题时，虽然效率有时候可能赶不上用原始数组存储处理，但是vector丰富的成员函数可以有效提升代码编写效率。例如，在插入、删除任意元素时，只需要调相应成员方法即可，不需要像原始数组那样需要自己写循环来批量后移或者前移数组元素。
1.引入vector头文件
要使用vector，首先要引入vector头文件：#include<vector>。
2.申明vector变量
因为vector是模板类，所以申明vector变量时需要指明元素的数据类型。例如：
vector<int> v1; vector<double> v2; vector<Circle> v3; vector<int> v4(20); //v4有20个int元素，每个元素值均为0 vector<int> v5(1000,-1); //v5有1000个int元素，每个元素值均为-1
特别地，vector<bool>并不是一个通常意义上的vector容器，这个源自于历史遗留问题，强烈建议不要使用vector<bool>，可以换用vector<int>或者vector<char>。
3.在末尾追加、删除元素
可以使用push_back()向vector末尾追加元素，pop_back()删除末尾的元素，调用size()可以返回vector中元素的数量：
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> v;
cout<<v.size()<<endl; //空vector，元素数量为0
v.push_back(100); //向末尾追加1个元素
cout<<v.size()<<endl; //元素数量为1
for(int i=2;i<=10;i++) //继续追加9个元素
v.push_back(i*100);
cout<<v.size()<<endl; //元素数量为10
v.pop_back(); //删除末尾的1个元素
cout<<v.size()<<endl; //元素数量为9
v.clear(); //通过empty()清空所有元素
cout<<v.size()<<endl; //空vector，元素数量为0
if(v.empty()){ //通过empty()判断vector是否为空
cout<<"none."<<endl;
}
return 0;
}
通过上面的例子可以清晰地看到，vector的存储空间可以自动动态扩展，我们只需要调用其成员函数就可以追加或者删除元素，操作后由vector内部自己来实现存储空间的动态扩展。vector也提供了insert()和erase()两个成员函数来实现更普遍的插入、删除元素。
4.访问元素
可以像使用数组元素那样，通过[]来访问vector的元素（要注意下标最大值是v.size()-1），还可以使用at()来返回某个元素，此外通过front()返回第一个元素的值，back()返回最后一个元素的值：
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> v;
for(int i=1;i<=10;i++) v.push_back(i*100);
cout<<v[0]<<" "<<v[9]<<" "<<v[v.size()-1]<<endl;
cout<<v.at(0)<<" "<<v.at(9)<<" "<<v.at(v.size()-1)<<endl;
cout<<v.front()<<" "<<v.back()<<endl;
for(size_t i=0;i<v.size();i++)
cout<<v[i]<<" ";
cout<<endl;
for(size_t i=0;i<v.size();i++)
cout<<v.at(i)<<" ";
cout<<endl;
return 0;
}
5.遍历vector
那么如何遍历一个vector呢？最简单的方法当然是通过下标变化的方式来遍历：
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> v;
for(int i=1;i<=10;i++) v.push_back(i*100);
//正向遍历vector，循环控制变量建议使用size_t
for(size_t i=0;i<v.size();i++)
cout<<v[i]<<" ";
cout<<endl;
//反向遍历vector，循环控制变量【不能】使用size_t
//size_t是无符号整数，无符号整数0-1结果是一个很大的无符号整数，导致死循环
//其实反向遍历建议时候后面介绍的反向迭代器
for(int i=v.size()-1;i>=0;i--)
cout<<v[i]<<" ";
cout<<endl;
return 0;
}
对于STL中支持遍历的容器，STL提供了一种迭代器的方式来遍历这些容器。vector有两个特殊的成员函数，begin()返回一个迭代器（iterator，可以理解为指针），指向vector的第 0 个元素；end()也返回一个迭代器，指向vector最后一个元素的下一个位置（注意，这里不是指向最后一个元素），所以vector的最后一个元素的迭代器其实是v.end()-1（和指针一样，-1对应的是元素的地址），借助for循环和迭代器可以高效遍历vector：
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> v;
for(int i=1;i<=10;i++) v.push_back(i*100);
//迭代器变量it指向vector第一个元素
//注意这里it变量数据类型的写法
vector<int>::iterator it = v.begin();
for(;it!=v.end();it++){
//迭代器变量it实质是指针，*it获取到迭代器指向的vector元素
cout<<*it<<" ";
}
return 0;
}
此外还可以通过反向迭代器反向遍历vector：
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> v;
for(int i=1;i<=10;i++) v.push_back(i*100);
//反向迭代器变量it指向vector反向的第一个元素（最后一个元素）
//注意这里it变量数据类型、赋值语句、判断条件的写法，特别是reverse_iterator、rbegin和rend
vector<int>::reverse_iterator it = v.rbegin();
for(;it!=v.rend();it++) //这里依然是it++
cout<<*it<<" ";
return 0;
}
以上迭代器变量it的类型写法比较复杂，可以使用C++高级语法的auto数据类型简化：
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> v;
for(int i=1;i<=10;i++) v.push_back(i*100);
for(auto it=v.begin();it!=v.end();it++){
//迭代器变量it实质是指针，*it获取到迭代器指向的vector元素
cout<<*it<<" ";
}
cout<<endl;
for(auto it=v.rbegin();it!=v.rend();it++){
//迭代器变量it实质是指针，*it获取到迭代器指向的vector元素
cout<<*it<<" ";
}
cout<<endl;
return 0;
}
也可以自定义函数遍历vector的所有元素：
#include<iostream>
#include<vector>
using namespace std;
//通过[]遍历vector
void print(const vector<int> &ve){
for(size_t i = 0;i<ve.size();i++)
cout<<ve[i]<<" ";
cout<<endl;
}
//通过迭代器遍历vector
void print2(const vector<int> &ve){
//常量迭代器（只可以取元素的值，不能设置元素的值）
for(auto it=ve.cbegin();it!=ve.cend();it++)
cout<<*it<<" ";
cout<<endl;
}
//遍历容器的模板函数
template<typename Iter>
void list_elements(Iter begin, Iter end){
while(begin!=end){
cout<<*begin<<" ";
begin++;
}
cout<<endl;
}
int main()
{
vector<int> v;
for(int i=1;i<=10;i++) v.push_back(i);
print(v);
print2(v);
list_elements(v.begin(),v.end());
list_elements(v.rbegin(),v.rend());
return 0;
}
还可以通过迭代器遍历vector的过程中设置元素的值：
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> ve(10);
auto it = ve.begin();
for(int i=1;it!=ve.end();it++,i++){
*it = i*i;
}
for(auto it=ve.cbegin();it!=ve.cend();it++){
cout<<*it<<" ";
}
return 0;
}
此外，还可以借助C++语言for循环的高级用法遍历vector：
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> ve{1,2,3,4,5,6,7,8,9,10};
for(int n:ve){
cout<<n<<endl;
}
return 0;
}
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> ve{1,2,3,4,5,6,7,8,9,10};
for(int &n:ve){ //引用方式遍历
n = n*n; //修改n值，ve元素值也会改变
}
for(int n:ve){
cout<<n<<endl;
}
return 0;
}
6.vector两种典型用法的比较
先来看两段程序代码，比较两者的不同，试猜想两段程序的运行结果：
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> ve;
for(int i=1;i<=10;i++)
ve.push_back(i*i);
for(size_t i=0;i<ve.size();i++)
cout<<ve[i]<<" ";
return 0;
}
1 4 9 16 25 36 49 64 81 100
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> ve(10);
for(int i=1;i<=10;i++)
ve.push_back(i*i);
for(size_t i=0;i<ve.size();i++)
cout<<ve[i]<<" ";
return 0;
}
0 0 0 0 0 0 0 0 0 0 1 4 9 16 25 36 49 64 81 100
第二段程序定义变量的语句是vector ve(10);这里已经初始化了一个长度（元素数量）为10（元素值都是0）的vector。后面再push_back，是继续在vector的尾部追加。
再比较一下下面的两段程序代码：
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> ve;
for(int i=1;i<=10;i++)
ve.push_back(i*i);
for(size_t i=0;i<ve.size();i++)
cout<<ve[i]<<" ";
return 0;
}
1 4 9 16 25 36 49 64 81 100
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> ve(10);
for(int i=1;i<=10;i++)
ve[i-1] = i*i;
for(size_t i=0;i<ve.size();i++)
cout<<ve[i]<<" ";
return 0;
}
1 4 9 16 25 36 49 64 81 100
注意，第二段程序在循环体中通过赋值语句为已经存在的元素重新赋值。上面两段程序就体现了vector的两种典型使用方法。
7.vector的长度与容量
在向vector追加元素的过程中，vector的长度（元素的数量，通过size()能获取到）会不断增加。前面提到了vector的容量，也就是为vector划分的最大内存存储区，vector的容量往往大于实际存储长度。如果vector容量吃紧，那么会重新分配一块更大的内存区域，将vector已有内容拷贝到新的内存区域，这个过程也就是扩容的过程。vector内部有一套机制来实现自动扩容，包括何时扩容和扩容多少，保证了操作过程中不会因为频繁扩容而导致效率低下。vector的容量可以由capacity()获取。通过下面的程序可以简单测试一下vector扩容的次数：
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> ve;
int tot = 0;
size_t lca = ve.capacity(); //记录扩容前的容量
for(int i=1;i<=10000;i++) {
ve.push_back(i);
if(lca != ve.capacity()) { //出现扩容
cout<<lca<<" "<<ve.size()<<" "<<ve.capacity()<<endl;
tot++;
lca = ve.capacity();
}
}
cout<<"Auto resize capacity times:"<<tot<<endl;
cout<<ve.size()<<" "<<ve.capacity()<<endl;
return 0;
}
8.其它
- resize()改变vector元素的数量，可以产生截断或者扩充的效果；
- reserve()设置vector的容量。注意vector的容量和元素的数量不是同一个概念，容量是vector能够装入的元素的数量，在未突破容量前，vector可以一直追加新元素，不会产生重新分配空间的情况；超过了容量就会按照本文开头描述的方式自动扩充容量。为了避免使用过程中vector频繁自动扩充容量导致性能降低，可以使用reserve()来设置vector的容量；
- capacity()返回当前容量；
- swap()与另外一个vector交换所有元素；
- insert()和erase()可以较为随意地插入元素到指定位置、删除指定位置的元素，但执行效率比起在末尾追加、删除的push_back()和pop_back()差。
#include<iostream>
#include<vector>
using namespace std;
void print(const vector<int> &ve){
for(size_t i = 0;i<ve.size();i++)
cout<<ve[i]<<" ";
cout<<endl;
}
int main()
{
vector<int> v;
for(int i=1;i<=5;i++) v.push_back(i);
print(v);
//在指定迭代器（第一个参数）前插入一个元素
v.insert(v.begin(),0);
print(v);
//在指定迭代器（第一个参数）前插入若干相同元素
v.insert(v.begin()+3,4,-1);
print(v);
//删除指定迭代器处的元素
v.erase(v.begin());
print(v);
//删除两处迭代器区间的所有元素（左闭右开）
v.erase(v.begin()+1,v.end()-4);
print(v);
//通过迭代器遍历删除值为-1的所有元素
auto it = v.begin();
while(it!=v.end()){
//erase返回指向“删除元素的下一个元素”的迭代器
if(*it==-1) it = v.erase(it);
else it++;
}
print(v);
return 0;
}
三、多维vector
如果一个vector的元素也是vector，那么这样的vector就是一个二维vector（类似于二维数组），定义一个二维vector的方法如下：
vector<vector<int> > v;
这里有一个细节要注意，数据类型vector<vector<int> >书写时最后的两个右尖括号不能连在一起，中间需要用空格隔开，否则会出现编译错误！
可以指定二维vector的第一维长度（其实就是行数）：vector<vector<int> > v(n);
通过一个简单的例子来看二维vector的使用：
//二维vector
#include<iostream>
#include<vector>
using namespace std;
int main()
{
int n;
cin>>n;
//vector的元素也是vector
//注意两个>中间必须用空格隔开
vector<vector<int> > v(n); //指定行大小为n
for(int i=0;i<n;i++){
//第i行依次放入 1,2,...,i
for(int j=0;j<=i;j++)
v[i].push_back(j+1); //v[i]是一个vector
}
//遍历二维vector
for(size_t i=0;i<v.size();i++){
for(size_t j=0;j<v[i].size();j++){
cout<<v[i][j]<<" ";
}
cout<<endl;
}
//使用迭代器遍历二维vector
for(auto ite1=v.begin();ite1!=v.end();ite1++){
//迭代器ite1指向的是一个vector
for(auto ite2=ite1->begin();ite2!=ite1->end();ite2++){
cout<<*ite2<<" ";
}
cout<<endl;
}
return 0;
}
也可以不指定二维vector的行数：vector<vector<int> > v;，通过push_back的方式追加空的vector<int>到v中：
//二维vector
#include<iostream>
#include<vector>
using namespace std;
int main()
{
int n;
cin>>n;
//vector的元素也是vector
//注意两个>中间必须用空格隔开
vector<vector<int> > v; //未指定二维vector的行数
for(int i=0;i<n;i++){
v.push_back(vector<int>()); //这一句不能少：向v的末尾追加空的vector<int>（新添加一行）
//第i行依次放入 1,2,...,i
for(int j=0;j<=i;j++)
v[i].push_back(j+1); //v[i]是一个vector
}
//遍历二维vector
for(size_t i=0;i<v.size();i++){
for(size_t j=0;j<v[i].size();j++){
cout<<v[i][j]<<" ";
}
cout<<endl;
}
//使用迭代器遍历二维vector
for(auto ite1=v.begin();ite1!=v.end();ite1++){
//迭代器ite1指向的是一个vector
for(auto ite2=ite1->begin();ite2!=ite1->end();ite2++){
cout<<*ite2<<" ";
}
cout<<endl;
}
return 0;
}
四、对vector排序
前面已经提到，vector的begin()返回的是指向第一个元素的迭代器，end()返回的是指向最后一个元素的下一个位置的迭代器，结合前面介绍的sort函数排序时两个参数确定的排序区间是左闭右开的特点，可知对vector简单排序使用sort(v.begin(),v.end());即可。排序结束后，和数组一样，vector内部的元素会按照排序规则重新排列。
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
void print(const vector<int> &ve){
for(size_t i = 0;i<ve.size();i++)
cout<<ve[i]<<" ";
cout<<endl;
}
int main()
{
vector<int> v;
for(int i=0;i<10;i++) v.push_back(10-i);
print(v);
//升序排序
sort(v.begin(),v.end());
print(v);
//借助greater<int>()实现降序排序（也可以自定义比较函数实现）
sort(v.begin(),v.end(),greater<int>());
print(v);
return 0;
}
从上面的程序可以看出，要实现降序排序需要自定义比较函数或者使用greater<int>()作为比较函数，其实还可以使用sort(v.rbegin(),v.rend());（反向迭代器）来实现降序排序。
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
void print(const vector<int> &ve){
for(size_t i = 0;i<ve.size();i++)
cout<<ve[i]<<" ";
cout<<endl;
}
int main()
{
vector<int> v;
for(int i=1;i<=10;i++) v.push_back(i);
print(v);
//借助反向迭代器实现降序排序
sort(v.rbegin(),v.rend());
print(v);
return 0;
}
五、经典例题：流感传染
问题见NOI OpenJudge：OpenJudge - 6262:流感传染
思路一：借助循环递推每一天所有房间的情况，标记出来每天新感染病人的房间，这样是一个典型的三重循环结构，时间复杂度\(O(mn^2)\)。大家可以自行尝试按照这样的思路编写程序解决问题。
思路二：其实只有前一天新感染的病人传染附近房间健康的人成为当天新感染的病人，所以只需要记录每天新感染的病人所在房间信息即可，可以由这些信息计算出接下来一天新感染的病人所在房间信息，这样依次递推下去。不需要每天都扫描所有房间，只需要扫描新感染病人的房间即可，降低了时间复杂度。这里可以使用vector来记录每天新感染的病人所在房间的信息。
#include<iostream>
#include<vector>
using namespace std;
//标记房间住人情况：1表示健康，0-其他情况
int ho[110][110];
//每个房间相邻4个房间时坐标变化情况
int dir[4][2] = {
{0,1},
{0,-1},
{1,0},
{-1,0}
};
//房间坐标信息
struct Point{
int x,y;
Point(){}
Point(int x,int y){
this->x = x;
this->y = y;
}
};
//ve记录当前感染病人的房间信息
//vet记录新感染病人的房间信息
vector<Point> ve,vet;
int main()
{
int n,m,ans = 0;
char ch;
cin>>n;
for(int x=1;x<=n;x++){
for(int y=1;y<=n;y++){
cin>>ch;
if(ch=='.') ho[x][y] = 1;
if(ch=='@') ve.push_back(Point(x,y));
}
}
ans += ve.size();
cin>>m;
for(int i=2;i<=m;i++){
//没有新感染病人信息，不用继续递推，提前退出循环
if(ve.size() == 0) break;
//由当前感染病人信息ve计算出新感染病人信息vet
vet.clear();
for(int j=0;j<ve.size();j++){
for(int k=0;k<4;k++){
int nx = ve[j].x+dir[k][0];
int ny = ve[j].y+dir[k][1];
//ho数组有多开，并且存储从下标1开始，
//相当于实际数据存储区域被全是0的边界围着，
//不要担心数组下标溢出
if(ho[nx][ny]){
ho[nx][ny] = 0;
//记录一个新感染病人信息
vet.push_back(Point(nx,ny));
}
}
}
//新感染的病人信息成为下一天推导时的“当前感染病人信息”
ve = vet;
ans += ve.size();
}
cout<<ans<<endl;
return 0;
}
重点关注程序中的vector变量直接赋值语句：ve = vet;，vector变量可以像结构体一样，直接赋值成其他vector变量的值，其实STL中的其它容器也能直接赋值。