很多人在学习STL容器的时候都会经历这样一段vector写起来很顺手list看起来也没什么难度无非就是链表。但等到你真正尝试“list使用模拟实现”这条路尤其是要把底层结构亲手写一遍的时候才会发现这个所谓的“简单容器”里全是门道。我先说一个自己带新手时的常见场景。有个同学用 list 用得挺熟push_back、push_front、sort 都会调但是问他“list的迭代器为什么不能直接用指针”“为什么insert之后迭代器不失效、vector却会失效”“自己写一个list该从哪里入手”他一下就卡住了。原因很简单会调用接口不等于理解实现。list 的使用和模拟实现是两码事中间隔着一层“设计逻辑”。这篇文章就是针对这个缺口写的。我会把 list 在容器家族里的定位、常用接口背后的语义、模拟实现最关键的三步设计哨兵位头节点、迭代器封装、const迭代器复用、以及模拟之后回头再看使用层面那些坑全部串起来。适合刚学完 C 基础、正准备啃 STL 源码的初学者也适合在准备面试时需要系统梳理 list 知识点的同学。思路清楚了代码自己就能写出来。文章最后我还会分享几个我实际踩过的编译错误和调试经验帮你少走弯路。1. list的定位它其实是“带头双向循环链表”1.1 从数组到链表list解决的是“连续存储”的痛点C 里最基本的数据结构是数组vector 也是连续存储。连续存储意味着访问某个元素非常快vec[i]直接靠地址偏移就能拿到时间O(1)。但它有个很烦人的问题如果要在中间插入或删除一个元素后面的元素全部要往后面挪或者往前面补。数据量一大这个“挪动”的开销会让人头大。list 的思路完全不同。它的元素一个个分散存储每个节点里除了数据本身还带两个指针一个指向前一个节点一个指向后一个节点。你可以把它想象成一栋楼里分散在不同楼层的小仓库每个仓库门口都贴了两张纸条一张写着“上一辆车停在几楼”一张写着“下一辆车停在几楼”。你要在中间塞一个新仓库只需要把相邻两张纸条改一下完全不需要挪动其它仓库。这种“改纸条”的操作在数据结构里就是修改指针指向。无论链表里有1万个节点还是10万个节点只要你能拿到目标位置前后的节点插入和删除都是O(1)时间和链表规模无关。这就是 list 存在的根本价值。1.2 为什么标准库选择双向循环结构而不是单向链表很多初学者会问不是说链表吗为什么我看到的 STL list 都是“带头双向循环链表”而不是很多教材里先讲的单链表这里有几个非常实际的原因。第一如果需要删除“最后一个节点”单向链表会很尴尬。单链表每个节点只存了后继指针如果只有尾指针想删除尾部节点就必须从头遍历找到它的前驱时间是O(n)。而双向链表每个节点都有前驱指针删除任意节点都只要改前后两个指针真正达到O(1)。第二如果需要从后往前遍历或者求--end()这种操作单链表完全做不到。list 的end()返回的迭代器指向哨兵位--end()可以直接得到最后一个节点的迭代器这个语义靠的就是双向结构。第三循环 哨兵头把“空表”处理成了统一的边界。如果不用哨兵空链表时头指针是 nullptr遍历时每走一步都要判断“走了没到空吗”删除节点时还要处理“删的是不是头节点”这种特殊情况。有了哨兵头节点之后空表时_head-_next _head、_head-_prev _head遍历条件统一写成it ! end()就行代码逻辑会简单非常多。这个工程决策不是凭空来的是无数实现反复打磨后的经验。1.3 一张表看清 list 和 vector 的边界不少人选容器时会陷入纠结。我用一张表把几个关键维度列出来方便直观对比操作vectorlistdeque随机访问下标O(1)不支持O(1)头部插入/删除O(n)O(1)O(1)尾部插入/删除O(1) 摊还O(1)O(1)中间插入/删除O(n)已知迭代器时O(1)O(n)缓存友好度非常好较差一般额外内存开销基本无每个节点两个指针分块有少量管理开销注意表里“中间插入”这一行list 这行的限定条件是“已知迭代器”。很多人忽略了这个前提以为 list 在任何中间插入场景都能秒杀 vector但如果你要先查找再插入查找本身是O(n)总时间还是O(n)。list 真正的优势是我手里已经有一个合法的迭代器接下来在这个位置插入或删除才是O(1)。另外list 的节点是分散分配在内存里的遍历的时候 CPU 缓存命中率明显不如 vector。同样遍历一遍数据vector 连续内存一次缓存行能加载好几个元素list 可能要跳好几个内存页。这个差距在我自己本地跑简单测试时非常明显数据量越大越明显。所以“list 一定比 vector 快”是最大的误解它只在自己擅长的场景里快。2. 使用篇站在使用者视角把list的接口摸透2.1 构造函数、遍历和迭代器的基本用法list 的构造方式很标准基本覆盖了常见需求std::listint l1; // 空链表 std::listint l2(10, 5); // 10个5 std::listint l3(l2.begin(), l2.end()); // 迭代器区间构造 std::listint l4(l2); // 拷贝构造遍历最推荐的方式是范围 for因为它的底层其实就是在用迭代器std::listint lt; lt.push_back(3); lt.push_back(1); lt.push_back(4); lt.push_back(1); for (int v : lt) { std::cout v ; } // 输出 3 1 4 1如果你想显式地写迭代器那就是老一套for (std::listint::iterator it lt.begin(); it ! lt.end(); it) { std::cout *it ; }迭代器支持、--、*、-、、!但注意它不支持it 1、it 2这种随机访问操作。这是双向迭代器的基本特征也是后面会讲到“为什么 list 不能用 std::sort”的原因。2.2 增删改查insert/erase 为什么比 vector 好用这里分享一个我自己最常用的场景边遍历边删除。需求很简单把链表里所有偶数删掉。很多新手会写for (auto it lt.begin(); it ! lt.end(); it) { if (*it % 2 0) { lt.erase(it); // 危险擦除后 it 可能指向已释放节点 } }这段代码有隐患。erase 之后it指向的节点已经被 delete 了再往后it就是未定义行为运气好不崩运气不好直接访问野指针。正确做法是接收 erase 的返回值。list 的 erase 会返回“被删除元素的下一个位置的迭代器”所以可以这样写auto it lt.begin(); while (it ! lt.end()) { if (*it % 2 0) { it lt.erase(it); } else { it; } }这个特性非常重要。insert 也一样它返回“新插入节点的迭代器”。比如你找到某个目标值想在它前面插入一个100auto it std::find(lt.begin(), lt.end(), 3); if (it ! lt.end()) { it lt.insert(it, 100); // 在3之前插入100返回值指向新插入的100 }insert 在任意位置插入都是O(1)前提是你已经拿到了位置。vector 在中间插入是O(n)因为后面元素要搬移。这就是 list 最大的使用价值。2.3 容易被忽略的“搬移类”接口splice 和 mergelist 有一类接口在其它容器里很少见到那就是 splice。它的核心作用是“把节点从一个链表搬到另一个链表”这个过程只改指针不拷贝元素时间复杂度是O(1)。看一个例子std::listint A{1, 2, 3}; std::listint B{10, 20, 30}; auto pos A.begin(); pos; // pos 指向 A 中的 2 A.splice(pos, B); // 把 B 的所有节点搬到 A 中插在 2 之前 // A1 10 20 30 2 3 // B空splice 还有两个重载可以指定搬某一个迭代器指向的单个节点也可以指定一个迭代器区间。它特别适合做“多链表任务拆分/合并”这类应用。如果面试里有人问你“怎么把一个 list 中间的一小段 O(1) 移动到另一个 list”答案就是 splice。merge 则是把两个已排序的 list 合并成一个并且合并后依然有序。底层思路类似归并std::listint A{1, 3, 5}; std::listint B{2, 4, 6}; A.merge(B); // A1 2 3 4 5 6 // B空这里有一个坑调用 merge 前两个 list 必须都已经有序否则结果是未定义行为编译器不会帮你检查。这和后面要讲的 sort 问题会关联起来。2.4 清除类接口的隐藏规则remove 与 unique 都是“条件删除”list 里头专门提供了 remove、remove_if、unique 这几个清除接口它们和 vector 的 erase 语义不太一样。remove 是“按值删除所有匹配项”std::listint lt{1, 2, 1, 3, 1}; lt.remove(1); // 结果2 3remove_if 是“按条件删除”配合 lambda 非常灵活lt.remove_if([](int x) { return x % 2 0; });注意这里的 remove/remove_if 是真正把节点删掉、释放内存。连续存储容器里std::remove只是把不满足条件的元素往前覆盖后面还得手动 erase所以“伪删除”和“真删除”是两个完全不同的东西。list 因为天然离散步进直接就能真删除。unique 也容易踩坑。它只会去掉“相邻重复”的元素不是全局去重std::listint lt{1, 1, 2, 2, 3, 1}; lt.unique(); // 结果1 2 3 1看到没有最后那个 1 并没有被去掉因为它在序列里跟前面的 3 相邻和更早的 1 并不相邻。如果你希望全局去重得先 sort 再 unique或者自己写条件判断。3. 模拟实现前的设计课三件套的思考过程使用层面摸熟了现在进入核心部分模拟实现。我建议你不要急着抄代码先把三个设计问题想明白。3.1 为什么要有一个哨兵位头节点如果你自己写过一个不带哨兵的链表一定会被“空表”“只有一个节点”“删除头节点”这些边界情况折磨过。每次操作都要判断if (_head ! nullptr)还得处理_head-next是不是空逻辑很容易漏。带哨兵位的双向循环链表示意图大概是这样的有一个永远存在的节点_head它不存有效数据或者值无意义只起到“边界标尺”的作用。空表时_head-_next _head_head-_prev _head。任何位置插入节点都是在cur的_prev和cur之间挂一个新节点删除节点则是把prev和next直接互连。使用哨兵位后list 的设计会变成“绝对不会空”的状态。begin() 返回_head-_nextend() 返回_head。空表时 begin() end()遍历循环一次都不会进入。这种统一性极大减少了代码里的特殊分支。你去看任何一份成熟的双向链表教学实现几乎都推荐带头节点原因就在这里。3.2 迭代器为什么不能用原生指针糊弄过去vector 的迭代器可以直接用原生指针T*因为它数据在内存里连续存放就天然移动到下一个元素。list 不行list 的节点是散落在堆上的相邻节点之间在内存地址上毫无关联。要是拿ListNodeT*当迭代器写it它只会跑到当前节点地址的下一个内存位置极大概率不是链表下一个节点。所以 list 的迭代器必须是一个“包装原生态指针的类”把operator、operator--、operator*、operator-、operator、operator!全部重载成“链表语义”的操作。这个类内部实际保存的仍然是一个Node*但外面使用者感知到的“像指针”的行为全部由重载函数提供。打个比方原生指针像一个只懂得“顺序地址跳”的直性子。迭代器类则是一个翻译官把翻译成“走到 _node-_next”把--翻译成“回到 _node-_prev”。这也是为什么 list 的迭代器在 STL 分类里是双向迭代器而不是随机访问迭代器。因为它没有提供 n这种跳跃操作你没法一次性跨过 5 个节点——想找到下一个节点只能一步一步走。3.3 用同一份迭代器代码兼容 iterator 和 const_iterator手写 list 的另一个难点是 const 支持。如果listint是 const 对象遍历它时应该只能读不能改。那么迭代器也需要区分普通迭代器和 const 迭代器。一个很傻的办法是复制两份迭代器代码一份的operator*返回T另一份返回const T。代码几乎完全一样维护起来很痛苦。更好的办法是把“引用类型”和“指针类型”做成模板参数templateclass T, class Ref, class Ptr struct ListIterator { // ... };然后用两个 typedef 实例化两种迭代器typedef ListIteratorT, T, T* iterator; typedef ListIteratorT, const T, const T* const_iterator;这样一份类模板就能同时产出普通迭代器和 const 迭代器。这个设计思路在后面数学逻辑上等价于“把变化的部分参数化”也是模板编程的常见套路。初阶阶段能理解到这一层已经非常不错了。4. 手写核心骨架一个最小可用list的长这样设计问题想清楚后代码就顺理成章了。这一节我会给出一个能跑通插入、删除、遍历的最小实现并逐段讲清楚为什么这么写。4.1 节点结构头尾指针加数据templateclass T struct ListNode { ListNodeT* _prev; ListNodeT* _next; T _data; ListNode(const T data T()) : _prev(nullptr) , _next(nullptr) , _data(data) {} };节点本身没什么复杂的就是前驱、后继和数据。构造函数我给了默认参数这样new ListNodeT()时也可以用缺省值构造数据。如果用户存的是自定义类型T()会调用它的默认构造函数这算是一个初阶容易忽略但很实用的细节。4.2 迭代器类的运算符重载让链表节点“看起来像指针”templateclass 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*() 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 it) const { return _node it._node; } bool operator!(const Self it) const { return _node ! it._node; } };关键在于Ref和Ptr两个模板参数。Ref定义了operator*的返回类型普通迭代器返回Tconst 迭代器返回const T。Ptr定义了operator-的返回值普通迭代器返回T*const 迭代器返回const T*。operator-这里有个小知识如果it指向自定义类型使用者写it-成员时编译器会把it-解释为it.operator-()得到一个指针然后再自动用-访问这个指针的成员。如果返回的是Date*那it-_year就会继续沿着Date*的-展开最终读到成员。初学者在这块卡住很正常可以先记住结论operator-返回“原生数据指针”使用者在语法层面会连续吃到两次箭头但代码只需要写一次。前置和后置都写了这是为了保持和内置类型一致的习惯it返回引用it返回旧值。4.3 主类骨架构造、插入、删除、清空与析构templateclass T class List { public: typedef ListNodeT Node; typedef ListIteratorT, T, T* iterator; typedef ListIteratorT, const T, const T* const_iterator; List() { _head new Node; _head-_next _head; _head-_prev _head; } 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); } void push_back(const T x) { insert(end(), x); } void push_front(const T x) { insert(begin(), x); } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); } iterator insert(iterator pos, const T x) { Node* cur pos._node; Node* prev cur-_prev; Node* newNode new Node(x); newNode-_next cur; newNode-_prev prev; prev-_next newNode; 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() { iterator it begin(); while (it ! end()) { it erase(it); } } ~List() { clear(); delete _head; _head nullptr; } private: Node* _head; };这段代码我自己复制到编译器里是能直接跑的主要功能都能用。插入时pos可以是end()这时相当于在最后一个节点后面插入也就是尾插所以push_back可以直接复用insert(end(), x)。同样pop_back用erase(--end())这利用了哨兵节点_prev指向最后一个节点的性质非常优雅。clear里我采用“边 erase 边更新迭代器”的写法。因为 erase 返回下一个节点所以it erase(it)可以安全地遍历到空。清除完后还要记得 delete 哨兵节点这就是析构函数里clear()之后再delete _head的原因。4.4 两个最容易写错的地方erase的返回值和空表边界我一开始写这个模拟实现的时候犯过一个特别典型的错误erase 返回类型写成了 void。后果就是我在写clear时没办法用it erase(it)只能改成erase(it)。虽然能跑但代码特别别扭而且面试官看到之后会追问“为什么这样写旧迭代器是否安全”很容易把自己绕晕。所以建议大家直接按“返回迭代器”的语义来写这既是标准库的行为也是最好用的行为。另一个容易出问题的地方是初始化和空表。构造函数里必须让_head-_next和_head-_prev都指向_head自己。有人会图省事只初始化_next结果第一个push_front时prev还是 nullptr插入逻辑里prev-_next newNode直接对空指针解引用程序瞬间崩溃。这个“自己指向自己”的初始化很容易被漏掉但它恰恰是哨兵位设计的精髓——把空表变成一个已存在的闭合环形。5. 模拟实现之后回看使用中的那些坑把代码手写一遍之后很多使用层面的“怪现象”就有了答案。5.1 迭代器失效list 和 vector 的判断标准完全不同面试里高频出现的问题是“vector 和 list 的迭代器失效有什么区别”。vector 的 insert 如果引发扩容整个容器的内存可能重新分配所有迭代器全部失效即使没有扩容插入位置之后的元素也会整体向后平移所以插入位置之后的迭代器也都失效。vector 的 erase 更明显删除一个元素后后面所有元素前移从被删除位置向后的所有迭代器都悬空。list 因为节点独立插入一个节点只是改几个指针原有节点的地址一个都没变所以插入后已有迭代器全部有效。erase 时只有“指向被删除节点”的那个迭代器失效其它迭代器仍然有效。正因为这个性质上面那种“边遍历边删除”的循环才能成立你只需要及时把失效的迭代器替换成 erase 的返回值即可。用生活类比就是vector 是电影院连排座位中途有人离开后面所有人都要挪位置你手里记着“第 5 排第 6 座”的小纸条可能就指向另一个人了list 是每个人座位之间有松紧绳抽掉一个人松紧绳重新搭上其它座位的人一步没动你的纸条自然仍然准确。5.2 list::sort 和 std::sort 的矛盾归并排序才是答案很多新手第一次写std::sort(lt.begin(), lt.end())会编译失败报错信息很抽象。原因是std::sort要求随机访问迭代器而 list 的迭代器只是双向迭代器无法支持it n这种跳跃行为。那 list 怎么排序它提供了成员函数sort()lt.sort(); // 默认升序 lt.sort(std::greaterint()); // 降序成员函数 sort 一般实现为归并排序。归并排序不需要随机访问只需要不断把相邻区间拿出来比较合并非常契合链表的指针操作。这也是一个“容器自我适配算法”的经典例子不是所有算法都适用于所有容器容器会提供自己的专属版本。sort 之后迭代器是否失效list 的 sort 只是调整节点之间的连接关系每个节点本身还活着。所以你手里已有的迭代器依然指向原来的节点但因为节点被重新排列遍历时经过这个节点的“顺序”发生了变化。这和 vector 的 sort 语义又不一样vector sort 之后迭代器位置不变但位置上的人数据变了。这两种差异也经常被用来考细节理解。5.3 手撕list时常犯的编译错从const迭代器到erase返回值根据我带别人的经验手写 list 最常见的编译错大概集中在这几类第一类是 const 对象无法遍历。如果你只写了iterator begin()没有写const_iterator begin() const那么在 const 对象上调用 begin 就会报“无法将 const 对象转换为非常量引用”。范围 for 在 const 链表上也会罢工。第二类是 erase 返回值类型错。一旦把 erase 返回类型写成 voidit erase(it)直接编译失败。这时候你就被迫写erase(it)虽然能跑但语义不够直观也容易在边界情况翻车。第三类是 operator- 的Ptr参数配错。比如 const 迭代器里operator-返回了T*就会造成 const 对象居然可以修改内容这是权限泄漏会在别的地方埋雷。第四类是内存问题。析构时如果先 delete_head再遍历或者 clear 之后没有置空_next/_prev都会导致访问已释放内存。这类问题编译期不会报错只能靠调试工具或者仔细阅读代码排查。遇到这类问题我的习惯是先看报错指向的行再往 typedef 追一层看看这个迭代器到底是iterator还是const_iterator然后检查返回的是T还是const T。八成问题都能解决。对于报错信息特别长的模板错误我往往会先缩小范围把功能拆成最小可复现的例子逐个验证比盯着几百行报错硬看有效得多。5.4 如果还想继续深入一点可以做这两件事手写一个最小 list 只是第一步。想把它补成一个更像标准库的版本我建议做两件事。第一件事是加入_size成员在 insert、erase 时同步维护让size()变成O(1)的操作。C11 之后标准要求 list 的size()是常数时间底层普遍就是这么实现的。自己加上这个字段后你会感受到“为了满足接口复杂度承诺实现里要多维护一样东西”的工程取舍。第二件事是补齐拷贝构造、赋值运算符和区间构造。模板里涉及深拷贝可以用来检验你对内存管理的掌握。加上后你会发现写一个容器远比想象中琐碎但也远比想象中有成就感。如果再往上走还可以研究reverse_iterator适配器、带分配器参数的标准实现、C11 的移构语义但那些已经超出初阶范围了。先把眼前这个最小版本写扎实后面的路会顺畅很多。实际学习这套内容时我最大的体会是把 vector、list 的模拟实现亲手敲一遍再回来看文档里那些接口感觉完全不一样。以前是背接口不知道接口为什么长这样后来是看到接口就能推断它底层大概率做了什么。list 的哨兵位头节点、迭代器封装、insert/erase 返回值设计这些都不是花架子全是为了让使用者少踩坑、让实现更优雅。如果你也想验证自己是否真正掌握 list建议关掉标准库手写一个最小可用版本再用它跑一遍插入、删除、范围 for 和排序。能跑通这个知识点就真正焊死在脑子里了。
很多人在学习STL容器的时候都会经历这样一段vector写起来很顺手list看起来也没什么难度无非就是链表。但等到你真正尝试“list使用模拟实现”这条路尤其是要把底层结构亲手写一遍的时候才会发现这个所谓的“简单容器”里全是门道。我先说一个自己带新手时的常见场景。有个同学用 list 用得挺熟push_back、push_front、sort 都会调但是问他“list的迭代器为什么不能直接用指针”“为什么insert之后迭代器不失效、vector却会失效”“自己写一个list该从哪里入手”他一下就卡住了。原因很简单会调用接口不等于理解实现。list 的使用和模拟实现是两码事中间隔着一层“设计逻辑”。这篇文章就是针对这个缺口写的。我会把 list 在容器家族里的定位、常用接口背后的语义、模拟实现最关键的三步设计哨兵位头节点、迭代器封装、const迭代器复用、以及模拟之后回头再看使用层面那些坑全部串起来。适合刚学完 C 基础、正准备啃 STL 源码的初学者也适合在准备面试时需要系统梳理 list 知识点的同学。思路清楚了代码自己就能写出来。文章最后我还会分享几个我实际踩过的编译错误和调试经验帮你少走弯路。1. list的定位它其实是“带头双向循环链表”1.1 从数组到链表list解决的是“连续存储”的痛点C 里最基本的数据结构是数组vector 也是连续存储。连续存储意味着访问某个元素非常快vec[i]直接靠地址偏移就能拿到时间O(1)。但它有个很烦人的问题如果要在中间插入或删除一个元素后面的元素全部要往后面挪或者往前面补。数据量一大这个“挪动”的开销会让人头大。list 的思路完全不同。它的元素一个个分散存储每个节点里除了数据本身还带两个指针一个指向前一个节点一个指向后一个节点。你可以把它想象成一栋楼里分散在不同楼层的小仓库每个仓库门口都贴了两张纸条一张写着“上一辆车停在几楼”一张写着“下一辆车停在几楼”。你要在中间塞一个新仓库只需要把相邻两张纸条改一下完全不需要挪动其它仓库。这种“改纸条”的操作在数据结构里就是修改指针指向。无论链表里有1万个节点还是10万个节点只要你能拿到目标位置前后的节点插入和删除都是O(1)时间和链表规模无关。这就是 list 存在的根本价值。1.2 为什么标准库选择双向循环结构而不是单向链表很多初学者会问不是说链表吗为什么我看到的 STL list 都是“带头双向循环链表”而不是很多教材里先讲的单链表这里有几个非常实际的原因。第一如果需要删除“最后一个节点”单向链表会很尴尬。单链表每个节点只存了后继指针如果只有尾指针想删除尾部节点就必须从头遍历找到它的前驱时间是O(n)。而双向链表每个节点都有前驱指针删除任意节点都只要改前后两个指针真正达到O(1)。第二如果需要从后往前遍历或者求--end()这种操作单链表完全做不到。list 的end()返回的迭代器指向哨兵位--end()可以直接得到最后一个节点的迭代器这个语义靠的就是双向结构。第三循环 哨兵头把“空表”处理成了统一的边界。如果不用哨兵空链表时头指针是 nullptr遍历时每走一步都要判断“走了没到空吗”删除节点时还要处理“删的是不是头节点”这种特殊情况。有了哨兵头节点之后空表时_head-_next _head、_head-_prev _head遍历条件统一写成it ! end()就行代码逻辑会简单非常多。这个工程决策不是凭空来的是无数实现反复打磨后的经验。1.3 一张表看清 list 和 vector 的边界不少人选容器时会陷入纠结。我用一张表把几个关键维度列出来方便直观对比操作vectorlistdeque随机访问下标O(1)不支持O(1)头部插入/删除O(n)O(1)O(1)尾部插入/删除O(1) 摊还O(1)O(1)中间插入/删除O(n)已知迭代器时O(1)O(n)缓存友好度非常好较差一般额外内存开销基本无每个节点两个指针分块有少量管理开销注意表里“中间插入”这一行list 这行的限定条件是“已知迭代器”。很多人忽略了这个前提以为 list 在任何中间插入场景都能秒杀 vector但如果你要先查找再插入查找本身是O(n)总时间还是O(n)。list 真正的优势是我手里已经有一个合法的迭代器接下来在这个位置插入或删除才是O(1)。另外list 的节点是分散分配在内存里的遍历的时候 CPU 缓存命中率明显不如 vector。同样遍历一遍数据vector 连续内存一次缓存行能加载好几个元素list 可能要跳好几个内存页。这个差距在我自己本地跑简单测试时非常明显数据量越大越明显。所以“list 一定比 vector 快”是最大的误解它只在自己擅长的场景里快。2. 使用篇站在使用者视角把list的接口摸透2.1 构造函数、遍历和迭代器的基本用法list 的构造方式很标准基本覆盖了常见需求std::listint l1; // 空链表 std::listint l2(10, 5); // 10个5 std::listint l3(l2.begin(), l2.end()); // 迭代器区间构造 std::listint l4(l2); // 拷贝构造遍历最推荐的方式是范围 for因为它的底层其实就是在用迭代器std::listint lt; lt.push_back(3); lt.push_back(1); lt.push_back(4); lt.push_back(1); for (int v : lt) { std::cout v ; } // 输出 3 1 4 1如果你想显式地写迭代器那就是老一套for (std::listint::iterator it lt.begin(); it ! lt.end(); it) { std::cout *it ; }迭代器支持、--、*、-、、!但注意它不支持it 1、it 2这种随机访问操作。这是双向迭代器的基本特征也是后面会讲到“为什么 list 不能用 std::sort”的原因。2.2 增删改查insert/erase 为什么比 vector 好用这里分享一个我自己最常用的场景边遍历边删除。需求很简单把链表里所有偶数删掉。很多新手会写for (auto it lt.begin(); it ! lt.end(); it) { if (*it % 2 0) { lt.erase(it); // 危险擦除后 it 可能指向已释放节点 } }这段代码有隐患。erase 之后it指向的节点已经被 delete 了再往后it就是未定义行为运气好不崩运气不好直接访问野指针。正确做法是接收 erase 的返回值。list 的 erase 会返回“被删除元素的下一个位置的迭代器”所以可以这样写auto it lt.begin(); while (it ! lt.end()) { if (*it % 2 0) { it lt.erase(it); } else { it; } }这个特性非常重要。insert 也一样它返回“新插入节点的迭代器”。比如你找到某个目标值想在它前面插入一个100auto it std::find(lt.begin(), lt.end(), 3); if (it ! lt.end()) { it lt.insert(it, 100); // 在3之前插入100返回值指向新插入的100 }insert 在任意位置插入都是O(1)前提是你已经拿到了位置。vector 在中间插入是O(n)因为后面元素要搬移。这就是 list 最大的使用价值。2.3 容易被忽略的“搬移类”接口splice 和 mergelist 有一类接口在其它容器里很少见到那就是 splice。它的核心作用是“把节点从一个链表搬到另一个链表”这个过程只改指针不拷贝元素时间复杂度是O(1)。看一个例子std::listint A{1, 2, 3}; std::listint B{10, 20, 30}; auto pos A.begin(); pos; // pos 指向 A 中的 2 A.splice(pos, B); // 把 B 的所有节点搬到 A 中插在 2 之前 // A1 10 20 30 2 3 // B空splice 还有两个重载可以指定搬某一个迭代器指向的单个节点也可以指定一个迭代器区间。它特别适合做“多链表任务拆分/合并”这类应用。如果面试里有人问你“怎么把一个 list 中间的一小段 O(1) 移动到另一个 list”答案就是 splice。merge 则是把两个已排序的 list 合并成一个并且合并后依然有序。底层思路类似归并std::listint A{1, 3, 5}; std::listint B{2, 4, 6}; A.merge(B); // A1 2 3 4 5 6 // B空这里有一个坑调用 merge 前两个 list 必须都已经有序否则结果是未定义行为编译器不会帮你检查。这和后面要讲的 sort 问题会关联起来。2.4 清除类接口的隐藏规则remove 与 unique 都是“条件删除”list 里头专门提供了 remove、remove_if、unique 这几个清除接口它们和 vector 的 erase 语义不太一样。remove 是“按值删除所有匹配项”std::listint lt{1, 2, 1, 3, 1}; lt.remove(1); // 结果2 3remove_if 是“按条件删除”配合 lambda 非常灵活lt.remove_if([](int x) { return x % 2 0; });注意这里的 remove/remove_if 是真正把节点删掉、释放内存。连续存储容器里std::remove只是把不满足条件的元素往前覆盖后面还得手动 erase所以“伪删除”和“真删除”是两个完全不同的东西。list 因为天然离散步进直接就能真删除。unique 也容易踩坑。它只会去掉“相邻重复”的元素不是全局去重std::listint lt{1, 1, 2, 2, 3, 1}; lt.unique(); // 结果1 2 3 1看到没有最后那个 1 并没有被去掉因为它在序列里跟前面的 3 相邻和更早的 1 并不相邻。如果你希望全局去重得先 sort 再 unique或者自己写条件判断。3. 模拟实现前的设计课三件套的思考过程使用层面摸熟了现在进入核心部分模拟实现。我建议你不要急着抄代码先把三个设计问题想明白。3.1 为什么要有一个哨兵位头节点如果你自己写过一个不带哨兵的链表一定会被“空表”“只有一个节点”“删除头节点”这些边界情况折磨过。每次操作都要判断if (_head ! nullptr)还得处理_head-next是不是空逻辑很容易漏。带哨兵位的双向循环链表示意图大概是这样的有一个永远存在的节点_head它不存有效数据或者值无意义只起到“边界标尺”的作用。空表时_head-_next _head_head-_prev _head。任何位置插入节点都是在cur的_prev和cur之间挂一个新节点删除节点则是把prev和next直接互连。使用哨兵位后list 的设计会变成“绝对不会空”的状态。begin() 返回_head-_nextend() 返回_head。空表时 begin() end()遍历循环一次都不会进入。这种统一性极大减少了代码里的特殊分支。你去看任何一份成熟的双向链表教学实现几乎都推荐带头节点原因就在这里。3.2 迭代器为什么不能用原生指针糊弄过去vector 的迭代器可以直接用原生指针T*因为它数据在内存里连续存放就天然移动到下一个元素。list 不行list 的节点是散落在堆上的相邻节点之间在内存地址上毫无关联。要是拿ListNodeT*当迭代器写it它只会跑到当前节点地址的下一个内存位置极大概率不是链表下一个节点。所以 list 的迭代器必须是一个“包装原生态指针的类”把operator、operator--、operator*、operator-、operator、operator!全部重载成“链表语义”的操作。这个类内部实际保存的仍然是一个Node*但外面使用者感知到的“像指针”的行为全部由重载函数提供。打个比方原生指针像一个只懂得“顺序地址跳”的直性子。迭代器类则是一个翻译官把翻译成“走到 _node-_next”把--翻译成“回到 _node-_prev”。这也是为什么 list 的迭代器在 STL 分类里是双向迭代器而不是随机访问迭代器。因为它没有提供 n这种跳跃操作你没法一次性跨过 5 个节点——想找到下一个节点只能一步一步走。3.3 用同一份迭代器代码兼容 iterator 和 const_iterator手写 list 的另一个难点是 const 支持。如果listint是 const 对象遍历它时应该只能读不能改。那么迭代器也需要区分普通迭代器和 const 迭代器。一个很傻的办法是复制两份迭代器代码一份的operator*返回T另一份返回const T。代码几乎完全一样维护起来很痛苦。更好的办法是把“引用类型”和“指针类型”做成模板参数templateclass T, class Ref, class Ptr struct ListIterator { // ... };然后用两个 typedef 实例化两种迭代器typedef ListIteratorT, T, T* iterator; typedef ListIteratorT, const T, const T* const_iterator;这样一份类模板就能同时产出普通迭代器和 const 迭代器。这个设计思路在后面数学逻辑上等价于“把变化的部分参数化”也是模板编程的常见套路。初阶阶段能理解到这一层已经非常不错了。4. 手写核心骨架一个最小可用list的长这样设计问题想清楚后代码就顺理成章了。这一节我会给出一个能跑通插入、删除、遍历的最小实现并逐段讲清楚为什么这么写。4.1 节点结构头尾指针加数据templateclass T struct ListNode { ListNodeT* _prev; ListNodeT* _next; T _data; ListNode(const T data T()) : _prev(nullptr) , _next(nullptr) , _data(data) {} };节点本身没什么复杂的就是前驱、后继和数据。构造函数我给了默认参数这样new ListNodeT()时也可以用缺省值构造数据。如果用户存的是自定义类型T()会调用它的默认构造函数这算是一个初阶容易忽略但很实用的细节。4.2 迭代器类的运算符重载让链表节点“看起来像指针”templateclass 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*() 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 it) const { return _node it._node; } bool operator!(const Self it) const { return _node ! it._node; } };关键在于Ref和Ptr两个模板参数。Ref定义了operator*的返回类型普通迭代器返回Tconst 迭代器返回const T。Ptr定义了operator-的返回值普通迭代器返回T*const 迭代器返回const T*。operator-这里有个小知识如果it指向自定义类型使用者写it-成员时编译器会把it-解释为it.operator-()得到一个指针然后再自动用-访问这个指针的成员。如果返回的是Date*那it-_year就会继续沿着Date*的-展开最终读到成员。初学者在这块卡住很正常可以先记住结论operator-返回“原生数据指针”使用者在语法层面会连续吃到两次箭头但代码只需要写一次。前置和后置都写了这是为了保持和内置类型一致的习惯it返回引用it返回旧值。4.3 主类骨架构造、插入、删除、清空与析构templateclass T class List { public: typedef ListNodeT Node; typedef ListIteratorT, T, T* iterator; typedef ListIteratorT, const T, const T* const_iterator; List() { _head new Node; _head-_next _head; _head-_prev _head; } 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); } void push_back(const T x) { insert(end(), x); } void push_front(const T x) { insert(begin(), x); } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); } iterator insert(iterator pos, const T x) { Node* cur pos._node; Node* prev cur-_prev; Node* newNode new Node(x); newNode-_next cur; newNode-_prev prev; prev-_next newNode; 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() { iterator it begin(); while (it ! end()) { it erase(it); } } ~List() { clear(); delete _head; _head nullptr; } private: Node* _head; };这段代码我自己复制到编译器里是能直接跑的主要功能都能用。插入时pos可以是end()这时相当于在最后一个节点后面插入也就是尾插所以push_back可以直接复用insert(end(), x)。同样pop_back用erase(--end())这利用了哨兵节点_prev指向最后一个节点的性质非常优雅。clear里我采用“边 erase 边更新迭代器”的写法。因为 erase 返回下一个节点所以it erase(it)可以安全地遍历到空。清除完后还要记得 delete 哨兵节点这就是析构函数里clear()之后再delete _head的原因。4.4 两个最容易写错的地方erase的返回值和空表边界我一开始写这个模拟实现的时候犯过一个特别典型的错误erase 返回类型写成了 void。后果就是我在写clear时没办法用it erase(it)只能改成erase(it)。虽然能跑但代码特别别扭而且面试官看到之后会追问“为什么这样写旧迭代器是否安全”很容易把自己绕晕。所以建议大家直接按“返回迭代器”的语义来写这既是标准库的行为也是最好用的行为。另一个容易出问题的地方是初始化和空表。构造函数里必须让_head-_next和_head-_prev都指向_head自己。有人会图省事只初始化_next结果第一个push_front时prev还是 nullptr插入逻辑里prev-_next newNode直接对空指针解引用程序瞬间崩溃。这个“自己指向自己”的初始化很容易被漏掉但它恰恰是哨兵位设计的精髓——把空表变成一个已存在的闭合环形。5. 模拟实现之后回看使用中的那些坑把代码手写一遍之后很多使用层面的“怪现象”就有了答案。5.1 迭代器失效list 和 vector 的判断标准完全不同面试里高频出现的问题是“vector 和 list 的迭代器失效有什么区别”。vector 的 insert 如果引发扩容整个容器的内存可能重新分配所有迭代器全部失效即使没有扩容插入位置之后的元素也会整体向后平移所以插入位置之后的迭代器也都失效。vector 的 erase 更明显删除一个元素后后面所有元素前移从被删除位置向后的所有迭代器都悬空。list 因为节点独立插入一个节点只是改几个指针原有节点的地址一个都没变所以插入后已有迭代器全部有效。erase 时只有“指向被删除节点”的那个迭代器失效其它迭代器仍然有效。正因为这个性质上面那种“边遍历边删除”的循环才能成立你只需要及时把失效的迭代器替换成 erase 的返回值即可。用生活类比就是vector 是电影院连排座位中途有人离开后面所有人都要挪位置你手里记着“第 5 排第 6 座”的小纸条可能就指向另一个人了list 是每个人座位之间有松紧绳抽掉一个人松紧绳重新搭上其它座位的人一步没动你的纸条自然仍然准确。5.2 list::sort 和 std::sort 的矛盾归并排序才是答案很多新手第一次写std::sort(lt.begin(), lt.end())会编译失败报错信息很抽象。原因是std::sort要求随机访问迭代器而 list 的迭代器只是双向迭代器无法支持it n这种跳跃行为。那 list 怎么排序它提供了成员函数sort()lt.sort(); // 默认升序 lt.sort(std::greaterint()); // 降序成员函数 sort 一般实现为归并排序。归并排序不需要随机访问只需要不断把相邻区间拿出来比较合并非常契合链表的指针操作。这也是一个“容器自我适配算法”的经典例子不是所有算法都适用于所有容器容器会提供自己的专属版本。sort 之后迭代器是否失效list 的 sort 只是调整节点之间的连接关系每个节点本身还活着。所以你手里已有的迭代器依然指向原来的节点但因为节点被重新排列遍历时经过这个节点的“顺序”发生了变化。这和 vector 的 sort 语义又不一样vector sort 之后迭代器位置不变但位置上的人数据变了。这两种差异也经常被用来考细节理解。5.3 手撕list时常犯的编译错从const迭代器到erase返回值根据我带别人的经验手写 list 最常见的编译错大概集中在这几类第一类是 const 对象无法遍历。如果你只写了iterator begin()没有写const_iterator begin() const那么在 const 对象上调用 begin 就会报“无法将 const 对象转换为非常量引用”。范围 for 在 const 链表上也会罢工。第二类是 erase 返回值类型错。一旦把 erase 返回类型写成 voidit erase(it)直接编译失败。这时候你就被迫写erase(it)虽然能跑但语义不够直观也容易在边界情况翻车。第三类是 operator- 的Ptr参数配错。比如 const 迭代器里operator-返回了T*就会造成 const 对象居然可以修改内容这是权限泄漏会在别的地方埋雷。第四类是内存问题。析构时如果先 delete_head再遍历或者 clear 之后没有置空_next/_prev都会导致访问已释放内存。这类问题编译期不会报错只能靠调试工具或者仔细阅读代码排查。遇到这类问题我的习惯是先看报错指向的行再往 typedef 追一层看看这个迭代器到底是iterator还是const_iterator然后检查返回的是T还是const T。八成问题都能解决。对于报错信息特别长的模板错误我往往会先缩小范围把功能拆成最小可复现的例子逐个验证比盯着几百行报错硬看有效得多。5.4 如果还想继续深入一点可以做这两件事手写一个最小 list 只是第一步。想把它补成一个更像标准库的版本我建议做两件事。第一件事是加入_size成员在 insert、erase 时同步维护让size()变成O(1)的操作。C11 之后标准要求 list 的size()是常数时间底层普遍就是这么实现的。自己加上这个字段后你会感受到“为了满足接口复杂度承诺实现里要多维护一样东西”的工程取舍。第二件事是补齐拷贝构造、赋值运算符和区间构造。模板里涉及深拷贝可以用来检验你对内存管理的掌握。加上后你会发现写一个容器远比想象中琐碎但也远比想象中有成就感。如果再往上走还可以研究reverse_iterator适配器、带分配器参数的标准实现、C11 的移构语义但那些已经超出初阶范围了。先把眼前这个最小版本写扎实后面的路会顺畅很多。实际学习这套内容时我最大的体会是把 vector、list 的模拟实现亲手敲一遍再回来看文档里那些接口感觉完全不一样。以前是背接口不知道接口为什么长这样后来是看到接口就能推断它底层大概率做了什么。list 的哨兵位头节点、迭代器封装、insert/erase 返回值设计这些都不是花架子全是为了让使用者少踩坑、让实现更优雅。如果你也想验证自己是否真正掌握 list建议关掉标准库手写一个最小可用版本再用它跑一遍插入、删除、范围 for 和排序。能跑通这个知识点就真正焊死在脑子里了。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
