前言
学完 vector 之后，再看 list 会很直观：它也是 STL 里的序列容器，但底层换成了双向循环链表。这个变化直接决定了它的强项和短板。中间插入、删除很顺手，随机访问就别指望了。
一、list 的介绍和使用
1.1 list 的基本概念
list 底层通常可以理解成带头结点的双向循环链表。节点不要求连续存储，所以它在频繁插入、删除时更有优势；代价是不能像 vector 那样通过下标直接定位元素。
1.2 常用接口
构造
list 支持默认构造、拷贝构造、区间构造，以及 C++11 的列表初始化。
list<int> l1; // 空列表
list<int> l2(4, 100); // 4 个 100
list<int> l3(l2.begin(), l2.end()); // 区间构造
list<int> l4{1, 2, 3}; // 列表初始化
迭代器
list 同样提供正向和反向迭代器。rbegin() 返回的是 reverse_iterator，它从最后一个元素开始；rend() 则对应第一个元素之前的位置。
auto it = l.begin();
while(it != l.end()){
cout << *it << " ";
++it;
}
增删改查
list 支持头尾插入和删除，这一点和 deque 有点像，但它真正的价值还是体现在中间节点的插入、删除上。
L.push_back(4);
L.push_front(0);
L.pop_back();
L.pop_front();
实际写代码时，迭代器怎么走要特别小心，尤其是删除操作之后。
迭代器失效
list 的一个好处是：插入不会让已有迭代器整体失效。只有被删除的那个节点对应的迭代器才会失效。这个特性在需要边遍历边删元素时很实用。
// 错误示范
while(it != l.end()){
l.erase(it);
++it; // it 已失效
}
// 正确做法
while(it != l.end()){
it = l.erase(it); // erase 返回下一个有效迭代器
}
二、list 的模拟实现
自己实现 list，关键不是把接口堆出来，而是把节点关系和迭代器封好。双向循环链表看起来简单，真正麻烦的地方都在指针连接上，插入和删除的时候最容易出错。
迭代器封装
list 的迭代器本质上是对节点指针的包装，需要重载解引用、自增、自减这些操作符。
template<class T, class Ref, class Ptr>
struct list_iterator {
typedef list_node<T> Node;
Node* _node;
// ... operator* , operator++ 等实现
};
类结构
主类里一般会放头指针 _head 和大小 _size。构造时要把哨兵节点初始化好，析构时把整条链释放干净。
template<class T>
class list {
Node* _head;
size_t _size;
// ... insert, erase, push_back 等
};
这里最值得盯紧的还是 insert 和 erase。链表实现只要这两块写对了，其他接口基本就是包装。
三、list 与 vector 的对比
| 特性 | vector | list |
|---|---|---|
| 底层结构 | 动态数组 | 双向循环链表 |
| 内存布局 | 连续 | 离散 |
| 随机访问 | O(1) | O(n) |
| 中间插入删除 | 慢 (O(n)) | 快 (O(1)) |
| 迭代器失效 | 扩容可能失效 | 仅删除当前节点失效 |
四、总结
list 更适合那些需要频繁在中间位置插入或删除元素的场景。它牺牲了连续内存带来的访问优势，换来的是更稳定的修改性能。写业务代码时不一定常用，但搞清楚它的链表结构，选容器时会少很多误判。
