STL是Standard Template Library的简称，中文名标准模板库。

从根本上说，STL是一些“容器”的集合，这些“容器”有list,vector,set,map等，STL也是算法和其他一些组件的集合。STL现在是C++的一部分，因此不用安装额外的库文件。

在C++标准中，STL被组织为下面的17个头文件：

<algorithm>、<deque>、<functional>、<iterator>、<array>、<vector>、<list>、<forward_list>、<map>、<unordered_map>、<memory>、<numeric>、<queue>、<set>、<unordered_set>、<stack>和<utility>。

一、vector

1. vector的自我介绍

• vector是向量的意思，可以理解为“可变长度的数组”。
• 就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
• 相当于一个动态数组，在你不知道需要的数组有多大时可以使用它来节省很多空间。在ACM中常常会出现内存溢出（out of memory）的问题导致WA（wrong answer），而使用vector就能节省很多内存。
• 使用vector要在程序开头加上#include<vector>来包含需要的头文件，还有加上“using namespace std;”，这样就可以在代码中使用vector了。

2.vector的定义

• 定义一个vector:

vector<typename> vectorname;

• 这个定义相当于定义了一个一维的数组vectorname[SIZE],只不过这个SIZE的长度是可以改变的，随着你“加入”进去数的个数而改变。所谓“可变长度的数组”。
• 和一维的数组一样，这里的typename可以是任何的类型，如int,double,char,string，long long ,也可以是结构体，甚至是STL的容器如vector，set,queue,stack等。注意！如果typename也是一个容器的话，比如vector<vector<int> > vectorname,要在两个'<'符号之间加上一个空格，否则编译时会误以为是位移操作。

3.vector的创建

vector<double> vec1; // 创建一个空的double向量
vector<int> vec(66); // 创建一个初始大小为66的int向量
vector<double> vec2(vec1); // 创建一个double型的vec2,并用vec1去初始化vec2
vector<char> vec(10,'k'); // 创建一个含有10个char型数据的vector，并全部初始化为'k'
vector<int> vec(10,1);//创建一个初始大小为10的并且值都是1的vector
vector<int> vec2(vec1.begin(),vec1.begin()+3);//用向量vec1的第0个到第2个值初始化vec2
int arr[5] = {1, 2, 3, 4, 5};
vector<int> vec(arr, arr + 5); //将arr数组的元素用于初始化vec向量,末尾指针指向结束元素
//的下一个
vector<int> vec(&arr[1], &arr[4]); //将arr[1]~arr[4]范围内的元素作为vec的初始值，不包含arr[4]，
//原因如上

4.特别的，元素为vector的vector数组

• （其实就是vector的二维数组）和vector数组！ 如果typename是vector，那么就这么定义vector<vector<int> > vectorname; 注意在相邻的'>'之间要加空格。 这个就像二维数组的定义，其中一维是一个元素是vector的vector数组。可以把vector数组 当作两个维长度都可变的二维数组理解。vector数组的定义vector<typename> Arrayname[arraySize]; 比如，vector<int> vec[66]; 这样Arrayname[0]~Arrayname[arraySize-1]中每一个都是vector容器。 而vector<vector<int> > vectorname不同的地方时，前者的第一维长度已经固定为arraySize了， 后者却是两个维度都可变长的数组。哈哈哈，用你的大脑，发挥空间想象能力，出现了什么图形？ 很神奇是不是！

5.vector容器内元素的访问形式

• vector一般有两种访问形式：通过下标访问或者是通过迭代器访问。

(1)通过下标访问

和访问普通数组是一样的，一个已经定义的vector<typename> vec的vector容器，直接访问vec[index]就可以了（比如 vec[0],vec[1])。需要注意的一点是，首先这个vec得有size!!!桥黑板!什么意思呢？就是如果一开始你定义了 比如vector<int> vec1;直接使用vec[0]是不对的！因为里面还没有长度啊！开始用的时候我就经常犯这个错误（尴尬） 。所以可以通过下标访问的范围是从0~vec.size()-1.

(2)通过迭代器访问

• 啥叫迭代器啊？好可怕~就理解为指针吧，不去考虑细节，两者是一样的(包括在java中最近遇见的引用，这简直是三胞胎！）。 定义如下： vector<typename>::iterator it;(it就是变量名，一般默认都写成it) 这样it就是一个vector<typename>::iterator 型的变量了(hhh,这个名字好长啊)，其中，typename就是定义vector时 写的类型。比如： vector<double>::iterator it; vector<int> vec; vector<int>::iterator it2; it2=vec.begin();(或者合成一条：vector<int>::iterator it2=vec.begin(); ) 这样就得到了迭代器it(or it2)，并且可以通过*it来访问vector里的元素。

vector<int> vec;
vector<int>::iterator it;
for (it = vec.begin(); it != vec.end(); it++)//vector的迭代器不支持it<vec.end()写法，因此循环中只能用it!=end()
cout << *it << endl;
//或者
vector<int>::iterator it=vec.begin();
for(int i=0;i<vec.size();i++){
printf("%d ",*(it+i));//桥黑板！！在STL容器中，只有vector和string这两个好基友，才允许使用vev.begin()+3这种迭代器加上整
//数的写法，只有这俩。
//从这里可以看出，vec[i]和*(vec.begin()+i)是等价的
}
//或者
for (size_t i = 0; i < vec.size(); i++) {
cout << vec.at(i) << endl;//见下文分解
}

好了，终于说完访问形式了，可以介绍基本操作啦！

6.vector的基本操作

(1)对容量的操作

• 得到向量的大小： vec.size();
• 得到向量最大可以是多大： vec.max_size();
• 重新设置容器size的大小： vec.resize(num);
• 重新设置容器capacity的大小： vec.reserve(num);
• 向量真实大小： vec.capacity();
• 判断向量是否为空： vec.empty();

注：关于resize()和reverse(),我觉得记住一点就行了，容器调用resize()函数后， 所有的空间都已经初始化了，所以可以直接访问。比如： vector<int> vet; vec.resize(100); vec[0]=1;//合法语句！ 而reserve()函数预分配出的空间没有被初始化，所以不可访问。 推荐一个关于resize()和reserve()写的不错的博客vector中resize()和reserve()区别

(2)修改元素

• 多个元素赋值： vec.assign(); //类似于初始化时用数组进行赋值
• 末尾添加元素： vec.push_back(i)//在末尾添加元素i
• 末尾删除元素： vec.pop_back();
• 任意位置插入元素： vec.insert(it,x);

1. 用来向vector的任意迭代器（见上文）it处插入一个元素x,时间复杂度O(N);

• 任意位置删除元素： vec.erase();

1. erease(it)即删除迭代器为it处的元素；
2. erase(first,last)即删除[first,last)内的所有元素；(老美的左闭右开，你懂的）

• 交换两个向量的元素： vec.swap();//不多讲，用的真的很少。同样，推荐博客vector利用swap()函数进行内存的释放

（3）惊现迭代器

开始指针：vec.begin();
末尾指针：vec.end(); //指向最后一个元素的下一个位置
指向常量的开始指针： vec.cbegin(); //意思就是不能通过这个指针来修改所指的内容，但还是可以通过其他方式修改的，而且指针也是可以移动的。（用的很少，不妨先忽略吧）
指向常量的末尾指针： vec.cend();（同上，不多说）

（4）元素的访问

下标访问： vec[1]; //桥黑板！！并不会检查是否越界
at方法访问： vec.at(1); //以上两者的区别就是at会检查是否越界，是则抛出out of range异常
访问第一个元素： vec.front();
访问最后一个元素： vec.back();
返回一个指针： int* p = vec.data(); //可行的原因在于vector在内存中就是一个连续存储的数组，所以可以返回一个指针指向这个数组。这是是C++11的特性。（可忽略）

（5）一些算法

• 遍历元素

Cvector<int>::iterator it; 
for (it = vec.begin();it != vec.end(); it++)
    cout << *it << endl;
//或者
for (size_t i = 0; i < vec.size(); i++) {
     cout << vec.at(i) << endl; 
}

• 元素翻转

C#include <algorithm>
reverse(vec.begin(), vec.end());

• 元素排序

C#include <algorithm> 
sort(vec.begin(), vec.end()); //采用的是从小到大的排序 
//如果想从大到小排序，可以采用上面反转函数，也可以采用下面方法: 
bool Comp(const int& a, const int& b) {//固定套路，要加上const，意思是不能修改引用 
return a > b; 
} 
sort(vec.begin(), vec.end(), Comp);

7.vector的用武之地

（1）储存数据

• vector本身可以作为数组使用，而且在一些元素个数不确定的场合可以很好的节省空间。
• 有些场合需要根据一些条件把部分数据输出在同一行，数据中间用空格隔开。由于输出的数据个数是不确定的，为了跟方便的处理最后一个满足条件的数据后面不输出额外的空格，可以先用vector记录所有需要输出的数据，然后一次性输出。
• 有强大的方法可以调用（妈呀，java学多了，请不要喷我，暂且就叫方法吧，介绍如上vector的基本操作（1）~（4））

( 2 )用邻接表存储图

• 使用vector实现邻接表可以有效避免指针，而且更容易把握。

哈哈哈，终于结束啦（喝口水）。
好了，说了这么多，当然废话也不少~~
来几道题目吧！
PAT A1039. Course List for Student (25)

PAT A1047. Student List for Course (25)

参考：C++ STL之vector用法总结
《算法笔记》（胡凡，曽磊）