★ FEATURED ARTICLE 如果你刷过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 位以上的指针压缩之后链表的内存成本明显高于数组。工程上取舍的通用原则我整理成一张表特性vectorlist底层结构连续动态数组带头双向循环链表随机访问O(1)不支持只能逐个遍历任意位置插入删除O(n)需要搬移元素O(1)只改指针尾部插入均摊 O(1)可能扩容O(1)缓存命中率很高很低额外内存开销少量容量冗余每节点两个指针适用场景频繁随机访问、尾部操作为主频繁中间插入删除、不要求随机访问看到这张表你就明白了list并不是替代vector的存在而是互补。访问多就选vector中间增删多就选list两个都不是银弹。2. List 的核心接口与常用操作2.1 四种常见构造方式与初始化list的使用入口首先是构造。常用的有四种写法#include list std::listint l1; // 1. 空链表 std::listint l2(10, 5); // 2. 10 个值为 5 的元素 std::listint l3(l2.begin(), l2.end()); // 3. 用迭代器区间构造 std::listint 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::listint 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 循环、C11 引入的范围 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 / removelist之所以自带一批特殊算法就是因为它的迭代器不支持随机访问通用算法套不上。我整理了我实际用得最多的五个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 与 dataSTL 中list的节点并不是简单的一个结构体但核心布局是一样的。每个节点有三个成员前驱指针_prev、后继指针_next、数据成员_data。我手写一个最简化版本去掉模板就可以直观理解template class T struct ListNode { ListNodeT* _prev; ListNodeT* _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*返回Tconst 版本要返回const T。如果为两种迭代器各写一份类代码重复得很痛。STL 的解决方法是引入第二个、第三个模板参数template class T, class Ref, class PtrRef是解引用的返回类型Ptr是箭头运算符的返回类型。这样普通迭代器用list::iterator实例化成ListIteratorT, T, T*常量迭代器用list::const_iterator实例化成ListIteratorT, const T, const T*。一份类模板两处使用这是我觉得模拟实现里最值得玩味的设计。4. 模拟实现从零手写一个能用的 List4.1 完整代码框架与关键接口下面是我在学习和复习时手写过无数遍的简化版List它去掉了编译期语法糖和复杂 allocator把核心骨架完整保留下来。这段代码既可以在理解后默写也可以作为面试前的手撕基础。template class T struct ListNode { ListNodeT* _prev; ListNodeT* _next; T _data; ListNode(const T data T()) : _prev(nullptr), _next(nullptr), _data(data) {} }; template class T, class Ref, class Ptr struct ListIterator { typedef ListNodeT Node; typedef ListIteratorT, 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 ListNodeT Node; typedef ListIteratorT, T, T* iterator; typedef ListIteratorT, 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指向_headprev指向尾节点新节点插在尾节点和头节点之间其实就是尾插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 listT lt) { empty_init(); for (auto v : lt) push_back(v); } listT operator(const listT lt) { if (this ! lt) { listT 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 和 backlist为空时调用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 ListIteratorT, Ref, Ptr Self必须写在类模板内部不然operator返回类型没法方便地写。第二const成员函数要区分begin() const返回const_iteratorbegin()返回iterator两个重载不能少否则常量list对象无法遍历。第三clear()之后别忘把_head-_next和_head-_prev指回_head否则析构函数会重复delete已经释放的节点内存直接程序崩溃。我个人在实际操作中的体会是手写一遍list比背十遍 STL 源码更能打通底层逻辑。这个简化版去掉了很多内存分配器、异常安全、右值引用之类的现代细节但骨架完全忠实于 STL 的设计思想。真正把insert四步指针操作、end()指向哨兵头、迭代器三模板参数这些概念亲手敲一遍你再看vector和list各自的选型理由会有一种豁然开朗的感觉。最后再补充一个扩展方向如果你觉得双向链表占内存太多更新一点的std::forward_list是单向链表节点少一个指针内存更省但代价是只能单向遍历。实际项目中数据量小的时候vector依然最优数据量大且中间插入删除频繁才轮到list出马而forward_list则适合极简内存场景。具体用哪个回到你的需求里重新评估一遍比到处复制网上推荐更靠谱。
阅读完成 · 觉得有帮助？
