【C++】：list容器的深度剖析及模拟实现
目录
- 前言
- 一，节点类
- 二，迭代器类
- 1，普通迭代器类的实现
- 2，->运算符的使用场景
- 3，const迭代器类的实现
- 4，通过模板参数，把两个类型的迭代器类结合
- 5，迭代器类的一些问题的思考
- 三，list 类
- 1，list类的结构
- 2，迭代器的实现
- 3，插入数据insert
- 4，删除数据erase
- 5，头插，头删，尾插，尾删
- 6，常见构造函数的实现
- 7，析构函数
前言
点击跳转到文章：【list的基本使用】
（图片来源网络，侵删）要模拟实现list，必须要熟悉list的底层结构以及其接口的含义，list的底层是带头双向循环链表，通过上一篇文章的学习，这些内容已基本掌握，现在我们来模拟实现list容器的主要接口。
与前面的vector类似，由于使用了模板，也只分成.cpp和.h两个文件。
.cpp文件里放节点类，迭代器类，list类及其成员函数，测试函数的实现，在.h文件里进行测试。
本文的重点是：对三个类的区分与理解，迭代器类的实现。
一，节点类
1.为什么定义节点结构体时使用struct而不是class?
答：(1)其实用class也可以，但是class与struct默认的访问限定不同，当没有声明公有，私有时，struct内容默认是公有，class内容默认的私有，所以用class要加上public。
(2)当我们用class没有加上public，也没有实例化对象时，编译不会报错(报私有成员的错误)，因为模版是不会被细节编译的。只有当我们实例化出对象，模版才会被编译，并且类的实例化并不是对所有成员函数都实例化，而是调用哪个成员函数就实例化哪个。这叫做按需实例化。
2.可用匿名对象初始化。如果T是自定义类型，则调用其默认构造，并且T是内置类型也升级成了有默认构造的概念了。
template struct ListNode { ListNode* _next; ListNode* _prev; T _data; ListNode(const T& data = T()) :_next(nullptr) ,_prev(nullptr) ,_data(data) {} };二，迭代器类
前面学习的string类和vector的迭代器用的是原生指针类型，即T*。但是在list容器中是不能这样的，因为前面两者的底层物理空间是连续的，符合迭代器++与- -的行为。但是list是由一个一个节点构成的，物理空间不连续，Node*的++和- -不符合迭代器的行为，无法变遍历。
所以用一个类把Node* 封装，就可以重载运算符，使得用起来像内置类型，但会转换成函数调用，继而控制Node*的行为。
1，普通迭代器类的实现
遍历需要的核心运算符重载是 *，!=，++ 和 ->。所以只需要利用带头双向循环链表的特性，对Node * 进行封装，从而控制Node * 的行为。
class ListIterator { typedef ListNode Node; typedef ListIterator Self;//名字变得简短 public: Node* _node;//定义一个节点指针 ListIterator(Node* node) :_node(node) {} //前置:返回之后的值 //++it;//返回与自己一样的类型 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; } T& operator*() { return _node->_data; } //返回的是数据的地址 T* operator->() { return &_node->_data; } bool operator!=(const Self& it) { return _node != it._node; } bool operator==(const Self& it) { return _node == it._node; } };2，->运算符的使用场景
假设某个场景下存在一个坐标类：
struct Pos { int _row; int _col; Pos(int row = 0,int col = 0) :_row(row) ,_col(col) {} };如果我们插入坐标，并且想要打印出坐标，该如何遍历？
错误示范：
void test_list2() { list lt1; lt1.push_back(Pos(100, 100));//使用匿名对象 lt1.push_back(Pos(200, 200)); lt1.push_back(Pos(300, 300)); //这里的it是Pos*,是结构体指针 list::iterator it = lt1.begin(); while (it != lt1.end()) { cout list //方式1： //cout list cout typedef ListNode} //前置:返回之后的值 //++it;//返回与自己一样的类型 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; } // 所以我们要再定义一个类，使用const控制*和-的返回值就可以 const T& operator*() { return _node-_data; } const T* operator-() { return &_node-_data; } bool operator!=(const Self& it) { return _node != it._node; } bool operator==(const Self& it) { return _node == it._node; } }; typedef ListNode} //前置:返回之后的值 //++it;//返回与自己一样的类型 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; } Ref operator*() { return _node-_data; } Ptr operator->() { return &_node->_data; } bool operator!=(const Self& it) { return _node != it._node; } bool operator==(const Self& it) { return _node == it._node; } };5，迭代器类的一些问题的思考
(1) 类中是否需要写析构函数？
这个迭代器类不要写析构函数，因为这里的节点不是迭代器的，是链表的，不用把它释放。我们使用begin，end返回节点给迭代器，是借助迭代器修改，访问数据，所以我们不需要释放。
(2) 类中是否需要写拷贝构造进行深拷贝和写赋值拷贝？
这里也不需要写拷贝构造进行深拷贝，因为这里要的就是浅拷贝。begin返回了第一个节点的迭代器给it，这里就是用默认生成的拷贝构造，浅拷贝给it，那这两个迭代器就指向同一个节点，所以这里用默认的拷贝构造和赋值拷贝就可以了。
三，list 类
1，list类的结构
template class list { typedef ListNode Node; public: //物理空间不是连续的，不符合迭代器的行为，无法遍历 //typedef Node* iterator; //规范命名 //typedef ListIterator iterator; //typedef ListConstIterator const_iterator; typedef ListIterator iterator; typedef ListIterator const_iterator; //……………… private: Node* _head; };2，迭代器的实现
包含普通迭代器和const迭代器。
iterator begin() { //iterator it(_head->_next); //return it; 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); }3，插入数据insert
iterator insert(iterator pos, const T& x) { Node* cur = pos._node;//找到当前节点 Node* newnode = new Node(x);//申请节点 Node* prev = cur->_prev;//找到前一个节点 //prev newnode cur 进行链接 newnode->_next = cur; cur->_prev = newnode; prev->_next = newnode; newnode->_prev = prev; return iterator(newnode); }注意：链表的insert没有迭代器失效问题，因为没有扩容的概念，pos位置的节点不会改变。但是STL库里insert也给了返回值，返回的是新插入位置的迭代器。
4，删除数据erase
iterator erase(iterator pos) { assert(pos != end());//防止删除头节点 Node* cur = pos._node;//找到当前节点 Node* prev = cur->_prev;//找到前一个节点 Node* next = cur->_next;//找到后一个节点 prev->_next = next; next->_prev = prev; delete cur; return iterator(next); }注意：链表的erase后有迭代器失效问题，pos失效了，因为pos指向的节点被释放了。所以也要返回值，返回的是删除节点的下一个节点的迭代器。
5，头插，头删，尾插，尾删
可以复用前面的 insert和 erase 。
//尾插:end()的下一个位置 void push_back(const T& x) { //Node* newnode = new Node(x);//申请节点并且初始化 //Node* tail = _head->_prev; 链接节点 //tail->_next = newnode; //newnode->_prev = tail; //_head->_prev = newnode; //newnode->_next = _head; insert(end(), x); } //尾删 void pop_back() { erase(--end());//注意：前置-- } //头插:在begin前面插入 void push_front(const T& x) { insert(begin(), x); } //头删 void pop_front() { erase(begin()); }6，常见构造函数的实现
主要包含：构造函数，拷贝构造，initializer_list构造(列表构造)。
注意：由于这些都是在有哨兵位节点的前提下实现的，所以可以把申请哨兵位头节点这一步骤提取出来。
//空初始化，申请哨兵位头节点 void empty_init() { _head = new Node(); _head->_next = _head; _head->_prev = _head; } list() { empty_init(); } //拷贝构造:直接复用尾插，前提要有哨兵位头节点 //lt2(lt1) list(const list& lt) { empty_init(); //注意：使用范围for时加上const和& for (const auto& e : lt) { push_back(e); } } //initializer_list构造，前提要有哨兵位头节点 list(initializer_list il) { empty_init(); for (const auto& e : il) { push_back(e); } }7，析构函数
析构函数的作用是：删除整个链表结构，包括哨兵位节点。
//清空当前数据 留头节点，其余节点释放 void clear() { auto it = begin(); while (it != end()) { //返回删除节点的下一个节点的迭代器 it = erase(it); } } //析构：销毁整个链表 ~list() { clear(); delete _head; _head = nullptr; }
