15 STL
STL简介
STL（Standard Template Library，标准模板库）是 C++ 标准库的核心组成部分，提供了一套通用的、可复用的数据结构和算法，基于泛型编程（模板）实现，与具体数据类型无关。
在C++20标准中，STL指的是的如下三章所定义的库：
- 容器库
- 迭代器库
- 算法库
auto和decltype (C++11)
auto x = expr; 用变量初始化值推导变量类型，侧重定义变量。
decltype(expr)用于在编译期推导表达式的类型，而不实际计算表达式的值。
vector<int> ivec(10, 2);
auto it = ivec.begin();
decltype(ivec.begin()) iter;
反向迭代器
对普通迭代器做封装，实现从容器尾部向前遍历的迭代器，遍历方向与正向迭代器相反。
STL 中通过 reverse_iterator 模板实现，提供 rbegin()、rend() 两个成员函数获取反向迭代器。
rbegin()：指向最后一个元素rend()：指向首元素的前一个位置
遍历逻辑：++ 向前走，-- 向后走（和正向迭代器行为相反）。
vector<int>::reverse_iterator riter;
riter = ivec.rend();
*(iter - 1) = 100; // 将第0个元素的值改为100
容器简介
容器（Container）是存储和管理数据集合的对象。分为四类：
- 序列式容器
- 关联式容器
- 无序关联容器
- 容器适配器
顺序容器
简介
顺序容器（Sequence Container，序列式容器）是按元素插入的先后顺序线性存储的容器
| 容器 | 头文件 | 底层结构 | 访问特点 | 插入删除特点 |
|---|---|---|---|---|
| vector | <vector> |
动态连续数组 | 支持随机访问，访问速度快 | 尾部增删高效；头部/中间增删效率低，扩容会重新分配内存 |
| list | <list> |
双向循环链表 | 仅支持双向遍历，不支持随机访问 | 任意位置增删高效；删除元素外，其余迭代器不失效 |
| deque | <deque> |
分段连续内存 | 支持随机访问 | 头部、尾部增删都高效；中间位置增删较慢 |
| array | <array> |
静态原生数组 | 支持随机访问，效率等同普通数组 | 大小固定，无法动态插入、删除元素 |
| forward_list | <forward_list> |
单向链表 | 仅支持单向遍历，不支持随机访问 | 仅头部增删高效，能在已知节点之后进行单向的插入/删除操作 |
构造函数
| 函数使用形式 | 说明 |
|---|---|
C<T> c; |
创建空容器 |
C<T> c(cx); |
创建容器c作为cx的副本，c和cx必须是同类型且元素类型也相同 |
C<T> c(b, e); |
用迭代器b和e所标示范围内的元素初始化c（[b,e)半开区间） |
C<T> c(n, t); |
创建n个值为t的元素 |
C<T> c(n); |
创建n个值初始化的元素 |
C<T> c({...}); / C<T> c = {...}; |
用初始化列表创建（C++11），最为便利 |
vector<int> ivec1(10); // 10个值为0的元素
vector<int> ivec2(10, 1); // 10个值为1的元素
int ia[10] = {0,1,2,3,4,5,6,7,8,9};
vector<int> ivec3(ia, ia + 10); // 用数组初始化
vector<int> ivec4(ivec3); // 拷贝构造
vector<int> ivec5 = {1, 2, 3, 4}; // 初始化列表，可以用常量或变量
元素访问
| 使用形式 | 返回值 | 备注 |
|---|---|---|
c.front() |
第0个元素的引用 | 容器为空则行为未定义 |
c.back() |
最后一个元素的引用 | 容器为空则行为未定义 |
c[index] |
下标为index的元素的引用 | 不检查越界，list不提供该操作 |
c.at(index) |
下标为index的元素的引用 | 进行越界检查，越界则抛出异常，list不提供该操作 |
迭代器
| 使用形式 | 返回值 | 备注 |
|---|---|---|
c.begin() / c.cbegin() |
指向第0个元素的迭代器 | 带c前缀版本返回常迭代器（只读） |
c.end() / c.cend() |
指向最后一个元素的下一位置 | 带c前缀版本返回常迭代器（只读） |
c.rbegin() / c.crbegin() |
逆向迭代器，指向最后一个元素 | 带c前缀版本返回常迭代器（只读） |
c.rend() / c.crend() |
逆向迭代器，指向第0个元素的前一位置 | 带c前缀版本返回常迭代器（只读） |
forward_list 不提供 rbegin() 和 rend()
插入元素
| 使用形式 | 操作效果 |
|---|---|
c.push_back(t) |
在尾端增加值为t的元素 |
c.push_front(t) |
在头端增加值为t的元素（vector不提供） |
c.insert(iter, t) |
在iter所指元素之前插入值为t的元素，返回指向新插入元素的迭代器 |
c.insert(iter, n, t) |
在iter所指元素之前插入n个值为t的元素 |
c.insert(iter, b, e) |
在iter所指元素之前插入[b,e)范围内的元素 |
// 任意位置插入，第一个参数是迭代器
v.insert(v.begin(), 5); // 开头插入 5
v.insert(v.begin()+1,5); //在v的第1个元素（从第0个算起）的位置插入数值5，如a为1,2,3,4，插入元素后为1,5,2,3,4
删除元素
| 使用形式 | 操作效果 | 备注 |
|---|---|---|
c.pop_back() |
删除最后一个元素 | 容器为空则行为未定义 |
c.pop_front() |
删除第一个元素 | 容器为空则行为未定义；vector不提供 |
c.erase(iter) |
删除iter所指向的元素 | 若iter等于c.end()则行为未定义，返回指向被删除元素段下一元素的迭代器 |
c.erase(b, e) |
删除[b,e)范围内的所有元素 | 返回指向被删除元素段下一元素的迭代器 |
c.clear() |
删除所有元素 |
erase返回的迭代器可用于连续删除：
ideq.erase(ideq.erase(iter + 1)); // 连续删除第1、第2个元素
比较操作
| 操作 | 结果 |
|---|---|
== |
元素个数相同且对应位置元素都相等 |
!= |
与==相反 |
<，<=，>，>= |
字典序比较：若一个容器是另一容器的前缀，则较短的小于较长的；否则以第一对不相等元素的比较结果为准 |
容量操作
| 使用形式 | 返回值 / 操作效果 |
|---|---|
c.empty() |
容器为空返回true，否则返回false |
c.size() |
返回当前元素数目，类型为C::size_type |
c.max_size() |
返回可存放元素的最大数目 |
c.resize(n) |
将容器大小调整为n；若n < c.size()则删除多余元素，否则在尾端增加值初始化的新元素 |
c.resize(n, t) |
同上，但新增元素取值为t |
// 重新分配容量
v.resize(10); //将v的现有元素个数调至10个，多则删，少则补，其值随机
v.resize(10,2); //将v的现有元素个数调至10个，多则删，少则补，其值为2
赋值和交换
| 使用形式 | 操作效果 | 备注 |
|---|---|---|
c1 = c2 |
删除c1所有元素，将c2元素复制给c1 | c1和c2必须同类型且元素类型相同 |
c.assign(b, e) |
删除c所有元素，将[b,e)范围内元素复制到c中 | b和e不能指向c中的元素 |
c.assign(n, t) |
删除c所有元素，存放n个值为t的元素 | |
c1.swap(c2) |
交换c1和c2的所有元素（实际上是交换名称） | c1和c2必须同类型且元素类型相同 |
关联式容器
基础概念
关联容器按 键（key） 组织元素，与序列式容器按插入顺序组织不同。
- Map / Dict：映射/字典，键值对的集合
- Set：集合，元素无顺序、不重复
- Pair：键值对，由key和value组成
容器类型
| 类名 | 说明 | 头文件 |
|---|---|---|
map |
通过键存取的关联数组，键唯一 | <map> |
multimap |
支持重复键的关联数组 | <map> |
set |
元素的集合，键即值，不可重复 | <set> |
multiset |
允许重复元素的集合 | <set> |
unordered_map |
无序的map，基于哈希表实现 | <unordered_map> |
unordered_set |
无序的set，基于哈希表实现 | <unordered_set> |
std::pair
pair<T1, T2>代表一个由类型T1和类型T2组成的有序对，定义在<utility>中。
#include <utility>
auto p = std::make_pair("Alice", 100); // 用make_pair构造
std::pair<std::string, int> q("Bob", 90); // 直接构造
p.first; // 访问第一个元素（key）
p.second; // 访问第二个元素（value）
map
map中的元素是键值对，按key有序排列，key唯一。
map的迭代器解引用后得到的是pair<const K, T>类型的引用，因此通过迭代器访问key和value时使用箭头运算符：
for (auto it = m.begin(); it != m.end(); ++it) {
cout << it->first << ",\t" << it->second << '\n';
}
// 等价写法：(*it).first, (*it).second
构造函数
map<K, T> m; // 空map
map<K, T> m(mx); // 拷贝构造
map<K, T> m(b, e); // 用迭代器范围初始化
map<K, T> m = { {"key1", v1}, {"key2", v2} }; // 初始化列表（C++11）
插入元素
insert返回一个pair：第一个元素是指向被插入元素的迭代器，第二个元素指示插入是否成功。
map<string, int> m = {{"hello", 1}};
m.insert({"h", 10});
m.insert(std::pair{"Kageyama", 180});
最简便的方法是直接用下标运算符，同时适用于插入和修改：
m["me"] = 10; // 若"me"不存在则插入，已存在则修改
注意：用
[]访问不存在的key会自动插入一个值初始化的元素。
查找元素
| 使用形式 | 返回值 |
|---|---|
m.find(k) |
存在则返回指向该元素的迭代器；否则返回m.end() |
m.count(k) |
k在容器中的出现次数（map中为0或1） |
删除元素
| 使用形式 | 操作效果 | 备注 |
|---|---|---|
m.erase(k) |
删除键为k的元素 | 返回被删除元素的个数，0表示不存在 |
m.erase(iter) |
删除iter所指向的元素 | 若iter等于m.end()则行为未定义 |
m.erase(b, e) |
删除[b,e)范围内的所有元素 | b要么等于e，要么出现在e之前 |
multimap
multimap与map类似，但允许重复键，键相同的元素相邻存放。
与map的主要区别：
- 不支持下标操作
insert每次调用都会增加新元素（即使key已存在）- 以键为参数的
erase删除该键关联的所有元素，返回被删除元素的数目 count返回指定键的出现次数find返回指向与被查找键关联的第一个元素的迭代器
结合count和find可依次访问与特定键关联的所有元素。
multimap还提供了按键范围查找的操作：
| 使用形式 | 返回值 | 备注 |
|---|---|---|
m.lower_bound(k) |
指向容器中第一个键 >= k 的元素的迭代器 | 若k不存在，两者返回值相同，都指向k应该插入的位置 |
m.upper_bound(k) |
指向容器中第一个键 > k 的元素的迭代器 | |
m.equal_range(k) |
返回一个pair，first等价于lower_bound(k)，second等价于upper_bound(k) |
一次调用获取键k对应的整个范围 |
// 遍历multimap中键为key的所有元素
auto range = m.equal_range(key);
for (auto it = range.first; it != range.second; ++it) {
cout << it->first << " -> " << it->second << endl;
}
set
set中元素本身就是key，没有单独的mapped value。
map支持的操作set基本上都支持，但有区别：
- 不支持下标操作
- 没有定义
mapped_type类型 value_type不是pair类型，而是与key_type相同
set<int> s = {1, 2, 3, 4};
auto iter1 = s.find(3);
auto iter2 = s.insert(3); // 返回值为指向已有3的迭代器，没有实际插入
bool b = (iter1 == iter2); // true