最近在带一个 C 初阶讨论组群里经常有人问vector 和 list 到底怎么选大多数人都能背出“vector 随机访问 O(1)list 插入删除 O(1)”但再追问一句“list 的迭代器为什么不支持 3”或者“list 里 erase 之后迭代器还能不能用”基本就没声了。后来我花了一个晚上把 C STL 中 list 的使用和模拟实现彻底捋了一遍还手写了一个能跑的 mini list。这篇文章就是那次梳理的产物。前半部分聊使用后半部分动手拆实现最后把自制版本和标准库的差距盘一遍。适合刚学完 C 基础语法、想摸清 STL 底细的初阶同学也适合想用自写容器练内存管理和模板封装的读者。1. 为什么初学阶段就要和 list 较真从一张容器对比表说起1.1 list 在容器家族中的生态位先看一张表后面很多问题都能从这张表里推出来。容器底层结构随机访问中间插入/删除缓存友好性迭代器能力vector连续动态数组O(1)O(n)很友好随机访问deque多段连续缓冲区O(1)两端 O(1)中间 O(n)较友好随机访问list带头循环双向链表不支持O(1)前提是已有迭代器较差双向forward_list带头单向链表不支持O(1)前提是已有迭代器较差单向list 不支持随机访问不是实现缺陷而是双向链表的天然属性。每个节点都是独立分配的一小块内存节点之间靠 prev/next 指针联系想找第 N 个元素只能从头部或尾部一节一节走过去。你可以类比成一列只有前后相通的车厢想去中间某一节司机只能逐节通知过去不存在“瞬间跳到第 8 节”的通道。对初阶学习者来说list 真正难理解的地方在于vector 的迭代器底层就是连续数组上的指针而 list 的迭代器是一个包装了节点指针的自定义类型。你越早亲手包一个这样的迭代器越容易理解 STL 为什么能把算法和容器解耦。这也是我坚持让讨论组的同学去手写 list而不是只背接口的原因。1.2 标准 list 的接口清单不能只会 push_back很多初学者接触 list只会 push_back、push_front、遍历这三板斧。实际上标准 list 的接口可以按功能分成几组构造list()、list(n)、list(n, val)、list(first, last)、拷贝/移动构造、initializer_list构造迭代器begin、end、rbegin、rend、cbegin、cend容量empty、size、max_size访问front、back修改push_front、pop_front、push_back、pop_back、insert、erase、swap、clear操作merge、splice、remove、remove_if、reverse、unique、sort注意 list 没有operator[]也没有at。很多初学朋友会拿 vector 的使用习惯往 list 上套然后编译报错才反应过来一个不支持随机访问的容器自然不应该提供随机访问接口。这个认知比记住接口列表更重要。1.3 初阶最应记住的行为差异list 和 vector 最核心的行为差异全部源于“节点式存储”这四个字。插入和删除元素不会让其他迭代器失效。erase之后只有指向被删除节点的迭代器失效。splice能在常数时间里把一个 list 的节点搬到另一个 list。list 自带sort成员函数因为全局std::sort需要随机访问迭代器。C11 起size()保证常数时间很多老教程里写的“list 的 size 是 O(n)”已经过时。这几条不需要死记。只要抓住“节点地址稳定、双向链表连接”这个根因任何边界行为都能现场推出来。2. list 使用中的那些边界行为接口好记坑在细节2.1 先跑一个最小 demo学习任何一个容器第一步永远是把最小可运行代码敲一遍而不是只看文档。#include list #include iostream int main() { std::listint l; l.push_back(1); l.push_back(2); l.push_front(0); std::cout l.front() l.back() \n; // 0 2 for (auto it l.begin(); it ! l.end(); it) { std::cout *it ; // 0 1 2 } std::cout \n; for (int x : l) { // 底层也是 begin/end std::cout x ; } }这里值得留意的是基于范围的 for 循环能直接作用在 list 上是因为 list 提供了符合要求的 begin/end 迭代器。迭代器必须支持解引用、自增、比较这套语义就是容器和算法之间约定的“暗号”。2.2 insert/erase 的返回值和迭代器失效规则list 的insert返回指向新插入元素的迭代器erase返回被删除元素的下一个元素的迭代器。最经典的应用场景是“在遍历中删除满足条件的元素”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; } // 结果为 1 3 5为什么不能这样写for (auto it l.begin(); it ! l.end(); it) { if (*it % 2 0) l.erase(it); // it 指向的节点被 delete继续 it 是灾难 }因为erase之后it指向的节点内存已经释放再对it做就是在访问悬空指针。list 的迭代器失效规则不是“区间失效”而是“节点失效”这比 vector 温和得多但同样需要认真对待。2.3 list 自带的“算法型”成员函数list 有一批其他容器没有的成员函数原因是全局算法在链表结构上“使不上劲”。std::listint nums {1, 5, 2, 5, 3, 5}; nums.remove(5); // 删除所有等于 5 的元素结果 1 2 3 std::listint a {1, 1, 2, 2, 1}; a.unique(); // 只删连续重复结果是 1 2 1remove和全局std::remove的区别非常容易被忽略全局std::remove只是把不需要的元素移到序列末尾并不真正删除而 list 的成员remove是直接摘链并释放节点。unique只处理连续重复的元素如果数据不是有序的想“去重”得先sort。std::listint vals {3, 1, 2}; vals.sort(); // 默认升序 vals.sort(std::greaterint()); // 需要 functionalmerge和splice也是 list 的招牌操作。merge要求两个 list 都已经有序合并后另一个 list 会变空。splice则是把另一个 list 的节点“搬过来”整个过程不需要复制数据只改指针所以是 O(1)。std::listint x {1, 3, 5}; std::listint y {2, 4, 6}; x.merge(y); // y 变空x 变成 1 2 3 4 5 6 std::listint from {7, 8}; std::listint to {1, 2}; to.splice(to.end(), from); // to 变成 1 2 7 8from 变空2.4 我踩过的三个应用层坑第一个坑是空 list 上调用front或back。这是未定义行为debug 版本可能直接断言release 版本可能读到脏数据。不要依赖“反正不会崩”的侥幸心理调用前先用empty()判断。第二个坑是clear()之后继续使用旧的迭代器。clear会释放所有数据节点旧迭代器全部失效。这看起来和“list 插入不使迭代器失效”矛盾其实不矛盾失效只发生在节点被删除时clear删了所有节点自然所有迭代器都失效。第三个坑是用remove_if时lambda 里错误地捕获了外部迭代器。比如你先保存了auto it l.begin()然后在谓词里引用它一旦中途删除节点it就悬空了。正确的做法是谓词里不要依赖任何指向同一容器的迭代器只依赖输入值和外部普通变量即可。3. 手写一个 mini list双链表骨架是这样一层层拆出来的3.1 我选择的结构带头节点的循环双向链表动手写 list 之前必须先定数据结构。我选择的是“带头节点的循环双向链表”这也是标准库最常见的设计。头节点也叫哨兵节点它不存业务数据只作为链表起点。空链表时head_-next指向head_head_-prev也指向head_。非空时head_-next是第一个元素head_-prev是最后一个元素。这个设计带来的最大好处是插入和删除不需要特判“是不是首尾”。尾插时直接向end()插入而end()就是哨兵节点遍历到哨兵节点时结束正好对应it ! end()。如果不用哨兵头插、尾删、遍历退出条件都要写特殊逻辑代码复杂度会翻倍。3.2 节点和迭代器先定义好“一块骨头”节点类只负责两件事存数据、连前后。不要往节点里塞操作逻辑否则会越来越不像容器。templatetypename T struct ListNode { T data; ListNodeT* prev; ListNodeT* next; explicit ListNode(const T val) : data(val), prev(nullptr), next(nullptr) {} };迭代器是这次模拟实现里最值得花时间的部分。表面上看它只是对ListNodeT*的包装一旦包装好基于范围的 for 能跑标准库那些只依赖迭代器接口的工具函数也能接入。#include cstddef #include iterator templatetypename T, typename Ref, typename Ptr struct ListIterator { using iterator_category std::bidirectional_iterator_tag; using value_type T; using difference_type std::ptrdiff_t; using pointer Ptr; using reference Ref; using Self ListIteratorT, Ref, Ptr; ListNodeT* node; ListIterator(ListNodeT* ptr nullptr) : node(ptr) {} Ref operator*() const { return node-data; } Ptr operator-() const { 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 rhs) const { return node rhs.node; } bool operator!(const Self rhs) const { return node ! rhs.node; } };你可能注意到这里引入了Ref和Ptr两个模板参数这是为了同时生成普通迭代器和 const 迭代器第 4 章会专门讲。类里那些iterator_category、value_type等别名不是装饰品它们相当于迭代器的“身份证”。当你调std::distance、std::advance这类泛型工具时算法要靠这些别名决定策略。3.3 List 主体增删改查的完整骨架List 类本身我给出一个能跑的核心版本。为了篇幅移动语义、分配器等暂时不写留给后续扩展。#include algorithm #include cstddef templatetypename T class List { public: using value_type T; using size_type std::size_t; using iterator ListIteratorT, T, T*; using const_iterator ListIteratorT, const T, const T*; List() { createHead(); } ~List() { clear(); delete head_; } List(const List other) { createHead(); for (const T x : other) push_back(x); } List operator(const List other) { if (this ! other) { List tmp(other); swap(tmp); } return *this; } 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_); } bool empty() const { return size_ 0; } size_type size() const { return size_; } T front() { return head_-next-data; } T back() { return head_-prev-data; } const T front() const { return head_-next-data; } const T back() const { return head_-prev-data; } void push_back(const T val) { insert(end(), val); } void push_front(const T val) { insert(begin(), val); } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); } iterator insert(iterator pos, const T val) { ListNodeT* cur pos.node; ListNodeT* pre cur-prev; ListNodeT* nn new ListNodeT(val); pre-next nn; nn-prev pre; nn-next cur; cur-prev nn; size_; return iterator(nn); } iterator erase(iterator pos) { ListNodeT* cur pos.node; if (cur head_) return end(); ListNodeT* pre cur-prev; ListNodeT* nxt cur-next; pre-next nxt; nxt-prev pre; --size_; delete cur; return iterator(nxt); } void clear() { while (size_ ! 0) erase(begin()); } void swap(List other) noexcept { std::swap(head_, other.head_); std::swap(size_, other.size_); } private: ListNodeT* head_ nullptr; size_type size_ 0; void createHead() { head_ new ListNodeT(T()); head_-next head_; head_-prev head_; size_ 0; } };这段代码有几个刻意设计。begin()返回head_-nextend()返回head_。因为链表是循环的从第一个节点出发绕一圈回到哨兵节点正好对应遍历结束。insert复用为push_back和push_front向end()插入就是尾插向begin()插入就是头插。erase(end())在标准库中是未定义行为我的教学版做了防御处理但工程代码里不应依赖这类保护。一个必须强调的点是new ListNodeT(val)要放在修改指针之前。如果先改指针再 new而new或T的拷贝构造抛异常链表已经处于被破坏的中间状态。先成功创建新节点再接入链表才能保证失败时原链表不变。3.4 为什么 insert 要先 new 再挂指针我最早写这个 mini list 时顺序是反的。先让前驱节点的 next 指向新位置再 new看起来没什么问题。结果某次故意让T的拷贝构造抛异常链表直接断成两截程序崩溃。原因很简单链表是靠指针连接维持结构的任何修改指针的操作都算“提交变更”。如果提交之前准备工作没做完异常一抛结构就回不去了。正确的顺序是先把新节点完整造出来再一次性更新四个指针。这一步做好了insert就具备基本的强异常安全保证。erase那边也要注意顺序先保存pre和nxt再摘链最后delete cur。如果先delete cur再访问cur-prev就是典型的 use-after-free。代码跑起来很快但这类问题一旦出现调试成本极高。3.5 拷贝构造和赋值深拷贝与 copy-and-swapList 的成员变量里有一个裸指针head_。如果拷贝构造时直接写head_ other.head_两个 list 会共享同一组节点析构时 double free改动一个还会影响另一个。最稳妥的写法是深拷贝先构造一个空表然后遍历other逐个push_back。赋值运算符更推荐 copy-and-swap 写法List operator(const List other) { if (this ! other) { List tmp(other); swap(tmp); } return *this; }先拷贝出一个完整的tmp再和*this交换内部指针。tmp在函数结束时会自动析构原对象里的旧节点被安全释放。这样写不仅免去了手动判断自赋值的烦恼还天然具备异常安全如果拷贝过程中抛出异常*this还没有发生任何变化。4. 模拟实现中最容易翻车的两个地方const 迭代器和深拷贝4.1 const 迭代器const 容器必须能只读遍历很多初阶同学写完 List 主体后发现下面的代码编译不过const Listint cl; for (auto it cl.begin(); it ! cl.end(); it) { // 这里想读每个元素 }原因很简单如果没有只返回 const 迭代器的begin() constcl.begin()会尝试调用非 const 版本的begin()可cl是 const 对象编译器不允许。于是报错信息五花八门最常见的是“discards qualifiers”。const 容器能不能遍历取决于一个容器是否提供 const 迭代器。这不是“锦上添花”而是 const 语义的一部分。标准库为每个容器都提供了const_iterator目的就是让只读遍历成为一等公民。4.2 两种设计方案对比bool 模板参数 vs Ref/Ptr 双模板参数实现 const 迭代器有两种常见路线。方案 A 是给迭代器类加一个bool IsConst模板参数再用std::conditional_t决定operator*返回const T还是T。优点是迭代器类型数量少缺点是实现里到处是条件类型读起来绕。方案 B 就是我在前面代码里用的把Ref和Ptr单独作为模板参数让iterator和const_iterator成为同一个类模板的两种实例化。这样operator*直接返回Ref代码干净直观也更接近 libstdc 里__normal_iterator的思路。方案核心思路优点缺点方案 A单个迭代器类 bool 模板参数类型数量少条件类型多可读性差方案 BRef/Ptr 双模板参数直观、贴近标准库模板参数多两个初次看到有点绕初阶段我强烈推荐方案 B。你要理解的核心不是“哪种写法看起来更高级”而是 const 迭代器和普通迭代器本质上就是不同类型通过模板参数把差异隔离出来是最简单可靠的办法。4.3 begin/end 的 const 版本和底层指针的类型细节List 里我写了两个begin()iterator begin() { return iterator(head_-next); } const_iterator begin() const { return const_iterator(head_-next); }这两个函数参数列表一模一样靠 const 限定符区分重载。const 版本返回 const 迭代器所以const Listint对象只能拿到只读入口。这里有一个需要交代的简化我写的const_iterator内部存的仍然是ListNodeT*而不是const ListNodeT*。从严格类型角度看这不够严谨。但效果是安全的因为ListIterator的operator*返回Ref当Ref const T时外部拿到的引用就是 const 的编译器会拦截修改行为。标准库会做得更严格但教学版没必要一开始就把节点指针的 const 传播也做成模板参数那会让代码瞬间难懂一倍。4.4 深拷贝之外还容易翻车的两个细节第一个是clear和析构的分工。我最初的版本在clear里把哨兵节点也删了析构里又删一次调试器直接报 double free。正确的分工是clear只负责删所有数据节点让链表回到空表状态析构函数先clear再delete head_。谁分配的谁释放这个原则在容器类里尤其重要。第二个是自赋值。如果赋值运算符不判断this ! other自赋值时先clear再深拷贝等于把自己清空后又复制一份空表数据全丢。copy-and-swap 写法天然规避了这个问题因为拷贝发生在修改之前。写完初版后至少跑这样一组自测Listint a; a.push_back(1); a.push_back(2); Listint b(a); // 深拷贝 b.push_back(3); // a.size() 2, b.size() 3 const Listint ca a; for (auto it ca.begin(); it ! ca.end(); it) { // *it 是 const int不能赋值 }如果这组测试顺利通过说明 const 迭代器、深拷贝、析构三个最容易翻车的点基本稳了。5. 我的 mini list 与标准库 list 的差距说清这些你才算真懂5.1 功能对照mini list 到标准库还差多少我的 mini list 能跑但它和标准库 list 之间的差距正好是一张很好的“待办学习清单”。功能标准库 list我的 mini list分配器 Allocator支持可定制内存策略不支持直接 new/delete反向迭代器 rbegin/rend支持不支持splice/merge/remove/remove_if/unique/sort支持需要自己扩展emplace/emplace_back支持C11 起不支持移动构造/移动赋值支持未实现initializer_list 构造支持不支持max_size/get_allocator支持不支持这些不是花架子。分配器解决的是“节点从哪来”的问题高频插入删除时重复 new/delete 的开销会被放大emplace 能直接在节点内存里构造对象省掉一次临时对象拷贝移动语义让容器间转移资源变得廉价initializer_list 让初始化顺手不少。初阶不需要一次全补但要知道前方还有这些山头。5.2 内存布局和性能差异教学模式的标准库 list本质上也是带头循环双向链表这一点和我的 mini list 没有本质区别。真正的差异体现在微观和外围标准库通常会从分配器手里拿内存节点内部可能把连接字段和数据字段拆开哨兵节点不需要真正构造 T 对象。这些优化让它在频繁插入删除时的表现远比教学版稳定。我在本机做了一次很粗糙的实测Release x64 下单次运行几千个元素级别两者几乎没有差距到百万级重复 push_back 时标准库由于内存分配策略更平滑整体领先幅度会明显拉大。这个结果不奇怪也不代表我的代码写错了。教学版的目的是让你看清机制不是替代标准库。把 mini list 用在生产环境里的首要风险不是功能不全而是没有处理内存分配失败、异常安全、并发访问等真实世界的复杂情况。5.3 异常安全的三层思考异常安全通常分三个层次基本保证、强保证、不抛异常保证。基本保证操作抛出异常后对象仍处于有效状态不泄漏内存。强保证操作抛出异常后容器保持原样就像没操作过一样。不抛异常保证操作本身不会抛异常比如swap。前面说的“先 new 再接入”让insert在节点分配或 T 拷贝构造失败时保持原链表不变这就达到了强保证的要求。赋值运算符使用 copy-and-swap 后即使拷贝中途抛异常*this也没有被改过同样是强保证的直观体验。标准库对这些行为有明确承诺初阶可以不用深究标准条款但写容器时养成“失败后容器不能坏”的习惯非常值钱。5.4 这次拆轮子到底拆出了什么最后把我眼中最有价值的几个“为什么”集中放在一起。为什么 list 不能直接使用std::sort因为全局 sort 要求随机访问迭代器list 的迭代器只有双向移动能力。成员 sort 用的是归并排序只依赖和--所以能正常工作。这解释了为什么标准库要给 list 单独提供 sort。为什么list::remove会真的删除元素而全局std::remove只是搬移全局 remove 是“把不该留的值往后面覆盖”它拿不到容器的删除权限成员 remove 长在容器内部可以直接摘链并释放节点。同样是“删除”底层机制不同表现也不同。为什么 list 插入不使其他迭代器失效因为每个节点地址独立稳定插入只是修改了相邻节点的 prev/next 指针。vector 扩容时会搬走整片内存所以规则完全不同。这两个容器放在一起对比学习才能真正理解“迭代器失效”不是一个抽象概念而是由内存模型直接决定的。按我个人的学习路径来说把 mini list 写到能跑、能过自测、能讲清楚和标准库的差距比刷十道链表选择题有用得多。接下来你可以试着给它补上 merge、unique、splice或者写一个不带头节点的版本对比两种实现的边界条件哪个更麻烦。补完这些再回头看 cppreference 上 list 那一页你会发现自己不是在查文档而是在对照自己写过的代码理解设计。这个感觉和单纯背接口完全不一样。