坦白讲C的list是我见过最容易被“低估”的STL容器。平时用push_back加数据跑得很开心可一旦面试官问起“迭代器为什么失效”“insert为什么不导致迭代器失效”或者要求你徒手模拟一个list很多人就卡住了。我自己就吃过这个亏当年面试手撕list模拟实现写了半小时还踩了typename和迭代器封装的坑后来在项目里用list维护高频插入删除的任务队列又踩了缓存不友好和sort用错的坑。这篇文章把list的使用细节和底层模拟实现一次性讲透适合正在学STL的初学者也适合准备面试和想深挖源码的进阶读者。1. 先搞清楚list到底是什么1.1 双向循环链表长什么样list在STL里是一个双向循环链表每一个节点除了存数据之外还有两个指针prev指向前一个节点next指向后一个节点。为什么强调“循环”因为容器内部有一个不存数据的哨兵头节点也叫header节点链表尾部节点的next指向这个哨兵哨兵的prev指向尾部节点。这样一来end()位置就是哨兵节点的位置遍历到end()就说明转完了一圈。这个结构带来的直接结果就是begin()指向哨兵的下一个节点end()指向哨兵本身。空链表时哨兵的next和prev都指向自己。所以你看list的empty()其实是判断begin() end()也就是头节点的前后指针是否都指向自己。模拟实现的时候只要维护好这个哨兵节点空链表、单节点、多节点的情况都能统一处理不用写一堆if (head nullptr)的特殊逻辑。1.2 list和vector、forward_list怎么选很多人选容器就是“一拍脑袋”其实你只需要看两个维度随机访问频率和中间插入删除频率。vector是连续内存支持O(1)随机访问[]和at()随便用。但它在中间插入删除时要搬移元素复杂度是O(n)而且扩容时会涉及整体拷贝或移动。list正好相反任何位置的插入删除只需要改前后指针时间复杂度O(1)但它没有随机访问能力你想取第5个元素只能从头部或尾部过去复杂度O(n)。forward_list是单向链表比list省一个prev指针的内存但插入删除只能在一个方向上操作而且没有size()接口push_back也别想用只能push_front。它是C11为了极致节省内存而设计的实际业务代码里用得很少。如果你需要双向遍历、需要从尾部插入老老实实用list。我之前做过一个任务分发模块多个生产者往队列尾部塞任务消费者从头部取任务同时还要支持随时删除还没执行的任务。这种情况我用list就非常合适因为中间的删除和尾部的追加都是O(1)而且删除一个任务不影响其他任务的内存位置迭代器还能安全保存。1.3 list适合干什么不适合干什么list最适合的场景有两类一类是需要频繁在已知位置进行插入删除另一类是需要把节点从一个链表拼接到另一个链表也就是splice操作。这两个场景下vector无论如何都做不到O(1)。但list有个很隐蔽的缺点新手容易忽视缓存不友好。链表节点在内存里是零散分布的你遍历整个链表时CPU缓存命中率极低。我实测过同样遍历100万个intvector比list快一个数量级都不止。所以如果是“建好链表然后只是从头到尾遍历”的场景list反而不如vector。另一个不适合的场景是“随机访问为主”。比如你写一个排行榜要频繁按索引取第N名list就完全不行。这时候要么vector要么deque。deque是分段连续内存两头插入删除O(1)随机访问O(1)但多一次间接跳转属于list和vector之间的折中。2. list接口使用要点拿过来就能用2.1 构造与赋值的方式list的构造方式有五种我建议全部记下面试和写代码都很常用。#include list #include iostream using namespace std; int main() { // 1. 默认构造空链表 listint l1; // 2. 构造 n 个 value listint l2(5, 10); // 5个10 // 3. 迭代器区间构造 int arr[] {1, 2, 3, 4, 5}; listint l3(arr, arr 5); // 4. 拷贝构造 listint l4(l3); // 5. 初始化列表 listint l5 {1, 2, 3, 4, 5}; // 6. 移动构造C11 listint l6(std::move(l5)); for (int x : l6) cout x ; return 0; }要注意list没有operator[]和at()因为它不支持随机访问。这是它和vector最大使用差异。也不要试图用l.begin() 3这种操作编译直接报错。赋值方面除了拷贝赋值运算符operator之外assign有两个重载比较实用l.assign(3, 7)将链表重置为3个7l.assign(begin, end)用迭代器区间重置。它们会先清空原有元素再重新填充。2.2 常用接口与迭代器我把最常碰到的接口列出来你直接照着用就行。迭代器相关begin()、end()、rbegin()、rend()以及C11的cbegin()、cend()。反向迭代器通过向前移动注意rbegin()对应最后一个元素。容量相关empty()、size()、max_size()。元素访问front()、back()。注意没有operator[]。修改相关push_front、pop_front、push_back、pop_back、insert、erase、swap、clear、resize、assign。给个综合例子listint lst {1, 2, 3}; lst.push_front(0); // 0 1 2 3 lst.push_back(4); // 0 1 2 3 4 lst.pop_front(); // 1 2 3 4 lst.pop_back(); // 1 2 3 lst.resize(5, 99); // 1 2 3 99 99 auto it lst.begin(); it; lst.insert(it, 100); // 在第二个位置前插入100 lst.erase(lst.begin()); // 删除第一个元素 for (int x : lst) cout x ; // 输出: 100 2 3 99 99insert的返回值是指向新插入元素的迭代器erase的返回值是指向被删除元素下一个位置的迭代器这是C11之后的规定非常关键。尤其是erase如果你写lst.erase(it)后还继续用it那就是悬空指针出问题只是时间问题。2.3 算法型成员函数sort、unique、merge、splice、remove、reverselist自带一批算法成员函数因为通用算法比如std::sort需要随机访问迭代器链表用不了。这些接口高频出现逐个说。sortlst.sort()默认升序也可以传仿函数或lambdalst.sort(greaterint())实现降序。它内部是归并排序稳定。不要拿std::sort直接对list用编译会报错。也不要以为list::sort是简单的冒泡它底层是归并复杂度O(n log n)。uniquelst.unique()只删除相邻且相等的元素。如果链表是{1, 1, 2, 2, 2, 1}unique()之后是{1, 2, 1}最后一个1不会被删因为不相邻。想全局去重先sort再unique。merge合并两个已排序的链表。lst1.merge(lst2)执行后lst2会变成空链表。这个操作是O(mn)的比把lst2元素逐个插入lst1快很多因为底层是链表节点指针的拼接。splice把一个链表的节点直接“嫁接”到另一个链表不拷贝不移动元素复杂度O(1)。最常用的形式是lst1.splice(pos, lst2)把lst2全部节点拼接到lst1的pos位置之前。这个函数是list相比vector的杀手锏如果两批任务需要合并用splice比反复insert效率高一个量级。remove / remove_iflst.remove(5)删除所有值为5的元素lst.remove_if([](int x){ return x % 2 0; })删除所有偶数。它是真正的条件删除和unique性质不一样。reverselst.reverse()反转链表O(n)复杂度但只是改指针方向不需要移动数据。2.4 使用list的3个隐蔽坑第一个坑不要保存end()迭代器做插入判断。end()是一个固定的哨兵迭代器但这个迭代器在插入后仍然有效可它指向的位置可能不再是“最后一个元素的下一位置”了。具体说你保存auto endIt lst.end();然后lst.push_back(5)endIt依然指向哨兵用起来没问题。但如果你先insert再判断it ! endIt逻辑上可能出错。稳妥做法是每次需要end()就现场调用。第二个坑size()是O(1)别自己遍历算长度。STL的list在C11之后要求size()必须是常数复杂度实现里维护了_size字段。所以你写for (auto it lst.begin(); it ! lst.end(); it) cnt;完全是白费时间。第三个坑不要把迭代器当指针用。常见错误是auto it lst.begin(); it-someMethod();这种指针式访问其实是合法的-被重载了没问题。但如果你写*(it 1)这种随机偏移编译不过。链表迭代器只支持、--不支持 n。记住std::advance(it, n)才是通用写法。3. 迭代器失效面试必问的list专属问题3.1 为什么list的insert不失效erase会失效这是面试高频题答案的关键在“内存连续性”。vector插入元素可能触发扩容原来元素整体搬到了新内存所以所有迭代器都可能失效而list的每个节点是独立分配在堆上的插入新节点只是改了几个指针已经有节点的内存地址完全不变所以除了指向被插入位置之前的那个迭代器之外其他迭代器全部有效。注意即使insert位置在中间原来指向那个位置元素的迭代器依然有效因为元素本身没动只是多了一个前驱节点。erase为什么失效因为被删除的那个节点已经delete了指向它的迭代器保存的是这个已释放内存的地址再解引用就是悬空访问典型UB。正确的用法是it lst.erase(it);用返回值接过下一个位置。这在删除满足条件的元素时特别重要listint lst {1, 2, 3, 4, 5, 6}; for (auto it lst.begin(); it ! lst.end();) { if (*it % 2 0) it lst.erase(it); // erase返回下一个元素迭代器 else it; }3.2 保存end()迭代器的后果list的end()指向哨兵节点。哨兵节点是容器成员不会被删除所以end()理论上“永远有效”。但你保存它之后事情会变得诡异。比如listint lst {1, 2, 3}; auto endIt lst.end(); lst.push_back(4); // 此时 endIt 仍然指向哨兵输出*endIt没有意义但比较 是和 end() 等价的真正危险的是如果你保存的endIt来自另一个链表或者你在erase时把哨兵节点删了。虽然erase(end())本身也是UB标准不允许删除end()。更常见的问题是先保存auto it lst.end();然后it lst.erase(--lst.end());因为erase返回下一个迭代器而下一个就是end()结果it又成了合法end()这种没问题。但如果你保存的迭代器是指向被删除节点的那就彻底悬空了。我的建议是不要保存end()不要保存begin()不要保存任何可能被erase的迭代器。用的时候重新拿插入删除后再用返回值重新赋值养成这个习惯链表相关的悬空问题能少一大半。3.3 vector和list迭代器失效对比把两者的失效规则放一起一目了然操作vector迭代器/引用list迭代器/引用插入元素可能全部失效扩容或插入位置之后失效原有全部有效删除元素被删位置之后全部失效仅被删元素失效push_back扩容则全部失效不影响已有迭代器push_front不支持deque才支持不影响已有迭代器重新赋值/clear全部失效全部失效节点被释放面试时这么答基本能把“容器迭代器失效”这个专题拿下。实际写代码时vector优先考虑“下标”list优先考虑“迭代器”因为链表没有随机访问能力。4. 模拟实现list从0开始搭建4.1 节点结构和整体设计模拟实现前先设计节点template class T struct ListNode { ListNodeT* _prev; ListNodeT* _next; T _data; ListNode(const T data T()) : _prev(nullptr), _next(nullptr), _data(data) {} };这里_prev和_next是原始指针_data直接存储数据。有人问为什么不存unique_ptr或shared_ptr原因很简单链表节点互相指向的指针是“借用关系”不是所有权关系。每个节点的生命周期由链表容器统一管理如果用shared_ptr反而容易造成循环引用用unique_ptr又没法实现prev指针。所以裸指针在这个场景是合理的。整体设计是三件套ListNodeT节点、list_iteratorT, Ref, Ptr迭代器、listT容器本体。真正的STL实现还要考虑空间配置器、reverse_iterator适配、const迭代器转换、异常安全等但我们模拟实现聚焦核心逻辑先把主链路打通。4.2 迭代器封装为什么不能直接拿指针你可能想问vector的迭代器直接就是T*那list的迭代器能不能直接拿ListNodeT*不行。原因有两个第一operator的语义不同。原生指针会跳到sizeof(T)之后的内存地址但链表的下一个节点在堆上任意位置并不在当前节点地址后面。原生指针无法提供“跳到_next指向的节点”这个行为。所以迭代器必须重载和--本质是返回_next和_prev。第二解引用语义不同。对ListNodeT*解引用你得到的是节点本身ListNodeT而不是用户数据T。用户写出*it想拿到的是T。这必须通过重载operator*返回_data来实现。所以迭代器必须是一个包装类内部持有一个ListNodeT*指针对外模拟指针的行为。这也是STL迭代器设计中最精妙的地方把所有容器差异隐藏在统一接口后面。模板参数设计成三个T是数据类型Ref是引用类型Ptr是指针类型。这样做是为了让iterator和const_iterator共用一份迭代器代码template class T, class Ref, class Ptr struct list_iterator { typedef ListNodeT Node; typedef list_iteratorT, Ref, Ptr self; Node* _node; // 指向某个链表节点 list_iterator(Node* node nullptr) : _node(node) {} Ref operator*() { return _node-_data; } Ptr operator-() { 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; } };注意operator-返回的是_node-_data也就是T*这样it-member才能访问到数据成员的内部字段。4.3 list类主体一构造、析构、拷贝控制链表本体维护一个哨兵节点_head和一个大小字段_size。构造函数最重要的是初始化哨兵并让_head-_prev _head-_next _head形成自环。template class T class list { public: typedef ListNodeT Node; typedef list_iteratorT, T, T* iterator; typedef list_iteratorT, const T, const T* const_iterator; private: Node* _head; size_t _size; void create_head() { _head new Node; _head-_prev _head; _head-_next _head; _size 0; } public: list() { create_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); }再看拷贝构造和赋值。链表是深拷贝容器必须一个节点一个节点复制。不能用memcpy因为T可能不是POD类型。核心逻辑是遍历源链表逐节点push_backlist(const listT lt) { create_head(); for (const auto x : lt) push_back(x); } listT operator(const listT lt) { if (this ! lt) { clear(); for (const auto x : lt) push_back(x); } return *this; } ~list() { clear(); delete _head; _head nullptr; }clear()负责删除所有数据节点保留哨兵节点void clear() { Node* cur _head-_next; while (cur ! _head) { Node* next cur-_next; delete cur; cur next; } _head-_prev _head; _head-_next _head; _size 0; }很多人在模拟实现里写while (size() 0) pop_back();这也行但每次都调用erase和--_size多一层函数开销不如直接用clear遍历一次删除干净。4.4 list类主体二插入删除核心操作插入的核心是insert它在pos指向的节点之前插入新节点。关键是指针连接顺序不要写错最好画个图再写iterator insert(iterator pos, const T value) { Node* cur pos._node; Node* prev cur-_prev; Node* newNode new Node(value); newNode-_prev prev; newNode-_next cur; prev-_next newNode; cur-_prev newNode; _size; return iterator(newNode); }先让新节点建立与前后节点的连接再修改前后节点的指针。顺序错了会导致链表断链。如果pos是end()cur就是哨兵prev是最后一个节点新节点插到了链表尾部这就是push_back的实现基础。所以void push_back(const T value) { insert(end(), value); } void push_front(const T value) { insert(begin(), value); }删除的核心是eraseiterator 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); }pop_back和pop_front都能用erase组合出来void pop_back() { erase(--end()); } void pop_front() { erase(begin()); }这里有个细节erase(begin())没问题因为begin()指向第一个数据节点erase(--end())也没问题因为--让end()向前走一步变成最后一个数据节点。但千万不要写erase(end())那会把哨兵删掉整个链表直接崩。5. 完整模拟实现代码与测试可直接抄作业5.1 完整代码清单把上面所有片段拼成一个完整可编译的头文件去掉重复声明。这里给出可以直接抄的版本#include iostream #include cassert using namespace std; template class T struct ListNode { ListNodeT* _prev; ListNodeT* _next; T _data; ListNode(const T data T()) : _prev(nullptr), _next(nullptr), _data(data) {} }; template class T, class Ref, class Ptr struct list_iterator { typedef ListNodeT Node; typedef list_iteratorT, Ref, Ptr self; Node* _node; list_iterator(Node* node nullptr) : _node(node) {} Ref operator*() { return _node-_data; } Ptr operator-() { 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; } }; template class T class list { public: typedef ListNodeT Node; typedef list_iteratorT, T, T* iterator; typedef list_iteratorT, const T, const T* const_iterator; private: Node* _head; size_t _size; void create_head() { _head new Node; _head-_prev _head; _head-_next _head; _size 0; } public: list() { create_head(); } list(const listT lt) { create_head(); for (const auto x : lt) push_back(x); } listT operator(const listT lt) { if (this ! lt) { clear(); for (const auto x : lt) push_back(x); } return *this; } ~list() { clear(); delete _head; _head nullptr; } 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; } T front() { return *begin(); } T back() { return *(--end()); } void clear() { Node* cur _head-_next; while (cur ! _head) { Node* next cur-_next; delete cur; cur next; } _head-_prev _head; _head-_next _head; _size 0; } iterator insert(iterator pos, const T value) { Node* cur pos._node; Node* prev cur-_prev; Node* newNode new Node(value); newNode-_prev prev; newNode-_next cur; prev-_next newNode; cur-_prev newNode; _size; 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; --_size; return iterator(next); } void push_back(const T value) { insert(end(), value); } void push_front(const T value) { insert(begin(), value); } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); } };5.2 测试用例与运行输出用下面这个main函数测试完整流程#include list.hpp #include iostream using namespace std; struct Point { int x, y; Point(int a 0, int b 0) : x(a), y(b) {} }; int main() { listint l1; l1.push_back(1); l1.push_back(2); l1.push_front(0); l1.push_back(3); cout 正向遍历: ; for (auto it l1.begin(); it ! l1.end(); it) cout *it ; cout endl; cout 反向遍历: ; for (auto it --l1.end(); it ! l1.begin(); --it) cout *it ; cout *l1.begin() endl; // 在第二个位置插入100 auto it l1.begin(); it; l1.insert(it, 100); // 删除值为2的元素 for (auto p l1.begin(); p ! l1.end();) { if (*p 2) p l1.erase(p); else p; } cout 测试后: ; for (auto x : l1) cout x ; cout endl; listint l2(l1); // 拷贝构造 listint l3; l3 l2; // 赋值 cout l3 size: l3.size() endl; // 自定义类型测试 listPoint pts; pts.push_back(Point(1, 2)); pts.push_back(Point(3, 4)); auto pit pts.begin(); cout Point: pit-x , pit-y endl; cout Point: (*pit).x , (*pit).y endl; return 0; }编译参数建议加上-Wall -g。预期输出如下正向遍历: 0 1 2 3 反向遍历: 3 2 1 0 测试后: 0 100 1 3 l3 size: 3 Point: 1, 2 Point: 1, 2这里验证了几个关键点insert插入后链表顺序正确erase删除元素后返回合法迭代器front/back取值正常自定义类型的-运算符重载可用拷贝构造和赋值深拷贝无误。5.3 内存与异常安全说明模拟实现里最需要注意的异常安全问题如果push_back过程中new抛异常内存不足链表可能处于不一致状态。标准库会保证强异常安全或基本安全我们的简化版做不到完整保证但在学习阶段够用了。另一个问题是拷贝构造里如果中途new失败已经分配的新节点会泄漏。更严谨的做法是用try-catch包裹失败时clear再rethrow。实际面试时提到这一点反而能加分。析构函数里delete _head之后把_head置空这算防御性编程。真实STL实现还会有allocator来定制内存分配比如用内存池减少频繁new/delete的开销。我们模拟实现直接用new/delete道理是一样的只是性能差点。6. 常见问题与排查技巧实录6.1 erase之后还能用旧迭代器吗不能这是链表使用最高频的UB来源。erase会立刻delete节点旧迭代器保存的地址已经释放。读它、写它、它都是未定义行为。有些人说“我试过好像没事”那是因为释放后的内存还没被系统回收或复用但这是纯粹的运气换个场景立刻崩溃。正确的通用删除模式我之前已经写过it lst.erase(it);返回值一定指向被删元素的下一个位置。如果你要连续删除多个元素就持续用返回的迭代器继续判断。还有一个容易错的地方不要在范围for循环里erase因为范围for会缓存end()删除后缓存失效运行期可能崩。6.2 clear之后内存释放了吗clear()会把所有数据节点delete掉所以节点内存释放了。但有两个隐含问题第一哨兵节点还在链表对象仍然占着堆上的一块内存第二delete只是把内存还给堆管理器操作系统层面不一定立即回收物理内存这只是所有new/delete程序的共性和list没关系。另外如果T本身是std::string或vector等容器clear会正确调用它们的析构函数释放深层资源。我们的模拟实现里delete cur会触发Node析构而Node的成员_data会自动调用T::~T()所以不用手动清理_data。6.3 list的sort和std::sort怎么选这是新手最容易踩的坑。std::sort需要随机访问迭代器list的迭代器是双向迭代器所以std::sort(lst.begin(), lst.end())编译不过。必须用lst.sort()成员函数。list::sort内部是归并排序不是快排。归并排序稳定而且适合链表结构因为它只需要改指针不需要搬移数据。如果你要稳定排序list::sort本来就很合适。还要注意sort之后链表元素的地址会变因为要重新连接节点指针。如果你在sort之前保存了某个元素的迭代器sort之后这个迭代器仍然指向原来那个节点但节点在链表中的位置变了。如果你保存的迭代器指向的元素不存在了那就别用了。6.4 实战什么时候list反而不如vector我自己实测过大流量场景维护一个高频插入删除的缓冲区list在插入删除上的优势非常明显但如果是“先收集数据再统一遍历输出”的模式list反而慢到离谱。原因就是缓存不友好链表节点散落在内存各处遍历时每次都要跳到一个随机地址CPU缓存几乎没有命中。所以我的选择标准是数据量大且只遍历vector。频繁中间插入删除且删除位置已知list。双端操作又要随机访问deque。需要把整个链表嫁接到另一个链表listsplice别的容器替代不了。另外list每个节点都有两个指针如果存的是小对象节点指针的内存开销可能比数据本身还大。比如listchar存1字节数据却要额外8字节或16字节对齐的指针开销内存浪费严重。这时候就用dequechar或vectorchar。我个人还有个小技巧如果对list的插入删除性能不满意先问自己“是不是用了太多new导致内存碎片”。常规办法是写一个内存池分配器让节点从内存池分配而不是每次走new。STL的std::allocator本来就能定制你可以在声明listT, MyAllocator时传入。不过这个属于进阶优化面试能说出来是加分项项目里如果没到瓶颈也别轻易上复杂度会明显上升。回到本文的模拟实现最后再提醒一句不管看多少遍源码都不如手写一遍。你把节点、迭代器、插入删除、拷贝构造这四个模块写通list基本就吃透了。写的时候遇到编译报错优先检查是不是忘了typename——类外定义成员函数时返回类型里的listT::iterator必须写成typename listT::iterator告诉编译器这是个类型而不是静态成员。这个错误几乎所有手写STL的人都会遇到至少一次。