如果你在 C 项目里用 vector 用得顺手头一回来碰 list大概率会冒出一堆问号为什么 list 的 insert 不引起重分配为什么它没有 operator[]为什么迭代器不支持加减运算这篇是 C list 专题的第二篇重点做两件事一是把 list 的接口挨个掰开讲清楚二是带着你从零手写一个满足基本功能的 list 容器。写这个专题的起因是我在实际项目中遇到过好几次“该用 list 还是 vector”的争论很多人对 list 的理解停留在“链表嘛插入删除快”这种口头层面真问到接口细节、迭代器失效规则、底层结构设计时又含糊了。所以这篇文章我想把 list 的常见接口、边界行为、内部结构一次说透再给一份可以直接拿来学习的实现代码。适合正在学 C STL 的人、准备面试的人以及写代码时总在容器之间纠结的工程向同学。1. 接口全景list 能做什么该在什么时候用1.1 list 的“身份证”双向链表结构带来的能力边界list 在标准库里的全称是 std::list底层是双向链表。这里的“双向”意味着每个节点除了存数据还有两个指针一个指向前一个节点一个指向后一个节点。和 vector 那种连续内存的数组结构比list 的能力边界非常清晰。先看它擅长的事。中间位置的插入和删除是 O(1) 复杂度这是在你已经持有迭代器的情况下成立的。比如你手里有个迭代器指向链表的第三个元素你想在它前面插入一个新元素list 只需要改动附近几个节点的指针数据本身完全不用搬动。vector 就不一样了中间插入意味着要把插入位置之后的所有元素整体后移最坏情况 O(n)如果扩容还要整体拷贝到新内存。再看它不擅长的事。list 没有随机访问能力你想取第 n 个元素只能从头部或者尾部一个个遍历过去时间复杂度 O(n)。所以标准库干脆不给你提供 operator[]。list 也不擅长查找你把整个链表翻一遍才能确认某个值在不在这跟 vector 的二分查找配合排序完全没法比。还有一个很多人容易忽略的点list 的每个节点是单独分配内存的节点之间在物理内存上大概率不连续。这就导致一个后果遍历链表的时候CPU 缓存命中率远低于遍历 vector。因为 vector 的元素在内存里是挨着的访问完第一个元素第二个元素大概率已经加载进缓存了list 的节点东一个西一个访问完一个节点下一个节点很可能不在缓存里需要重新到内存里取。实际工程里即使 list 在插入删除上有理论优势遇到频繁遍历的场景性能往往还不如 vector。所以结论很直接如果数据体量不大、也不需要频繁在中间插入删除优先考虑 vector如果确实需要在任意位置高频插入删除并且持有迭代器作为操作入口才考虑 list。1.2 常用接口速查与使用要点list 的接口分几类构造、容量、元素访问、修改、特殊操作。我把工程里最常用的整理成一张表后面逐个挑重点讲。分类接口作用复杂度构造list()构造空链表O(1)构造list(n, val)构造含 n 个 val 的链表O(n)构造list(begin, end)用迭代器区间构造O(n)容量empty()是否为空O(1)容量size()元素个数O(1)C11 起元素访问front() / back()访问首元素 / 尾元素O(1)修改push_front / pop_front头插 / 头删O(1)修改push_back / pop_back尾插 / 尾删O(1)修改insert(pos, val)在 pos 之前插入 valO(1)修改erase(pos)删除 pos 指向的元素O(1)特殊splice(pos, other)把另一个 list 接进来O(1)特殊merge(other)合并两个有序链表O(nm)特殊unique()删除连续重复元素O(n)特殊sort()链表排序O(n log n)特殊remove(val)删除所有等于 val 的元素O(n)先说一个高频考点list 的 size() 在 C98 时代可能是 O(n) 的因为标准没有强制要求常数时间很多早期实现靠遍历计数。但 C11 之后标准明确规定 size() 必须是 O(1)所以现代编译器里你可以放心使用 size()不用担心遍历整个链表数元素。再看元素访问。list 只有 front() 和 back()没有 at() 也没有 operator[]。而且 front() 和 back() 在空链表上调用是未定义行为别指望它给你抛异常。实际写代码时要先判断 empty()哪怕觉得“这地方肯定非空”也建议留着防御逻辑尤其是链表的元素是从外部传入的时候。insert 接口有个容易混淆的点。vector 的 insert 会导致迭代器失效list 的 insert 接在指定位置之前原有的所有迭代器都保持有效不会失效。这一点在面试中经常作为 vector 和 list 的对比点出现。原因不难理解list insert 只是改了指针指向不搬动任何已存在的节点节点的地址没有变化指向它们的迭代器自然仍然有效。erase 接口则需要留意。list 的 erase 会使“被删除节点”的迭代器失效但其他迭代器不受影响。C11 之前 erase 返回 void你删除元素后想继续遍历得先把要删除的迭代器保存到临时变量再推进。C11 之后 erase 返回被删除元素的下一个迭代器遍历删除的写法简化了不少。splice 是 list 独有的重要接口也是很多人第一次见到时觉得神奇的接口。它能把一个 list 中的节点直接“搬”到另一个 list注意是搬而不是复制。搬完之后源 list 的对应节点就没了但节点本身没有被销毁只是换了归属。这个操作在需要把多个链表拼接到一起的场景特别有用比如实现任务队列时把一批待处理任务整体挂到主队列末尾。merge 用于合并两个已排序的 list合并后目标 list 保持有序。这里要特别提醒源 list 的元素在 merge 之后会被清空这和直觉不太一样。很多人第一次用 merge发现另一个 list 变空了以为是 bug其实就是标准语义merge 是转移合并不是复制合并。unique 用来删除连续的重复元素。注意是“连续”如果相同的元素分散在不同位置unique 不会管它们。所以通常先 sort 再 unique才能实现真正去重。remove 则不同它是把链表中所有等于指定值的元素都删掉不需要元素连续也不需要链表有序。2. 看不见的内部结构哨兵节点和迭代器2.1 哨兵头节点让所有边界条件消失的设计要理解 list 的实现先要看懂它的节点结构。标准库里的 list 节点不是光秃秃的一个数据加两个指针通常会有一个哨兵头节点sentinel node。这个头节点不存实际数据它的 next 指向链表第一个元素prev 指向链表最后一个元素。链表为空时头节点的 next 和 prev 都指向它自己。哨兵节点的意义在于消除边界条件。假如没有哨兵空链表和只有一个元素的链表需要单独处理头部插入和尾部插入也要分别判断代码里到处是 if (head nullptr) 这种分支。有了哨兵节点所有操作都统一了。你想想 erase 的逻辑。删除一个节点需要四个步骤找到它的前驱节点找到它的后继节点把前驱的 next 指向后继把后继的 prev 指向前驱。如果链表只有一个节点这个节点的前驱和后继都是谁呢如果没有哨兵这里就得特殊处理前驱和后继都不存在。有了哨兵哪怕链表里只有一个节点它的前驱和后继也都是哨兵节点删除操作走同一套逻辑就能完成。begin() 返回指向第一个实际元素的迭代器就是 head_-nextend() 返回指向哨兵节点的迭代器。当一个循环遍历到这个“空的”哨兵时说明链表到头了。这就是为什么下面这种遍历写法能正常工作for (auto it lst.begin(); it ! lst.end(); it) { // 处理 it 指向的元素 }end() 返回的其实是一个指向“哨兵”的迭代器它不代表任何实际元素只代表链表的结束位置。如果你自己手写 list这个设计值得重点学习。初学者经常在 insert、erase 里写出一堆状态判断就是因为少了哨兵节点。2.2 迭代器链表访问的核心抽象迭代器是 list 设计的第二个关键点。你可以把迭代器理解成“指针的泛化”。对 vector 来说迭代器差不多就是普通的 T* 指针因为 vector 的元素连续存储指针加减就能访问任意位置的元素。但 list 不行元素不连续T* 这种原生指针没法完成“指向下一个节点”的操作因为谁也不知道下一个节点在内存的哪个角落。所以 list 的迭代器必须是自己定义的类类型内部封装一个 Node*对外提供类似指针的操作接口。常见操作包括operator让内部的 Node* 指向 next前移operator--让内部的 Node* 指向 prev后退operator*返回当前节点的数据引用operator-返回当前节点的数据指针operator / operator!比较两个迭代器是否指向同一个节点这些操作封装好之后迭代器的使用体验和原生指针非常接近。算法库里那些针对迭代器写的算法find、count、for_each 等也能直接作用于 list。迭代器按能力分类list 的迭代器属于双向迭代器Bidirectional Iterator支持 和 --但不支持 n、-n、[] 这类随机访问操作。标准库里的 sort 算法要求随机访问迭代器所以 list 的 sort 算法和 sort 函数的 sort 是两个不同的东西一个成员函数、一个算法。这边也解释了一个面试常见问题为什么 list 有单独的成员函数 sort因为 std::sort 要求随机访问迭代器双向迭代器玩不了必须提供自己的排序实现。2.3 迭代器失效规则与实际影响迭代器失效是个经常踩坑的话题。vector 里插入删除元素后所有迭代器都可能失效因为底层可能整体搬了家。list 里规则要温和得多。插入操作insert、push_front、push_back、splice不会使任何现有的迭代器失效。删除操作erase、pop_front、pop_back、remove、unique只会使被删除元素的迭代器失效其他迭代器保持有效。这个规则的意义在于你可以放心地在遍历 list 的过程中删除元素。最稳妥的写法是利用 C11 之后 erase 返回后继迭代器的特性for (auto it lst.begin(); it ! lst.end(); ) { if (需要删除(*it)) { it lst.erase(it); // erase 返回下一个有效迭代器 } else { it; } }在 C11 之前erase 不返回迭代器很多人会这样写for (auto it lst.begin(); it ! lst.end(); ) { if (需要删除(*it)) { lst.erase(it); // 先用后加it 先拷贝并递增 } else { it; } }这个写法利用了后置 先自增再返回旧值的特性让 erase 删除的是旧迭代器指向的节点而 it 已经安全地指向了下一个节点。两种写法都有效但前者更直观、更不容易出错。我个人推荐在新代码里统一用 C11 的写法。3. 手写 list从零实现一个可用的容器3.1 节点设计与类骨架光看不练假把式。理解了上面的结构接下来我用一个简化但功能完整的 list 实现来验证这些设计。先定义节点结构。template typename T struct ListNode { T data; ListNode* prev; ListNode* next; explicit ListNode(const T val T()) : data(val), prev(nullptr), next(nullptr) {} };这里用 struct 是因为节点内部字段需要被 list 类和迭代器类直接访问用 struct 省去一堆 friend 声明。然后定义 list 类的骨架。为了代码清晰我没有把全部接口都写进去但核心接口已经覆盖了绝大部分使用场景。template typename T class list { public: // 类型别名便于外部使用 using value_type T; using size_type size_t; using reference T; using const_reference const T; // 迭代器这里先用一个占位下面再实现 class iterator; class const_iterator; list(); list(size_type n, const T val); template typename InputIt list(InputIt first, InputIt last); list(const list other); list operator(const list other); ~list(); iterator begin(); iterator end(); const_iterator begin() const; const_iterator end() const; bool empty() const; size_type size() const; reference front(); reference back(); const_reference front() const; const_reference back() const; void push_front(const T val); void pop_front(); void push_back(const T val); void pop_back(); iterator insert(iterator pos, const T val); iterator erase(iterator pos); iterator erase(iterator first, iterator last); void clear(); void splice(iterator pos, list other); private: using Node ListNodeT; Node* head_; // 哨兵节点 size_type size_; // 元素个数 };构造函数里的哨兵节点初始化很关键。创建空链表时要让 head_ 的 next 和 prev 都指向自己这样链表就处于“空”状态begin() 和 end() 都指向 head_。template typename T listT::list() : head_(new Node()), size_(0) { head_-next head_; head_-prev head_; }注意哨兵节点虽然也是 Node 类型但它并不存放实际数据。这个节点一直存活到 list 被析构起到维护链表边界的作用。3.2 迭代器实现封装指针让算法统一迭代器的实现是我认为整个手写 list 中最精华的部分。它把“链表节点怎么走”的细节全部藏起来对上层提供统一的指针式语法。template typename T class listT::iterator { public: // 让算法库识别迭代器类型 using iterator_category std::bidirectional_iterator_tag; using value_type T; using difference_type std::ptrdiff_t; using pointer T*; using reference T; iterator() : node_(nullptr) {} explicit iterator(Node* node) : node_(node) {} reference operator*() const { return node_-data; } pointer operator-() const { return node_-data; } iterator operator() { node_ node_-next; return *this; } iterator operator(int) { iterator tmp *this; node_ node_-next; return tmp; } iterator operator--() { node_ node_-prev; return *this; } iterator operator--(int) { iterator tmp *this; node_ node_-prev; return tmp; } bool operator(const iterator other) const { return node_ other.node_; } bool operator!(const iterator other) const { return node_ ! other.node_; } // 迭代器访问底层节点list 内部用 Node* node() const { return node_; } private: Node* node_; };这里有几个细节值得展开说。首先operator* 返回的是 node_-data 的引用不是拷贝所以你可以通过 *it 直接修改链表中的元素。其次前置 返回迭代器自身的引用效率比后置 返回临时对象更高这也是为什么循环里优先写 it 而不是 it。const_iterator 和 iterator 的实现结构基本一致区别在于 operator* 和 operator- 返回 const 引用和 const 指针。为了简化代码我这里没有完整写出来但原理完全相同。这里插一句题外话标准库的实现里 iterator 可以隐式转换为 const_iterator这样当你把 list 传给一个接受 const list 的函数时函数里用 begin() 拿到的迭代器能正常赋值给 const_iterator。自己实现时如果有需要可以在 const_iterator 里加一个接受 iterator 的构造函数。3.3 构造与内存管理拷贝控制是重头戏list 的默认构造容易但涉及到拷贝构造、赋值、析构时很多新手会翻车。原因是链表的内存是分散的你必须逐个节点地复制过去不能像 vector 那样 memcpy。析构函数的核心是逐个销毁节点注意哨兵节点最后也得 delete。template typename T listT::~list() { clear(); delete head_; } template typename T void listT::clear() { Node* cur head_-next; while (cur ! head_) { Node* nxt cur-next; delete cur; cur nxt; } head_-next head_; head_-prev head_; size_ 0; }clear 的循环条件写得是 cur ! head_因为哨兵节点是链表遍历的终点。循环里先保存 cur-next再 delete cur这个顺序不能反否则你删了当前节点就找不到下一个节点的地址了。拷贝构造需要遍历原链表逐个把元素用 insert 方式链到新链表里。template typename T listT::list(const list other) : head_(new Node()), size_(0) { head_-next head_; head_-prev head_; for (const auto val : other) { push_back(val); } } template typename T listT listT::operator(const list other) { if (this ! other) { list tmp(other); // 拷贝构造临时对象 swap(tmp); // 交换内部状态 } return *this; }赋值运算符我这里用到了 copy-and-swap 惯用法先构造一个临时链表再把临时链表和当前链表的内容交换。这样写的好处是如果拷贝过程抛异常当前链表的内容不会被破坏异常安全性能得到保证。当然要真正支持 swap需要在类里加一个 swap 成员函数或友元函数这里为了篇幅没有完整展开但思路是对的。3.4 插入、删除与元素访问链表操作的核心逻辑push_back 和 push_front 是最简单的插入操作本质都是在边界位置插入一个新节点调整四个指针。template typename T void listT::push_back(const T val) { Node* new_node new Node(val); Node* tail head_-prev; tail-next new_node; new_node-prev tail; new_node-next head_; head_-prev new_node; size_; } template typename T void listT::push_front(const T val) { Node* new_node new Node(val); Node* first head_-next; head_-next new_node; new_node-prev head_; new_node-next first; first-prev new_node; size_; }push_back 的步骤是找到当前尾节点head_-prev让尾节点的 next 指向新节点新节点的 prev 指向尾节点新节点的 next 指向哨兵最后让哨兵的 prev 指向新节点。四个指针全部更新完新节点就正式挂到了链表尾部。pop_back 和 pop_front 是反向操作删除一个节点后要保证哨兵的 prev 或 next 正确指向下一个节点。template typename T void listT::pop_back() { Node* tail head_-prev; Node* new_tail tail-prev; new_tail-next head_; head_-prev new_tail; delete tail; --size_; }insert 是给一个位置迭代器在它前面插入新节点。这就是哨兵节点发挥作用的地方。无论 pos 是指向开头、末尾还是中间逻辑都是同一套拿到 pos 的前驱节点把新节点插在前驱和 pos 之间。template typename T typename listT::iterator listT::insert(iterator pos, const T val) { Node* cur pos.node(); Node* pre cur-prev; Node* new_node new Node(val); pre-next new_node; new_node-prev pre; new_node-next cur; cur-prev new_node; size_; return iterator(new_node); }来看这个逻辑有多统一。如果 pos 指向哨兵节点也就是 end()那么 pre 就是真正的尾节点新节点插到尾部效果等价于 push_back。如果 pos 指向第一个实际节点begin()那么 pre 就是哨兵新节点插到头部效果等价于 push_front。不管怎么插代码都不用写分支。erase 的逻辑同样统一。删除一个节点把前驱的 next 指向后继把后继的 prev 指向前驱然后 delete 节点。template typename T typename listT::iterator listT::erase(iterator pos) { Node* cur pos.node(); Node* pre cur-prev; Node* nxt cur-next; pre-next nxt; nxt-prev pre; delete cur; --size_; return iterator(nxt); }这里同样可以体会哨兵节点带来的便利。如果删除的是尾部元素nxt 就是哨兵不会出现空指针问题。如果删除的是头部元素pre 就是哨兵也不会有空指针问题。基于 insert 和 erasepush_back、push_front、pop_back、pop_front 其实都可以用统一的接口实现。实际标准库的实现里这些接口最终都会落到统一的插入删除逻辑上。3.5 独特算法接口splice、merge、unique 怎么实现这几个接口是 list 独有的vector 想都别想。splice 的实现有点反直觉它不用 new 和 delete而是直接把一个链表上的节点“摘下来”挂到另一个链表上。template typename T void listT::splice(iterator pos, list other) { if (other.empty()) return; Node* cur pos.node(); Node* pre cur-prev; Node* first other.head_-next; // 源链表第一个元素 Node* last other.head_-prev; // 源链表最后一个元素 // 把 [first, last] 整个区间摘下来 other.head_-next other.head_; other.head_-prev other.head_; // 把区间挂到当前链表 pre-next first; first-prev pre; last-next cur; cur-prev last; size_ other.size_; other.size_ 0; }这个操作的核心是只改指针不创建新节点。源链表搬走之后变空了其 size_ 归零当前链表的 size_ 相应增加。这种“搬节点”的语义在标准库里就是 splice 的默认行为面试里经常考到对源链表状态的影响。merge 合并两个有序链表。常见实现方式是依次比较两个链表头部的元素把较小的那个从源链表“拆”下来挂到目标链表中。由于两个链表本身有序这个比较过程可以做到线性复杂度。template typename T void listT::merge(list other) { if (this other) return; iterator it_this begin(); iterator it_other other.begin(); while (it_this ! end() it_other ! other.end()) { if (*it_other *it_this) { // 把 other 的当前节点搬到 it_this 前面 iterator next_other it_other; next_other; Node* move_node it_other.node(); Node* pos_node it_this.node(); Node* pre pos_node-prev; // 先从 other 摘除 move_node-prev-next move_node-next; move_node-next-prev move_node-prev; // 再挂到 this 里 pre-next move_node; move_node-prev pre; move_node-next pos_node; pos_node-prev move_node; it_other next_other; size_; --other.size_; } else { it_this; } } // 如果 other 还有剩余都是较大元素整体拼到尾部 if (!other.empty()) { splice(end(), other); } }merge 的实现细节较多核心还是指针的摘除和挂接。这个实现里我用了迭代器操作稍微显得繁琐一点但便于理解语义。标准库的实际实现更底层思路是一样的。unique 的实现就是在链表中遍历一遍把相邻重复的元素删除掉。因为链表的节点之间通过指针相连删除之后需要继续比较新的相邻关系所以用迭代器循环最方便。4. 常见坑和排查心得4.1 迭代器失效的典型场景实际使用 list 时迭代器失效问题比 vector 温和很多但它不是没有。最常见的坑出现在 erase 和 splice 的混用上。先看 erase。如果删除一个元素后还继续使用指向它的迭代器程序可能会出现未定义行为。具体表现可能是随机崩溃、数据错乱也可能运气好没报错。问题在于节点被 delete 之后那块内存可能已经被回收或者被其他对象占用你再访问它里面存的指针鬼才知道会发生什么。我在实际代码 review 中见过一个典型错误。有人想把链表里所有的偶数值都删掉他写出了这样一段逻辑for (auto it lst.begin(); it ! lst.end(); ) { if (*it % 2 0) { lst.erase(it); // it 已经失效了 it; // 这步是未定义行为 } else { it; } }这段代码第一眼看上去没什么问题但 erase 之后 it 指向的节点已经被释放此时再执行 it相当于访问了已释放的内存。表面上可能不崩溃但这是纯粹靠运气。正确的做法是直接用 erase 的返回值更新 it或者用前面提到的 it 技巧。splice 的坑则更隐蔽。splice 把一个节点从源链表搬到目标链表之后源链表中原本指向这个节点的迭代器并没有失效它还指向同一个节点。区别在于这个节点现在已经属于目标链表了你通过源链表的这个迭代器操作节点修改的不再是源链表的内容。这一点在逻辑上很容易被忽略调试的时候经常让人一头雾水。4.2 list 与 vector 的性能对比数据不会说谎光说理论没有感觉我写过一个简单的性能测试分别用 list 和 vector 做相同的操作结果比较有意思。插入测试在链表头部连续插入 100 万个元素。list 的 push_front 是 O(1)vector 的 insert(begin()) 是 O(n)因为每次插入后面全部元素都要移动。这个测试 list 完胜差别是数量级的。遍历测试对 100 万个元素做累计求和。vector 耗时大约是 list 的五分之一到三分之一。原因就是我前面说的缓存命中率。vector 是连续内存遍历时 CPU 能高效预取list 节点分散在堆中访问一个节点就要去内存里捞一次。排序测试对 100 万个随机整数排序。这里有个反直觉的结果。vector 用 std::sort 比 list 的成员函数 sort 快很多差距可能在十倍以上。虽然两者时间复杂度都是 O(n log n)但 vector 的常数因子小得多连续内存的访问效率碾压链表的指针跳跃。这个测试给我最大的启发是链表的 O(1) 插入删除优势是有条件的一旦操作频率不够高或者遍历和查询占比很大vector 反而是更好的选择。工程上选择容器不要只看复杂度还要看数据规模、操作分布、内存访问模式。4.3 内存碎片、分配器和工程建议list 的每个节点单独 new这是它能做到 O(1) 插入的原因但也带来了内存碎片问题。如果你的程序频繁创建和销毁大量 list 节点堆上会出现很多小块内存碎片导致内存利用率下降甚至影响整体性能。缓解手段有两个思路。第一个思路是用自定义分配器。标准库的 list 模板第二个模板参数就是 allocator你可以在一个大的内存池上实现节点分配减少对全局堆的依赖。第二个思路是直接用 std::list 的静态方法比如提前批量插入、避免频繁 clear。这个效果有限很多时候还是分配器更靠谱。说实话在大多数业务代码里list 都不是性能瓶颈所在。我见过很多项目把 list 用在小规模数据上比如配置文件里的几十个目录项、UI 消息队列里的少量事件对象。这种场景直接用 std::list 就好别在这上面花太多心思做优化。如果你确实遇到要频繁创建链表节点的场景还有另一个思路用 std::vector 加上逻辑上的“链表行为”或者直接用第三方的侵入式链表。侵入式链表的节点里不存指向自己的指针而是由外部容器管理这能省去每个节点的独立分配开销。但这个方案写起来复杂可读性也差些除非有明确的性能瓶颈否则不建议在团队项目里贸然引入。我自己的经验是优先用标准库容器不要过早优化。等 profiling 数据明确指出 list 的内存分配是热点再考虑换分配器或者改侵入式方案。绝大多数情况下vector 加合理的预留reserve就已经处理得很好了。写到这里手写 list 的核心逻辑都过了一遍。我实际做这个练习时最大的感触是自己写一遍和只看文档是完全不同的体验。只有亲手处理过 node_-prev-next 这类指针操作你才真正理解为什么 list 的接口长这个样子为什么 insert 不失效、erase 只让当前迭代器失效。如果你正在学 STL 源码我建议你也动手写一个简化版 list不用管异常安全先跑通基本功能。写的过程里遇到的所有“为什么”都会成为你面试时最扎实的答案。 C++ list深入解析：接口剖析、迭代器失效与手写实现
如果你在 C 项目里用 vector 用得顺手头一回来碰 list大概率会冒出一堆问号为什么 list 的 insert 不引起重分配为什么它没有 operator[]为什么迭代器不支持加减运算这篇是 C list 专题的第二篇重点做两件事一是把 list 的接口挨个掰开讲清楚二是带着你从零手写一个满足基本功能的 list 容器。写这个专题的起因是我在实际项目中遇到过好几次“该用 list 还是 vector”的争论很多人对 list 的理解停留在“链表嘛插入删除快”这种口头层面真问到接口细节、迭代器失效规则、底层结构设计时又含糊了。所以这篇文章我想把 list 的常见接口、边界行为、内部结构一次说透再给一份可以直接拿来学习的实现代码。适合正在学 C STL 的人、准备面试的人以及写代码时总在容器之间纠结的工程向同学。1. 接口全景list 能做什么该在什么时候用1.1 list 的“身份证”双向链表结构带来的能力边界list 在标准库里的全称是 std::list底层是双向链表。这里的“双向”意味着每个节点除了存数据还有两个指针一个指向前一个节点一个指向后一个节点。和 vector 那种连续内存的数组结构比list 的能力边界非常清晰。先看它擅长的事。中间位置的插入和删除是 O(1) 复杂度这是在你已经持有迭代器的情况下成立的。比如你手里有个迭代器指向链表的第三个元素你想在它前面插入一个新元素list 只需要改动附近几个节点的指针数据本身完全不用搬动。vector 就不一样了中间插入意味着要把插入位置之后的所有元素整体后移最坏情况 O(n)如果扩容还要整体拷贝到新内存。再看它不擅长的事。list 没有随机访问能力你想取第 n 个元素只能从头部或者尾部一个个遍历过去时间复杂度 O(n)。所以标准库干脆不给你提供 operator[]。list 也不擅长查找你把整个链表翻一遍才能确认某个值在不在这跟 vector 的二分查找配合排序完全没法比。还有一个很多人容易忽略的点list 的每个节点是单独分配内存的节点之间在物理内存上大概率不连续。这就导致一个后果遍历链表的时候CPU 缓存命中率远低于遍历 vector。因为 vector 的元素在内存里是挨着的访问完第一个元素第二个元素大概率已经加载进缓存了list 的节点东一个西一个访问完一个节点下一个节点很可能不在缓存里需要重新到内存里取。实际工程里即使 list 在插入删除上有理论优势遇到频繁遍历的场景性能往往还不如 vector。所以结论很直接如果数据体量不大、也不需要频繁在中间插入删除优先考虑 vector如果确实需要在任意位置高频插入删除并且持有迭代器作为操作入口才考虑 list。1.2 常用接口速查与使用要点list 的接口分几类构造、容量、元素访问、修改、特殊操作。我把工程里最常用的整理成一张表后面逐个挑重点讲。分类接口作用复杂度构造list()构造空链表O(1)构造list(n, val)构造含 n 个 val 的链表O(n)构造list(begin, end)用迭代器区间构造O(n)容量empty()是否为空O(1)容量size()元素个数O(1)C11 起元素访问front() / back()访问首元素 / 尾元素O(1)修改push_front / pop_front头插 / 头删O(1)修改push_back / pop_back尾插 / 尾删O(1)修改insert(pos, val)在 pos 之前插入 valO(1)修改erase(pos)删除 pos 指向的元素O(1)特殊splice(pos, other)把另一个 list 接进来O(1)特殊merge(other)合并两个有序链表O(nm)特殊unique()删除连续重复元素O(n)特殊sort()链表排序O(n log n)特殊remove(val)删除所有等于 val 的元素O(n)先说一个高频考点list 的 size() 在 C98 时代可能是 O(n) 的因为标准没有强制要求常数时间很多早期实现靠遍历计数。但 C11 之后标准明确规定 size() 必须是 O(1)所以现代编译器里你可以放心使用 size()不用担心遍历整个链表数元素。再看元素访问。list 只有 front() 和 back()没有 at() 也没有 operator[]。而且 front() 和 back() 在空链表上调用是未定义行为别指望它给你抛异常。实际写代码时要先判断 empty()哪怕觉得“这地方肯定非空”也建议留着防御逻辑尤其是链表的元素是从外部传入的时候。insert 接口有个容易混淆的点。vector 的 insert 会导致迭代器失效list 的 insert 接在指定位置之前原有的所有迭代器都保持有效不会失效。这一点在面试中经常作为 vector 和 list 的对比点出现。原因不难理解list insert 只是改了指针指向不搬动任何已存在的节点节点的地址没有变化指向它们的迭代器自然仍然有效。erase 接口则需要留意。list 的 erase 会使“被删除节点”的迭代器失效但其他迭代器不受影响。C11 之前 erase 返回 void你删除元素后想继续遍历得先把要删除的迭代器保存到临时变量再推进。C11 之后 erase 返回被删除元素的下一个迭代器遍历删除的写法简化了不少。splice 是 list 独有的重要接口也是很多人第一次见到时觉得神奇的接口。它能把一个 list 中的节点直接“搬”到另一个 list注意是搬而不是复制。搬完之后源 list 的对应节点就没了但节点本身没有被销毁只是换了归属。这个操作在需要把多个链表拼接到一起的场景特别有用比如实现任务队列时把一批待处理任务整体挂到主队列末尾。merge 用于合并两个已排序的 list合并后目标 list 保持有序。这里要特别提醒源 list 的元素在 merge 之后会被清空这和直觉不太一样。很多人第一次用 merge发现另一个 list 变空了以为是 bug其实就是标准语义merge 是转移合并不是复制合并。unique 用来删除连续的重复元素。注意是“连续”如果相同的元素分散在不同位置unique 不会管它们。所以通常先 sort 再 unique才能实现真正去重。remove 则不同它是把链表中所有等于指定值的元素都删掉不需要元素连续也不需要链表有序。2. 看不见的内部结构哨兵节点和迭代器2.1 哨兵头节点让所有边界条件消失的设计要理解 list 的实现先要看懂它的节点结构。标准库里的 list 节点不是光秃秃的一个数据加两个指针通常会有一个哨兵头节点sentinel node。这个头节点不存实际数据它的 next 指向链表第一个元素prev 指向链表最后一个元素。链表为空时头节点的 next 和 prev 都指向它自己。哨兵节点的意义在于消除边界条件。假如没有哨兵空链表和只有一个元素的链表需要单独处理头部插入和尾部插入也要分别判断代码里到处是 if (head nullptr) 这种分支。有了哨兵节点所有操作都统一了。你想想 erase 的逻辑。删除一个节点需要四个步骤找到它的前驱节点找到它的后继节点把前驱的 next 指向后继把后继的 prev 指向前驱。如果链表只有一个节点这个节点的前驱和后继都是谁呢如果没有哨兵这里就得特殊处理前驱和后继都不存在。有了哨兵哪怕链表里只有一个节点它的前驱和后继也都是哨兵节点删除操作走同一套逻辑就能完成。begin() 返回指向第一个实际元素的迭代器就是 head_-nextend() 返回指向哨兵节点的迭代器。当一个循环遍历到这个“空的”哨兵时说明链表到头了。这就是为什么下面这种遍历写法能正常工作for (auto it lst.begin(); it ! lst.end(); it) { // 处理 it 指向的元素 }end() 返回的其实是一个指向“哨兵”的迭代器它不代表任何实际元素只代表链表的结束位置。如果你自己手写 list这个设计值得重点学习。初学者经常在 insert、erase 里写出一堆状态判断就是因为少了哨兵节点。2.2 迭代器链表访问的核心抽象迭代器是 list 设计的第二个关键点。你可以把迭代器理解成“指针的泛化”。对 vector 来说迭代器差不多就是普通的 T* 指针因为 vector 的元素连续存储指针加减就能访问任意位置的元素。但 list 不行元素不连续T* 这种原生指针没法完成“指向下一个节点”的操作因为谁也不知道下一个节点在内存的哪个角落。所以 list 的迭代器必须是自己定义的类类型内部封装一个 Node*对外提供类似指针的操作接口。常见操作包括operator让内部的 Node* 指向 next前移operator--让内部的 Node* 指向 prev后退operator*返回当前节点的数据引用operator-返回当前节点的数据指针operator / operator!比较两个迭代器是否指向同一个节点这些操作封装好之后迭代器的使用体验和原生指针非常接近。算法库里那些针对迭代器写的算法find、count、for_each 等也能直接作用于 list。迭代器按能力分类list 的迭代器属于双向迭代器Bidirectional Iterator支持 和 --但不支持 n、-n、[] 这类随机访问操作。标准库里的 sort 算法要求随机访问迭代器所以 list 的 sort 算法和 sort 函数的 sort 是两个不同的东西一个成员函数、一个算法。这边也解释了一个面试常见问题为什么 list 有单独的成员函数 sort因为 std::sort 要求随机访问迭代器双向迭代器玩不了必须提供自己的排序实现。2.3 迭代器失效规则与实际影响迭代器失效是个经常踩坑的话题。vector 里插入删除元素后所有迭代器都可能失效因为底层可能整体搬了家。list 里规则要温和得多。插入操作insert、push_front、push_back、splice不会使任何现有的迭代器失效。删除操作erase、pop_front、pop_back、remove、unique只会使被删除元素的迭代器失效其他迭代器保持有效。这个规则的意义在于你可以放心地在遍历 list 的过程中删除元素。最稳妥的写法是利用 C11 之后 erase 返回后继迭代器的特性for (auto it lst.begin(); it ! lst.end(); ) { if (需要删除(*it)) { it lst.erase(it); // erase 返回下一个有效迭代器 } else { it; } }在 C11 之前erase 不返回迭代器很多人会这样写for (auto it lst.begin(); it ! lst.end(); ) { if (需要删除(*it)) { lst.erase(it); // 先用后加it 先拷贝并递增 } else { it; } }这个写法利用了后置 先自增再返回旧值的特性让 erase 删除的是旧迭代器指向的节点而 it 已经安全地指向了下一个节点。两种写法都有效但前者更直观、更不容易出错。我个人推荐在新代码里统一用 C11 的写法。3. 手写 list从零实现一个可用的容器3.1 节点设计与类骨架光看不练假把式。理解了上面的结构接下来我用一个简化但功能完整的 list 实现来验证这些设计。先定义节点结构。template typename T struct ListNode { T data; ListNode* prev; ListNode* next; explicit ListNode(const T val T()) : data(val), prev(nullptr), next(nullptr) {} };这里用 struct 是因为节点内部字段需要被 list 类和迭代器类直接访问用 struct 省去一堆 friend 声明。然后定义 list 类的骨架。为了代码清晰我没有把全部接口都写进去但核心接口已经覆盖了绝大部分使用场景。template typename T class list { public: // 类型别名便于外部使用 using value_type T; using size_type size_t; using reference T; using const_reference const T; // 迭代器这里先用一个占位下面再实现 class iterator; class const_iterator; list(); list(size_type n, const T val); template typename InputIt list(InputIt first, InputIt last); list(const list other); list operator(const list other); ~list(); iterator begin(); iterator end(); const_iterator begin() const; const_iterator end() const; bool empty() const; size_type size() const; reference front(); reference back(); const_reference front() const; const_reference back() const; void push_front(const T val); void pop_front(); void push_back(const T val); void pop_back(); iterator insert(iterator pos, const T val); iterator erase(iterator pos); iterator erase(iterator first, iterator last); void clear(); void splice(iterator pos, list other); private: using Node ListNodeT; Node* head_; // 哨兵节点 size_type size_; // 元素个数 };构造函数里的哨兵节点初始化很关键。创建空链表时要让 head_ 的 next 和 prev 都指向自己这样链表就处于“空”状态begin() 和 end() 都指向 head_。template typename T listT::list() : head_(new Node()), size_(0) { head_-next head_; head_-prev head_; }注意哨兵节点虽然也是 Node 类型但它并不存放实际数据。这个节点一直存活到 list 被析构起到维护链表边界的作用。3.2 迭代器实现封装指针让算法统一迭代器的实现是我认为整个手写 list 中最精华的部分。它把“链表节点怎么走”的细节全部藏起来对上层提供统一的指针式语法。template typename T class listT::iterator { public: // 让算法库识别迭代器类型 using iterator_category std::bidirectional_iterator_tag; using value_type T; using difference_type std::ptrdiff_t; using pointer T*; using reference T; iterator() : node_(nullptr) {} explicit iterator(Node* node) : node_(node) {} reference operator*() const { return node_-data; } pointer operator-() const { return node_-data; } iterator operator() { node_ node_-next; return *this; } iterator operator(int) { iterator tmp *this; node_ node_-next; return tmp; } iterator operator--() { node_ node_-prev; return *this; } iterator operator--(int) { iterator tmp *this; node_ node_-prev; return tmp; } bool operator(const iterator other) const { return node_ other.node_; } bool operator!(const iterator other) const { return node_ ! other.node_; } // 迭代器访问底层节点list 内部用 Node* node() const { return node_; } private: Node* node_; };这里有几个细节值得展开说。首先operator* 返回的是 node_-data 的引用不是拷贝所以你可以通过 *it 直接修改链表中的元素。其次前置 返回迭代器自身的引用效率比后置 返回临时对象更高这也是为什么循环里优先写 it 而不是 it。const_iterator 和 iterator 的实现结构基本一致区别在于 operator* 和 operator- 返回 const 引用和 const 指针。为了简化代码我这里没有完整写出来但原理完全相同。这里插一句题外话标准库的实现里 iterator 可以隐式转换为 const_iterator这样当你把 list 传给一个接受 const list 的函数时函数里用 begin() 拿到的迭代器能正常赋值给 const_iterator。自己实现时如果有需要可以在 const_iterator 里加一个接受 iterator 的构造函数。3.3 构造与内存管理拷贝控制是重头戏list 的默认构造容易但涉及到拷贝构造、赋值、析构时很多新手会翻车。原因是链表的内存是分散的你必须逐个节点地复制过去不能像 vector 那样 memcpy。析构函数的核心是逐个销毁节点注意哨兵节点最后也得 delete。template typename T listT::~list() { clear(); delete head_; } template typename T void listT::clear() { Node* cur head_-next; while (cur ! head_) { Node* nxt cur-next; delete cur; cur nxt; } head_-next head_; head_-prev head_; size_ 0; }clear 的循环条件写得是 cur ! head_因为哨兵节点是链表遍历的终点。循环里先保存 cur-next再 delete cur这个顺序不能反否则你删了当前节点就找不到下一个节点的地址了。拷贝构造需要遍历原链表逐个把元素用 insert 方式链到新链表里。template typename T listT::list(const list other) : head_(new Node()), size_(0) { head_-next head_; head_-prev head_; for (const auto val : other) { push_back(val); } } template typename T listT listT::operator(const list other) { if (this ! other) { list tmp(other); // 拷贝构造临时对象 swap(tmp); // 交换内部状态 } return *this; }赋值运算符我这里用到了 copy-and-swap 惯用法先构造一个临时链表再把临时链表和当前链表的内容交换。这样写的好处是如果拷贝过程抛异常当前链表的内容不会被破坏异常安全性能得到保证。当然要真正支持 swap需要在类里加一个 swap 成员函数或友元函数这里为了篇幅没有完整展开但思路是对的。3.4 插入、删除与元素访问链表操作的核心逻辑push_back 和 push_front 是最简单的插入操作本质都是在边界位置插入一个新节点调整四个指针。template typename T void listT::push_back(const T val) { Node* new_node new Node(val); Node* tail head_-prev; tail-next new_node; new_node-prev tail; new_node-next head_; head_-prev new_node; size_; } template typename T void listT::push_front(const T val) { Node* new_node new Node(val); Node* first head_-next; head_-next new_node; new_node-prev head_; new_node-next first; first-prev new_node; size_; }push_back 的步骤是找到当前尾节点head_-prev让尾节点的 next 指向新节点新节点的 prev 指向尾节点新节点的 next 指向哨兵最后让哨兵的 prev 指向新节点。四个指针全部更新完新节点就正式挂到了链表尾部。pop_back 和 pop_front 是反向操作删除一个节点后要保证哨兵的 prev 或 next 正确指向下一个节点。template typename T void listT::pop_back() { Node* tail head_-prev; Node* new_tail tail-prev; new_tail-next head_; head_-prev new_tail; delete tail; --size_; }insert 是给一个位置迭代器在它前面插入新节点。这就是哨兵节点发挥作用的地方。无论 pos 是指向开头、末尾还是中间逻辑都是同一套拿到 pos 的前驱节点把新节点插在前驱和 pos 之间。template typename T typename listT::iterator listT::insert(iterator pos, const T val) { Node* cur pos.node(); Node* pre cur-prev; Node* new_node new Node(val); pre-next new_node; new_node-prev pre; new_node-next cur; cur-prev new_node; size_; return iterator(new_node); }来看这个逻辑有多统一。如果 pos 指向哨兵节点也就是 end()那么 pre 就是真正的尾节点新节点插到尾部效果等价于 push_back。如果 pos 指向第一个实际节点begin()那么 pre 就是哨兵新节点插到头部效果等价于 push_front。不管怎么插代码都不用写分支。erase 的逻辑同样统一。删除一个节点把前驱的 next 指向后继把后继的 prev 指向前驱然后 delete 节点。template typename T typename listT::iterator listT::erase(iterator pos) { Node* cur pos.node(); Node* pre cur-prev; Node* nxt cur-next; pre-next nxt; nxt-prev pre; delete cur; --size_; return iterator(nxt); }这里同样可以体会哨兵节点带来的便利。如果删除的是尾部元素nxt 就是哨兵不会出现空指针问题。如果删除的是头部元素pre 就是哨兵也不会有空指针问题。基于 insert 和 erasepush_back、push_front、pop_back、pop_front 其实都可以用统一的接口实现。实际标准库的实现里这些接口最终都会落到统一的插入删除逻辑上。3.5 独特算法接口splice、merge、unique 怎么实现这几个接口是 list 独有的vector 想都别想。splice 的实现有点反直觉它不用 new 和 delete而是直接把一个链表上的节点“摘下来”挂到另一个链表上。template typename T void listT::splice(iterator pos, list other) { if (other.empty()) return; Node* cur pos.node(); Node* pre cur-prev; Node* first other.head_-next; // 源链表第一个元素 Node* last other.head_-prev; // 源链表最后一个元素 // 把 [first, last] 整个区间摘下来 other.head_-next other.head_; other.head_-prev other.head_; // 把区间挂到当前链表 pre-next first; first-prev pre; last-next cur; cur-prev last; size_ other.size_; other.size_ 0; }这个操作的核心是只改指针不创建新节点。源链表搬走之后变空了其 size_ 归零当前链表的 size_ 相应增加。这种“搬节点”的语义在标准库里就是 splice 的默认行为面试里经常考到对源链表状态的影响。merge 合并两个有序链表。常见实现方式是依次比较两个链表头部的元素把较小的那个从源链表“拆”下来挂到目标链表中。由于两个链表本身有序这个比较过程可以做到线性复杂度。template typename T void listT::merge(list other) { if (this other) return; iterator it_this begin(); iterator it_other other.begin(); while (it_this ! end() it_other ! other.end()) { if (*it_other *it_this) { // 把 other 的当前节点搬到 it_this 前面 iterator next_other it_other; next_other; Node* move_node it_other.node(); Node* pos_node it_this.node(); Node* pre pos_node-prev; // 先从 other 摘除 move_node-prev-next move_node-next; move_node-next-prev move_node-prev; // 再挂到 this 里 pre-next move_node; move_node-prev pre; move_node-next pos_node; pos_node-prev move_node; it_other next_other; size_; --other.size_; } else { it_this; } } // 如果 other 还有剩余都是较大元素整体拼到尾部 if (!other.empty()) { splice(end(), other); } }merge 的实现细节较多核心还是指针的摘除和挂接。这个实现里我用了迭代器操作稍微显得繁琐一点但便于理解语义。标准库的实际实现更底层思路是一样的。unique 的实现就是在链表中遍历一遍把相邻重复的元素删除掉。因为链表的节点之间通过指针相连删除之后需要继续比较新的相邻关系所以用迭代器循环最方便。4. 常见坑和排查心得4.1 迭代器失效的典型场景实际使用 list 时迭代器失效问题比 vector 温和很多但它不是没有。最常见的坑出现在 erase 和 splice 的混用上。先看 erase。如果删除一个元素后还继续使用指向它的迭代器程序可能会出现未定义行为。具体表现可能是随机崩溃、数据错乱也可能运气好没报错。问题在于节点被 delete 之后那块内存可能已经被回收或者被其他对象占用你再访问它里面存的指针鬼才知道会发生什么。我在实际代码 review 中见过一个典型错误。有人想把链表里所有的偶数值都删掉他写出了这样一段逻辑for (auto it lst.begin(); it ! lst.end(); ) { if (*it % 2 0) { lst.erase(it); // it 已经失效了 it; // 这步是未定义行为 } else { it; } }这段代码第一眼看上去没什么问题但 erase 之后 it 指向的节点已经被释放此时再执行 it相当于访问了已释放的内存。表面上可能不崩溃但这是纯粹靠运气。正确的做法是直接用 erase 的返回值更新 it或者用前面提到的 it 技巧。splice 的坑则更隐蔽。splice 把一个节点从源链表搬到目标链表之后源链表中原本指向这个节点的迭代器并没有失效它还指向同一个节点。区别在于这个节点现在已经属于目标链表了你通过源链表的这个迭代器操作节点修改的不再是源链表的内容。这一点在逻辑上很容易被忽略调试的时候经常让人一头雾水。4.2 list 与 vector 的性能对比数据不会说谎光说理论没有感觉我写过一个简单的性能测试分别用 list 和 vector 做相同的操作结果比较有意思。插入测试在链表头部连续插入 100 万个元素。list 的 push_front 是 O(1)vector 的 insert(begin()) 是 O(n)因为每次插入后面全部元素都要移动。这个测试 list 完胜差别是数量级的。遍历测试对 100 万个元素做累计求和。vector 耗时大约是 list 的五分之一到三分之一。原因就是我前面说的缓存命中率。vector 是连续内存遍历时 CPU 能高效预取list 节点分散在堆中访问一个节点就要去内存里捞一次。排序测试对 100 万个随机整数排序。这里有个反直觉的结果。vector 用 std::sort 比 list 的成员函数 sort 快很多差距可能在十倍以上。虽然两者时间复杂度都是 O(n log n)但 vector 的常数因子小得多连续内存的访问效率碾压链表的指针跳跃。这个测试给我最大的启发是链表的 O(1) 插入删除优势是有条件的一旦操作频率不够高或者遍历和查询占比很大vector 反而是更好的选择。工程上选择容器不要只看复杂度还要看数据规模、操作分布、内存访问模式。4.3 内存碎片、分配器和工程建议list 的每个节点单独 new这是它能做到 O(1) 插入的原因但也带来了内存碎片问题。如果你的程序频繁创建和销毁大量 list 节点堆上会出现很多小块内存碎片导致内存利用率下降甚至影响整体性能。缓解手段有两个思路。第一个思路是用自定义分配器。标准库的 list 模板第二个模板参数就是 allocator你可以在一个大的内存池上实现节点分配减少对全局堆的依赖。第二个思路是直接用 std::list 的静态方法比如提前批量插入、避免频繁 clear。这个效果有限很多时候还是分配器更靠谱。说实话在大多数业务代码里list 都不是性能瓶颈所在。我见过很多项目把 list 用在小规模数据上比如配置文件里的几十个目录项、UI 消息队列里的少量事件对象。这种场景直接用 std::list 就好别在这上面花太多心思做优化。如果你确实遇到要频繁创建链表节点的场景还有另一个思路用 std::vector 加上逻辑上的“链表行为”或者直接用第三方的侵入式链表。侵入式链表的节点里不存指向自己的指针而是由外部容器管理这能省去每个节点的独立分配开销。但这个方案写起来复杂可读性也差些除非有明确的性能瓶颈否则不建议在团队项目里贸然引入。我自己的经验是优先用标准库容器不要过早优化。等 profiling 数据明确指出 list 的内存分配是热点再考虑换分配器或者改侵入式方案。绝大多数情况下vector 加合理的预留reserve就已经处理得很好了。写到这里手写 list 的核心逻辑都过了一遍。我实际做这个练习时最大的感触是自己写一遍和只看文档是完全不同的体验。只有亲手处理过 node_-prev-next 这类指针操作你才真正理解为什么 list 的接口长这个样子为什么 insert 不失效、erase 只让当前迭代器失效。如果你正在学 STL 源码我建议你也动手写一个简化版 list不用管异常安全先跑通基本功能。写的过程里遇到的所有“为什么”都会成为你面试时最扎实的答案。