list容器：双向链表的全面解析
说实话，在STL的序列容器里，list是个特别的存在。它不像vector那样连续存储，也不像deque那样分段连续。list的本质是双向链表——每个节点都保存着指向前后节点的指针。这种结构决定了它的性格：插入删除快如闪电，随机访问慢如蜗牛。
我记得刚入行时，有个同事在项目里用vector做频繁的中间插入，结果性能惨不忍睹。后来换成list，问题迎刃而解。嗯，选对容器，有时候比优化代码更重要。
1. list的基本概念
list底层是双向循环链表。每个节点包含三个部分：数据域、前驱指针、后继指针。这意味着你可以从任意方向遍历，但无法像数组那样直接跳转到第N个元素。
核心特点：
- 插入和删除操作不会导致迭代器失效（除非指向被删除的元素）
- 不支持随机访问，访问第N个元素需要O(N)时间
- 每次插入都会动态分配内存，频繁插入时会有内存碎片问题
- 支持常数时间的头部和尾部插入删除
你想想看，为什么list的插入不会导致其他迭代器失效？因为每个节点都是独立的内存块，插入新节点只需要调整指针，其他节点的内存地址纹丝不动。这一点和vector完全不同——vector扩容时所有迭代器都会失效。
2. list的构造函数
list提供了多种构造方式，我平时最常用的是前三种：
#include <list>
// 1. 默认构造
std::list<int> l1; // 空链表
// 2. 指定初始大小
std::list<int> l2(5); // 5个元素，默认值为0
// 3. 指定大小和初始值
std::list<int> l3(5, 100); // 5个元素，值都是100
// 4. 拷贝构造
std::list<int> l4(l3); // 复制l3
// 5. 迭代器范围构造
std::vector<int> vec = {1, 2, 3, 4, 5};
std::list<int> l5(vec.begin(), vec.end());
// 6. 初始化列表（C++11起）
std::list<int> l6 = {10, 20, 30, 40};个人建议：如果你知道大概要存多少个元素，用带大小的构造函数可以避免多次内存分配。不过list每次插入都会new节点，所以这个优化效果不如vector明显。
3. list的赋值与交换
赋值操作和vector类似，但有个细节要注意——list的赋值是深拷贝，每个节点都会重新创建。
std::list<int> l1 = {1, 2, 3};
std::list<int> l2 = {4, 5, 6, 7};
// 赋值操作
l1 = l2; // l1现在有4个元素：4,5,6,7
// assign成员函数
l1.assign(3, 100); // l1变成：100,100,100
l1.assign({9, 8, 7}); // 初始化列表赋值
// swap交换
l1.swap(l2); // 交换两个list的内容，O(1)时间swap操作是list的一大亮点。因为list只交换头指针，所以是常数时间。我在项目中经常用swap来做「无异常保证」的赋值——先构造一个新list，然后swap进去，这样即使构造过程抛出异常，原数据也不会被破坏。
4. list的大小操作
大小操作很直观，但有个坑我要提醒你：
std::list<int> lst = {1, 2, 3, 4, 5};
// 大小相关
size_t sz = lst.size(); // 返回5
bool empty = lst.empty(); // 返回false
lst.resize(8); // 扩展到8个元素，新增的默认0
lst.resize(10, 99); // 扩展到10个，新增的用99填充
lst.resize(3); // 缩小到3个，多余的元素被删除我曾经踩过的坑：在C++11之前，list的size()是O(N)的！因为标准允许list不缓存大小信息。虽然现代C++里size()已经是O(1)了，但如果你在维护老代码，还是要注意一下。判断空的时候用empty()而不是size()==0，因为empty()永远是O(1)。
5. list的插入与删除
这才是list的强项。插入和删除操作都是O(1)的——前提是你已经有了指向插入位置的迭代器。
std::list<int> lst = {10, 20, 30, 40};
// 头部和尾部操作
lst.push_front(5); // 5,10,20,30,40
lst.push_back(50); // 5,10,20,30,40,50
lst.pop_front(); // 10,20,30,40,50
lst.pop_back(); // 10,20,30,40
// 任意位置插入
auto it = lst.begin();
++it; // 指向20
lst.insert(it, 15); // 在20之前插入15：10,15,20,30,40
// 插入多个
lst.insert(it, 3, 99); // 在当前位置插入3个99
// 删除
lst.erase(it); // 删除it指向的元素
lst.remove(30); // 删除所有值为30的元素
lst.remove_if([](int x) { return x > 20; }); // 删除所有大于20的元素
// 清空
lst.clear();这里有个细节：insert和erase之后，除了被删除元素的迭代器，其他迭代器都依然有效。这在写复杂算法时特别省心。
6. list的数据存取
list不支持随机访问，所以存取操作很有限：
std::list<int> lst = {1, 2, 3, 4, 5};
// 访问首尾元素
int first = lst.front(); // 1
int last = lst.back(); // 5
// 没有operator[]，也没有at()
// 想访问中间元素？只能遍历
auto it = lst.begin();
std::advance(it, 2); // 前进2步，指向3
int val = *it; // 3重要提醒：如果你需要频繁随机访问，别用list。我见过有人用list存了上万条数据，然后循环里用std::advance找元素，性能直接爆炸。这种场景请用vector或deque。
7. list的反转与排序
list有自己的sort和reverse成员函数，和STL的通用算法不同：
std::list<int> lst = {3, 1, 4, 1, 5, 9, 2, 6};
// 反转
lst.reverse(); // 6,2,9,5,1,4,1,3
// 排序（默认升序）
lst.sort(); // 1,1,2,3,4,5,6,9
// 自定义排序（降序）
lst.sort(std::greater<int>()); // 9,6,5,4,3,2,1,1
// 合并两个有序list
std::list<int> l1 = {1, 3, 5};
std::list<int> l2 = {2, 4, 6};
l1.merge(l2); // l1变成1,2,3,4,5,6，l2为空为什么list不用std::sort？因为std::sort需要随机访问迭代器，list的迭代器是双向的，不满足要求。list自己的sort用的是归并排序，稳定且不需要随机访问。
我的经验：list的sort在数据量大的时候性能不错，但如果你频繁排序，建议考虑其他容器。另外，merge要求两个list都是有序的，否则结果未定义——我曾经因为这个bug排查了半天。
总结一下
list是个偏科生：插入删除是学霸，随机访问是学渣。选它的时候要想清楚场景。我个人习惯是：需要频繁在中间插入删除，且不需要随机访问时，list是首选。其他情况，vector更通用。
嗯，list的内容就这些。记住它的特性，用对地方，它就是一把利器。
公众号:蓝海资料掘金营，微信deep3321