STL是标准模板库，主要有容器、分配器、算法、适配器、迭代器和函数对象等组成，各类之间互相独立，比如容器和算法互相独立，通过迭代器来沟通。
容器
容器有一个非常好的设计理念，从名字上看也十分容易理解，容器container用于存放数据的类模板。可变长数组、链表、平衡二叉树等数据结构在STL中都被实现为容器。
- 普适性
容器的方法以及容器中容纳元素的方式都使用了模板类的定义方法，使用过程中只用考虑容器的元素操作，而不用关心方法是否能够作用于各种各样的元素。
- 标准性
使用标准模板的方法产生的容器自然可以适用于标准库中使用同样标准的函数，STL中的许多算法即函数模板，如排序、查找等算法。当然有些时候需要重载这些方法来适应特殊的元素，或者重载元素的运算符来适应容器。
| 顺序容器 | 功能 |
|---|---|
| array | 固定大小的数组，支持下标访问，不能添加或者或者删除元素，操作和普通数组相似 |
| vector | 向量容器可以改变大小，同样可以像数组一样操作，非尾部增删元素效率低下 |
| list | 双向链表，不支持下标访问，但是能够双向顺序访问，在任何位置插入删除操作都较快 |
| queue | 队列是一种先进先出的容器，不能够随机访问，只能访问和操作首尾元素 |
| stack | 栈容器遵循先进后出的原则，同样不能随机访问，访问范围只限于栈顶元素 |
数组
array模板定义了一种标准数组的容器类型。基本和数组一致，需要定义元素类型和大小，不能够更改容器的容量。序列容器中的元素严格按照线性顺序排序，各个元素按其顺序进行访问。它的大小是本身属性常量获取没有内存或时间的编译开销，应该常用array来代替数组，这样更安全。
方法
size()：返回容器的大小
array<int, 5> nums = {1, 3, 2};
cout << nums.size();
at()：由角标指定访问容器元素
array<int, 5> nums = {3, 2, 1, 4, 5};
int a = nums.at(3);
// Or it can be accessed randomly like an array.
int b = nums[3];
data()：返回一个指向容器头部的指针
array<double, 3> nums = {2.7, 3.0, 1.5};
double *p = nums.data();
向量
vector相当于数组可以像数组一样操作，但容量可以扩大，所以可以将它看作一种动态数组。可以从后端添加元素，因为在内存中是线性连续存储，当容量不够容器扩大时要把数据拷贝到更大的内存区域来储存，这样会很消耗性能。最好在建立vector时就给定一定的空间，极不推荐向中间某个位置添加元素。
方法
clear()：清空容器中的所有元素
vector<int> nums{1, 3, 5};
nums.clear();
// Clear the elements in the container, so siz == 0.
int siz = nums.size();
push_back()：在向量容器后添加元素pop_back()：将容器尾部元素弹出
vector<int> nums{1};
nums.push_back(3);
nums.pop_back();
insert()：在某一个位置插入一个元素
vector<double> nums{1.0, 2.0, 3.0};
// Position of the element is the position pointed to by iterator or pointer.
nums.insert(nums.begin() + 1, 8.0);
resize()：重新设置该容器的大小
// Changes the number of elements and fills with zero values or others. If the
// container smaller later, the following elements will be given up directly.
vector<int> nums(10);
nums.resize(4);
assign()：向容器赋值或者拷贝区间内的值到容器
vector<long> nums{1, 2, 3};
vector<long> cp;
// nums's elements copy in the other vector
cp.assign(nums.begin(), nums.end());
nums.assign(4, 1);
链表
list是由多个节点构成线性链表结构，每个节点前驱指针指向前一个节点和后驱指针指向后一个节点，具有双向性。因为它存于不连续的内存空间里用指针相连，但也因此它的随机访问能力低下，不能用at()和数组访问法。也同样因为其底层结构，向其中添加或删除元素高效且影响较小。
方法
insert()：向某一个位置添加元素
array<int, 4> nums = 1;
list<int> cp(nums.begin(), nums.end());
cp.insert(cp.begin() + 2, 7); // 1 3 7 4 5
for (list<int>::iterator it = cp.begin(); it != cp.end(); ++it) {
cout << *it << " ";
//rely on iterators to access and output elements
}
splice()：将两个list实现不需要拷贝的拼接
list<int> frist, seconde;
frist.assign(4, 1);
second.assign(4, 0);
// 1 1 1 1 0 0 0 0
frist.splice(second);
// second container be emptied
second.assign(2, 2);
list<int>::iterator it = frist.begin() + 1;
first.splice(it, second);
队列
queue是一种先进先出的数据结构，需要将数据进行顺序处理的时候会采用这种数据结构，如BFS广度优先搜索。其底层是deque但却对访问进行了控制，这体现出了面向对象编程中的封装这一概念。
方法
push()：在队列尾部添加元素pop()：弹出队列头部的元素
queue<int> q;
q.push(4);
q.push(5);
q.pop();
front()：访问队列头部的元素back()：访问队列尾部的元素
// If there are no elements in the queue, an error will be occured.
cout << q.front() << endl;
cout << q.back() << endl;
栈
stack一种先进后出的数据结构，常被用于内存管理，同时栈也可以利用这种性质来构建单调栈来处理问题。
方法
top()：返回栈顶的元素
stack<int> st;
st.push(1);
int a = st.top(); // a == 1
push()：在栈顶添加元素pop()：弹出栈顶元素
stack<int> st;
// Add and pop elements according to the data structure characteristics of the stack.
st.push(1);
st.push(2);
st.pop();
| 关联容器 | 功能 |
|---|---|
| map | 表容器，但通过底层的红黑树实现key-value的查询的数据结构 |
| set | 容器中元素唯一且无需，实现数学中集合定义的容器 |
图
map是一种关联容器，它存储唯一的关键字并建立和值的关联关系。底层使用红黑树，并且在树中的元素被排序。由于其一一对应的特点，其具有较强的关键字处理能力，但比不过unordered_map的 $O(1)$ 复杂度的查找。它在完成一些检索一对一数据时能够提高效率，能够自动建立key和value的关联，所以向里面通常插入一个pair数据。
方法
insert()：向表中添加键值对
map<int, string> mp;
mp[0] = "Tony";
// It can also insert elements into the graph with pair.
mp.insert(make_pair(2, string("Alan")));
mp.insert(pair<int, string>(3, "Colin"));
at()：根据key的值来访问其中元素
// The parameter of the member function at() is the key value.
mp.at(3);
// It can also use the subscript notation [].
int val = mp[2];
find()：函数检索key返回指向键值对的迭代器
man.find(100)
// It will return the iterator found, if not found return the end() iterator.
count()：统计key在表中的关联数量
// Check whether the corresponding key-value exists in the table.
if (man.count("Tom") == 0)
cout << "no this key" << endl;
集合
set也是通过红黑树实现，类似于数学中集合的一种容器。其中的每一个元素都是唯一并且无序的，如果需要重复元素则用multiset。因为它的数据结构的原因，对其中元素检索效率要高过序列容器。set中所有元素都是靠节点来储存，其节点指向父节点和子节点。
方法
insert()：像容器中插入元素erase()：从容器中擦除一定区间的元素，或者擦除特定元素
set<int> nums{1, 2, 3, 5};
nums.insert(4);
nums.erase(3);
find()：从容器中查找某元素并返回指向它的迭代器
// Set can only use function find() to access elements because the elements in
// the unordered container cannot be directly accessed.
set<int> nums{1, 2, 3, 4};
set<int>::iterator it = nums.find(3);
size()：获取集合容器的大小
迭代器
对于STL来说，如果要访问容器中的元素则需要通过迭代器来实现，相当于容器和操纵容器的算法之间的中介，其作用和指针差不多。
迭代器分类
- 正向迭代器
container::iterator it;
- 常量正向迭代器
container::const_iterator it;
- 反向迭代器
container::reverse_iterator it;
- 常量反向迭代器
container::const_reverse_iterator it;
迭代器的使用
对正向迭代器进行++操作时，迭代器会指向容器中的后一个元素 而对反向迭代器进行++操作时，迭代器会指向容器中的前一个元素
因为迭代器就相当于一种适用于容器的特殊指针，所以使用方面同样可以像指针一样操作指向或者++自加自减。
- 正向迭代器
如果是正向迭代器，那么它可以有指针的基本自增操作，并且同类型的迭代器还可以相互赋值，相互比较。
- 双向迭代器
双向迭代器有正向迭代器的所有功能，并且可以自由自增自减。有list、set和map等采用了双向的迭代器。
- 随机访问迭代器
随机访问迭代器是双向迭代器的超集，它支持了非自增自减的跳跃式的访问，是很多支持随机访问的容器的迭代器类型如vector和deque等。
迭代器函数
迭代器作为一个STL中不可或缺的部分，自然也有针对的函数对其进行操作。
| 函数名 | 功能 |
|---|---|
| advance() | 两个参数，分别是迭代器和一个数字，可以达到移动迭代器向前或者向后一定数量的元素 |
| distance() | 计算两个迭代器之间的距离，如果已经在之前则会陷入死循环 |
| iter_swap() | 可以快捷的交换两个迭代器指向的元素的值，普通的swap()交换的是迭代器的值 |
遍历容器
虽然各个容器的数据结构不一样，遍历元素的方式不一样，但是用迭代器遍历不同容器的代码是完全一样的。迭代器一般实现为容器的嵌套类型，在容器内部提供具体的实现。是因为迭代器提供了常用的operator!=、operator++、operator\*等运算符的重载函数，把迭代容器的细节全部隐藏在这些通用的运算符重载函数里面，因此用户侧表现出来的就是，迭代器遍历所有容器的方式都是一样的。
使用简循环
这种是C++11新标准下的for循环遍历，其实底层就是用的迭代器的自增运算实现的，实质上和下面的方法一致。
map<int, string> mp;
for (auto it : mp) {
if (it.frist) {
// If the current key-value pair exists.
} else {
// Otherwise, the key-value pair does not exist.
}
}
正常遍历
正常的声明一个迭代器变量并进行操作，非常常见的作法。
vector<int> nums;
for (vector<int>::iterator it = nums.begin(); it != nums.end(); it++) {
// code...
}