C++ STL list手写指南：从双向链表到迭代器封装

如果你准备过C++开发相关的面试，或者刷过几轮笔试，大概率碰到过这个经典问题：请实现一个list容器，或者至少讲讲它和vector的区别。STL容器里，list一直是个被低估的角色——业务代码里vector一把梭是常态，真需要中间插入删除时才想起它，但一旦落到“怎么自己写一个能正常工作的list”，很多人第一反应是这不就是个双向链表嘛，封装一下节点不就行了？结果一动手，发现迭代器怎么封装、哨兵头要不要、const迭代器怎么复用、深拷贝怎么写，一个比一个容易翻车。

这篇文章我想把两件事一次说透：第一，std::list在什么场景下真正值得选，使用中有哪些容易忽略的行为细节；第二，从零手写一个具备核心功能的list，包括节点设计、迭代器封装、插入删除、拷贝赋值和析构，并复盘那些只有动手写过才会踩到的坑。适合准备C++方向面试的读者，也适合想彻底弄懂STL容器的朋友。不是单纯贴代码，而是把每一步设计背后的理由讲清楚。

1. 双向链表到底解决了什么问题：先聊聊vector做不到的事

1.1 从一类典型需求说起

想象一个场景：你要维护一个比较长的对象序列，而且经常要在中间某个位置插入或者删除，比如编辑器里的撤销历史、音视频播放列表、任务队列里优先级的重排。用vector做这些操作，问题很明显：插入到中间位置，它会把后续所有元素整体往后搬，平均O(n)次元素移动；删除同样要覆盖搬移。如果序列里存的是复杂对象，拷贝构造的开销会更夸张。

list的底层是双向链表，每个节点独立分配在堆上，节点之间用prev/next指针连接。插入、删除只需要改相邻节点指针，是真正的O(1)。没有元素搬移，没有引用失效。这是它存在的根本理由。

1.2 一张表看清list和vector的差别

这里有一个反直觉的点：list的O(1)插入不是免费的。它省略的是元素搬移，却付出了两个代价——节点new/delete的开销，以及缓存不友好带来的低效。如果你只是往尾部连续push_back，vector通常会更快。list真正擅长的是“中间位置且频繁”的插入删除，或者你持有迭代器需要长期稳定的场景。

1.3 那std::list到底什么时候选

我的经验判断：需要一个容器反复做“找到位置然后插入/删除”的操作，而位置由外部逻辑指定，不是每次都从头遍历，list有明显优势。对元素稳定性要求高，插入删除不能把别的对象的地址弄飞，list天然满足。小而多的中间插入，配合splice使用，list几乎不可替代。其他情况默认vector。很多人会说“我只需要尾插尾删，用list也不差”——确实不差，但性能和内存上都吃亏，除非你需要的是迭代器稳定。

2. 正式使用list之前，这几个行为必须先记住

2.1 迭代器失效：比vector友善得多

这事经常被面试官拿来对比。vector在push_back触发扩容后，所有迭代器都可能失效；中间插入还会让后续迭代器全部失效。list不一样，它的节点彼此独立，insert和erase只修改局部指针，所以：

• insert：所有原有迭代器都有效；
• erase：除了被删除的那个节点，其余迭代器都有效；
• 在遍历过程中边删边走是安全的，只要妥善利用erase的返回值。

还有一个细节值得留意：list的end()迭代器在插入删除后依旧有效，因为它始终指向哨兵头，哨兵头的位置从来没变过。这一点和vector完全不同，写代码时可以利用这个特性减少一些对end()重新获取的担心。

2.2 erase返回值：删除遍历的正确姿势

很多人会写错这段代码：

for (auto it = lt.begin(); it != lt.end(); ++it) { if (*it % 2 == 0) { lt.erase(it); // 这里it已经失效了 } }

一旦进入erase分支，it指向的节点已经被delete，随后的++it在野指针上做运算，常见结果是崩溃，运气好是内存被重用后的数据错乱。正确的写法是接收返回值：

for (auto it = lt.begin(); it != lt.end(); ) { if (*it % 2 == 0) { it = lt.erase(it); // erase返回被删节点的下一个节点 } else { ++it; } }

需要说明的是，erase返回“被删元素的下一个元素”的迭代器，这个行为从早期标准起就存在，所以这个习惯在任何标准版本下都成立。而list的insert在较早的标准里返回void，C++11开始才统一返回新插入节点的迭代器，写老风格代码时要注意标准差异。

2.3 splice：链表版“乾坤大挪移”

splice是把另一个list的一段节点直接拼过来，不拷贝数据，只改指针，常数时间。这在LRU缓存、定时器管理、任务调度里特别实用。

给一个简单场景：维护一个热点列表，要删除中间节点，并把它放到头部。常规写法是先erase再push_front，但简单的写法是用splice一行完成：

std::list<int> tasks{1, 2, 3, 4, 5}; auto it = std::next(tasks.begin(), 2); // 指向3 tasks.splice(tasks.begin(), tasks, it); // 把it指向的节点移动到头部 // tasks现在是 3, 1, 2, 4, 5

注意splice的用法细节：当目标list和源list是同一个list时，就是在自己链上搬节点，不会有数据拷贝，被搬移节点的迭代器仍然有效。这个操作的返回值是void，但它确实是常数时间。很多人不知道这个函数，直到遇到需要在多个链表间转移元素的需求才后悔没早点掌握。

2.4 别拿std::sort去排list

这是新手最容易踩的编译错误：list不支持随机访问迭代器，std::sort必须随机访问迭代器才能工作，直接传给std::sort会编译失败。应当调用list自带的成员函数sort()，底层是归并排序，稳定且O(nlogn)。同理，unique()去重、merge()归并两个有序链表、remove()按值删除，都是list自己的成员函数，和算法库的同名函数行为接近，但直接作用于链表内部结构，效率更高。

3. 手写list前必须想明白的三件事

3.1 节点结构：为什么都要带一个哨兵头

按直觉设计节点，一个struct就够了：

template<class T> struct __list_node { T _data; __list_node<T>* _prev; __list_node<T>* _next; };

但链表为空时，begin/end的边界判断会非常啰嗦。标准实现的做法是额外分配一个不存数据的头节点，叫哨兵头。它始终存在：

• _head->_next指向第一个有效节点；
• _head->_prev指向最后一个有效节点；
• 链表为空时，_head->_next == _head，_head->_prev == _head；
• end()迭代器指向的就是这个哨兵头。

这样一来，insert/erase在头尾位置和中间位置的处理逻辑完全一致，不需要特殊判断。我第一次写链表时尝试不带头节点，很快被空表特判恶心到，换成哨兵头后代码量直接缩水一半。这是一个“先信，再用代码验证”的设计。

3.2 迭代器为什么不能是裸指针

list的内存不连续，无法用“指针自增”来移动到下一节点，裸指针无法胜任++、--、*这些操作。所以迭代器必须是一个独立的类，内部保存一个指向节点的指针，重载各种运算符。真正理解这个点，才会明白为什么STL的迭代器是一个抽象层。

具体来说，std::list std::string ::iterator内部不是string*，而是一个迭代器对象。它提供类似指针的语法，但底层走的是节点指针的prev/next跳跃。用类封装后，const迭代器和非const迭代器也自然可以复用同一套逻辑。

3.3 内存归属和值语义

list的每个数据节点都是new出来的，谁持有list对象，谁就对该list的所有节点内存负责。这里必须明确：

• clear()：释放所有数据节点，哨兵头保留；
• 析构：clear之后，再释放哨兵头；
• 拷贝构造：深拷贝，创建一套全新的节点；
• 赋值：把右边的节点状态完整复制到左边，并释放左侧旧节点。

如果忽视了深拷贝，用编译器默认生成的拷贝构造，两个list共享同一串节点，任何一个析构都会导致另一个悬空，这是模拟实现里翻车率第一名。

4. 从零动手：一个能跑的list是怎么写出来的

4.1 节点与类骨架

先把节点和list的类骨架搭出来。节点里存数据、前驱指针、后继指针。list类里除了哨兵头，我还额外维护一个_size成员，让size()是O(1)。标准库从C++11开始也要求size是常数时间。

template<class T> struct __list_node { T _data; __list_node<T>* _prev; __list_node<T>* _next; __list_node(const T& val = T()) : _data(val), _prev(nullptr), _next(nullptr) {} }; template<class T> class list { public: typedef __list_node<T> Node; typedef __list_iterator<T, T&, T*> iterator; typedef __list_iterator<T, const T&, const T*> const_iterator; list() { _head = new Node; _head->_next = _head; _head->_prev = _head; _size = 0; } 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); } size_t size() const { return _size; } bool empty() const { return _size == 0; } private: Node* _head; size_t _size; };

注意构造里一定要让哨兵头的next和prev都指向自己，否则空链表状态下begin()和end()无法正确工作。这里的节点构造函数给_data提供了默认值T()，所以在构造空链表时不会遇到数据初始化问题，但真实标准库对节点内存和对象构造是分离的，不会要求T必须可默认构造，这一点我们后面再提。

4.2 迭代器封装：三个模板参数比两个更省事

迭代器类内部持有一个Node*，重载需要的运算符。这里用三个模板参数T、Ref、Ptr，Ref用于决定operator*的返回类型，Ptr用于决定operator->的返回类型。这样做的好处是，iterator和const_iterator可以共用同一个类模板，不用写两遍几乎一样的代码。

template<class T, class Ref, class Ptr> struct __list_iterator { typedef __list_node<T> Node; typedef __list_iterator<T, Ref, Ptr> self; Node* _node; __list_iterator(Node* node) : _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& s) const { return _node == s._node; } bool operator!=(const self& s) const { return _node != s._node; } };

几个点说明一下。前置++返回引用，后置++返回旧值的副本，这是C++运算符重载的惯例，后置返回的临时对象不能绑定非const引用，所以写成返回self而不是self&。operator->返回的是T*，当T是自定义类型时，it->member会被编译器解释成it.operator->()得到一个指针，再用这个指针访问member，所以能正常工作。

当遇到一个const list对象时，遍历它需要const_iterator。如果没有const版本的begin()和end()，const对象上根本调不了begin()，代码会编译失败。有了上面这个模板，const_iterator和iterator共用一套实现，只是实例化时Ref被推导成const T&，于是operator*返回const引用，数据只读不可改。

4.3 insert/erase：位置无关的指针手术

核心的插入删除逻辑如下。insert是在pos位置之前插入新节点，pos可以是end()，此时就是在链表尾部插入，push_back完全可以复用insert。erase是删除pos指向的节点并返回下一个有效节点。

iterator insert(iterator pos, const T& val) { Node* cur = pos._node; Node* prev = cur->_prev; Node* new_node = new Node(val); prev->_next = new_node; new_node->_prev = prev; new_node->_next = cur; cur->_prev = new_node; ++_size; return iterator(new_node); } iterator erase(iterator pos) { Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; prev->_next = next; next->_prev = prev; delete cur; --_size; return iterator(next); } 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()); }

insert里新节点是独立new出来的，new操作如果抛异常，链表结构完全没有被改动，_size也没有增加，这是一个很自然的异常安全保证。如果你在真实工程中需要极强的性能，可以把节点分配改成内存池，但那是后话。

erase有个隐藏风险：如果传入end()，cur就是哨兵头，delete哨兵头之后链表结构直接崩坏。生产级代码应该加assert(pos != end())或者提前判断。教学代码里我通常只在文档里强调，但实战里宁可把断言写上。

pop_back()的写法erase(--end())，是从end()往前移动一步，得到最后一个有效节点，然后删除。注意不要在空表上调用pop系列，否则--end()会跑到哨兵头前面，也是未定义行为。

4.4 析构、拷贝构造、赋值：内存封闭性的三道防线

链表的节点都是new出来的，所以必须手动管理生命周期。clear释放所有数据节点但保留哨兵头，析构函数先clear再释放哨兵头，这两个步骤不能反过来，也不能合并。

void clear() { Node* cur = _head->_next; while (cur != _head) { Node* next = cur->_next; delete cur; cur = next; } _head->_next = _head; _head->_prev = _head; _size = 0; } ~list() { clear(); delete _head; _head = nullptr; } list(const list<T>& lt) { _head = new Node; _head->_next = _head; _head->_prev = _head; _size = 0; for (const auto& e : lt) { push_back(e); } } void swap(list<T>& lt) { std::swap(_head, lt._head); std::swap(_size, lt._size); } list<T>& operator=(list<T> lt) { swap(lt); return *this; }

这里最值得解释的是operator=的写法：参数是list lt，按值传参，所以进入函数时已经通过拷贝构造生成了一个全新的链表。随后swap把自己和这个临时链表交换，本对象接管新链表，旧链表的剩余节点随着lt析构被释放。整个过程要么拷贝成功再交换，要么拷贝异常时根本不会进入swap，本对象保持原状。这就是copy-and-swap惯用法，它天然解决了两个问题：自赋值安全，异常安全。

如果改成“先delete所有旧节点，再从右侧拷贝”，一旦拷贝过程中抛出异常，左侧就是一个已经清空的半崩溃链表。我见过不少线上崩溃最后定位到类似问题，所以这个细节值得反复强调。

5. 实测和踩坑：模拟实现过程中最易翻车的地方

5.1 浅拷贝导致的double free

我最初写完list后，第一时间测试拷贝构造，结果程序在退出时直接崩溃，报错信息指向内存释放。原因很简单：没写拷贝构造，编译器默认生成逐成员拷贝，两个list的_head指向同一串节点。第一个对象析构时把节点全delete了，第二个对象析构时再次delete同一块内存，double free。

这种问题在vector上不明显，因为vector的默认拷贝构造会拷贝内部堆数组的指针，同样会double free，但vector的报错往往更隐蔽。解决方式就是上面的深拷贝实现。建议写完这个容器后，专门写一段测试：把a拷贝给b，然后修改b的数据，再打印a，确认a完全不受影响。这个测试能帮你快速确认拷贝构造是否真正独立。

5.2 erase后继续使用旧迭代器

除了上面说的野指针++问题，还有一个更隐蔽的坑：erase之后，即使不做自增，仅仅对旧迭代器做比较也可能触发未定义行为。因为节点已经被delete，迭代器内部保存的那个指针指向已释放的内存，任何对它的解引用、比较、自增都属于未定义行为。

正确习惯是：erase之后立刻重新赋值。要么it = erase(it)，要么干脆在别的分支使用新的迭代器。写代码时把“旧迭代器在erase后立即失效”当成铁律，就不会在边界条件上栽跟头。

5.3 const版本迭代器：operator*返回引用的细节

如果迭代器类里operator*固定返回T&，那么const_iterator就形同虚设：const list对象上依然可以通过iterator修改数据，const性完全被绕过。解决办法有两个：写两个几乎一样的迭代器类，或者用模板参数控制返回类型。我选择后者。

有了三模板参数的迭代器后，还需要在list中提供const版本的begin()和end()。否则：

void printList(const list<int>& lt) { for (auto it = lt.begin(); it != lt.end(); ++it) { std::cout << *it << ' '; } }

这段代码在只有非const begin()时无法编译，因为const对象上不能调用非const成员函数。补上const begin()/end()后，auto推导为const_iterator，*it返回const T&，数据只读，编译通过。

我见过不少人在这里偷懒，只写iterator版本的begin/end，结果整个项目里const list处处编译报错，最后就干脆把const去掉，绕过了类型检查，也把bug埋下了。

5.4 赋值运算符为什么值得用“传值+swap”

如果手写一个传统的operator=，典型做法是：

list<T>& operator=(const list<T>& lt) { if (this != &lt) { clear(); for (const auto& e : lt) push_back(e); } return *this; }

这种写法能工作，但有两个问题。第一，clear之后如果push_back抛出异常，本对象已经空了，数据丢失。第二，如果T类型比较大，拷贝失败的概率不是零。用传值+swap的写法，临时对象构造成功才可能进入swap，之前的对象一直完整可用。两行代码解决自赋值判断，解决异常安全，值得养成习惯。

6. 模拟实现跑完，和真正的std::list还差什么

6.1 功能差距：还有一堆成员函数没补

把核心链条写完，这个list已经能应对大多数教学场景和面试手写题。但真实std::list还有这些高频成员函数：splice、sort、unique、merge、remove_if、emplace_back、emplace、initializer_list构造支持，以及allocator模板参数。其中splice和sort这两块非常值得自己动手补一遍：splice涉及在不同链表间转移节点；sort需要实现归并排序，能把“链表不适合随机访问但适合归并”这个特性体会得很深。

6.2 性能差距：教学版和标准库不在一个量级

标准库实现会用allocator来管理节点内存，默认分配器也比裸new多一层灵活的扩展机制；标准库在边界情况的处理、异常安全性、constexpr支持上都远比教学版讲究。更关键的是，list天生存在缓存不友好的问题：节点分散在堆上，遍历时CPU缓存命中率远低于vector。我在自己机器上测过类似的场景，插入大量数据后整体遍历一遍，vector比list快三五倍是很常见的。这不是list的bug，而是它的成本结构决定的。

所以手写list的目的不是取代std::list，而是通过复刻核心机制来理解容器本质。真到生产环境，优先用标准库。自己写的版本更适合用来做实验、做对比、看每一步操作到底改动了哪些指针。

6.3 我的建议与后续练习方向

动手写一个list，价值不只是应付面试，而是真正理解迭代器抽象和值语义。我的建议是从“只读不抄”开始：先自己设计节点和迭代器，把代码写跑，再打开标准库头文件对照，你会发现标准库的实现比你想象的复杂得多，但核心思想就这些。

后续可以做这些练习：给list补上splice和归并版sort；实现reverse_iterator；给节点加allocator支持；再进一步，模拟实现vector，把连续内存容器和链表容器的迭代器设计对比着学。最后分享一个小技巧：写这类容器模拟题时，始终让代码满足“强异常安全”——插入失败不改变容器、赋值失败不改变左侧。我排查过不少容器相关崩溃，绝大多数根因都是浅拷贝、迭代器失效或异常中留下的半状态。手写一遍list，你会对这些问题形成肌肉记忆。