I - 概述 STL
1.1 - 范围与定义
Standard Template Library (标准模板库) 包含于 Standard Library (标准库) 中，都封装于命名空间 std 中。
属于泛型编程 (Generic Programming) ，使用模板 (template) 为主要工具来编写的程序。
1.2 - 组成与关系
STL 包含六大组件 :
- 容器 (Containers)
- 分配器 (Allocators)
- 算法 (Algorithms)
- 迭代器 (Iterators)
- 适配器 (Adapters)
- 仿函数 (Functors)
这六大组件之间的关系图如下：
容器 用来存储数据，数据占用内存，容器背后有一个部件负责内存的分配与释放，这个组件就是分配器 ，此操作对用户透明，所以在使用容器时，基本不需要去管内存的分配与释放。
算法 ，如常用的 sort 排序和查找等，算法通过 迭代器 去访问容器的内容，有时我们排序需要自定义排序方式，这些自定义的方法就是 仿函数 ，其他的一些细节的操作就是通过 适配器 来完成的。
1.3 - 实用举例
如下，使用了六个组件的一段代码：
int arr[6] = {
19, 23, 52, 18, 50, 9 };
std::vector<int, allocator<int>> vec(arr, arr+6);
std::cout << count_if(vec.begin(), vec.end(),
not1(bind2nd(less<int>(), 50)));
首先来识别一下代码中的各个元素：
代码中首先创建一个 6 个元素的整型数组，然后基于数组构建一个 整型容器 vector<int> vec ，容器使用整型的默认分配器，count_if 为算法，通过 vec 的首尾迭代器访问容器中的全部元素，此算法为条件计数，仿函数 less<int>() 比较任意两个元素的小于是否满足。
bind2nd 为仿函数适配器，将仿函数的第二个元素绑定为 50 ，即所有小于 50 的元素，not1 同样为仿函数适配器，将原来的结果取反，即 vec 中所有大于等于 50 的元素个数，所以输出结果为 2。
II - 概述容器
2.1 - 迭代器
迭代器是一种泛化的指针，可以使用 ++ 和 -- 去访问容器中的元素，需要注意它的访问区间是一个 前闭后开 的区间。
c.begin() 解引用是容器的第一个元素，c.end() 指向的是容器最后一个元素的下一个元素，所以不能解引用，即 *(c.end()); 可能导致程序异常，程序崩溃异常退出。
基于范围的 for 循环 (range-based for loop)，使用迭代器遍历元素语法：
for (decl : coll) {
statement;
}
// 遍历
for (auto elem : container) {
// ...
}
// 修改
for (auto& elem : container) {
//...
}
// 查找，建议使用 算法
auto iter = std::find(c.begin(), c.end(), target);
示例
std::vector<double> vec = {
/* ... */};
// 遍历
for (double elem : vec) {
std::cout << elem << std::endl;
}
// 修改
for (double& elem : vec) {
elem *= 3;
}
// 查找
std::vector<double>::iterator iter = std::find(vec.begin(), vec.end(), 1.0);
2.2 - 容器的结构与分类
- 序列式容器
- 关联式容器 (associative containers) ，基于红黑树的实现
- 不定序容器 (unordered containers)， 或者叫无序容器，基于哈希表实现
2.3 - 序列式容器
- array，数组：固定大小，初始时需指定长度，不可更改。元素数量不能动态增长，支持随机访问。
- vector，向量，可变长度数组：可单向动态增长，两倍扩容或会造成内存空置。支持下标，随机访问，尾部以外的位置插入/删除可能会比较慢。
插入使用insert，尾部添加元素push_back和emplace_back，不提供push_front和emplace_front接口，由于首部添加需要移动所有元素，耗时操作。
- deque，双向增长，实质上伪双边增长，实现为映射管理多个分段连续内存。
两端操作都比较快，支持push_back，emplace_back和push_front，emplace_front。
- list，双向链表，每个元素包含两个指针，支持双向顺序访问。在链表任何位置插入/删除都很快。动态单个增长， “一个萝卜，一个坑” ，没有空置内存，但相同元素情况下，占用内存大于 vector 。
非连续内存，不支持随机访问，但遍历缓慢
- forward_list，单链表，与 list 相同，在任何位置插入删除都很快。相较 list，一个指针更节约内存，但迭代器不支持递减运算符 (
--)，不提供push_back和emplace_back尾端插入函数，由于过于耗时。
- stack 与 queue 栈与队列 ，为容器适配器，表示两种数据结构 栈 和 队列 ，栈先进后出 (FILO first in last out)，队列先进先出 (FIFO first in first out) 。插入方式
push，删除方式pop。不属于容器，不对外提供迭代器访问，不提供随机访问，会破坏结构设计。
2.4 - 关联式容器
关联式容器底层实现为红黑树，查询快，但插入耗时较久，由于每次插入都需要排序。
- set，集合，元素只存在一份，不重复。
- multiset，相同的元素可存在多份。
- map，键值对 (key value pair)，键存在时，
insert,emplace都会插入失败，[]赋值会覆盖。使用[]访问时，键不存在会创建。C++ 17 为提高性能，增加try_emplace接口，在键存在时，不会构造参数，在值复杂时可较多节省内存，提升性能。 - multimap，相同的键可存在多份，不支持
[]访问。
2.5 - 不定序容器
不定序容器底层实现为哈希表，插入元素，对其计算哈希值，分配到对应的 bucket （桶）上，哈希值计算可能会产生哈希冲突，即不同的值计算的哈希值相同。哈希表的查找时间复杂度为 O(1)，虽然元素哈希值相同时，还是会进行顺序查找，但不改变不定序容器查找基本为 O(1) 的情况。
为了避免较多的顺序查找，当 bucket 数量与元素个数相同时，bucket 会进行两倍扩容，之前的元素会被打散，重新计算哈希值，分布到新的 bucket 后。也会产生较多的内存空置，如 bucket 后无任何的元素。
- unordered_map
- unordered_set
- unordered_multimap
- unordered_multiset
先哈希查找，后循序查找。
2.6 - 总述
- 查询
序列式容器查找为顺序查找时间复杂度为 O(n)，关联式容器为红黑树时间复杂度 O(log n)，不定序容器为哈希表基本上为 O(1)。
查询效率：不定序容器 > 关联式容器 > 序列式容器
关联式容器和不定序容器都提供自身的 find 函数， STL 算法也提供 std::find 查找，但使用容器自身的查找会更快捷
- 排序
list 容器自身也提供 sort 接口，STL 算法提供的 std::sort 查找无法对 list 进行查找，因为 std::sort 接收的迭代器需要为随机访问迭代器类型，而 list 的迭代器为双向顺序访问迭代器。编码时若使用则会产生编译错误。
std::list<int> container = {
5, 6, 10, 1, 4, 8 };
std::sort(container.begin(), container.end(), greater<int>());
编译报错：
C:\Program Files (x86)\Microsoft Visual Studio\2019\Enterprise\VC\Tools\MSVC\14.20.27508\include\algorithm(3358): error C2676: binary '-': 'const std::_List_unchecked_iterator<std::_List_val<std::_List_simple_types<_Ty>>>' does not define this operator or a conversion to a type acceptable to the predefined operator
1> with
1> [
1> _Ty=int
1> ]
1>D:\GZC\Work\Train\TrainDemo\TrainDemo\TrainDemo\TrainDemo.cpp(17): note: see reference to function template instantiation 'void std::sort<std::_List_iterator<std::_List_val<std::_List_simple_types<_Ty>>>,std::greater<_Ty>>(const _RanIt,const _RanIt,_Pr)' being compiled
1> with
1> [
1> _Ty=int,
1> _RanIt=std::_List_iterator<std::_List_val<std::_List_simple_types<int>>>,
1> _Pr=std::greater<int>
1> ]
1>C:\Program Files (x86)\Microsoft Visual Studio\2019\Enterprise\VC\Tools\MSVC\14.20.27508\include\algorithm(3358): error C2672: '_Sort_unchecked': no matching overloaded function found
1>C:\Program Files (x86)\Microsoft Visual Studio\2019\Enterprise\VC\Tools\MSVC\14.20.27508\include\algorithm(3358): error C2780: 'void std::_Sort_unchecked(_RanIt,_RanIt,iterator_traits<_Iter>::difference_type,_Pr)': expects 4 arguments - 3 provided
1>C:\Program Files (x86)\Microsoft Visual Studio\2019\Enterprise\VC\Tools\MSVC\14.20.27508\include\algorithm(3328): note: see declaration of 'std::_Sort_unchecked'
需要修改为
std::list<int> container = {
5, 6, 10, 1, 4, 8 };
container.sort(greater<int>());
III - 参考书目
《STL源码剖析》 — 侯捷
《C++ Primer》— 中文版 第 5 版
