第十四章 标准模板库(STL)
STL 是“Standard Template Library”的缩写，中文译为“标准模板库”。STL 是 C++ 标准库的一部分，不用单独安装。
STL是一套功能强大的 C++ 模板类，提供了通用的模板类和函数，借助模板把常用的数据结构及其算法都实现了一遍，并且做到了数据结构和算法的分离。例如，vector 的底层为顺序表（数组），list 的底层为双向链表，deque 的底层为循环队列，set 的底层为红黑树，hash_set 的底层为哈希表。
C++ 标准模板库的核心包括以下三个组件(component)：
| 组件 | 描述 |
| 容器（Containers） | 容器可以看成是数组的拓展，是用来管理某一类对象的集合。C++ 提供了各种不同类型的容器，比如 栈(stack)、队列(queque)、链表(list)、向量(vector)、映射(map) 等。 |
| 算法（Algorithms） | 算法作用于容器。它们提供了执行各种操作的方式，包括对容器内容执行初始化、排序、搜索和转换等操作。 |
| 迭代器（iterators） | 迭代器可以认为是容器的”专用指针”，来表示数据位置，用于存取数据，遍历对象集合的元素。这些集合可能是容器，也可能是容器的子集。 |
STL（Standard Template Library）中的容器主要分为两大类：顺序容器和关联容器。
1. 顺序容器（Sequence Containers）
顺序容器用于按顺序存储数据，支持通过索引或迭代器访问元素，通常元素在内存中是连续存储的。常用的顺序容器包括：
vector：动态数组，支持高效的随机访问和在末尾插入/删除操作。插入或删除元素时，如果触发了容量扩展，性能会下降。deque：双端队列，允许在两端插入和删除元素，支持高效的随机访问。适用于需要在两端频繁插入/删除操作的场景。list：双向链表，支持高效的任意位置插入和删除，但随机访问效率低（O(n)）。forward_list：单向链表，只支持前向遍历，适用于需要极简链表结构的场景。array：定长数组，存储的元素数固定，性能接近原生数组，且支持 STL 提供的接口。
顺序容器的特点是元素的存储位置与插入顺序有关，适合需要按照顺序访问元素的场景。
2. 关联容器（Associative Containers）
关联容器用于通过键来存储数据，通常是通过树或哈希表实现的。这类容器自动根据键的顺序（有序）或哈希值（无序）来管理数据。常用的关联容器包括：
map：键值对的有序容器，底层实现为红黑树，键是唯一的，支持高效的查找、插入和删除操作（O(log n)）。multimap：允许重复键的有序关联容器，底层同样是红黑树。set：存储唯一元素的有序集合，底层为红黑树，支持高效的查找、插入和删除（O(log n)）。multiset：允许重复元素的有序集合，底层为红黑树。unordered_map：键值对的无序容器，底层实现为哈希表，键是唯一的，支持 O(1) 时间复杂度的查找和插入。unordered_multimap：允许重复键的无序关联容器，底层为哈希表。unordered_set：存储唯一元素的无序集合，底层为哈希表，支持 O(1) 时间复杂度的查找和插入。unordered_multiset：允许重复元素的无序集合，底层为哈希表。
关联容器适合需要快速查找、插入、删除特定键的场景。
这两类容器的主要区别在于存储和访问元素的方式：顺序容器强调顺序性，关联容器则侧重通过键进行高效查找和管理。