1. 为什么 List 接口看起来那么多底层数据结构决定了接口风格很多学 STL 的同学第一次打开 cppreference 的 List 页面时会被那一长串接口列表吓到构造、容量、元素访问、修改器、操作、迭代器……单是修改器一节就有十来种方法加到一起看着像要背五十个函数。但如果你先搞清楚一件事这些接口的冗余感会瞬间消解std::list 的底层是双向链表它的每一个操作本质上都是在做指针的重新指向而不是像 vector 那样做连续内存的搬移。因为底层是链表所以 List 天生具备几个其它容器没有的特性任意非末尾位置插入或删除元素都是常数时间、迭代器在插入操作中不会失效、NULL 指针不会被存进容器链表节点内部的 prev/next 是内部指针和容器元素无关。这三条特性直接决定了接口为什么长成现在这样。比如 vector 没有 push_front 和 pop_front因为头插头删对 vector 来说是灾难性的 O(n)而 list 有因为只需要改一下头结点的指针不需要搬动任何数据。另外要注意std::list 的接口按功能可以拆成四个象限构造如何创建、容量能存多少、元素访问如何获取值、操作如何增删改排序拼接。其中前三个象限和 vector 很像几乎可以套用真正的差异集中在操作和特殊算法这两块。换句话说List 被绕晕的人通常不是死在 push_back 和 size 上而是死在 splice、merge、remove_if、unique 和自带的 sort 上。我个人的记忆方法是List 的所有接口可以压缩成三条主线。第一节点的插入和移除对应 push/pop/insert/erase/emplace第二链表的重组对应 splice、merge、sort、reverse、unique第三条件性删除对应 remove 和 remove_if。把这三条主线串起来之后再看 List 的界面就不会有无从下手的感觉了。接下来我就按这三条主线把接口逐个拆开讲顺便把那些藏在接口背后的坑也一并交代清楚。2. 真正需要记住的核心接口清单构造、增删、查改2.1 构造七八种构造函数不要求全背但必须会用List 的构造函数有默认构造、指定元素个数构造、指定个数和值构造、迭代器区间构造、拷贝构造、移动构造、初始化列表构造七种。实际开发中最多用到的是默认构造、初始化列表构造和拷贝构造剩下几种在特殊场景里也会碰到。#include list using namespace std; listint l1; // 空列表 listint l2(5); // 5 个默认值 0 listint l3(5, 10); // 5 个 10 listint l4 {1, 2, 3, 4, 5}; // 初始化列表C11 之后最常用 listint l5(l4); // 拷贝构造 listint l6(std::move(l4)); // 移动构造转移底层节点O(1) listint l7(l3.begin(), l3.end()); // 迭代器区间构造这里有个容易忽略的点listint l2(5)会得到 5 个 0因为是值初始化如果元素类型是自定义类那么会调用 5 次默认构造。而l6是移动构造它把 l4 的整个链表头指针偷了过来所以 l6 拥有原来 l4 的所有元素而 l4 变空。偷不是拷贝这就是移动语义和拷贝语义的本质差别。对于 list 这种节点分散分配的结构移动构造的代价固定为常数因为只需要移动若干个指针而 vector 移动构造虽然也是常数但后续的扩容策略会让它的内存重新分配机制不同这一点初学者容易混。2.2 增删push/pop 只是冰山一角insert/erase 才是重点增删是 List 使用频率最高的操作。push_front、push_back、pop_front、pop_back、emplace_front、emplace_back 这些和 deque 相同区别在于 list 的 push_front 和 push_back 都是 O(1)不需要做任何容量检查。但真正值得花时间的是 insert 和 erase。listint l {1, 2, 3, 4, 5}; auto it l.begin(); it; // 指向 2 // 在 it 之前插入 l.insert(it, 99); // 现在列表是 1, 99, 2, 3, 4, 5 l.insert(it, 3, 88); // it 仍然指向 2在其前插 3 个 88 l.insert(l.end(), {77, 78}); // 尾部插入两个元素insert 的返回值是一个迭代器指向第一个新插入的元素。很多人不用返回值但如果你需要链式插入返回值就很有用。erase 也一样它返回被删除元素的下一个迭代器。这个返回值在遍历删除时是救命稻草我后面讲迭代器失效时会专门说。另外注意 emplace 家族l.emplace_back(参数们)和l.push_back(对象)的区别在于 emplace 直接调用元素的构造函数省去一次临时对象的构造和拷贝。对 list 这种节点分布式的容器来说省一次拷贝能明显减少开销尤其是存储的对象是个重量级类时。所以如果插入的是复杂对象我的习惯是优先 emplace_back、emplace_front、emplace 而不是 push 系列。2.3 容量与访问size 是 O(1)但 front/back 才是你该用的size 从 C11 起就被标准要求是常数时间所以你可以放心地反复调用l.size()。empty 和 clear 也很直白empty 判断容器是否为空clear 把节点全部释放并置 size 为 0。resize 如果你之前用过 vector 就不会陌生不过是把链表截断或补长而已。元素访问接口上list 只有 front() 和 back()没有 operator[]。这一点是接口设计层面的刻意为之链表的随机访问是 O(n)真要去实现 operator[]要么 O(n) 遍历要么额外维护一个索引结构两者都会破坏链表的设计目标。所以 STL 直接不给 list 提供随机访问迭代器也不提供 operator[]就是逼你在需要随机访问时去用 vector。listint l {10, 20, 30}; if (!l.empty()) { int first l.front(); // 10 int last l.back(); // 30 } l.resize(2); // 截断只留下 10, 20 l.resize(5, -1); // 补 3 个 -1还有一个细节front() 和 back() 返回的是引用所以你可以直接通过l.front() 100;修改元素值。但如果你调用 front()/back() 时容器为空结果是未定义行为多数实现下你会拿到一个悬空的引用然后踩进内存地狱。所以无论是访问还是修改调用前检查 empty() 是一个值得养成的习惯别嫌麻烦。3. 最容易踩坑的 List 专属接口splice、remove、merge、unique、sort这一节才是 List 真正区别于其它容器的部分。很多人在学 vector 的 push_back、erase 之后就以为天下太平结果一到 list 的 splice 就懵了根本不知道这个把节点从一个链表搬进另一个链表的操作到底在干嘛。3.1 splice不拷贝、只搬指针但有三条潜规则splice 倒腾的是节点本身不是元素的拷贝。它有三种常见形态std::listint a {1, 2, 3}; std::listint b {10, 20, 30}; // 形态一把 b 所有节点拼到 a 的 pos 之前 a.splice(a.end(), b); // a: 1, 2, 3, 10, 20, 30b 变空 // 形态二把 b 中 it 指向的单个节点拼过去 std::listint b2 {5, 15}; auto it2 b2.begin(); // 指向 5 a.splice(a.begin(), b2, it2); // a: 5, 1, 2, 3, 10, 20, 30b2: 15 // 形态三把 b3 的 [first, last) 区间拼过去 std::listint b3 {7, 8, 9}; auto f b3.begin(); auto e b3.end(); a.splice(a.begin(), b3, f, e); // a: 7, 8, 9, 5, 1, ...第一条潜规则splice 之后源链表的节点到了目标链表里但节点的地址没有变。也就是说如果你有一个指向那个节点的迭代器在 splice 之后它仍然有效只是现在它属于另一个链表。这一点非常反直觉因为 vector 里搬数据后所有迭代器都失效但链表不会。它帮你做到的是纯粹的指针重接代价是复杂度永远 O(1)除非是形态三且你跨链表拼接时涉及距离计算。第二条潜规则splice 的 pos 不能指向源链表中的节点否则会把自己搬给自己行为未定义。同一列表内用 splice 想要移动节点位置是允许的但 pos 必须落在源区间之外。比如想把自己内部的某个节点移到最前面可以用a.splice(a.begin(), a, it)这里 it 原本指向 a 中某个节点而 a.begin() 是目标位置逻辑上没问题但如果你把 pos 设成区间内部的迭代器后果自负。第三条潜规则形态三跨链表拼接时底层会花 O(n) 计算 distance因为需要知道区间长度来更新目标链表的 size。所以如果你要移动一个很长的区间这个间隙不是完全免费。不过这是标准库实现层面的细节你在工程上只需要理解节点节点的转移是常数时间但区间的长度统计是有代价的。3.2 remove/remove_if真正的按值/按条件删除remove 是 list 特有的接口它和通用算法 std::remove 完全不同。l.remove(val)会遍历整个链表把所有值为 val 的节点一次性删除并自动回收内存同时会改变链表的 size。而std::remove只是把不等于 val 的元素搬移到前面然后返回新的逻辑尾部真正的删除还得靠 erase 配合。list 的 remove 把这两步合一了用起来顺手很多。std::listint l {1, 2, 2, 3, 4, 2, 5}; l.remove(2); // 结果1, 3, 4, 5 l.remove_if([](int x) { return x % 2 0; }); // 结果1, 3, 5remove_if 配合 lambda 是删选的主力军比手写 for 循环加 erase 更安全。注意 remove_if 接受的谓词返回 true 时元素会被删除。如果你想要的是保留满足条件的元素用std::not1在 C17 之后已经废弃C20 改为std::not_fn更简单的是在 lambda 里直接写!取反别修饰过度。3.3 sort、merge、uniqueList 自带算法别拿 std::sort 硬套这是 List 踩坑的重灾区。新手最常见的错误是写std::sort(l.begin(), l.end())编译直接报错。原因很简单std::sort 要求随机访问迭代器而 list 的迭代器是双向迭代器不支持it n这种跳跃。list 有自己的成员函数 sort()底层使用归并排序不需要随机跳所以能用双向迭代器完成整个排序过程。std::listint l {3, 1, 4, 1, 5, 9, 2, 6}; l.sort(); // 默认升序 l.sort([](int a, int b) { return a b; }); // 降序 l.sort(std::greaterint()); // 另一个降序写法merge 是把两个已经排好序的链表合并成一个有序链表l1.merge(l2)合并后 l1 持有所有元素并保持有序l2 变空。和 splice 不同的是merge 过程中会按顺序把 l2 的节点挨个搬到 l1 的相应位置最终整个 l1 依然有序。如果你的 l1 或 l2 没先排序去找 merge得到的结果不一定是你以为的顺序甚至可能违反基本直觉。unique 是去重接口l.unique()删除连续重复的元素让每个相邻元素的相邻处不再有重复值。注意它只删除连续重复不是全局去重。所以陌生数据想真正去重得先 sort 再 unique顺序不能反。下面的代码演示一个完整的排重流水线std::listint l {5, 3, 3, 1, 2, 3, 5, 5, 1}; l.sort(); // 1, 1, 2, 3, 3, 3, 5, 5, 5 l.unique(); // 1, 2, 3, 5sort、merge、unique、reverse 这四个成员函数在功能性上都和标准算法库有重叠但 list 之所以提供成员版本就是为了绕开迭代器限制并发利用链表结构特性。reverse 是翻转链表顺序它不需要任何条件l.reverse()直接倒序。这四个接口是 List 的核心操作闭环也是面试时不厌其烦考你的内容。4. 迭代器的那些坑List 迭代器的特点与失效规则4.1 双向迭代器为什么不能 2vector 的迭代器可以it 5直接跳到目标位置因为底层是连续数组地址偏移就完了。list 的迭代器只能it或--it因为节点之间靠指针串起来没有下标可算。这个限制推开了 list 的随机访问也决定了排序算法不能用 std::sort。如果你在代码里写了listint::iterator it l.begin(); it 2;编译时会得到一条含义明确但新手看不懂的报错没有为 bidirectional_iterator_tag 定义。看到这行错你就要反应过来这是迭代器类别不匹配。平时写循环遍历 List我用的是下面两种写法第二种是万物皆迭代器时的利器// 普通 for 循环 for (auto it l.begin(); it ! l.end(); it) { /* ... */ } // 范围 for内部其实也是迭代器但更省事 for (int v : l) { /* ... */ }范围 for 内部会展开成迭代器遍历但如果你在循环体内对容器做了结构性修改比如 erase 当前元素这个范围 for 底层持有的迭代器可能失效运行时行为不可预知。所以做边遍历边删除时请老实使用显式迭代器范围 for 只用于不修改容器的场景。4.2 erase 的返回值遍历删除的万能钥匙list 的 erase 会删除指定元素但同时只有被删元素的迭代器失效其它迭代器完全不受影响。这一点和 vector 的 erase 行为截然不同vector 在任意位置 erase 都会让 pos 之后的所有迭代器失效因为后面元素要前移覆盖。这是链表结构的天然优势也是面试常问的区别点。正因为如此list 里遍历删除最稳妥的写法是直接利用返回的迭代器std::listint l {1, 2, 3, 4, 5, 6}; for (auto it l.begin(); it ! l.end();) { if (*it % 2 0) { it l.erase(it); // erase 返回被删节点的下一个迭代器 } else { it; } }如果你写成it前先 erase然后循环底部再it但 erase 已经把当前元素释放it变成野指针再自增就是未定义行为。而it l.erase(it)把新的位置接住配合自增逻辑非常清晰。我看到很多老手写 list 遍历删除时已经默认用这种模式了新手越早养成越好。4.3 insert 之后的迭代器管理insert 同样有这个返回值特性。l.insert(pos, value)返回指向新插入元素的迭代器后续如果要链式插入或定位操作直接用返回值就行不必重新去找。还有一点容易被低估insert 不会使任何现有迭代器失效不管你插在什么位置原有节点的地址不变迭代器指向的元素也不变。这与 vector 在扩容时会全部失效形成鲜明对比。splice 影响的是节点归属而不是元素的搬家。所以 splice 之后如果你原先持有指向被搬节点的迭代器这个迭代器依然合法只是它现在属于目标链表。这比 vector 的搬移逻辑好用太多你不需要重新找新位置。5. List 和 Vector/Deque 的选型边界接口设计背后的性能逻辑5.1 复杂度对照表接口吹牛性能落地List 的接口设计之所以看起来自由背后全是复杂度代价和优势的权衡。我用一张表把它的复杂度特性和 Vector/Deque 摆在一起你用的时候直接对照操作std::liststd::vectorstd::deque尾部插入O(1)均摊 O(1)均摊 O(1)头部插入O(1)O(n)均摊 O(1)中间插入O(1)需已定位O(n)O(n)中间删除O(1)需已定位O(n)O(n)随机访问O(n) 不支持O(1)O(1)迭代器失效规则仅被删元素splice 后仍有效扩容可能全失效中间删除后部分失效插入可能全失效删除端部部分失效缓存局部性极差极好中等所以 List 的 O(1) 插入不是全能的它要求你在插入前已经有一个迭代器定位到了目标位置。如果你每次都拿着find去扫一遍才知道插在哪那整体复杂度还是 O(n)优势就没了。这也是为什么 List 非常适合迭代器模式使用——如果你有固定的几个位置要反复操作维护好位置迭代器List 会非常快。5.2 什么场景才真正需要 List实际工程里用 List 的场景大致有三类。第一类是频繁在中间位置插入删除且插入删除的点通常用迭代器维护。比如一个双向链表模拟的 LRU 缓存节点在命中时被 move 到头部这天然就是 splice 的主场用 vector 模拟 LRU 的话每次命中还要搬移全部节点代价太大。第二类是需要稳定的迭代器语义。如果你有一批代码在持有迭代器的同时反复在容器里插入其它元素vector 可能会让那些持有迭代器的代码纷纷失效list 则完全不受影响。这种场景常在事件驱动或图遍历逻辑中出现。第三类是需要 O(1) 的头部插入/删除且总数据量较大。虽然 deque 也支持常数时间的头插但 deque 的中间插入依然是 O(n)list 则做到真正常数。5.3 什么场景别用 List缓存友好性是真凶很多人被插入 O(1)蛊惑觉得 list 万能结果从 vector 切换到 list 后整体运行反而变慢。原因在于缓存局部性。一个双向链表的每个节点至少多出两个指针也就是 16 字节的额外开销64 位平台下当链表节点分散在堆中各处时遍历链表的每个节点都可能触发一次 cache miss。而 vector 的元素是连续的遍历时硬件预取器能连续加载一整块内存往往一次 cache miss 就能把后续十几二十个元素带进缓存。一句话总结我的选择原则需要随机访问就选 vector只需要在头部频繁操作可以加 deque真正要反复在中间改结构、又需要长期持有迭代器时才选 list。工程上list 在大多数只是遍历并偶尔 insert/erase的场合都未必比 vector 快因为 cache miss 的损失远比搬几个元素大。如果你不确定先写 vector拿数据说话只有 profile 出来中段插入确实是瓶颈时再切 list。6. 实战中我总结的 List 接口记忆法与代码规范6.1 记忆框架把 List 接口压缩成三张图每次有人跟我说 List 接口多、记不住我就让他们按下面的框架把接口归位。第一类是增加节点push_back、push_front、insert、emplace_back、emplace_front、emplace。它们有一个共同点——都是制造新节点链入链表。其中 emplace 系列可以原地构造比 push 少一个临时量拷贝尤其推荐。第二类是删除节点pop_back、pop_front、erase、remove、remove_if、clear。erase 是删除迭代器指向的单个或区间节点remove/remove_if 是按值或按条件批量删。它们的迭代器失效规则不同记住一句口诀erase 会让当前迭代器失效remove 系列在内部删除并正确维护clear 全没。第三类是重排列及重组splice、sort、merge、unique、reverse。这一组是链表的灵魂操作重点在 splice。剩下的口诀是sort 排序、merge 合并有序表、unique 去连续、reverse 翻转干活的都是节点指针代价和算法讲解直接对应。这三张图装进脑子List 的界面就不再是几十个函数而是三捆动作。6.2 推荐代码习惯与工程规范基于这么多年的踩坑经验我在工程里对 List 的使用定了几条硬性规范也分享给你。比如遍历中若有结构性修改绝不使用范围 for改用显式迭代器。范围 for 看似高级底层还是持有迭代器一旦在循环体内 erase 当前节点迭代器就失效了。这不是编译器帮你拦的东西只有你能拦。再如尽量少用裸 new 构造 list 的元素。list 存储复杂对象时如果对象内部含有指针并拥有堆内存删除节点会自动析构这部分还好但如果你建 list 存指针并把所有权交给 list就要记得在 clear 之前手动 delete 或改用智能指针否则会出现内存泄漏和悬空指针双料事故。这是容器管理能力之外的事STL 不负责替你管理指针指针的所有权。还如优先 emplace 而不是 push 临时变量尤其当元素是 string、pair 这类构造函数开销不低的对象时。比如// 不如 std::liststd::pairint, std::string pl; pl.emplace_back(1, hello); // 不推荐多一次临时量拷贝 pl.push_back(std::make_pair(1, hello));6.3 一个综合示例用 splice、sort、remove_if 管理任务队列我经常拿任务队列管理当 List 的实操模板这里也贴一段把前面讲的接口都串起来#include list #include string #include iostream struct Task { std::string name; int priority; // 数值越小优先级越高 bool done false; }; void print(const std::listTask tasks) { for (const auto t : tasks) std::cout t.name ( t.priority , (t.done ? done : todo) ) ; std::cout \n; } int main() { std::listTask todo { {write report, 3, false}, {fix bug, 1, false}, {meeting, 2, true}, {review code, 2, false} }; std::listTask finished; // 把已完成任务移动到 finished并从未完成列表中移除 for (auto it todo.begin(); it ! todo.end();) { if (it-done) { finished.splice(finished.end(), todo, it); // 注意先 splice 后 it } else { it; } } // 按优先级排序1 最高 todo.sort([](const Task a, const Task b) { return a.priority b.priority; }); // 删除满足条件如优先级大于 5 且名称带 temp的任务 todo.remove_if([](const Task t) { return t.priority 5 t.name.find(temp) ! std::string::npos; }); std::cout TODO: ; print(todo); std::cout FINISHED: ; print(finished); return 0; }这段代码有几处值得细看。首先是finished.splice(finished.end(), todo, it)这一行先把 it 指向的节点拼接到 finished 末尾再把 it 向后移动。注意这里的自增是在 splice 之前完成的参数求值顺序决定的splice 会把当前节点移走it 此时还能安全地指向下一个节点吗答案是splice 后 it 指向的那个节点已经属于 finished但 it 本身仍然合法。不过在这个循环里我们再把 it 自增时it 必须先变成下一个节点这不会踩到被搬走的节点。实际我更推荐的写法是auto tmp it; it; finished.splice(...);这样可读性好且不依赖求值顺序不过大多数编译器和 C17 的函数参数求值顺序已保证自增在 splice 前完成风险可控。稳妥至上你可以在写项目时把这种一行遍历改成两行。其次是排序用的是 list 自带的 sort因为 std::sort 无法作用于双向迭代器。再次是 remove_if 配合 lambda 做条件删除一条链从遍历删除 拼接 排序全部覆盖了今天讲的三大主线。你如果能把这段代码看懂并背下来List 接口的面试题基本就难不倒你了。最后再分享一个小技巧如果你确实只是想知道某个元素存不存在用std::find(l.begin(), l.end(), val)返回迭代器能找到就说明存在如果是单纯想删除所有等于 val 的元素用l.remove(val)就行不需要先 find 再 erase少写一行是一行。这些接口用熟了List 不但不吓人反而会变成你手里最随手的小工具。