1.vector

vector是STL 的动态数组，在运行时能根据需要改变数组大小。由于它以数组形式存储,也就是说它的内存空间是连续的,所以索引可以在常数时间内完成,但是在中间进行插入和删除操作会造成内存块的复制。另外,如果数组后面的内存空间不够.需要重新申请一块足够大的内存。这些都会影响 vector的效率。

数组是基本的数据结构,有静态数组和动态数组两种类型。在算法竞赛中:如果空间足够,能用静态数组就用静态数组，而不用指针管理动态数组，这样编程比较简单并且不会出错;如果空间紧张,可以用 STL的vector 建立动态数组。

2.定义

2.1 定义一维数组

vector<int>a;  //默认初始化，a为空
vector<int>b(100);  //b的大小为100，每一位都是0
vector<int>c(100,5);  // c的大小为100，每一位都是5
vector<int>d(c);  // 用c定义d  
vector<string>e(10,"zimiao")；// e的大小是10，每一位都是 zimiao
vector<int>f{1,2,3,4,5}; // f的大小为5，f[0]=1
注意：vector下标是从0开始的

2.2 结构体数组

struct node{
  int x;
  double y;
}
vector<node>a;

2.3一位数组应用

示例1：输入n个数字，输出

#include<iostream>
#include<vector> 
using namespace std;
int main(){
	vector<int>a;
	int x,n;
	cin >> n;
	for(int i=0;i<n;i++){
		cin >> x;
		a.push_back(x); //在a的尾部插入元素x
	}
	for(int i=0;i<n;i++){
		cout << a[i] << " ";
	}
	return 0;
}

示例2：输入n个数字，输出（n<=100）

#include<iostream>
#include<vector> 
using namespace std;
int main(){
	vector<int>a(100);
	int x,n;
	cin >> n;
	for(int i=0;i<n;i++){
		cin >> a[i];
	}
	for(int i=0;i<n;i++){
		cout << a[i] << " ";
	}
	return 0;
}

可以把a想像成一个气球，示例2中，气球已经被撑开了，所以可以在输入的时候随意使用a[i],而示例1中的气球是没有空间的，所以只能使用push_back。

2.4定义二维数组

方法一：适用于行数固定，列不固定的数据输入。比如：输入一个n行m列的二维数组，其中n<=100。

vector<int> v[100];//v的第一维(行)是固定的5，第二维(列)是动态的
v[0].push_back(1); // 第1行末尾插入1
v[1].push_back(2); // 第2行末尾插入2


// 插入元素的方法 输入n行m列的元素（n<=100）
vector<int>v[100];
for(int i=0;i<n;i++){
  for(int j=0;j<m;j++){
     int x;
     cin >> x;
     a[i].push_back(x);
  }
}
//常规双重for循环输出验证结果

方法二：适用于行列都不固定的数据输入。比如：输入一个n行m列的二维数组，其中n*m<=100000。

vector<vector<int>>v; // 行列都为空
vector<int> t1{1, 2, 3, 4}; // 创建t1数组
vector<int> t2{2, 3, 4, 5}; // 创建t2数组
v.push_back(t1); // 把t1放进v的第一行
v.push_back(t2); // 把t2放进v的第二行
v.push_back({3, 4, 5, 6}) // v的第三行放入3，4，5，6   


// 二维数组输入方法
vector<vector<int>>v;
int n,m,x;
cin >> n >> m;
for(int i=0;i<n;i++){
  vector<int>a;
  for(int j=0;j<m;j++){
    cin >> x;
    a.push_back(x);
  }
  v.push_back(a);
}
//常规双重for循环输出验证结果

方法三：行列都固定，输入n行m列的数组（建议直接用二维数组，不用vector）

//行列长度均固定 n + 1行 m + 1列初始值为0
vector<vector<int>> a(n + 1, vector<int>(m + 1, 0));

3.常用操作

4.迭代器遍历

方法一：下标法遍历

//一维数组
for(int i=0;i<n;i++){
  cout << a[i] << " ";
}
//二维数组
for(int i=0;i<n;i++){
  for(int j=0;j<m;j++){
    cout << a[i][j] << " ";
  }
  cout << endl;
}

方法二：迭代器

vector<int>a{1, 2, 3, 4, 5}; 
// 方法1
vector<int>::iterator it = a.begin();
for(int i = 0; i < 5; i++)
    cout << *(it + i) << " ";
// 方法2
vector<int>::iterator it;
for(it=a.begin();it!=a.end();it++){
  cout << *it << " ";
}
// 方法3
vector<int>::iterator it = a.begin();
while(it!=a.end()){
  cout << *it << " ";
  it++;
}