在C中，有很多东西需要自己实现。C++提供了标准模板库（Standard Template Libray,STL）,其中封装了很多容器，不需要费力去实现它们的细节而直接调用函数来实现功能。
具体容器链接：set，string，map，queue，priority_queue，stack，pair
1、vector的用法
vector：向量，这里叫“变长数组”，长度根据需要而自动改变的数组。有时会碰到普通数组会超过内存的情况，可以使用vector解决。而且，vector可以用来以邻接表的方式存储图，可以解决当节点数太多，无法使用邻接矩阵，又害怕使用指针实现邻接表的时候，使用很简单。
使用vector，需要添加头文件，#include<vector>，还要头文件下加入using namespace std;
1.1、vector的定义
vector<typename> name;
相当于定义了一个一维数组name[SIZE]，只不过size可以根据需要进行变化，比较节省空间，也就是变长数组
typename:任何基本类型，int,char,double,结构体,STL容器vector,set,queue等。
如果typename是STL容器，定义的时候要在>>之后加上空格，如果不加空格，编译器就把它认为是位操作。
vector<int> stu; vector<double> stu; vector<char> stu; vector<Node> stu;//Node是结构体类型 vector<vector<int>> name;
二维数组的定义：一维是一个数组的数组
vector<typename> Arrayname[arraySize]
/*Arrayname[]的每一个元素都是一个vector，可以理解为两个维都是可变长的二维数组*/
写法一：vector<int> vi[100];//一维长度已经固定为arraySize
vi[0]~vi[99]中每一个都是一个vector容器。
写法二：vector<vector<int>> vi//区别：这个两个维度是变长的
1.2、vector容器内元素的访问
vector访问方式：下标访问、迭代器访问。
1.2.1、下标访问
和访问普通数组一样，下标从0~size()-1。
比如定义的：vector<typename> vi，使用vi[index](vi[0],vi[1])。
1.2.2、通过迭代器访问
迭代器（iterator）理解为类似指针的东西。
定义：vector<typename>::iterator it;//it是一个迭代器变量。
#include<stdio.h> #include<vector> using namespace std; int main() { vector<int> vi; for(int i=0;i<5;i++) { vi.push_back(i); } vector<int>::iterator it=vi.begin();//vi.begin()是vi的首元素地址，用迭代器变量it指向这个地址 for(int i=0;i<5;i++) { printf("%d ",*(it+i));//输出vi[i]; } return 0; }
注：vi[i]与*(vi.begin()+i)等价
end()函数：并不是取vi的尾元素地址，而是取尾元素的下一个地址。就相当于左闭右开区间。
#include<stdio.h> #include<vector> using namespace std; int main() { vector<int> vi; for(int i=0;i<5;i++) { vi.push_back(i); } vector<int>::iterator it=vi.begin();//vi.begin()是vi的首元素地址，用迭代器变量it指向这个地址 for(int i=0;i<5;i++) { printf("%d ",*(it+i));//输出vi[i]; } //使用begin(),end()函数，访问 for(vector<int>::iterator it=vi.begin();it!=vi.end();it++) { printf("%d ",*it); } return 0; }
注：在常用STL容器中，只有vector和string才可以使用vi.begin()+i这种迭代器加整数的写法，因为他们两个看做数组的下标的访问方式。
1.3、vector常用函数
1.3.1、push_back()函数
push_back(x)就是在vector后面添加一个元素x，时间复杂度为O(1)。
1.3.2、pop_back()函数
pop_back(x)就是删除vector的尾元素x，时间复杂度为O(1)。
1.3.3、size()函数
用来获得vector中元素的个数，时间复杂度为O(1)。
1.3.4、clear()函数
用来清空vector所有的元素，时间复杂度为O(N)，N为元素总个数。
1.3.5、insert()函数
用insert(it,x)往vector的任意迭代器it初传入一个元素x。时间复杂度为O(N)。
1.3.6、erase()函数
用erase()函数删除单个元素，或者一个区间的元素
#include<stdio.h> #include<vector> using namespace std; int main() { vector<int> vi; for(int i=0;i<5;i++) { vi.push_back(i);//jpush_back()函数应用 } vi.pop_back(i);//删除vi的尾部元素4 int i=vi.size();//size()返回的unsingned类型 vi.clear();//清空vector所有元素 vi.insert(vi.begin()+2,23);//将23插入vi[2]的位置 vi.erase(vi.begin()+1);//删除单个元素vi[1]; vi.erase(vi.begin()+1,vi.begin()+3);//删除vi[1],vi[2],左闭右开区间 return 0; }
1.4、vector常见用途
1.4.1、存储数据
vector本身可以作为数组使用，当元素个数不确定的时候，可以很好地节省空间。
有些时候需要把部分数据输出在同一行，用空格隔开数据。由于数据的个数不知道，
可以使用vector记录所有的需要输出的数据，然后一次性输出。
1.4.2、用邻接表存储图
可以使用vector实现邻接表，避免使用指针的邻接链表。
2018-09-25 14:24:20 @author:Foreordination