前言：
C++中的List容器是标准模板库（STL）中的一种序列容器，它实现了双向链表的功能。与数组（如vector）和单向链表相比，List容器提供了更加灵活的元素插入和删除操作，特别是在容器中间位置进行这些操作时。
一.list的介绍及使用
1. list的介绍
- 双向链表结构： list容器使用双向链表来存储元素，每个元素（节点）都包含数据部分和两个指针，分别指向前一个元素和后一个元素。这种结构使得在链表的任何位置进行插入和删除操作都非常高效，时间复杂度为
O(1)。 - 动态大小： list容器的大小可以在运行时动态改变，即可以在程序运行过程中添加或移除元素。
- 不支持随机访问： 与
vector和array等连续内存的容器不同，list不支持随机访问迭代器，不能直接通过索引获取元素，而需要通过迭代器遍历。 - 迭代器稳定性： 在list中插入或删除元素不会导致其他迭代器失效（除了指向被删除元素的迭代器）。这是因为它通过调整相邻节点的指针来维护链表结构，而不需要移动元素或重新分配内存。
2. list的使用
list的使用参考文档：list的文档介绍
2.1 list的构造
代码演示：
#include<list>intmain(){
list<int> l1;//构造空的l1;
list<int>l2(4,100);//l2中存放4个值为100的元素
list<int>l3(l2.begin(),l2.end());//用l2的[begin,end）左开右闭区间构造l3;
list<int>l4(l3);//用l3拷贝构造l4// 以数组为迭代器区间构造l5int array[]={16,2,77,29};
list<int>l5(array, array +sizeof(array)/sizeof(int));// 列表格式初始化C++11
list<int> l6{1,2,3,4,5};// 用迭代器方式打印l5中的元素
list<int>::iterator it = l5.begin();while(it != l5.end()){
cout <<*it <<" ";++it;}
cout << endl;// C++11范围for的方式遍历for(auto& e : l5)
cout << e <<" ";
cout << endl;return0;}2.2 list iterator的使用
此处，大家可暂时将迭代器理解成一个指针，该指针指向list中的某个节点。
注意：
- begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
- rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动
代码演示：
intmain(){int array[]={1,2,3,4,5,6,7,8,9,0};
list<int>l(array, array +sizeof(array)/sizeof(array[0]));// 使用正向迭代器正向list中的元素// list<int>::iterator it = l.begin(); // C++98中语法auto it = l.begin();// C++11之后推荐写法while(it != l.end()){
cout <<*it <<" ";++it;}
cout << endl;// 使用反向迭代器逆向打印list中的元素// list<int>::reverse_iterator rit = l.rbegin();auto rit = l.rbegin();while(rit != l.rend()){
cout <<*rit <<" ";++rit;}
cout << endl;return0;}2.3 list capacity
2.4 list element access
2.5 list modifiers
代码演示：
#include<iostream>#include<vector>usingnamespace std;voidPrintList(const list<int>& l){// 注意这里调用的是list的 begin() const，返回list的const_iterator对象for(list<int>::const_iterator it = l.begin(); it != l.end();++it){
cout <<*it <<" ";}
cout << endl;}// list插入和删除// push_back/pop_back/push_front/pop_frontvoidTestList1(){int array[]={1,2,3};
list<int>L(array, array +sizeof(array)/sizeof(array[0]));// 在list的尾部插入4，头部插入0
L.push_back(4);
L.push_front(0);PrintList(L);// 删除list尾部节点和头部节点
L.pop_back();
L.pop_front();PrintList(L);}// insert /erase voidTestList2(){int array1[]={1,2,3};
list<int>L(array1, array1 +sizeof(array1)/sizeof(array1[0]));// 获取链表中第二个节点auto pos =++L.begin();
cout <<*pos << endl;// 在pos前插入值为4的元素
L.insert(pos,4);PrintList(L);// 在pos前插入5个值为5的元素
L.insert(pos,5,5);PrintList(L);// 在pos前插入[v.begin(), v.end)区间中的元素
vector<int> v{7,8,9};
L.insert(pos, v.begin(), v.end());PrintList(L);// 删除pos位置上的元素
L.erase(pos);PrintList(L);// 删除list中[begin, end)区间中的元素，即删除list中的所有元素
L.erase(L.begin(), L.end());PrintList(L);}// resize/swap/clearvoidTestList3(){// 用数组来构造listint array1[]={1,2,3};
list<int>l1(array1, array1 +sizeof(array1)/sizeof(array1[0]));PrintList(l1);// 交换l1和l2中的元素
list<int> l2;
l1.swap(l2);PrintList(l1);PrintList(l2);// 将l2中的元素清空
l2.clear();
cout << l2.size()<< endl;}intmain(){TestList1();TestList2();TestList3();return0;}运行结果：
2.6 list的迭代器失效
前面已经说过了，此处可以将迭代器理解为类似于指针的东西，迭代器失效即迭代器指向的节点失效了，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list进行插入操作时不会导致迭代器失效，只有删除时才会失效，并且失效的是被删除节点的迭代器，其他迭代器不会受到影响。
二.list的模拟实现
1. list的节点
template<classT>structlist_node{
T _data;
list_node<T>* _next;
list_node<T>* _prev;list_node(const T& x =T()):_data(x),_next(nullptr),_prev(nullptr){}};2. list的成员变量
template<classT>classlist{typedef list_node<T> Node;public://成员函数private:
Node* _head;//哨兵位的头节点}; 没有用访问限定符限制的成员class默认是私有的，struct默认是公有的，如果一个类既有公有也有私有就用class，全部为公有一般用struct。这不是规定，只是个惯例。
3.list迭代器相关问题
简单分析：
&emsp； 这里不能像以前一样给一个结点的指针作为迭代器，如果it是typedef的节点的指针，it解引用得到的是节点，不是里面的数据，但是我们期望it解引用是里面的数据，++it我们期望走到下一个节点去，而list中++走不到下一个数据，因为数组的空间是连续的，++可以走到下一个数据。但是链表达不到这样的目的。所以原身指针已经无法满足这样的行为，怎么办呢？这时候我们的类就登场了
用类封装一下节点的指针，然后重载运算符，模拟指针。
例如：
reference operator*()const{return(*node).data;}
self& opertor++(){
node =(link_type)((*node).next);return*this;}3.1 普通迭代器
template<classT>structlist_iterator{typedef list_node<T> Node;typedef list_iterator<T> Self;
Node* _node;list_iterator(Node* node):_node(node){}
T&operator*()//用引用返回可以读数据也可以修改数据{return _node->_data;}
T*operator->(){return&_node->_data;}
Self&operator++(){
_node = _node->_next;return*this;}
Self&operator--(){
_node = _node->_prev;return*this;}
Self operator++(int){
Self tmp(*this);
_node = _node->_next;return tmp;}
Self operator--(int){
Self tmp(*this);
_node = _node->_prev;return tmp;}booloperator!=(const Self& s){return _node != s._node;}};3.2 const迭代器
const迭代器在定义的时候不能直接定义成typedef const list_iterator<T> const_iterator,const迭代器的本质是限制迭代器指向的内容不能被修改，而前面的这种写法限制了迭代器本身不能被修改，所以迭代器就不能进行++操作。那该怎能办呢？答案是我们可以实现一个单独的类：
template<classT>structlist_const_iterator{typedef list_node<T> Node;typedef list_const_iterator<T> Self;
Node* _node;list_const_iterator(Node* node):_node(node){}const T&operator*(){return _node->_data;//返回这个数据的别名，但是是const别名，所以不能被修改}const T*operator->(){return&_node->_data;//我是你的指针，const指针}
Self&operator++(){
_node = _node->_next;return*this;}
Self&operator--(){
_node = _node->_prev;return*this;}
Self operator++(int){
Self tmp(*this);
_node = _node->_next;return tmp;}
Self operator--(int){
Self tmp(*this);
_node = _node->_prev;return tmp;}booloperator!=(const Self& s){return _node != s._node;}};普通法迭代器与const迭代器的区别就是：普通迭代器可读可写，const迭代器只能读
上面是我们自己实现的普通迭代器和const迭代器，用两个类，并且这两个类高度相似，下来就让我们一起看一看库里面是怎么实现的吧！
我们可以看到库里面是写了两个模板，让编译器去生成对应的类。其本质上也是写了两个类，只不过是让编译器去生成对应的类。
迭代器不需要我们自己写析构函数、拷贝构造函数、赋值运算符重载函数，因为这里要的是浅拷贝，例如我把一个迭代器赋值给另外一个迭代器，就是期望两个迭代器指向同一个节点，这里用浅拷贝即可，拷贝给你我们两个迭代器就指向同一个节点。
4. list的成员函数
4.1 list的空初始化
voidempty_init()//空初始化{
_head =newNode();
_head->_next = _head;
_head->_prev = _head;}4.2 push_back
//普通版本voidpush_back(const T& x){
Node* new_node =newNode(x);
Node* tail = _head->_prev;
tail->_next = new_node;
new_node->_prev = tail;
new_node->_next = _head;
_head->_prev = new_node;}//复用insert版本insert(end(),x);4.3 构造函数
list_node(const T& x =T()):_data(x),_next(nullptr),_prev(nullptr){}4.4 insert
iterator insert(iterator position;const T& val){
Node* cur = pos._node;
Node* newnode =newNode(val);
Node* prev = cur->_prev;//prev newnode cur
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;returniterator(newnode);}4.4 erase
iterator erase(iterator pos){assert(pos !=end());
Node* del = pos._node;
Node* prev = del->_prev;
Node* next = del->_next;
prev->_next = next;
next->_prev = prev;delete del;returniterator(next);}4.5 push_front
voidpush_front(const T& x){insert(begin(), x);}4.6 pop_front
voidpop_front(){erase(begin());}4.7 pop_back
voidpop_back(){erase(--end());}4.8 clear
voidclear(){auto it =begin();while(it !=end()){
it =erase(it);}}4.8 析构函数
~list(){clear();delete _head;
_head =nullptr;}4.9 swap
voidswap(list<T>& tmp){
std::swap(_head, tmp._head);//交换哨兵位的头节点}4.10 赋值运算符重载
//现代写法//lt2=lt3//list<T>& operator=(list<T> lt)
list&operator=(list lt)//不加模板参数{swap(lt);//交换就是交换哨兵位的头节点return*this;}//lt3传给lt去调用拷贝构造，所以lt就和lt3有一样大的空间一样大的值，lt2很想要，也就是/this想要，lt2之前的数据不想要了，交换给lt,此时lt2就和lt3有一样大的空间一样大的值，//lt出了作用域就被销毁了构造函数和赋值运算符重载函数的形参和返回值类型可以只写类名 list，不需要写模板参数，这种写法在类里面可以不加，只能在类里面可以这样写，类外面是不行的，一般情况下加上好一点。
最后想说：
本章我们STL的List就介绍到这里，下期我将介绍关于stack和queue的有关知识，如果这篇文章对你有帮助，记得，最后别忘了关注作者，作者将带领你探索更多关于C++方面的问题。