1. list 的介绍
list是 STL 中非常重要的序列式容器之一，它可以在常数时间 O(1)内在任意位置进行插入和删除元素。
list 的底层结构是带头结点的双向循环链表：
- 每个节点包含一个数据域
data、一个前驱指针prev和一个后继指针next； - 头结点（哨兵节点）不保存有效数据，它的
next指向第一个有效节点，prev指向最后一个有效节点； - 空表时，哨兵节点的
next和prev都指向自己。
由于底层是链表，list 支持高效的任意位置插入/删除，但不支持随机访问，访问第 i 个元素的复杂度是 O(N)。
2. list 的使用
list 接口很多，学习时应该先掌握“如何正确使用”，再去研究背后的实现原理。下面是 list 中常见的重要接口。
2.1 list 的构造
| 接口 | 说明 |
|---|---|
list (size_type n, const value_type& val = value_type()) | 构造包含 n 个值为 val 的元素的 list |
list() | 构造空的 list |
list (const list& x) | 拷贝构造函数 |
list (InputIterator first, InputIterator last) | 用[first, last)区间中的元素构造 list |
使用示例：
#include<iostream>#include<list>usingnamespacestd;intmain(){list<int>l1;// 空 listlist<int>l2(4,100);// {100, 100, 100, 100}list<int>l3(l2);// 拷贝构造list<int>l4(l2.begin(),l2.end());// 迭代器区间构造list<int>l5{1,2,3,4,5};// C++11 initializer_list 构造return0;}2.2 list 的迭代器
此处可以暂时把迭代器理解成一个指针，该指针指向 list 中的某个节点。
| 接口 | 说明 |
|---|---|
begin + end | 返回第一个元素的迭代器 + 最后一个元素下一个位置的迭代器 |
rbegin + rend | 反向迭代器：rbegin即end位置，rend即begin位置 |
注意：
begin与end是正向迭代器，对迭代器执行++，迭代器向后移动；rbegin（end）与rend（begin）是反向迭代器，对迭代器执行++，迭代器向前移动。
使用示例：
list<int>l{1,2,3,4,5};// 正向遍历for(autoit=l.begin();it!=l.end();++it)cout<<*it<<" ";// 反向遍历for(autoit=l.rbegin();it!=l.rend();++it)cout<<*it<<" ";// 范围 for（本质也是 begin()/end()）for(auto&e:l)cout<<e<<" ";2.3 list capacity
| 接口 | 说明 |
|---|---|
empty | 检测 list 是否为空，是返回 true，否则返回 false |
size | 返回 list 中有效节点的个数 |
2.4 list element access
| 接口 | 说明 |
|---|---|
front | 返回 list 的第一个节点中值的引用 |
back | 返回 list 的最后一个节点中值的引用 |
2.5 list modifiers
| 接口 | 说明 |
|---|---|
push_front | 在 list 首元素前插入值为 val 的元素 |
pop_front | 删除 list 中第一个元素 |
push_back | 在 list 尾部插入值为 val 的元素 |
pop_back | 删除 list 中最后一个元素 |
insert | 在 list 的 position 位置插入值为 val 的元素 |
erase | 删除 list 的 position 位置的元素 |
swap | 交换两个 list 中的元素 |
clear | 清空 list 中的有效元素 |
2.6 list 的迭代器失效
因为 list 的底层结构是带头结点的双向循环链表，所以：
- 插入操作不会导致 list 的迭代器失效；
- 删除操作只会使指向被删除节点的那个迭代器失效，其他迭代器不受影响。
经典错误示例：删除节点后还继续使用已经失效的迭代器。
voidTestListIterator1(){intarray[]={1,2,3,4,5,6,7,8,9,0};list<int>l(array,array+sizeof(array)/sizeof(array[0]));autoit=l.begin();while(it!=l.end()){// erase() 执行后，it 所指向的节点已被删除，因此 it 已经失效l.erase(it);++it;// 对失效迭代器 ++，未定义行为！}}改正方式：利用后置++先保存旧迭代器、再前进、最后删除旧节点。
voidTestListIterator(){intarray[]={1,2,3,4,5,6,7,8,9,0};list<int>l(array,array+sizeof(array)/sizeof(array[0]));autoit=l.begin();while(it!=l.end()){l.erase(it++);// 等价于 it = l.erase(it);}}3. list 的模拟实现
要模拟实现 list，必须熟悉它的底层结构以及每个接口的含义。
3.1 整体结构：哨兵节点 + 双向循环链表
下面是本次审查的手写实现的核心结构（略有删减，行号对应原始List.h）：
#pragmaonce#include<iostream>#include<assert.h>usingnamespacestd;namespacetx_list{template<typenameT>classlist_Node{friendclasslist<T>;public:list_Node(constT&value=T()):data(value),next(nullptr),prev(nullptr){}private:T data;// 数据域list_Node<T>*next;// 后继指针list_Node<T>*prev;// 前驱指针};template<typenameT>classlist{typedeflist_Node<T>Node;public:list(){empty_init();}// 拷贝构造list(constlist<T>&l){empty_init();for(auto&e:l)push_back(e);}// initializer_list 构造list(initializer_list<T>il){empty_init();for(auto&e:il)push_back(e);}// 拷贝赋值（copy-and-swap 惯用法）list<T>&operator=(list<T>lt){swap(lt);return*this;}~list(){clear();delete_head;_head=nullptr;}voidempty_init(){_head=newNode(T());// 创建哨兵节点_head->next=_head;// 哨兵的 next 指向自己_head->prev=_head;// 哨兵的 prev 指向自己_size=0;}private:Node*_head;// 哨兵节点size_t _size;};}设计要点：
- 哨兵节点（头结点）：不存有效数据，让所有插入/删除操作都不需要特判“空表/首尾”情况；
- 循环链表：
_head->next是第一个节点，_head->prev是最后一个节点； - copy-and-swap 赋值：
operator=(list<T> lt)按值传参先拷贝一份，再交换内部指针，天然保证异常安全和自赋值安全。
3.2 迭代器设计：list 的迭代器不是原生指针
vector底层是连续空间，迭代器可以用原生指针T*；但list的节点在内存中不连续，++/--必须“跳节点”，所以list 的迭代器是对节点指针的封装。
一个非常巧妙的做法是：用Ref和Ptr两个模板参数，让同一个模板同时生成iterator和const_iterator：
template<classT,classRef,classPtr>structlist_iterator{typedeflist_Node<T>Node;typedeflist_iterator<T,Ref,Ptr>Self;Node*_node;list_iterator(Node*node):_node(node){}Refoperator*(){return_node->_data;}Ptroperator->(){return&_node->_data;}Self&operator++(){_node=_node->_next;return*this;}Self&operator--(){_node=_node->_prev;return*this;}Selfoperator++(int){Selftmp(*this);_node=_node->_next;returntmp;}booloperator!=(constSelf&s)const{return_node!=s._node;}booloperator==(constSelf&s)const{return_node==s._node;}};然后在list里 typedef：
typedeflist_iterator<T,T&,T*>iterator;// 普通迭代器typedeflist_iterator<T,constT&,constT*>const_iterator;// const 迭代器3.3 关键接口实现
insert：在 pos 之前插入
voidinsert(iterator pos,constT&value){Node*newNode=newNode(value);Node*cur=pos._node;Node*prev=cur->prev;// 双向链表四步链接：prev <-> newNode <-> curprev->next=newNode;newNode->prev=prev;newNode->next=cur;cur->prev=newNode;_size++;}erase：删除 pos 指向的节点
voiderase(iterator pos){assert(pos!=end());// 不能删除哨兵节点Node*prev=pos._node->prev;Node*next=pos._node->next;prev->next=next;next->prev=prev;deletepos._node;_size--;}复用 insert/erase 实现 push/pop
voidpush_back(constT&value){insert(end(),value);}// 在哨兵前插入，即尾插voidpush_front(constT&x){insert(begin(),x);}// 在首节点前插入voidpop_back(){erase(--end());}// end() 前一个即尾节点4. list 与 vector 的对比
vector 与 list 都是 STL 中非常重要的序列式容器，由于两者底层结构不同，导致其特性及应用场景也不同。
| 维度 | vector | list |
|---|---|---|
| 底层结构 | 动态顺序表，一段连续空间 | 带头结点的双向循环链表 |
| 随机访问 | 支持随机访问，访问某个元素 O(1) | 不支持随机访问，访问某个元素 O(N) |
| 插入和删除 | 任意位置插入/删除效率低，需搬移元素 O(N)；插入时可能增容（开新空间、拷贝元素、释放旧空间） | 任意位置插入/删除效率高，不需搬移元素，O(1) |
| 空间利用率 | 底层连续空间，不易造成内存碎片，空间利用率高，缓存利用率高 | 节点动态开辟，小节点易造成内存碎片，空间利用率低，缓存利用率低 |
| 迭代器 | 原生指针 | 对原生指针（节点指针）进行封装 |
| 迭代器失效 | 插入可能因扩容使所有迭代器失效；删除时当前迭代器需重新赋值 | 插入不导致迭代器失效；删除只使当前迭代器失效，其他不受影响 |
| 使用场景 | 需要高效存储、支持随机访问、不关心插入删除效率 | 大量插入和删除操作、不关心随机访问 |
5. 总结
- list 的底层结构是带头结点的双向循环链表，因此任意位置插入/删除是 O(1)，但不支持随机访问（O(N)）。
- list 的迭代器是对节点指针的封装，
++/--实际是沿next/prev指针移动；用Ref/Ptr模板参数可以让一套代码同时生成iterator和const_iterator。 - 反向迭代器可以包装正向迭代器实现：反向
++= 正向--。 - list 的迭代器失效规则：插入不失效；删除只使“被删节点”对应的迭代器失效。删除遍历时要写
l.erase(it++);。 - 手写 list 的三个高频坑（本次审查发现的阻塞级问题）：
erase返回void却写了it = erase(it)，无法编译 ——erase应返回后继迭代器；- 迭代器访问节点私有成员但忘了声明友元；
- 后置
--误写为返回Self&，返回局部对象引用（悬垂引用）。
- vector vs list：随机访问、连续存储选
vector；频繁任意位置插入删除选list。
参考资料
- cplusplus.com - list
- cppreference.com - std::list
