如果你刷过C++算法题或写过相关业务代码，大概率遇到过这种场景：需要在一个大型对象的集合里频繁做头部插入、中间删除，结果用std::vector一跑，数据量一上去立刻卡顿；换std::list之后，插入删除瞬间变得很轻快。这就是我要聊的 C++ STL 里的 List 容器，这次我会把它的常用姿势和底层实现一起讲明白，不但告诉你接口怎么调，还会拆到节点结构、迭代器封装、哨兵头节点这些原理层面，并且带你把一个可用的模拟 List 手写出来。不管你是刚学 STL 的初学者，还是打算应付面试八股的求职者，这篇文章都值得花二十分钟读一遍——很多细节是我在实际写代码和翻源码时踩过坑才总结出来的。
1. 为什么需要 List：先搞清楚 vector 的痛点
1.1 vector 在中间插入删除时的性能灾难
std::vector底层是一块连续的内存，元素一个挨一个地排列，所以通过下标访问任何一个元素都只需要一次指针偏移，速度和数组几乎一样。但代价是：在容器中部或者头部插入一个元素，你不得不把从插入位置开始到末尾的所有元素整体向后搬移一位；删除的话就要把后面的元素逐个向前搬。数据量少的时候无所谓，一旦到了几万、几十万这个量级，每插入一个元素就触发一次大规模拷贝，CPU 缓存和内存带宽都会跟着遭殃。
我印象特别深的一次是在某个项目里，需要按优先级往本地维护的一组记录中反复插入新记录。一开始图方便全用vector存，前几千条没事，后面涨到接近十万条的时候，每次头部插入都要搬移近十万个对象，操作延迟肉眼可见。后来把容器换成list，插入逻辑没变，性能瓶颈直接消失。这个经历让我意识到一个基本结论：list存在的意义就是解决vector在非尾部位置插入删除时 O(n) 复杂度的痛点。
1.2 List 的核心能力与适用边界
std::list底层是双向链表，它的每一个元素都是一个节点，节点内部保存数据、指向前一个节点的指针、指向后一个节点的指针。因为节点在内存里并不连续，所以插入和删除不需要搬移任何已有元素，只要修改相邻节点的指针即可，理论上处处都是 O(1)。
当然，链表不是万能的。它最大的短板是没法随机访问：你想拿第 5 个元素，只能从头开始一个一个走过去，复杂度 O(n)。此外，节点分散在内存各处，遍历时 CPU 缓存命中率远低于vector，同等规模下遍历速度可能慢一个数量级。再加上每个节点多两个指针的开销，通常 16 位以上的指针压缩之后，链表的内存成本明显高于数组。
工程上取舍的通用原则我整理成一张表：
| 特性 | vector | list |
|---|---|---|
| 底层结构 | 连续动态数组 | 带头双向循环链表 |
| 随机访问 | O(1) | 不支持，只能逐个遍历 |
| 任意位置插入删除 | O(n)，需要搬移元素 | O(1)，只改指针 |
| 尾部插入 | 均摊 O(1)，可能扩容 | O(1) |
| 缓存命中率 | 很高 | 很低 |
| 额外内存开销 | 少量容量冗余 | 每节点两个指针 |
| 适用场景 | 频繁随机访问、尾部操作为主 | 频繁中间插入删除、不要求随机访问 |
看到这张表你就明白了：list并不是替代vector的存在，而是互补。访问多就选vector，中间增删多就选list，两个都不是银弹。
2. List 的核心接口与常用操作
2.1 四种常见构造方式与初始化
list的使用入口首先是构造。常用的有四种写法：
#include <list> std::list<int> l1; // 1. 空链表 std::list<int> l2(10, 5); // 2. 10 个值为 5 的元素 std::list<int> l3(l2.begin(), l2.end()); // 3. 用迭代器区间构造 std::list<int> l4(l2); // 4. 拷贝构造需要特别提醒的是，list没有operator[]，因为它不支持随机访问。初学的时候很多人会下意识地写l3[3]这种代码，编译直接报错。访问list中的元素只有两条路：迭代器，或者front()/back()这两个只开放首尾接口的成员函数。
2.2 插入删除操作中的几个关键细节
插入和删除是list的核心功能。常用接口包括push_back、push_front、pop_back、pop_front、insert、erase。
一个非常容易踩的坑是insert的插入位置。list::insert表示把新元素插入到迭代器pos之前，而不是pos之后。这个设计跟vector::insert保持一致，都是“插到 pos 指向位置的前面”。如果是端点插入，直接begin()相当于头插，end()相当于尾插。
erase则有一个重要返回值：它返回被删除元素的下一个迭代器。这样设计是方便你在循环中安全地“边删除边遍历”：
std::list<int> mylist = {1, 2, 3, 3, 4, 5, 6}; auto it = mylist.begin(); while (it != mylist.end()) { if (*it % 2 == 0) { it = mylist.erase(it); // erase 返回下一个迭代器，it 不会失效 } else { ++it; } } // 删除偶数之后，mylist 变为 1, 3, 3, 5这段代码是面试和工作中都会反复用到的经典模式。如果你只写mylist.erase(it)而忘了接收返回值，后续再++it就会对一块已经释放的内存做二次操作，程序跑起来大概率会莫名其妙崩溃。
2.3 迭代器遍历：list 迭代器不是随机访问迭代器
遍历list有三种姿势：基于迭代器的 for 循环、C++11 引入的范围 for、以及需要反向遍历时的反向迭代器rbegin/rend。
for (auto it = mylist.begin(); it != mylist.end(); ++it) { std::cout << *it << " "; } for (auto v : mylist) { std::cout << v << " "; } for (auto rit = mylist.rbegin(); rit != mylist.rend(); ++rit) { std::cout << *rit << " "; }这里我要重点敲一下黑板：list迭代器属于双向迭代器，只支持++和--，不支持it + n、it += n、it - it2这类操作。std::list没有重载operator+，更不要说operator[]。所以std::sort无法直接排序list，因为std::sort要求随机访问迭代器，这也是面试中高频出现的“为什么不用std::sort而用list::sort”的原因。
2.4 list 自带的高阶成员函数：sort / unique / splice / merge / remove
list之所以自带一批特殊算法，就是因为它的迭代器不支持随机访问，通用算法套不上。我整理了我实际用得最多的五个：
sort()：list内部的归并排序实现，不需要随机访问迭代器，也避免把元素搬进临时数组的开销。unique()：删除相邻重复元素，注意只有相邻，不是全局去重。splice()：把一个list中的节点直接转移到另一个list的指定位置，整个操作只改指针，O(1)。merge()：合并两个已排序的list，结果仍有序。remove()：删除所有值等于指定元素的节点，与erase需要迭代器不同，它直接按值删。
一个经典的使用组合：去重前先排序。如果不排序，{1,1,2,1}执行unique()之后会得到{1,2,1}，因为只有相邻的重复会被处理。排序后再unique()才是全量去重。这个坑我实际见过不止一次，别人问我为什么 debug 出来结果不对，十有八九就是忘了先sort。
splice是个很容易被低估的接口，它能把listA里的某一段节点“抠下来”接到listB里，数据本身不拷贝，只是改指针，所以在做任务调度、批量转移这种操作时极其高效。
3. 从效果到原理：List 底层的几个关键设计
3.1 节点的结构：pre、next 与 data
STL 中list的节点并不是简单的一个结构体，但核心布局是一样的。每个节点有三个成员：前驱指针_prev、后继指针_next、数据成员_data。我手写一个最简化版本，去掉模板就可以直观理解：
template <class T> struct ListNode { ListNode<T>* _prev; ListNode<T>* _next; T _data; ListNode(const T& data = T()) : _prev(nullptr), _next(nullptr), _data(data) {} };每个节点的内存是独立分配的，节点之间靠_prev和_next串成一条双向链。这种聚簇结构的好处是插入删除不需要移动数据，坏处是节点在内存里的地址完全随机，对缓存不友好——这也解释了为什么list遍历往往比vector慢。
3.2 哨兵头节点：为什么要带一个不存数据的 head
真正理解list底层，绕不开“哨兵头节点”这个概念。list内部维护一个永远存在的头节点_head，它不存储有效数据，_head->_next指向第一个元素节点，_head->_prev指向最后一个元素节点，整个链表是一个循环结构：从任意一个节点出发，顺着_next走一圈一定能回到它自己。
如果没有哨兵，链表的插入删除逻辑就得区分“是不是在头部”“链表是不是空”这些边界情况，代码会变成一坨分支判断。有了哨兵，insert就统一成“在任意节点的 _prev 和这个节点之间插入一个新节点”，erase也统一成“把前后两个节点接到一起”，边界情况被天然消解掉了。
这也是 STL 选择带头双向循环链表而不是简单双向链表的核心原因。有人可能会问：带头节点会不会浪费内存？一个空list也会有一个_head，所以确实会多占一个节点大小。但换来的是所有操作逻辑完全统一，这点开销非常值。
3.3 迭代器：它不是裸指针，而是一层封装
一个常见误区是以为list的迭代器就是原生指针。事实完全不是：底层节点的内存不连续，如果是裸指针node + 1去访问下一个节点，不知道会踩到什么垃圾内存。list的迭代器实际上是一个类对象，内部包装一个Node*指针，通过重载operator++和operator--让指针沿着_next或_prev移动：
self& operator++() { _node = _node->_next; return *this; }你写++it时，编译器实际调用的是这个成员函数，把内部的_node改为指向后继节点。*it则调用operator*，返回_node->_data的引用。
模拟实现时你会发现一个麻烦：普通迭代器可以修改数据，const_iterator不行；普通迭代器的operator*返回T&，const 版本要返回const T&。如果为两种迭代器各写一份类，代码重复得很痛。STL 的解决方法是引入第二个、第三个模板参数：template <class T, class Ref, class Ptr>，Ref是解引用的返回类型，Ptr是箭头运算符的返回类型。这样，普通迭代器用list::iterator实例化成ListIterator<T, T&, T*>，常量迭代器用list::const_iterator实例化成ListIterator<T, const T&, const T*>。一份类模板两处使用，这是我觉得模拟实现里最值得玩味的设计。
4. 模拟实现：从零手写一个能用的 List
4.1 完整代码框架与关键接口
下面是我在学习和复习时手写过无数遍的简化版List，它去掉了编译期语法糖和复杂 allocator，把核心骨架完整保留下来。这段代码既可以在理解后默写，也可以作为面试前的手撕基础。
template <class T> struct ListNode { ListNode<T>* _prev; ListNode<T>* _next; T _data; ListNode(const T& data = T()) : _prev(nullptr), _next(nullptr), _data(data) {} }; template <class T, class Ref, class Ptr> struct ListIterator { typedef ListNode<T> Node; typedef ListIterator<T, Ref, Ptr> Self; Node* _node; ListIterator(Node* node = nullptr) : _node(node) {} Ref operator*() { return _node->_data; } Ptr operator->() { return &_node->_data; } Self& operator++() { _node = _node->_next; return *this; } Self operator++(int) { Self tmp(*this); _node = _node->_next; return tmp; } Self& operator--() { _node = _node->_prev; return *this; } Self operator--(int) { Self tmp(*this); _node = _node->_prev; return tmp; } bool operator==(const Self& it) const { return _node == it._node; } bool operator!=(const Self& it) const { return _node != it._node; } }; template <class T> class list { public: typedef ListNode<T> Node; typedef ListIterator<T, T&, T*> iterator; typedef ListIterator<T, const T&, const T*> const_iterator; iterator begin() { return iterator(_head->_next); } iterator end() { return iterator(_head); } const_iterator begin() const { return const_iterator(_head->_next); } const_iterator end() const { return const_iterator(_head); } list() { _head = new Node; _head->_next = _head; _head->_prev = _head; } void push_back(const T& x) { insert(end(), x); } void push_front(const T& x) { insert(begin(), x); } iterator insert(iterator pos, const T& x) { Node* cur = pos._node; Node* prev = cur->_prev; Node* newnode = new Node(x); prev->_next = newnode; newnode->_prev = prev; newnode->_next = cur; cur->_prev = newnode; return iterator(newnode); } iterator erase(iterator pos) { Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; prev->_next = next; next->_prev = prev; delete cur; return iterator(next); } void clear() { Node* cur = _head->_next; while (cur != _head) { Node* next = cur->_next; delete cur; cur = next; } _head->_next = _head; _head->_prev = _head; } ~list() { clear(); delete _head; } private: Node* _head; };4.2 循环结构如何让 insert 和 erase 永远安全
看clear()的终止条件写的不是“遇到 nullptr”，而是“回到 _head”。因为这是一个循环链表，每个节点的遍历最终都会绕回哨兵头。如果你写while (cur != nullptr)，这个循环永远不会结束，最后会把_head也一起删了，造成双重释放或非法访问。
再看insert。pos是end()时，cur指向_head，prev指向尾节点，新节点插在尾节点和头节点之间，其实就是尾插；pos是begin()时，cur指向第一个有效节点，prev指向_head，新节点插在头节点和第一个有效节点之间，也就是头插。插入逻辑完全不用分支判断，这就是哨兵带来的优美性。
erase同样如此。prev->_next = next; next->_prev = prev;这两句就把被删节点从链中解了下来，然后再delete cur。注意返回值是next，也就是被删元素之后的那个节点。这个返回值就是前面说的“边遍历边删除”模式能成立的根本原因。
4.3 复制、赋值与销毁：内存管理的三件套
上面的代码还没有拷贝构造、赋值重载。一个只写了析构的类不能用来按值传递或复制，否则会浅拷贝同一份指针，导致二次析构。
我在自己实现的时候通常会加一个“拷贝插入”的思路：先搞一个空链表，遍历源链表依次push_back，再把结果 swap 给当前对象。
void empty_init() { _head = new Node; _head->_next = _head; _head->_prev = _head; } list(const list<T>& lt) { empty_init(); for (auto v : lt) push_back(v); } list<T>& operator=(const list<T>& lt) { if (this != <) { list<T> tmp(lt); std::swap(_head, tmp._head); } return *this; }赋值用“拷贝 + 交换”的写法，核心原因是强异常安全：如果拷贝构造过程中抛了异常，当前对象保持原状；如果成功，头和临时对象的头交换指针后，临时对象析构时会把旧数据带走。这比“先清空再逐个插入”的写法稳得多。很多面试官喜欢往这个方向追问，答到这一层基本能看出你是真的写过而不是背过八股。
4.4 为什么 end() 返回的不是 nullptr 而是 head
最后解释一个最容易让人发愣的细节：end()返回的迭代器内包装的是_head节点，而不是nullptr。这是 STL 中“左闭右开区间”设计在链表上的自然延伸：begin()指向第一个数据，end()指向最后一个元素的下一个位置。在循环链表中，最后一个元素的下一个位置就是哨兵头节点，所以end()只能是_head。
这也带来一个推论：空链表时begin()和end()返回的都是_head，也就是说begin() == end()。因此循环遍历的终止条件永远是it != end()而不是it->_node != nullptr。如果不理解这个设计，手写代码时很容易写出越界访问。
5. 实际使用中的常见问题与排查心得
5.1 迭代器失效规则和 vector 完全不同
很多从vector转到list的人，对迭代器失效的直觉是错的。vector插入元素一旦触发扩容，整容器的迭代器、指针、引用全部失效；list插入新节点只会分配一个独立节点，既不会移动已有数据，也不会让已有迭代器指向的内存发生任何变化，所以insert之后，除了新节点，所有已有迭代器依然有效。
但erase就比较危险了：被删节点的迭代器会失效，因为节点内存已经被delete。其他迭代器不受影响。如果你在循环中erase之后还想继续用同一个迭代器，必须用erase的返回值接住它的下一个位置。这是list和vector在迭代器失效规则上最重要的一条差异。
5.2 把 std::sort 直接传给 list 的错误现场
我用开发工具对比测试时特意用小程序复现过“在 list 上调用 std::sort”的编译错误。编译器最终会抛出一大堆模板实例化报错，核心问题出现在要求随机访问迭代器的那一步。我当时看到几百行报错时一度以为是自己环境坏了，后来才明白是迭代器类型不满足要求。
解决办法有三个方向：直接使用mylist.sort()；把元素搬到vector里排序再写回；或者干脆换成std::forward_list（单向链表，它有自己的sort）。从性能上讲，list::sort走归并排序，稳定且不需要频繁随机访问，是最贴合链表结构的选择。
5.3 unique 是相邻去重，不是全局去重
我在前面提过unique只删除相邻重复元素。实际中还有个连环坑是忘了它和sort的配合顺序。有个同事在项目里写了一段“去重”逻辑，数据大约一万多条，跑完之后数量还是没变，排查了半天才发现原数据无序，重复元素根本没挨在一起。后来改成先排序再unique，问题才消失。
顺带一提，unique也支持传一个二元谓词做自定义去重规则，例如按某个业务字段相等来去重。但不管怎么传，前提都是必须先把相同键值的元素聚到相邻位置。
5.4 空链表上的 front 和 back
list为空时调用front()或back()属于未定义行为。绝大多数标准库实现不会做安全检查，直接解引用头节点的_data，读到的就是一个未初始化的垃圾值，程序往往以“能用但不能解释”的方式隐性出错。所以调用这两个接口前先判一下empty()，是我写代码时的固定习惯。
5.5 size() 的性能可能是 O(n)
很多教材默认list::size()是 O(1)。但从实现角度讲，标准库并没有强制要求list维护元素个数。某些实现里size()需要从_head->_next一直走到_head数一遍，复杂度 O(n)。我在某次性能压测中发现，循环里反复调用size()导致耗时飙升，改成外部维护一个计数器之后性能立刻回来。如果你的目标是可移植的高性能代码，不要假设size()一定是 O(1)，尽量少在循环条件里调用它。
5.6 模拟实现时几个容易翻车的小细节
模拟实现list时最常翻车的地方有三个。第一，迭代器类模板中typedef ListIterator<T, Ref, Ptr> Self必须写在类模板内部，不然operator++返回类型没法方便地写。第二，const成员函数要区分：begin() const返回const_iterator，begin()返回iterator，两个重载不能少，否则常量list对象无法遍历。第三，clear()之后别忘把_head->_next和_head->_prev指回_head，否则析构函数会重复delete已经释放的节点内存，直接程序崩溃。
我个人在实际操作中的体会是，手写一遍list比背十遍 STL 源码更能打通底层逻辑。这个简化版去掉了很多内存分配器、异常安全、右值引用之类的现代细节，但骨架完全忠实于 STL 的设计思想。真正把insert四步指针操作、end()指向哨兵头、迭代器三模板参数这些概念亲手敲一遍，你再看vector和list各自的选型理由，会有一种豁然开朗的感觉。
最后再补充一个扩展方向：如果你觉得双向链表占内存太多，更新一点的std::forward_list是单向链表，节点少一个指针，内存更省，但代价是只能单向遍历。实际项目中数据量小的时候vector依然最优，数据量大且中间插入删除频繁才轮到list出马，而forward_list则适合极简内存场景。具体用哪个，回到你的需求里重新评估一遍，比到处复制网上推荐更靠谱。
