接触过C一段时间的朋友多半都绕不过std::list这个双向链表容器。网上讲list的教程一抓一大把但大部分都停留在API罗列层面push_back、push_front、pop_back……抄一遍语法就完事了。真正到了实际项目里什么时候该选list、什么时候该换vectorerase返回值到底怎么用remove_if和erase怎么配合才不会崩这些才是要命的地方。这篇文章不打算重复官方文档而是结合我这些年用list做实际业务的体会把常用操作掰开揉碎讲清楚尤其是那些“文档里不会明说但实战中一定会遇到”的坑。1. 先搞清楚list的底层脾气双向链表决定了它的行为边界很多初学者搞不懂一个问题明明vector啥都能干为什么还要发明list要回答这个得先从list的底层结构说起。list底层实现是一个带头节点的双向循环链表。每个元素是一个独立的节点节点内部除了存储数据本身还保存着指向下一个节点和上一个节点的指针。这跟vector那种“连续内存空间里依次摆放元素”的存储方式有本质区别。这种结构带来三个直接影响插入和删除是O(1)的——只要知道位置改一下前后节点的指针就行不涉及数据搬移不支持随机访问——想拿到第5个元素只能从头节点开始一个个跳过去下标访问list[5]压根不存在每个元素额外付出两个指针的内存开销——8字节/元素64位系统数据量大了以后内存占用比vector高不少正因为是循环链表list的end()迭代器其实指向的是头节点本身begin()指向头节点的下一个节点。所以遍历list的标准姿势就是#include list std::listint myList {1, 2, 3, 4, 5}; for (auto it myList.begin(); it ! myList.end(); it) { // it是一个双向迭代器只能或--不能it 2 std::cout *it ; }这里有个一开始容易犯迷糊的点list的迭代器是双向迭代器BidirectionalIterator只支持和--不支持 n这种随机跳转。想跳转得用std::advanceauto it myList.begin(); std::advance(it, 3); // 从begin走三步it指向第4个元素 // 注意advance底层是一个个走过去的速度O(n)我见过有同事把vector的写法直接搬到list上写auto it myList.begin() 2;编译直接报错。这种错误根子上还是没理解“双向迭代器不支持随机访问”这条限制。另外list的size()操作在C11之前是O(n)的因为标准允许list不维护元素个数。但从C11开始size()稳定为O(1)可以放心调用。还有一个反直觉的点list的插入操作不会让任何现有迭代器失效包括指向被插入位置的迭代器。这一点跟vector完全不同——vector一旦扩容所有迭代器全部失效。在写“边遍历边插入”的逻辑时这个特性用好了非常香后面会具体讲。2. 日常增删改查好用的都在API名字之外list的常用操作大部分人都知道push_back和push_front。但实际写业务的时候真正有价值的是那些“看起来不起眼、用起来省大事”的细节。2.1 构造与赋值的高效姿势list支持好几种构造方式比较常用的是std::listint l1; // 空list 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}; // 初始化列表 std::listint l6(std::move(l5)); // 移动构造l5被掏空移动构造这块容易被人忽略。如果你的list存的是很大的自定义对象std::move构造比深拷贝快得多——因为它只把几个指针搬过去不需要逐个复制元素。实测下来存10万个大对象的list移动构造耗时约为深拷贝的1/5以下差距非常明显。还有一个值得提的是assign函数。如果你想给已存在的list重新赋一组值std::listint l; l.assign({1, 2, 3}); // 等价于l {1, 2, 3} l.assign(5, 100); // 5个100 // 注意assign会先clear再插入不是追加2.2 splicelist独有的“搬家”操作std::list::splice是list区别于vector最显眼的操作之一它能把一个list里的节点直接“搬”到另一个list全程不复制、不移动元素本身只改指针复杂度O(1)。std::listint src {1, 2, 3, 4, 5}; std::listint dst {10, 20, 30}; auto it dst.begin(); std::advance(it, 1); // 让it指向dst的第2个元素(20) // 把src整个搬到dst的it位置之前 dst.splice(it, src); // 结果dst {10, 1, 2, 3, 4, 5, 20, 30} // src为空更精细的用法是把src中某个迭代器指向的节点搬过去std::listint src {1, 2, 3, 4, 5}; std::listint dst {10, 20, 30}; auto target src.begin(); std::advance(target, 2); // 指向3 auto pos dst.begin(); std::advance(pos, 1); // 指向20 dst.splice(pos, src, target); // 结果dst {10, 3, 20, 30} // src {1, 2, 4, 5}splice在实战中的价值在于它允许以O(1)代价把一个链表段从一个容器挪到另一个容器。比如一个任务分发系统里可以把“超时未处理的任务”从待处理队列整段挪到重试队列元素本身不发生拷贝性能优势非常明显。2.3 用好resize别把扩缩容搞混了resize函数是一个很容易被忽略的操作。它的作用是改变list中元素的个数如果新size大于当前size多的位置会用默认值填充也可以指定填充值如果新size小于当前size末尾的元素会被删除std::listint l {1, 2, 3, 4, 5}; l.resize(3); // l {1, 2, 3} l.resize(6, 99); // l {1, 2, 3, 99, 99, 99}我经常在一个场景里用到resize预分配一个固定长度的队列结构保留前N位有效数据后面用占位值填充。比手动erase简洁很多。3. 删除操作是最容易踩坑的地方迭代器失效要刻进DNAlist的删除操作表面上看就pop_back、pop_front、erase、remove、remove_if、clear几个但里面那些“失效”的讲究才是实战中最容易翻车的地方。3.1 erase的正确打开方式erase可以删除单个迭代器指向的元素也可以删除一个迭代器区间。最关键的是erase的返回值是“被删除元素的下一个元素”的迭代器。C11之前返回值是voidC11之后改成了返回迭代器。std::listint l {1, 2, 3, 4, 5}; auto it l.begin(); std::advance(it, 2); // 指向3 auto nextIt l.erase(it); // 删除3nextIt指向4早期版本C98/03里erase返回void那时候遍历删除的正确姿势是// C98风格 std::listint::iterator it l.begin(); while (it ! l.end()) { if (*it target) { it l.erase(it); // 如果是void版本这里根本编译不过 } else { it; } }C11之后的推荐写法其实一样只是利用返回值更安全了。千万不要把原迭代器继续拿来回用即使看起来下一个元素还在那也是未定义行为——因为it已经被释放了。3.2 remove和remove_if先找再删的便捷通道list的remove和remove_if跟算法库里的std::remove含义有区别。list自带的remove是“真的删除”直接调用底层节点释放逻辑把满足条件的元素全部移除而std::remove只是“把满足条件的元素移到末尾”容器size都没变要想真删还得配合erase。std::listint l {1, 2, 3, 2, 4, 2}; l.remove(2); // l {1, 3, 4}所有2都被干掉remove_if则接收一个谓词lambda、函数指针、仿函数都行std::listint l {1, 2, 3, 4, 5, 6}; l.remove_if([](int x) { return x % 2 0; }); // l {1, 3, 5}所有偶数被移除这里要特别提醒一点remove_if内部是边遍历边删除的迭代器失效的处理已经封装好了所以不需要手动管理迭代器。这也是为什么我强烈建议“能remove_if就不手写循环”它从设计上就把坑填了。3.3 erase配合条件删除反向遍历写法有些场景下你需要删除元素但还需要用元素的值做一些额外处理比如记日志、发通知这时候手写循环遍历删除更灵活。但正向遍历删除有个麻烦删除当前元素后你想继续处理“下一个”就不容易了因为当前迭代器已失效。这时候反向遍历反而是更稳的思路std::listint l {1, 2, 3, 4, 5}; auto it l.end(); while (it ! l.begin()) { --it; if (*it 3) { it l.erase(it); // erase返回被删元素的下一个实际上方向相反 } }不过说实话这种反面操作很容易绕晕。我个人的建议是能用remove_if就用remove_if如果必须手写就利用erase返回下一个位置的正向循环并且在删除后不递增itauto it l.begin(); while (it ! l.end()) { if (*it % 3 0) { it l.erase(it); // 删除后it已经指向下一个有效位置不能再it } else { it; } }这个写法是最直观的大家用这个就对了。3.4 clear和swap清空列表的重型武器clear()把list里所有元素删掉O(n)复杂度遍历并释放每个节点。要跳出的坑是clear之后指向这些元素的迭代器全部失效但list本身还能用可以继续往里面塞东西。如果你只是想“把这个list的资源和另一个空list交换”swap更合适std::listint l {1, 2, 3, 4, 5}; std::listint emptyList; l.swap(emptyList); // l清了emptyList变成了{1,2,3,4,5}swap是O(1)的只交换内部头节点指针。如果你不再需要原list里的数据swap一个空list比clear还快——因为它根本不去释放元素节点节点所有权转到另一个list里了。当然如果不打算保留那个临时list最终析构时一样要释放只是把释放动作延后了。3.5 删除时的一个隐藏坑迭代器指向被删元素后继续使用这算是我在真实项目里踩过最深的坑之一。当时写一个模版数据缓冲队列要根据元素类型分组后丢弃不需要的组。我用了一个list拿着begin()的迭代器遍历逻辑上觉得“删掉了就跳到下一个”但代码是这样写的for (auto it l.begin(); it ! l.end(); it) { if (shouldRemove(*it)) { l.erase(it); // 错误it在erase后已经失效循环里的it是未定义行为 } }这个版本在Debug模式下跑得没问题因为Debug迭代器有校验一开Release就随机崩溃。排查了整整半天最后才发现是erase让it失效了循环里又对它做了。这种错误编译器不报错但运行时会随机出现“数据错乱”或者偶发崩溃极难定位。一个可靠的替代写法是把“是否需要删除”的判断先收集到一个标志位遍历完后统一删除或者直接用remove_if加副作用// 利用remove_if返回void配合一个外部条件捕获处理 std::listint removedValues; l.remove_if([](int x) { if (shouldRemove(x)) { removedValues.push_back(x); return true; } return false; });lambda里先记录再返回true节点会被list内部安全删除外部又拿到了要删除的值的副本。这个写法既安全又优雅。4. 排序和归并list自己的玩法跟vector不太一样list有一个非常重要但又容易用错的操作sort()。是的list自带排序不用去调std::sort。4.1 为什么不直接用std::sortstd::sort要求随机访问迭代器list的迭代器不满足。所以std::sort(l.begin(), l.end())直接编译失败。list自己实现了一个稳定排序stable sort基于归并排序复杂度O(n log n)但底层的比较是靠指针访问节点整体比vector的std::sort要慢一些。std::listint l {5, 2, 8, 1, 9}; l.sort(); // 升序 l.sort(std::greaterint()); // 降序 l.sort([](int a, int b) { return a b; }); // 自定义比较器作用同上自定义对象排序也很方便比如按某个字段排struct Order { int id; double price; }; std::listOrder orders; orders.sort([](const Order a, const Order b) { return a.price b.price; // 按价格降序 });注意list::sort是稳定排序。如果比较器里两个元素的price相同它们的相对顺序会保持不变。这个特性在“先按时间排、再按价格排”的多级排序场景里特别有用。4.2 merge合并两个已排序的listmerge函数用于把两个各自已排序的list合并成一个仍然有序的list。前提是两个list都按同样的排序规则排好序否则结果不可预期。std::listint l1 {1, 3, 5}; std::listint l2 {2, 4, 6}; l1.merge(l2); // l1 {1, 2, 3, 4, 5, 6} // l2为空merge也是O(n)复杂度并且不复制元素——它是把l2的节点直接链接到l1的合适位置。这里要提醒一句merge之后l2的节点被“掏空”了l2变成空list。有些新手以为merge是“复制合并”实际上它更像“嫁接”。如果你想保留l2原有的数据得先把l2拷贝一份再merge或者手动用inserterase的方式实现复制合并但那就不是O(n)了。4.3 unique去重只对“连续相同”有效unique函数会删除连续的相同元素让list中相邻元素互不相同。如果你有一组数据{1, 1, 2, 2, 3, 1, 1}调用unique后结果是{1, 2, 3, 1}——注意最后的1跟前面的1不相邻所以不会被删除。std::listint l {1, 1, 2, 2, 3, 1, 1}; l.unique(); // l {1, 2, 3, 1}如果你想去掉所有重复元素正确姿势是先排序再去重std::listint l {1, 1, 2, 2, 3, 1, 1}; l.sort(); l.unique(); // l {1, 2, 3}unique也支持自定义比较器比如按绝对值去重std::listint l {-1, 1, -2, 2}; l.unique([](int a, int b) { return std::abs(a) std::abs(b); }); // l {-1, -2}注意unique的比较器是“相等判断”不是“小于判断”。别跟sort的“小于判断”搞混了。4.4 reverse逆序不等于排序reverse直接把list翻转。这个操作跟sort完全不同它不改值的大小关系只是把头尾对调。std::listint l {1, 2, 3, 4}; l.reverse(); // l {4, 3, 2, 1}reverse也是O(n)指针操作非常快。实话说reverse的实用场景不算多但当你需要“栈”模型里逆序取数据时它很方便。5. 遍历和访问list的迭代器玩法比想象中多list迭代器是双向迭代器不是随机访问迭代器导致很多“看起来”应该能做的事做不了。比如不能用it 2跳着走不能用it - it计算距离。5.1 遍历三种方式迭代器、范围for、反向迭代器正向遍历for (auto it l.begin(); it ! l.end(); it)范围forfor (const auto x : l)最推荐代码最简洁反向遍历for (auto rit l.rbegin(); rit ! l.rend(); rit)反向迭代器内部其实是通过“先指向最后一个节点的下一个位置再往前访问”实现的理解这个就明白为什么rbegin()指向的是最后一个元素、rend()指向的是第一个元素的前面。一个容易忽略的点是erase(rit.base())这种操作容易出错因为rit.base()指向的是正向迭代器中“反向迭代器当前元素的后一个位置”转来转去很容易越界。不建议在遍历时混用反向迭代器和erase逻辑太绕。5.2 不允许使用下标访问怎么取第N个元素list没有operator[]。想取第N个元素标准做法是用std::advancestd::listint l {10, 20, 30, 40, 50}; auto it l.begin(); std::advance(it, 3); // it指向40std::advance内部对双向迭代器是一步一步走的所以O(n)。还有一个std::next可以直接从某个迭代器出发偏移代码更简洁auto it std::next(l.begin(), 3); // 指向40begin不动 auto it2 std::prev(l.end(), 2); // 从end往前退两步指向40注意std::next/std::prev返回新迭代器原迭代器不变。随便在循环里用std::next时也要小心边界别从end往后跳了。5.3 获取首尾元素front和backfront()返回第一个元素的引用back()返回最后一个元素的引用。注意空list上调用这两个函数是未定义行为所以调用前最好检查一下!l.empty()。std::listint l {3, 1, 4}; int first l.front(); // 3 int last l.back(); // 4这里有个细节通过引用修改元素是允许的——l.front() 100;会直接修改第一个节点里的值不会重新分配节点。因为list的节点里存的是元素本体不是指针。5.4 关于迭代器失效情况的系统总结为了不让大家再踩我踩过的坑这里把list各种操作的迭代器影响整理成一个速查表操作迭代器/引用失效情况insert / emplace / emplace_back / emplace_front / push_back / push_front不影响现有迭代器和引用erase单个元素/区间仅被删除元素的迭代器和引用失效其他不受影响remove / remove_if与erase类似仅被删元素的迭代器失效clear所有迭代器、引用失效sort / reverse / unique / merge / splice迭代器本身不失效它们指向的节点还在但迭代器指向的元素可能已移动到其他位置sort后迭代器指向的节点内容变了不确定指向哪个值resize缩小被移除元素的迭代器失效剩下的保持有效resize扩大新添加的元素迭代器有效原有元素有效这里最反直觉的是sortsort会重排节点但节点本身没被删除所以“指向节点A的迭代器”在sort后还是指向原来的节点A只是节点A里的值可能已经变成原来的另一个值了。如果你拿着sort前的迭代器直接访问值跟“值已经移动”混在一起的话很容易出错。我建议排序后不要抱着旧迭代器不放用索引重新定位更靠谱。6. 关于“什么时候该用list什么时候不该用”的诚实建议list有它的优点但也别把它当万能药。前面说完了所有常用操作最后我要泼一盆冷水——不少场景下list其实不是最佳选型。6.1 业务场景里list的真正优势需要频繁在头部/中部插入删除元素的场景比如定时任务队列高优先级任务需要insert到最前面低优先级任务push_back任务执行完从中间erase。这类操作list是O(1)vector在中间insert/erase是O(n)。迭代器在插入/删除后需要保持稳定的场景比如一个结构里存了多个list迭代器作为“书签”vector一扩容就全都失效了list不会。需要splice“搬移”节点的场景比如线程池里的任务队列一个线程处理某个任务时想把另一个任务插入到当前任务前splice是O(1)解决。内存敏感性list不需要预留连续内存元素多了也不存在“扩容搬移”的问题。6.2 什么时候该立刻放弃list需要随机访问下标操作频繁的场景。list取第5000个元素要O(n)vector是O(1)。这种场景下list会让你寸步难行。遍历为主的场景虽然list遍历也是O(n)但是每个节点都要通过指针跳转CPU的缓存命中率很差。实测同样遍历100万个intvector比list快5到10倍差距是硬件层面的。元素体积小且数量大的场景list每个节点额外的指针开销占了内存大头10万个int的list比vector多占用约80万字节还不算节点对齐内存吃紧时不划算。需要与算法库深度配合的场景很多STL算法比如std::sort、std::binary_search、std::lower_bound都要随机访问迭代器list用不了。6.3 一个老油条的选择思路我通常的口头禅是“你绝大多数情况下要用的都是vector除非你能明确说出需要list的哪个特性否则别用list。”这话不是说list不好而是说vector的缓存局部性优势在工程上碾压性太强10次里有8次vector就够用了。真正确认list不可替代的三条标准需要O(1)在中间位置插入/删除需要迭代器在插入/删除后保持稳定需要splice这类O(1)搬移操作三条至少命中一条才轮到list出场。如果只是任务队列的“首尾增删”用std::deque反而更合适——它兼顾了push_back、push_front的O(1)还支持随机访问内存碎片也少。7. 结尾的几句掏心窝子话list这玩意儿API不算多但真要玩明白得下点功夫。我最想留给大家的其实不是每个函数怎么用而是那个“理解底层结构再决定怎么用”的习惯。每次写list代码前先想想我是不是需要频繁中间插入我是不是在意迭代器稳定性如果两个答案都是否那很可能改用vector或deque更划算。再分享一个小技巧作为收尾调试list代码时建议在编译阶段就打开迭代器检查功能。GCC可以用-D_GLIBCXX_DEBUGMSVC的Debug模式默认开或者用_ITERATOR_DEBUG_LEVEL控制。这个开关能让你在运行到迭代器失效的未定义行为时直接报错崩溃而不是在Release下神不知鬼不觉地跑出脏数据。我靠这个开关救回过好几个通宵的排查夜建议你也试试。