💭 写在前面
一听 list ，我们就知道是个双向带头循环链表。list 在实际的运用中用的没有 vector 多，包括大家在刷题的时候 list 也出现的很少，因为 list 不支持随机访问，有很多数据堆在那里你可能还需要排序一下，list 要排序，就是一个大问题，所以用 vector 的情况较多。
但 list 也并不是一文不值的，如果需要频繁的插入和删除，特别是需要在头尾部插入和删除，坐拥 的 list 就有了用武之地，比如后期讲 LRUCache 的时候就用得到。
如果觉得不错，欢迎点赞收藏加关注。话不多说，我们正式开始！
Ⅰ. list 的介绍和使用
0x00 初识 list
我们已经学习过 string 和 vector 了，想必大家已经掌握了查文档的技能。
现在我们要学习如何使用 list，最好的方式仍然是打开文档去学习！
🔍 查看文档：list - C++ Reference
template < class T, class Alloc = allocator<T> > class list;
① list 是一个顺序容器：
是允许你在任意位置进行 插入删除的顺序容器，并提供双向迭代器。
② list的底层是双向链表结构：
双向链表中每个元素存储在互不相关的独立结点中，在结点中通过两个指针指向其前后元素。
③ list 与 forward_list 非常相似：
它们很相似，最大的不同 forward_list 是单链表，只能向前迭代（也让其因此更简单高效）。
④ 与其他的序列式容器相比（array，vector，deque）：
list 通常在任意位置进行插入、移除元素的执行效率更好，因为是 。
list 和 forward_list 最大的缺陷是不支持任意位置的随机访问。举个例子：
如果要访问 list 中的第 6 个元素，必须从已知的位置（比如头部或者尾部）迭代到该位置，
在这段位置上迭代需要线性的时间开销。不仅如此，list 还需要一些额外的空间，
以保存每个结点的 "相关联信息"（对于存储类型较小元素的大 list 来说这 可能是一个重要的因素）
0x01 创建 list
📜 头文件：<list>
#include <list> using namespace std;
💬 引入头文件后，我们创建一个 <int> 类型的 list，我们给它取名为 L ：
#include <iostream> #include <list> using namespace std; int main(void) { list<int> L; // 创建一个 <int> 类型的 list return 0; }
Ⅱ. list 的修改操作
0x00 引入：
带头双向循环链表我们在数据结构专栏中有过详细的讲解，并且还带大家实现过。
我们知道，带头双向循环链表是非常合适任意位置的插入和删除的，因为通通都是 .
| 函数声明 | 接口说明 |
| push_front | 头插：在 list 首元素前插入值为 val 的元素 |
| pop_front | 头删：删除 list 中的第一个元素 |
0x01 push_back 头插
在 list 尾部插入值为 val 的元素。
💬 用 push_back 对 L 尾插：
#include <iostream> #include <list> using namespace std; int main(void) { list<int> L; // 创建一个<int>类型的list L.push_back(1); L.push_back(2); L.push_back(3); L.push_back(4); return 0; }
随手尾插了 ，我们现在来打印，看看尾插的效果如何。
❓ 首先思考一个问题：我们还能用 "下标 + 方框号" 的方式遍历吗？
💡 不行！因为 list 是链表，是通过指针连接的， 所以 list 不支持随机访问！
而 string 和 vector 可以，是因为它底层的结构是连续的数组，它的物理结构是连续的。
" 呵呵，现在到我迭代器了？"
💬 iterator：
int main(void) { /* 创建一个<int>类型的list */ list<int> L; /* 尾插一些数据 */ L.push_back(1); L.push_back(2); L.push_back(3); L.push_back(4); /* 利用迭代器遍历并打印 */ list<int>::iterator it = L.begin(); while (it != L.end()) { cout << *it << " "; it++; } cout << endl; return 0; }
🚩 运行结果如下：
（成功打印）
如果我们想倒着遍历，我们就可以使用 —— 反向迭代器
反向迭代器是反着遍历访问元素的，我们用 rbegin() 和 rend() 去操作。
"社稷有累卵之危，生灵有倒悬之急" —— 王司徒
💬 reverse_iterator：
int main(void) { /* 创建一个<int>类型的list */ list<int> L; /* 尾插一些数据 */ L.push_back(1); L.push_back(2); L.push_back(3); L.push_back(4); /* 反向迭代器倒着遍历并打印 */ list<int>::reverse_iterator rit = L.rbegin(); while (rit != L.rend()) { cout << *rit << " "; rit++; } cout << endl; return 0; }
🚩 运行结果如下：
（像 const 迭代器，只能读不能写，这里我们就不壹壹演示了）
0x02 push_front 头插
💬 用 push_front 头插一些数据到 L 中：
void list_test2() { /* 创建一个<int>类型的list */ list<int> L; /* 头插一些数据 */ L.push_front(1); L.push_front(2); L.push_front(3); L.push_front(4); /* 利用范围for打印 */ for (auto e : L) cout << e << " "; }
🚩 运行结果如下：
能用迭代器自然也就能用范围 for，因为语法简洁，我们下面都用范围 for 去打印。
（尾删和头删同理，这些操作我们已经接触过很多次了，下面介绍就直接贴代码，不做讲解了）
0x03 pop_back 尾删
💬 删除 L 中的最后一个数据：
void list_test3() { /* 创建一个<int>类型的list */ list<int> L; /* 尾插一些数据 */ L.push_back(1); L.push_back(2); L.push_back(3); L.push_back(4); cout << "删除前："; for (auto e : L) cout << e << " "; cout << endl; /* 尾删 */ L.pop_back(); cout << "删除后："; for (auto e : L) cout << e << " "; cout << endl; }
🚩 运行结果如下：
💬 当然，如果表内没有元素，进行删除操作，就会触发断言：
void list_test5() { list<int> L; L.pop_back(); }
（采用的是暴力的处理方式）
0x04 pop_front 头删
💬 删除 L 中的第一个数据：
void list_test4() { /* 创建一个<int>类型的list */ list<int> L; /* 尾插一些数据 */ L.push_back(1); L.push_back(2); L.push_back(3); L.push_back(4); cout << "删除前："; for (auto e : L) cout << e << " "; cout << endl; /* 头删 */ L.pop_front(); cout << "删除后："; for (auto e : L) cout << e << " "; cout << endl; }
🚩 运行结果如下：
0x05 insert 插入
在上一节讲解 vector 实现的时候，我们对迭代器失效的问题进行了一些简单探讨。
这里 list 的 insert 同样也会涉及迭代器失效的问题，这个我们在模拟实现的时候再次探讨。
（这里笔者绝非偷懒，(～￣▽￣)～ 因为模拟实现的时候结合底层去讲解会更容易理解）
0x06 clear 清空
清空 list 中的有效元素，并使容器的大小 size 变为 0。
💬 用 clear 清空 L 中有效元素：
void list_test5() { list<int> L; L.push_back(1); L.push_back(2); L.push_back(3); L.push_back(4); cout << "清空前："; for (auto e : L) cout << e << " "; cout << endl; /* 清空有效元素 */ L.clear(); cout << "清空后："; for (auto e : L) cout << e << " "; cout << endl; }
🚩 运行结果如下：
0x07 erase 删除
任意位置删除，这里仍然是用迭代器区间，find() 查找元素。
💬 erase：
void list_test6() { list<int> L; L.push_back(1); L.push_back(2); L.push_back(3); L.push_back(4); for (auto e : L) cout << e << " "; cout << endl; list<int>::iterator it = find(L.begin(), L.end(), 4); // 删除元素：4 if (it != L.end()) { // 判断it是否存在 L.erase(it); // 删除it } else { cout << "没找到"; } for (auto e : L) cout << e << " "; cout << endl; }
🚩 运行结果如下：
📌 再次提醒：erase 之前要做判断！如果待删目标不存在，会寄！
（如果不判断，并且待删目标不存在）
