STL，英文全称 standard template library，中文可译为标准模板库或者泛型库，其包含有大量的模板类和模板函数，是 C++ 提供的一个基础模板的集合，用于完成诸如输入/输出、数学计算等功能。
从根本上说，STL 是一些容器、算法和其他一些组件的集合，所有容器和算法都是总结了几十年来算法和数据结构的研究成果，汇集了许多计算机专家学者经验的基础上实现的，因此可以说，STL 基本上达到了各种存储方法和相关算法的高度优化。
vector 的底层为顺序表（数组），list 的底层为双向链表，deque 的底层为循环队列，set 的底层为红黑树，hash_set 的底层为哈希表
STL 是由容器、算法、迭代器、函数对象、适配器、内存分配器这 6 部分构成，其中后面 4 部分是为前 2 部分服务的
| 组件 | 描述 |
|---|---|
| 容器 | 一些封装数据结构的模板类，例如 vector 向量容器、list 列表容器等。 |
| 算法 | STL 提供了非常多（大约 100 个）的数据结构算法，它们都被设计成一个个的模板函数，这些算法在 std 命名空间中定义，其中大部分算法都包含在头文件 <algorithm> 中，少部分位于头文件 <numeric> 中。 |
| 迭代器 | 在 C++ STL 中，对容器中数据的读和写，是通过迭代器完成的，扮演着容器和算法之间的胶合剂。 |
| 函数对象 | 如果一个类将 () 运算符重载为成员函数，这个类就称为函数对象类，这个类的对象就是函数对象（又称仿函数）。 |
| 适配器 | 可以使一个类的接口（模板的参数）适配成用户指定的形式，从而让原本不能在一起工作的两个类工作在一起。值得一提的是，容器、迭代器和函数都有适配器。 |
| 内存分配器 | 为容器类模板提供自定义的内存申请和释放功能，由于往往只有高级用户才有改变内存分配策略的需求，因此内存分配器对于一般用户来说，并不常用。 |
C++ STL头文件
<iterator> |
<functional> |
<vector> |
<deque> |
|---|---|---|---|
<list> |
<queue> |
<stack> |
<set> |
<map> |
<algorithm> |
<numeric> |
<memory> |
<utility> |
STL序列式容器，其共同的特点是不会对存储的元素进行排序，元素排列的顺序取决于存储它们的顺序。
array<T,N>（数组容器）：表示可以存储 N 个 T 类型的元素。此类容器一旦建立，其长度就是固定不变的，不能增加或删除元素，只能改变某个元素的值；vector<T>（向量容器，常用）：用来存放 T 类型的元素，是一个长度可变的序列容器，即在存储空间不足时，会自动申请更多的内存。使用此容器，在尾部增加或删除元素的效率最高 O(1) ，在其它位置插入或删除元素效率较差 O(n) ；deque<T>（双端队列容器，常用）：和 vector 非常相似，区别在于使用该容器不仅尾部插入和删除元素高效，在头部插入或删除元素也同样高效 O(1) ，但是在容器中某一位置处插入或删除元素，时间复杂度为 O(n) 线性阶；list<T>（链表容器）：是一个长度可变的、由 T 类型元素组成的序列，它以双向链表的形式组织元素，在这个序列的任何地方都可以高效地增加或删除元素O(1)，但访问容器中任意元素的速度要比前三种容器慢，这是因为list<T>必须从第一个元素或最后一个元素开始访问，需要沿着链表移动，直到到达想要的元素。forward_list<T>（正向链表容器）：和 list 容器非常类似，只不过它以单链表的形式组织元素，它内部的元素只能从第一个元素开始访问，是一类比链表容器快、更节省内存的容器。
关联式容器的存储的元素为一个一个的“键值对”（ <key,value> ），它的功能是在使用关联式容器的过程中，如果已知目标元素的键的值，则直接通过该键就可以找到目标元素，而无需再通过遍历整个容器的方式。
关联式容器存储的元素，默认会根据各元素的键值的大小做升序排序。
关联式容器所具备的这些特性，归咎于 STL 标准库在实现该类型容器时，底层选用了 「红黑树」这种数据结构来组织和存储各个键值对
map，定义在<map>头文件中，使用该容器存储的数据，其各个元素的键必须是唯一的（即不能重复），该容器会根据各元素键的大小，默认进行升序排序（调用std::less<T>）set，定义在<set>头文件中，使用该容器存储的数据，各个元素键和值完全相同，且各个元素的值不能重复（保证了各元素键的唯一性）。该容器会自动根据各个元素的键（其实也就是元素值）的大小进行升序排序（调用std::less<T>）multimap，常用，定义在<map>头文件中，和 map 容器唯一的不同在于，multimap 容器中存储元素的键可以重复multiset，常用，定义在<set>头文件中，和 set 容器唯一的不同在于，multiset 容器中存储元素的值可以重复（一旦值重复，则意味着键也是重复的）
无序容器具有以下 2 个特点
- 无序容器内部存储的键值对是无序的，各键值对的存储位置取决于该键值对中的键
- 和关联式容器相比，无序容器擅长通过指定键查找对应的值（平均时间复杂度为 O(1)）；但对于使用迭代器遍历容器中存储的元素，无序容器的执行效率则不如关联式容器
本质上的不同，无序容器的底层实现采用的是「哈希表」的存储结构，关联式容器的底层实现采用的「红黑树」
实际场景中如果涉及大量遍历容器的操作，建议首选关联式容器；反之，如果更多的操作是通过键获取对应的值，则应首选无序容器
unordered_map，常用，存储键值对 <key, value> 类型的元素，其中各个键值对键的值不允许重复，且是无序的unordered_set，常用，不再以键值对的形式存储数据，而是直接存储数据元素本身（当然也可以理解为，该容器存储的全部都是键 key 和值 value 相等的键值对，正因为它们相等，因此只存储 value 即可）。另外，该容器存储的元素不能重复，且是无序的unordered_multimap，和 unordered_map 唯一的区别在于，该容器允许存储多个键相同的键值对unordered_multiset，和 unordered_set 唯一的区别在于，该容器允许存储值相同的元素
容器适配器是一个封装了序列容器的类模板，它在一般序列容器的基础上提供了一些不同的功能。之所以称作适配器类，是因为它可以通过适配容器现有的接口来提供不同的功能。
stack<T>，常用，是一个封装了deque<T>容器的适配器类模板，默认实现的是一个后入先出（Last-In-First-Out，LIFO）的压入栈。定义在头文件 stack 中queue<T>，常用，是一个封装了deque<T>容器的适配器类模板，默认实现的是一个先入先出（First-In-First-Out，LIFO）的队列。可以为它指定一个符合确定条件的基础容器。定义在头文件 queue 中priority_queue<T>，常用，是一个封装了vector<T>容器的适配器类模板，默认实现的是一个会对元素排序，从而保证最大元素总在队列最前面的队列。定义在头文件 queue 中
| 容器适配器 | 成员函数 | 基础容器 |
|---|---|---|
| stack | empty()、size()、back()、push_back()、pop_back() | 默认 deque，支持 vector、list |
| queue | empty()、size()、front()、back()、push_back()、pop_front() | 默认 deque，支持 list |
| priority_queue | empty()、size()、front()、push_back()、pop_back() | 默认 vector，支持 deque |
无论是序列容器还是关联容器，最常做的操作无疑是遍历容器中存储的元素，而实现此操作，多数情况会选用“迭代器（iterator）”来实现
我们知道，尽管不同容器的内部结构各异，但它们本质上都是用来存储大量数据的，换句话说，都是一串能存储多个数据的存储单元。因此，诸如数据的排序、查找、求和等需要对数据进行遍历的操作方法应该是类似的。
既然类似，完全可以利用泛型技术，将它们设计成适用所有容器的通用算法，从而将容器和算法分离开。但实现此目的需要有一个类似中介的装置，它除了要具有对容器进行遍历读写数据的能力之外，还要能对外隐藏容器的内部差异，从而以统一的界面向算法传送数据。
这是泛型思维发展的必然结果，于是迭代器就产生了。简单来讲，迭代器和 C++ 的指针非常类似，它可以是需要的任意类型，通过迭代器可以指向容器中的某个元素，如果需要，还可以对该元素进行读/写操作。
常用的迭代器按功能分为输入迭代器、输出迭代器、前向迭代器、双向迭代器、随机访问迭代器 5 种，功能越来越强
1、前向迭代器（forward iterator）
假设 p 是一个前向迭代器，则 p 支持 ++p，p++，*p 操作，还可以被复制或赋值，可以用 == 和 != 运算符进行比较。此外，两个正向迭代器可以互相赋值。
2、双向迭代器（bidirectional iterator）
双向迭代器具有正向迭代器的全部功能，除此之外，假设 p 是一个双向迭代器，则还可以进行 --p 或者 p-- 操作（即一次向后移动一个位置）
3、随机访问迭代器（random access iterator）
随机访问迭代器具有双向迭代器的全部功能。除此之外，假设 p 是一个随机访问迭代器，i 是一个整型变量或常量，则 p 还支持以下操作：
- p+=i：使得 p 往后移动 i 个元素。
- p-=i：使得 p 往前移动 i 个元素。
- p+i：返回 p 后面第 i 个元素的迭代器。
- p-i：返回 p 前面第 i 个元素的迭代器。
- p[i]：返回 p 后面第 i 个元素的引用。
此外，两个随机访问迭代器 p1、p2 还可以用 <、>、<=、>= 运算符进行比较。另外，表达式 p2-p1 也是有定义的，其返回值表示 p2 所指向元素和 p1 所指向元素的序号之差（也可以说是 p2 和 p1 之间的元素个数减一）
| 容器 | 对应的迭代器类型 |
|---|---|
| array | 随机访问迭代器 |
| vector | 随机访问迭代器 |
| deque | 随机访问迭代器 |
| list | 双向迭代器 |
| set / multiset | 双向迭代器 |
| map / multimap | 双向迭代器 |
| forward_list | 前向迭代器 |
| unordered_map / unordered_multimap | 前向迭代器 |
| unordered_set / unordered_multiset | 前向迭代器 |
| stack | 不支持迭代器 |
| queue | 不支持迭代器 |
| 迭代器定义方式 | 具体格式 |
|---|---|
| 正向迭代器 | 容器类名::iterator 迭代器名; |
| 常量正向迭代器 | 容器类名::const_iterator 迭代器名; |
| 反向迭代器 | 容器类名::reverse_iterator 迭代器名; |
| 常量反向迭代器 | 容器类名::const_reverse_iterator 迭代器名; |
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int arr[5] = {1, 2, 3, 4, 5};
vector<int> vec(arr, arr + 5); //vec被初始化成有 5 个元素
vector<int>::iterator iter; //创建一个正向迭代器，当然也支持其他 3 种定义迭代器的方式
// 第一种遍历方法：vec[i]
for (int i = 0; i < vec.size(); ++i)
cout << vec[i] << " ";
cout << endl; // 1 2 3 4 5
//第二种遍历方法：用 != 比较两个迭代器
for (iter = vec.begin(); iter != vec.end(); ++iter)
cout << *iter << " ";
cout << endl; // 1 2 3 4 5
//第三种遍历方法：用 < 比较两个迭代器
for (iter = vec.begin(); iter < vec.end(); ++iter)
cout
<< *iter << " ";
cout << endl; // 1 2 3 4 5
//第四种遍历方法：随机访问迭代器支持 "+= 整数" 的操作
iter = vec.begin();
while (iter < vec.end())
{
cout << *iter << " ";
iter += 2; // 1 3 5
}
}完全可以将迭代器适配器视为普通迭代器。之所以称为迭代器适配器，是因为这些迭代器是在输入迭代器、输出迭代器、正向迭代器、双向迭代器或者随机访问迭代器这些基础迭代器的基础上实现的。
1、反向迭代器（reverse_iterator）
又称“逆向迭代器”，其内部重新定义了递增运算符（++）和递减运算符（--），专门用来实现对容器的逆序遍历。
2、安插型迭代器（inserter或者insert_iterator）
通常用于在容器的任何位置添加新的元素，需要注意的是，此类迭代器不能被运用到元素个数固定的容器（比如 array）上。
3、流迭代器（istream_iterator / ostream_iterator）
输入流迭代器用于从文件或者键盘读取数据；相反，输出流迭代器用于将数据输出到文件或者屏幕上。
4、流缓冲区迭代器（istreambuf_iterator / ostreambuf_iterator）
输入流缓冲区迭代器用于从输入缓冲区中逐个读取数据；输出流缓冲区迭代器用于将数据逐个写入输出流缓冲区。
5、移动迭代器（move_iterator）
此类型迭代器是 C++ 11 标准中新添加的，可以将某个范围的类对象移动到目标范围，而不需要通过拷贝去移动。