STL基本概念
- 容器：用于存放数据的类模板，比如vector, list, stack, queue等。
- 迭代器：用于存取容器中存放的元素，可以理解成指针，用于遍历和操作容器。使用迭代器可以实现以相同的风格访问和操作大部分的容器。
- 算法：用来操作容器中元素的函数模板，比如sort, unique等。
容器
用于存放元素，实例化时指定元素类型。如果存储的是一个对象，那么最好重载==和<运算，因为大部分算法都会用这两个运算符来进行相等判断和排序。
容器分为两大类：
顺序容器：可变长动态数组vector、双端队列deque、双向链表list。顺序容器的元素具有前后关系，可指定位置插入和删除。
关联容器：set、multiset、map、multimap。关联容器的元素是排序过的，不能指向插入位置。插入的元素会自动排序。默认情况下，关联容器中的元素按从小到大排序，使用运算符"<"进行比较。关联容器在查找时有很好的性能。
容器适配器：栈stack、队列queue、优先队列priority_queue。在上两类容器的基础上屏蔽一部分功能，突出或增加另一部分功能。
任何两个容器对象，只要类型相同，就可以用<、<=、>、>=、==、!=进行字典式的比较，它们的运行规则如下：
a == b: a和b中的元素个数相同，且对应元素相等，使用==运算符。
a < b: 类似于单词的字典序比较，使用<运算符。
a != b: 等价于!(a == b)。
a > b: 等价于 b < a。
a <= b：等价于 !(b < a)。
a >= b: 等价于!(a < b)。
所有的容器都有以下两个成员函数：
int size()：返回容器对象中元素的个数。
bool empty()：判断容器对象是否为空。
顺序容器和关联容器还有以下成员函数：
begin(): 返回指向容器第一个元素的迭代器。
end(): 返回指向容器最后一个元素后面的位置的迭代器。
rbegin(): 返回指向容器最后一个元素的反向迭代器。
rend(): 返回指向容器第一个元素前面的位置的迭代器。
erase(): 删除一个或几个元素。
clear(): 删除所有元素。
顺序容器还有以下常用成员函数：
front(): 返回容器中第一个元素的引用。
back(): 返回容器中最后一个元素的引用。
push_back(): 在容器末尾增加新的元素。
pop_back(): 删除容器末尾的元素。
insert(): 插入一个或多个元素。
迭代器
用于访问容器中的元素，有以下四种：
1. 正向迭代器，定义方法如下：
2. 常量正向迭代器，定义方法如下：
容器类名::const_iterator 迭代器名;
3. 反向迭代器，定义方法如下：
容器类名::reverse_iterator 迭代器名;
4. 常量反向迭代器，定义方法如下：
容器类名::const_reverse_iterator 迭代器名;
注意，容器适配器stack、queue和priority_queue没有迭代器，它们有自己的方法用于访问元素。
迭代器的功能分类
不同的容器的迭代器功能有强弱之分，这决定了容器是否支持某种STL算法，比如，排序算法sort需要通过迭代器支持随机访问功能，如果某种容器不支持随机访问，如list，那就不支持使用sort进行排序。
常用的迭代器按功能强弱分为输入、输出、正向、双向、随机访问5种：
正向迭代器：支持++p和p++、*p，两个迭代器可以赋值，可以用==和!=比较；
双向迭代器：支持正向迭代器的全部功能，还支持--p和p--；
随机访问迭代器：在双向迭代器的基础上，支持 p+i、p-i、p+=i、p-=i、p[i]，还支持 <、>、<=、>=比较。
不同容器的迭代器功能：
| 容器 | 迭代器功能 |
|---|
| vector | 随机访问 |
| deque | 随机访问 |
| list | 双向 |
| set/multiset | 双向 |
| map/multimap | 双向 |
| stack | 不支持 |
| queue | 不支持 |
| priority_queue | 不支持 |
迭代器的辅助函数
advance(p, n): 使迭代器向前或向后移动n个元素。
distance(p, q): 计算两个迭代器之间的距离，即p经过多少次++后和q相等，如果p本身就在q后面，则这个函数会陷入死循环。
iter_swap(p, q): 用于交换两个迭代器q、q指向的值，相当于通过指针交换元素内容。
算法
能在各种容器上通用的函数模板，通过迭代器来操作元素。
大部分算法需要通过迭代器提供一个操作区间，比如begin()~end()。
有的算法返回一个迭代器，比如find算法。
排序、查找等算法需要对元素进行比较，比较判断大小及是否相等。在STL中，比较大小通过"<"运算符来实现，和">"无关。而比较相等时，并不一定是使用"=="运行符，而是要根据情况来确定。如果是在未排序的区间上应用find进行查找，那么使用"=="运算符来判断相等。如果是在已经排序好的区间上进行查找、合并等操作（比如折半查找算法binary_search，关联容器自身的find成员函数)，那么判断x=y的条件是x<y和y<x同时为假。如果一个类将"<"运算符重载为永远返回false，那么对于STL算法来说，这个类的所有对象都是相等的。
vector
可变长数组，支持以下迭代器：
- begin()/end()
- rbegin()/rend()
- cbegin()/cend()
- crbegin()/crend()
支持以下容量相关的操作：
- size()
- empty()
- resize()
- reserve()
- capacity()
支持以下元素访问操作：
注意front()和back()都是返回引用，也就是可以直接通过这两个函数的返回值来修改元素。
支持以下修改操作：
- push_back()
- pop_back()
- insert()
- erase()
- clear()
以下是vector的一些示例操作：
list
queue
