动态数组简介

有时候，我们在做题时会思考数组到底应该有多大才合适，有时可能不得而知。所以希望能够在运行时具有改变数组大小的能力。这也就出现了所谓的动态数组，动态数组是指在声明时没有确定数组大小的数组。动态数组可以在任何时候改变大小，既灵活又方便，有助于有效管理内存。

但是大部分情况下，我们还是使用静态数组的，尤其是在打比赛的时候。但是有时如果我们用静态数组空间会炸，所以只好用动态数组。但是动态数组又不太好写，因此C++的SLT给出了一个容器vector来帮助我们。

vector_5">vector容器

所在头文件：vector

定义：（其中Type为类型，如int，char，结构体，string等等）

vector <Type> v; //默认初始化 v为空
vector <Type> v(v1); //用v1定义v
vector <Type> v(n); //v有n个值为0的元素
vector <Type> v(n, x); //v有n个值为x的元素
vector <Type> v[MAXN + 10]; //第一维大小是(MAXN + 10),第二维是动态的二维数组

常用操作：

v[i]; //v的第i个元素
v.clear() //清空v
v.push_back(x); //在尾部添加元素
v.pop_back() //删除末尾元素
v.insert(a.begin() + i, x) //在v[i]前面插入一个元素x
v.insert(a.begin() + i, n, x) //在v[i]前面插入n个元素x
v.insert(a.end(), x) //在v尾部插入一个元素x
v.insert(a.end(), n, x) //在v尾部插入n个元素x
v.erase(a.begin() + i) //删除v[i]
v.erase(a.begin() + i, a.begin() + j) //删除v[i]到v[j - 1]
v.erase(a.begin() + i, a.end()) //删除v[i]到最后一个元素
v.resize(n) //将数组大小调整为n
int vsz = v.size(); //v中元素的个数
bool isEmpty = v.empty(); //判断v是否为空，如果为空则是true，否则是false

注意：vector在插入或删除某项时，需要将后面的值全部前移，算法时间复杂度是O(n)级别的。如果频繁移动，效率极低。