很多人在学C的STL时心里都有同一个疑问vector用得好好的list到底有什么值得专门拿出来学的我当年也这么想过直到在公司做了个需要高频在中间插入删除的小模块被vector那次痛苦的搬移测试狠狠教育了一顿才老实回去把std::list的源码和用法从头捋了一遍。这篇文章就是写给准备系统性啃STL的读者的我会从底层结构讲到常用接口再讲迭代器失效最后带你手写一个简化版list。这一圈走下来你对list的理解就不会停留在会用而是真正知道每一步它在内存里做了什么。1. 先回答一个灵魂问题用得好好的vector为什么非学list不可1.1 vector的三大痛点vector的底层是一块连续内存自带动态扩容尾部插入删除是O(1)按下标随机访问是O(1)再加上缓存命中率极高很多场景它确实是最优选。但它的痛点也恰恰来自连续这两个字第一个痛点是头部和中部插入删除太慢。你想想往数组中间塞一个元素后面的所有元素都得往后挪一位这可不是挪一个是挪n个。如果你写的是vector.insert(v.begin() 50000, value)后面五万多个元素全部搬家单次操作就是O(n)。要是在循环里反复干这事复杂度直接爆炸。第二个痛点是迭代器极易失效。vector扩容的时候底层内存直接重新分配之前拿到的所有指针、迭代器、下标统统作废中间插入一次插入点之后的所有迭代器也全部作废。很多人第一次踩到这个坑时代码跑出来是乱值排查半天才发现是迭代器失效问题。第三个痛点是无法高效拼接。如果有两个有序数组要合并或者要把一段数据搬移到另一个结构里vector只能循环insert每插一次搬移一次效率非常难看。1.2 list和vector的根本差异list的底层是双向链表每个元素是一个独立节点节点之间靠指针串联。你在任意位置插入或删除一个节点只需要修改前后两个节点的指针指向复杂度是稳定的O(1)不用搬动任何其他数据。数据结构的差异直接决定了使用方式的差异vector像一列火车车厢连着车厢编组密集可以一下算出任何一节车厢的位置list像一串珍珠项链每颗珍珠独立存在中间换一颗珠子只需要动两边的线扣但想找第10颗珍珠就必须一颗一颗数过去。所以list放弃了随机访问的能力不提供operator[]也不提供at()你只能靠迭代器从头往后走。这是它的短板也是它换来插入删除效率的代价。1.3 什么时候该选list我个人的经验判断标准是三条满足任意一条就倾向用list数据结构要求在任意位置高频插入删除而不是只在尾部追加需要迭代器在插入删除之后保持稳定程序逻辑高度依赖这个特性需要把两个序列整体拼接、搬移比如任务队列合并、日志分段合并。反过来如果主要操作是按下标访问、排序、查找那list并不合适。list虽然能sort但它的排序走的是归并排序的分支效率不如vector上直接调std::sort来得痛快。后面我会专门讲这个对比。2. 底层的底牌list是带哨兵位的双向环形链表2.1 节点结构prev、next、data标准库里的std::listT内部实现每个节点大概是这样的结构template typename T struct __list_node { __list_node* prev; // 指向前一个节点 __list_node* next; // 指向后一个节点 T* data; // 实际存储的数据 };注意在真正的libstdc实现里数据是指针形式的T*而不是直接内嵌一个T对象。这样做的好处是把节点结构和数据分离空节点不需要构造T对象哨兵位也不用存数据。咱们手写简化版的时候可以内嵌T对象因为更直观但你要知道标准库里不是这么干的。每个节点的生命是独立的插入时new一个节点删除时delete一个节点节点之间没有物理上的连续性所以list天然避开了vector扩容搬移的问题。2.2 哨兵位头节点让循环边界统一list里有一个你可能没注意过的设计它结构上是一个双向环形链表从头节点出发沿着next走一圈能回到头节点。头节点本身不存数据只是作为一个哨兵位存在。这个哨兵位的意义非常深远它让空链表和满链表的处理逻辑完全统一。空链表时头节点的next和prev都指向自己begin()就是头节点-nextend()就是头节点本身。无论链表是否为空end()永远有明确的落脚点不会出现空指针解引用。日常使用中l.end()拿到的就是这样一个指向哨兵位的迭代器。你访问*l.end()当然是未定义行为但拿它作循环终止判断是绝对安全的。这个设计让迭代器遍历的边界判断统一成了一个条件it ! l.end()。2.3 从内存布局看list的散与vector的整如果你用sizeof对比一下会发现list对象本身很小——它一般只包含一个头节点指针和大小计数而每个节点的内存分布在各处由malloc自由分配。遍历list的10万次寻址每次都可能跳到一个完全不同的内存页CPU缓存基本帮不上忙。vector遍历则是顺序扫内存预取器能提前把后面的数据加载进缓存。这也是为什么实测中小数据量的list遍历往往比vector慢好几倍的原因。链表本身的灵活都是用访存局部性换来的这个账一定要算清楚。3. 上手三板斧创建、插入删除、遍历3.1 创建和初始化从空表到批量填充list的构造函数有几种常用姿势直接上代码#include list #include iostream #include algorithm std::listint l1; // 空链表 std::listint l2(10); // 10个默认值0 std::listint l3(10, 5); // 10个5 std::listint l4(l3.begin(), l3.end()); // 用迭代器区间拷贝 std::listint l5 {1, 2, 3, 4}; // 初始化列表和vector不同的一个细节是list初始化完内存里有多少个节点就分配多少个节点不存在预留容量这个概念。vector有reserve()list没有也不需要。因为list每次插入都是单独申请节点内存不会因为扩容导致指针失效。3.2 插入删除头尾和中间的四种姿势list支持vector没有的头插头删操作因为单链表头插是O(1)vector头插要搬全体数据std::listint l {2, 3}; l.push_back(4); // 尾部插入 - 2 3 4 l.push_front(1); // 头部插入 - 1 2 3 4 l.pop_back(); // 尾部删除 - 1 2 3 l.pop_front(); // 头部删除 - 2 3中间插入删除用insert和erase传入的是迭代器位置。注意list的迭代器不能直接加数字不支持it 2这种写法。你要往某个位置插要么用std::advance(it, n)一步一步走要么就老老实实从头遍历std::listint l {1, 2, 3, 4}; auto it l.begin(); std::advance(it, 2); // it指向3 l.insert(it, 99); // 在3之前插入 - 1 2 99 3 4 l.erase(--it); // 删除99 - 1 2 3 4很多人会把insert和erase的迭代器参数记混insert是插在pos之前erase是删除pos本身并返回下一个元素的位置。这两个点都是基础但高频的考点。3.3 遍历迭代器与范围for遍历list最推荐的是范围for因为底层就是迭代器for (int x : l) { std::cout x ; }范围for的本质就是begin()和end()它最安全也不容易写出迭代器失效的代码。如果你需要修改元素就声明引用for (int x : l)。如果需要边遍历边删那就必须老老实实写迭代器循环而且不能偷懒用范围for因为范围for内部迭代器在删除时会失效。这条我在第5节会展开讲那是list使用中最大的一个坑。4. 含着金钥匙的独有接口splice、unique、merge、sort4.1 splice项链拼接术O(1)搞定list最让我觉得值回票价的一个接口是splice。它的作用是把一个链表的一段节点移植到另一个链表而且是纯指针调整不复制、不搬移、不释放任何节点。整个操作时间复杂度是O(1)除了要移动整个链表时。std::listint l1 {1, 2, 3}; std::listint l2 {10, 20, 30}; l1.splice(l1.end(), l2); // l1: 1 2 3 10 20 30 // l2: 空splice有三种常见形态// 形态一把other的所有节点搬到pos之前 l1.splice(pos, other); // 形态二把other中迭代器it指向的单个节点搬到pos之前 l1.splice(pos, other, it); // 形态三把other中[firs, last)区间的节点搬到pos之前 l1.splice(pos, other, first, last);注意splice搬走后源链表的这部分节点就没了。它不是复制。这在任务队列重新调度、缓冲区重组这种场景下特别实用比反复insert再erase高效太多了。4.2 sort为什么list不直接用std::sort这是一个非常经典的C问题也是面试八股常客。std::sort要求随机访问迭代器它的快排逻辑需要O(1)时间拿到任意位置的元素。list的迭代器是双向迭代器不支持、-运算所以std::sort根本无法编译通过。list内部提供的是自带的l.sort()底层实现是归并排序的变体时间复杂度是稳定的O(n log n)。std::listint l {3, 1, 4, 1, 5, 9, 2}; l.sort(); // 升序 l.sort(std::greaterint()); // 降序这里有个实操建议如果你的数据量不小而且数据最终要频繁随机访问那还是先转成vector排序再转回来更划算。因为list的归并排序虽然复杂度不差但每回合都要在节点间跳来跳去真实的访存开销远高于vector的连续内存排序。4.3 unique、merge、remove_if链表的专属算法这四个成员函数也是list有别于vector的特色接口unique()只去除相邻且相等的元素。所以用之前通常要先sort()否则不保证去重效果。merge(other)合并两个都已经有序的链表结果仍然有序。它同样是O(1)空间的指针拼接。remove(val)删除所有等于val的元素。remove_if(pred)删除满足谓词条件的元素配合lambda非常好用。std::listint l {3, 1, 2, 2, 3, 3, 4}; l.sort(); // 1 2 2 3 3 3 4 l.unique(); // 1 2 3 4 std::listint odd; for (int i 1; i 10; i) odd.push_back(i); odd.remove_if([](int x) { return x % 2 0; }); // odd: 1 3 5 7 9注意remove这个名字有迷惑性它其实等价于按值删除所有匹配元素而不是只删一个。另外remove和remove_if内部实际上先通过遍历把符合条件的节点摘除再统一销毁所以它不会破坏未删除元素的迭代器但被删除元素的迭代器当然还是会失效。5. 迭代器失效问题list到底有多抗造5.1 什么是迭代器失效迭代器失效就是迭代器指向的底层对象已经被销毁或内存位置已经变化你对它做任何操作解引用、自增都是未定义行为。vector扩容时所有迭代器失效list插入节点时只有被删除的那个迭代器失效其他所有迭代器包括指向其他节点的迭代器统统保持有效。这也是list被称为迭代器稳定容器的原因。只要你不在删除那个节点的操作之后继续用那个迭代器其余随便造。5.2 list的失效规则与vector对比用一个表格看得最清楚操作vector迭代器影响list迭代器影响尾部插入若扩容全部失效其他迭代器不受影响中间插入插入点之后全部失效其他迭代器不受影响尾部删除仅被删元素迭代器失效仅被删元素迭代器失效中间删除删除点之后全部失效仅被删元素迭代器失效扩容/capacity变化全部失效无此概念这个表格背后的原因是内存模型差异vector是连续内存插入删除导致元素位置变动list的每个节点是独立分配的删除一个节点只是把前后指针绕过去其他节点的物理位置纹丝不动。5.3 erase返回值的正确用法虽然list的迭代器稳定性好但删除节点时被删的那个迭代器本身确实失效了所以你不能在删除之后还拿它去。最经典的错误写法长这样// 错误示范erase之后还继续用旧的it去自增 for (auto it l.begin(); it ! l.end(); it) { if (*it % 2 0) { l.erase(it); // 删除后it已经失效再是未定义行为 } }正确做法是利用erase的返回值——它会返回被删除节点的下一个有效迭代器// 正确写法手动控制迭代器的推进 for (auto it l.begin(); it ! l.end();) { if (*it % 2 0) { it l.erase(it); // erase返回下一个节点完美衔接 } else { it; } }这段代码是list实战中最高频的模板建议直接背下来用。它同样适用于vector只不过vector的erase返回的是下一个元素的位置二者在这一点上倒是统一了。6. 手写一个简化版list把指针玩明白说一千道一万理解list最彻底的方式是自己写一个。我在学习时光是手写list就练了三遍从第一次的崩溃连连到后来能一遍过收获远超刷十道题。下面这个版本保留了核心骨架——哨兵位、双向链表、迭代器、插入删除去掉了一些标准库的进阶优化如allocator、异常处理方便你把注意力集中在指针操作上。6.1 节点与哨兵地基先打稳我们定义两个部分一个是节点结构一个是容器类。节点里就是前驱指针、后继指针、数据三件套。容器里保存哨兵位节点指针_head和元素个数_size。#include iostream #include cassert template typename T class MyList { private: struct Node { Node* prev; Node* next; T data; explicit Node(const T value T()) : prev(nullptr), next(nullptr), data(value) {} }; Node* _head; // 哨兵位不存有效数据 size_t _size; public: class iterator { public: Node* _p; explicit iterator(Node* ptr nullptr) : _p(ptr) {} T operator*() { return _p-data; } iterator operator() { _p _p-next; return *this; } iterator operator(int) { iterator tmp(*this); _p _p-next; return tmp; } iterator operator--() { _p _p-prev; return *this; } iterator operator--(int) { iterator tmp(*this); _p _p-prev; return tmp; } bool operator(const iterator other) const { return _p other._p; } bool operator!(const iterator other) const { return _p ! other._p; } };6.2 构造、析构、清空环怎么闭合构造函数里最关键的一步把哨兵位的next和prev都指向自己形成一个空环。这样空链表也能让begin()返回一个合法的终点即起点位置。MyList() : _head(new Node()), _size(0) { _head-next _head; _head-prev _head; } void clear() { Node* cur _head-next; while (cur ! _head) { Node* next cur-next; delete cur; cur next; } _head-next _head; _head-prev _head; _size 0; } ~MyList() { clear(); delete _head; _head nullptr; } iterator begin() { return iterator(_head-next); } iterator end() { return iterator(_head); } size_t size() const { return _size; } bool empty() const { return _size 0; }clear这里的写法是链表销毁的通用模板先记录下一个节点再删除当前节点否则删完当前节点后无法继续向后走。肉眼看不出来区别但实际跑起来一旦顺序错了就是野指针崩溃。6.3 插入删除四根指针的动手游戏手写链表最容易错的就是插入删除时的指针调整顺序。我的记忆口诀是先接新节点再断开旧连接——push_back其实就两步void push_back(const T val) { Node* node new Node(val); Node* tail _head-prev; node-prev tail; node-next _head; tail-next node; _head-prev node; _size; } void push_front(const T val) { Node* node new Node(val); Node* first _head-next; node-next first; node-prev _head; first-prev node; _head-next node; _size; }insert和erase是通用操作逻辑如下iterator insert(iterator pos, const T val) { Node* node new Node(val); Node* cur pos._p; node-next cur; node-prev cur-prev; cur-prev-next node; cur-prev node; _size; return iterator(node); } iterator erase(iterator pos) { assert(pos._p ! _head); Node* del pos._p; iterator ret(del-next); del-prev-next del-next; del-next-prev del-prev; delete del; --_size; return ret; }erase里我对哨兵位做了断言保护防止有人传入end()导致头节点被误删。实际项目中这类防御性检查非常值得养成习惯。6.4 边界情况的测试清单写完之后不能光看代码漂亮要真跑一遍边界测试。我一般会测这么几项空链表上push_back再遍历看环是否正确闭合连续push_front几次顺序是否逆序删除第一个、删除最后一个、删除唯一一个节点在end()位置insert效果应该等同于push_back遍历删除所有节点再往链表里插入新节点检查哨兵位是否还健康。int main() { MyListint lst; lst.push_back(1); lst.push_back(2); lst.push_front(0); lst.insert(lst.end(), 99); for (auto it lst.begin(); it ! lst.end(); it) std::cout *it ; // 0 1 2 99 auto it lst.begin(); lst.erase(it); std::cout \n lst.size(); // 3 return 0; }跑完这套测试你对list的指针操作会形成一种肌肉记忆再回去看标准库源码至少不会被那一层层的模板包装吓到。7. 实战避坑与面试八股里list的常见考点7.1 性能误区list并不是所有的插入都快说list插入快是有前提的插入动作本身是O(1)但如果你要先找到插入位置找位置的成本另算。比如你在一个1万元素的list里插入100个元素每次都先从头遍历找位置那总成本是O(n)级别的查找加上O(1)的插入。反而用vector一次性算出插入点再尾部搬移可能整体更快。另外list的每个节点都有额外的指针开销。一个存int的list节点在64位系统上光prev和next就是16字节可能比int数据本身还大。如果有100万个整数的list光指针开销就是160MB而vector存100万个int只要40MB不考虑容量余量。存大量小对象时这个内存放大效应必须考虑。7.2 常见错误清单我在review代码时list相关代码里反复看到这几类问题把list当vector用写it 3来定位节点编译直接报错。正确姿势是std::advance(it, 3)。在范围for里erase范围for内部用迭代器自增erase之后迭代器失效运行期行为未定义常见表现是死循环或跳元素。忘了splice会移动元素把splice当成copy来用源链表被掏空了还一脸懵。merge之前没排序merge要求两个链表都有序否则合并结果乱七八糟。把end()传给erase删除哨兵位轻则断言崩溃重则破坏整个链表的环结构。这些都是很隐蔽的bug不会每次必现但一旦出现就是最难排查的那类问题。7.3 面试八股考点总结如果你准备面试list这部分的考点其实相当集中我把常问的几条整理成一个速查表考点一句话答案list和vector的区别链表 vs 连续内存O(1)任意插入删除 vs O(1)随机访问list的迭代器类型双向迭代器不是随机访问迭代器为什么list不能调std::sortstd::sort需要随机访问迭代器list只有双向迭代器erase之后迭代器会怎样被删元素的迭代器失效其余迭代器不受影响splice的时间复杂度O(1)纯指针操作list的sort底层是什么归并排序的变体稳定list有reserve吗没有节点逐个分配不需要预留容量7.4 一个实际项目里的选择思路最后说一个真实的选型场景。之前我做日志分段收集器每秒钟会有几千条日志从不同线程汇入然后需要按时间戳合并排序后统一落盘。一开始图省事用了vector结果每次合并都要反复insert和erase高频时延迟飙得很厉害。后来改成list加splice合并再用sort()排序延迟降了一个数量级。原因就是list的合并是O(1)指针拼接而vector的合并是反复搬移数据。但反过来如果是需要频繁按下标读取的缓存池我绝不会用list。记住这个经验法则list胜在改结构得快输在查内容得慢。选型时先想清楚你的核心操作是改还是查再决定要不要上list。我自己学list最大的体会是STL的容器不是孤立的知识点它们的差异背后全是数据结构课上的那点事儿——连续内存和链式内存、随机访问和顺序访问、迭代器稳定性的代价和收益。把list吃透不仅多会一个容器更是把数据结构选型这堂课上扎实了。
