共计 3070 个字符，预计需要花费 8 分钟才能阅读完成。
一、前言
STL：Standard Template Library(规范模板库或泛型库)，是 C ++ 规范库的组成部分。STL 借助模板把罕用的数据结构及其算法实现了一次，并且做到了数据结构和算法的拆散。STL 已齐全被内置到反对 C++ 的编译器中，无需额定装置，这可能也是 STL 被宽泛应用的起因之一。STL 是以源代码的模式提供的。基本上来说，STL 是一些容器（封装有数据结构的模板类）、算法和其余的一些组件的汇合，根本达到了各种存储办法和相干算法的高度优化。
STL 的版本
HP STL
Alexandar Stepanov（STL 规范模板库之父）与 Meng Lee 单干实现。是开放源码的。
SGI STL
HP STL 的一个继承版本，开源、可读性好
STLport
为了使 SGI STL 的根本代码都实用于 VC++ 和 C++ Builder 等多种编译器而提出的，开源
PL STL
参照 HP STL 实现进去的，也是 HP STL 的一个继承版本，因而该头文件中不仅含有 HP STL 的相干受权信息，同时还有 P.J.Plauger 自己的版权信息。非开源。
Rouge Wave STL
由 Rouge Wave 公司开发的，也是继承 HP STL 的一个版本，它也不是开源的。
二、STL 的根本组成
STL 是由容器、算法、迭代器、函数对象、适配器、内存分配器 6 局部形成，其中迭代器、函数对象、适配器、内存分配器是为容器、算法服务。
| 组成部分 | 含意 |
|---|---|
| 容器 | 一些封装数据构造的模板类 |
| 算法 | STL 提供了十分多（大概 100 个）的数据结构算法，它们都被设计成一个个的模板函数，这些算法在 std 命名空间中定义，其中大部分算法都蕴含在头文件 <algorithm> 中，少部分位于头文件 <numeric> 中 |
| 迭代器 | 对容器中数据的读和写，是通过迭代器实现的，扮演着容器和算法之间的胶合剂 |
| 函数对象 | 一个类将 () 运算符重载为成员函数，这个类就称为函数对象类，这个类的对象就是函数对象（又称仿函数） |
| 适配器 | 能够使一个类的接口（模板的参数）适配成用户指定的模式，从而让本来不能在一起工作的两个类工作在一起。值得一提的是，容器、迭代器和函数都有适配器 |
| 内存分配器 | 为容器类模板提供自定义的内存申请和开释性能 |
在 C++ 规范中，STL 被从新组织为 13 个头文件，如下：
| <iterator> | <functional> | <vector> | <deque> | <list> |
| <queue> | <stack> | <set> | <map> | <algorithm> |
| <numeric> | <memory> | <utility> |
留神：
或者是为了向下兼容，或者是为了外部组织布局，某些 STL 版本同时存储具备扩展名和无扩展名的两份文件，倡议最好遵循 C ++ 标准，应用无扩展名的头文件。
三、容器是什么
在理论的开发过程中，存取数据的形式会间接影响到对它们进行增删改查操作的复杂程度和工夫耗费。
简略的了解容器，就是 一些模板类的汇合，但和一般模板类不同的是，容器中封装的是组织数据的办法（也就是数据结构）。STL 提供有 3 类规范容器，别离是序列容器、排序容器和哈希容器，其中后两类容器有时也统称为关联容器，如下表：
| 容器品种 | 性能 |
|---|---|
| 序列容器 | 次要包含 vector 向量容器、list 列表容器以及 deque 双端队列容器。之所以被称为序列容器，是因为元素在容器中的地位同元素的值无关，即容器不是排序的。将元素插入容器时，指定在什么地位，元素就会位于什么地位。 |
| 排序容器 | 包含 set 汇合容器、multiset 多重汇合容器、map 映射容器以及 multimap 多重映射容器。排序容器中的元素默认是由小到大排序好的，即使是插入元素，元素也会插入到适当地位。所以关联容器在查找时具备十分好的性能。 |
| 哈希容器 | C++ 11 新退出 4 种关联式容器，别离是 unordered_set 哈希汇合、unordered_multiset 哈希多重汇合、unordered_map 哈希映射以及 unordered_multimap 哈希多重映射。和排序容器不同，哈希容器中的元素是未排序的，元素的地位由哈希函数确定。 |
以上 3 类容器的存储形式齐全不同，因而应用不同容器实现雷同操作的效率也大不相同。因而在理论应用中，要依据具体的性能抉择最适宜的容器。
四、迭代器
无论是序列容器还是关联容器，最常做的操作无疑是遍历容器中存储的元素，而实现此操作，少数状况会选用“迭代器（iterator）”来实现。
尽管不同容器的内部结构各异，但它们实质上都是用来存储大量数据的，所以容器有一些操作方法是相似的，因而齐全能够利用泛型的技术，将其设计成实用所有容器的通用算法，从未将容器和算法拆散。
1、迭代器类别
STL 规范库为每一种规范容器定义了一种迭代器类型，即不同容器的迭代器不同，因而容器的迭代器性能的强弱也不同，进而决定了容器是否哦反对 STL 中的某些算法。
罕用的迭代器按性能强弱分为 输出迭代器、输入迭代器、前向迭代器、双向迭代器、随机拜访迭代器 5 种。输出迭代器和输入迭代器比拟非凡，它们不是把数组或容器当做操作对象，而是把输出流 / 输入流作为操作对象。对于输出迭代器和输入迭代器在这里临时不多讲。
假如存在一个迭代器 Iter
1）前向迭代器（forward iterator）
Iter 反对 ++Iter、Iter++、*Iter 操作、被复制或赋值、可应用 == 和!= 运算符进行比拟
2）双向迭代器（bidirectional iterator）
双向迭代用具有正向迭代器的全副性能，除此之外，还能够进行 –Iter 或者 Iter– 操作（即一次向后挪动一个地位）。
3）随机拜访迭代器（random access iterator）
随机拜访迭代用具有双向迭代器的全副性能。除此之外，假如 i 是一个整型变量或常量，则 Iter 还反对以下操作：
| 操作 | 阐明 |
|---|---|
| Iter+=i | 使得 Iter 往后挪动 i 个元素 |
| Iter-=i | 使得 Iter 往前挪动 i 个元素 |
| Iter+i | 返回 Iter 前面第 i 个元素的迭代器 |
| Iter-i | 返回 Iter 后面第 i 个元素的迭代器 |
| Iter[i] | 返回 Iter 前面第 i 个元素的援用 |
两个随机拜访迭代器 p1、p2 还能够用 <、>、<=、>= 运算符进行比拟。另外，表达式 p2-p1 也是有定义的，其返回值示意 p2 所指向元素和 p1 所指向元素的序号之差。
五、容器对应的迭代器
1、对应关系
| 容器 | 迭代器类别 |
|---|---|
| array | 随机拜访迭代器 |
| vector | 随机拜访迭代器 |
| deque | 随机拜访迭代器 |
| list | 双向迭代器 |
| set / multiset | 双向迭代器 |
| map / multimap | 双向迭代器 |
| forward_list | 前向迭代器 |
| unordered_map / unordered_multimap | 前向迭代器 |
| unordered_set / unordered_multiset | 前向迭代器 |
| stack | 不反对迭代器 |
| queue | 不反对迭代器 |
留神：
容器适配器 stack 和 queue 没有迭代器，它们蕴含有一些成员函数，能够用来对元素进行拜访。
2、迭代器的定义形式
| 迭代器类别 | 格局 |
|---|---|
| 正向迭代器 | 容器类名::iterator 迭代器名; |
| 常量正向迭代器 | 容器类名::const_iterator 迭代器名; |
| 反向迭代器 | 容器类名::reverse_iterator 迭代器名; |
| 常量反向迭代器 | 容器类名::const_reverse_iterator 迭代器名; |
阐明：
* 迭代器名：迭代器指向的元素
常量迭代器和十分量迭代器的别离在于：通过十分量迭代器还能批改其指向的元素
反向迭代器和正向迭代器的区别在于：对正向迭代器进行 ++ 操作时，迭代器会指向容器中的后一个元素；而对反向迭代器进行 ++ 操作时，迭代器会指向容器中的前一个元素。
以上 4 种定义迭代器的形式，并不是每个容器都实用。