本节博客先对list进行用法介绍，再在库的基础上简化其内容和形式，简单进行模拟实现，有需要借鉴即可。
1.list介绍
1.1 list概述
1.概述：list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2. 底层实现：list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
3. list与forward_list区别：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
4. list的优势：与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
5. list的缺陷：与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)
我们用代码来体会一下list的缺点：
void test_op1() { srand(time(0)); const int N = 1000000;//一百万数据 //两个链表 list<int> lt1; list<int> lt2; //一个顺序表 vector<int> v; //生成随机数据，尾插到链表1和顺序表v中去 for (int i = 0; i < N; ++i) { auto e = rand()+i;//加上这个i主要是为了减少重复数字概率 lt1.push_back(e); v.push_back(e); } //vector排序 int begin1 = clock(); sort(v.begin(), v.end()); int end1 = clock(); //list排序 int begin2 = clock(); lt1.sort(); int end2 = clock(); //打印比较两者用时 printf("vector sort:%d\n", end1 - begin1); printf("list sort:%d\n", end2 - begin2); }
void test_op2() { srand(time(0)); const int N = 1000000; list<int> lt1; list<int> lt2; for (int i = 0; i < N; ++i) { auto e = rand(); lt1.push_back(e); lt2.push_back(e); } // 拷贝vector int begin1 = clock(); vector<int> v(lt2.begin(), lt2.end()); // 排序 sort(v.begin(), v.end()); // 拷贝回lt2 lt2.assign(v.begin(), v.end()); int end1 = clock(); //lt1排序 int begin2 = clock(); lt1.sort(); int end2 = clock(); //打印 printf("list copy vector sort copy list sort:%d\n", end1 - begin1); printf("list sort:%d\n", end2 - begin2); }
1.2相关接口的介绍
2.简化模拟实现
通过去查看stl中list.h的源码我们可以知道，list是通过一个_head的Node*指针进行维护的，而其中广泛使用迭代器进行传值和访问数据。下面对其先直接摆代码，然后对其中细节进行详细介绍。
#pragma once #include<assert.h> #include<iostream> namespace zzg { template<typename T> struct ListNode { ListNode<T>* _next;//这个地方为什么类型不是T*？？？答：因为我们指针是需要指向一个ListNode<T>*类型的，而非T类型。 ListNode<T>* _prev; T _data; //ListNode有参构造 ListNode(const T& x = T()) :_next(nullptr) ,_prev(nullptr) , _data(x) {} }; template<class T, class Ref, class Ptr> class list_iterator { typedef struct ListNode<T> Node; typedef list_iterator<T, Ref, Ptr> Self; public: Node* _node; public: //带参构造 list_iterator(Node* node)//这个地方用值拷贝，用引用会有bug :_node(node) {} //++ Self& operator++() { _node = _node->_next; return *this; } Self operator++(int)//后置++ { Self temp = *this;//拷贝构造一份，这时候会调用编译器自动生成的拷贝构造，为浅拷贝，但是需求满足了。 _node = _node->_next; return temp;//这个地方得返回值了，因为现在的Self已经变了 } //-- Self& operator--() { _node = _node->_prev; return *this; } Self operator--(int)//后置-- { Self temp = *this;//拷贝构造一份，这时候会调用编译器自动生成的拷贝构造，为浅拷贝，但是需求满足了。 _node = _node->_prev; return temp;//这个地方得返回值了，因为现在的Self已经变了 } //*it Ref operator*() { return _node->_data; } //!= bool operator!=(const Self& it) { return _node != it._node; } //== bool operator==(const Self& it) { return _node == it._node; } //->重载 Ptr operator->() { return &_node->_data; } }; //template<typename T> //class list_const_iterator //{ // typedef struct ListNode<T> Node; // typedef list_const_iterator<T> Self; //public: // Node* _node; //public: // //带参构造 // list_const_iterator(Node* node)//这个地方用值拷贝，用引用会有bug // :_node(node) // {} // //++ // Self& operator++() // { // _node = _node->_next; // return *this; // } // Self operator++(int)//后置++ // { // Self temp = *this;//拷贝构造一份，这时候会调用编译器自动生成的拷贝构造，为浅拷贝，但是需求满足了。 // _node = _node->_next; // return temp;//这个地方得返回值了，因为现在的Self已经变了 // } // //-- // Self& operator--() // { // _node = _node->_prev; // return *this; // } // Self operator--(int)//后置-- // { // Self temp = *this;//拷贝构造一份，这时候会调用编译器自动生成的拷贝构造，为浅拷贝，但是需求满足了。 // _node = _node->_prev; // return temp;//这个地方得返回值了，因为现在的Self已经变了 // } // //*it // const T& operator*() // { // return _node->_data; // } // //!= // bool operator!=(const Self& it) // { // return _node != it._node; // } // //== // bool operator==(const Self& it) // { // return _node == it._node; // } // //->重载 // const T* operator->() // { // return &_node->_data; // } //}; template<typename T> class list { public: typedef list_iterator<T, T&, T*> iterator; typedef list_iterator<T, const T&, const T*> const_iterator; typedef struct ListNode<T> Node; private: Node* _head;//头节点 public: //无参构造函数 list() { empty_init(); } //拷贝构造 list(const list<T>& lt) { empty_init(); for (auto& e : lt) { push_back(e); } } // lt1 = lt3 list<T>& operator=(list<T> lt)//先调用拷贝构造，构造出一个lt来 { swap(lt);//然后交换这个局部变量与this，原this中是其他的东西 return *this;//返回this本身 } void empty_init() { _head = new Node; _head->_next = _head; _head->_prev = _head; } //清理函数 void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } } //析构函数 ~list() { clear(); delete _head; _head = nullptr; } iterator begin() { return _head->_next;//隐式类型转换 //return iterator(_head->_next); } iterator end() { return _head;//隐式类型转换 //return iterator(_head); } //const + 迭代器 --> 迭代器本身不可修改 //我们需要的：迭代器指向的内容不可修改 const T*类型 而不是 T* const类型 //如果我们直接在一般迭代器前面+const,即const iterator --> 该迭代器不可修改，因为这是一个自定义类 //解决，直接再单独一个自定义const迭代器类出来 const_iterator begin() const { return _head->_next;//return iterator(_head->_next); } const_iterator end() const { return _head;//return iterator(_head); } //尾插 void push_back(const T& x) { insert(end(), x); } //头插 void push_front(const T& x) { insert(begin(), x); } //void push_back(const T& x) //{ // Node* newnode = new Node(x); // //找到尾巴 // Node* tail = _head->_prev; // tail->_next = newnode;//链接临近两点 // newnode->_prev = tail; // newnode->_next = _head; // _head->_prev = newnode; //} //任意插入 void insert(iterator pos, const T& val) { Node* cur = pos._node; Node* prev = cur->_prev; Node* newnode = new Node(val); prev->_next = newnode; newnode->_prev = prev; newnode->_next = cur; cur->_prev = 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; return iterator(next); } //尾删 void pop_back() { erase(--end()); } //头删 void pop_front() { erase(begin()); } }; struct A { public: int _a; int _b; A(int a = 0, int b = 0) { _a = a; _b = b; } }; //测试函数 void test_list1() { /*list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); lt.push_back(6); lt.pop_back(); lt.pop_back(); lt.pop_back(); list<int>::iterator it = lt.begin(); while (it != lt.end()) { std::cout << *it << " "; it++; } std::cout << std::endl;*/ list<A> Al; Al.push_back({ 1,1 }); Al.push_back({ 2,2 }); Al.push_back({ 3,3 }); Al.push_back({ 4,4 }); Al.push_back({ 5,5 }); Al.push_back({ 6,6 }); list<A>::iterator it = Al.begin(); while (it != Al.end()) { //std::cout << (*it)._a << '/' << (*it)._b << std::endl; std::cout << it->_a << '/' << it->_b << std::endl;//it->_a ---> it->->_a == it.operator->()->_a; it++; } std::cout << std::endl; } }
3.各部分的细节详述
主要包含三个部分，一是整体的链表类，二是链表中的每个元素结点类，还有就是用来访问修改结点的迭代器类。
下面分开进行细节介绍。
3.1结点
每个结点我们很熟悉，无非是两个指针和一个数据，一个指针指向它前面的结点，另一个指向其后面的结点，数据中放具体元素的值。
下面是基本结构框架：
template<typename T> struct ListNode { ListNode<T>* _next;//这个地方为什么类型不是T*？？？答：因为我们指针是需要指向一个ListNode<T>*类型的，而非T类型。 ListNode<T>* _prev; T _data; //ListNode有参构造 ListNode(const T& x = T()) :_next(nullptr) ,_prev(nullptr) , _data(x) {} };
细节：
- 使用struct，标注为公有属性，方便外部调用
- list是带头双向循环链表，因而每个结点要有两个指针
- 提供全缺省的默认构造函数
思考：每个结点的两个指针为什么是ListNode*类型而不是T*类型呢？
答：因为我们每个结点的指针指向的是一个结点，T仅仅是一个结点中的数据而已。
3.2迭代器
template<class T, class Ref, class Ptr> class list_iterator { typedef struct ListNode<T> Node; typedef list_iterator<T, Ref, Ptr> Self; public: Node* _node; public: //带参构造 list_iterator(Node* node)//这个地方用值拷贝，用引用会有bug :_node(node) {} }
细节1：迭代器用原生指针还是专门设计为类的问题
思考：list迭代器为什么要专门设置一个类？？？
答：
这是由于list的每个节点物理空间不连续，导致迭代器不能像之前string\vector那样简单的设计为原生指针，而是设计为一个类，以此来扩大我们对迭代器行为控制权限，重新设计*，->,++等操作。
vector，string原生指针充当迭代器：
像之前string，vector这种容器，其原生指针T*就是天然的迭代器，因为++就会自动指向到下一个数据，*引用也是拿到的我们想要的数据。
但是在list中，我们++T*，很明显由于地址不连续的缘故，压根不知道会指向的是什么(大概率会是随机值)。
但是需要重点注意的是，我们所设计的迭代器类是模拟的string/vector中T*的动作。
细节2：迭代器++、–行为重载的返回类型问题
//++ Self& operator++() { _node = _node->_next; return *this; } Self operator++(int)//后置++ { Self temp = *this;//拷贝构造一份，这时候会调用编译器自动生成的拷贝构造，为浅拷贝，但是需求满足了。 _node = _node->_next; return temp;//这个地方得返回值了，因为现在的Self已经变了 } //-- Self& operator--() { _node = _node->_prev; return *this; } Self operator--(int)//后置-- { Self temp = *this;//拷贝构造一份，这时候会调用编译器自动生成的拷贝构造，为浅拷贝，但是需求满足了。 _node = _node->_prev; return temp;//这个地方得返回值了，因为现在的Self已经变了 }
思考：为什么前置++返回的是类对象引用，而后置++返回类型是一般类型？
答：这要结合函数设计来看，在前置++中，我们返回的是类本身；而后置++，我们返回的是一个局部的类对象，局部类对象在出函数后会自动销毁。
细节3：迭代器解引用返回类型
//*it Ref operator*() { return _node->_data; }
注：
//iterator: typedef list_iterator<T, Ref, Ptr> Self; //list: typedef list_iterator<T, T&, T*> iterator; typedef list_iterator<T, const T&, const T*> const_iterator;
返回Ref，用来区分const_iterator 和 iterator。
思考：为什么不重载const iterator?
答：const + 类 --> 表示该指针不可修改，并非我们所期望的指针指向内容不可修改。
思考：iterator 与 const_iterator 是同一个类吗？
答：不是。是利用同一份类模板生成的完全不同两份类。
细节4：迭代器operator->重载
//->重载 Ptr operator->() { return &_node->_data; }
注：
//iterator: typedef list_iterator<T, Ref, Ptr> Self; //list: typedef list_iterator<T, T&, T*> iterator; typedef list_iterator<T, const T&, const T*> const_iterator;
struct A { public: int _a; int _b; A(int a = 0, int b = 0) { _a = a; _b = b; } }; main: list<A> Al; Al.push_back({ 1,1 }); Al.push_back({ 2,2 }); Al.push_back({ 3,3 }); Al.push_back({ 4,4 }); Al.push_back({ 5,5 }); Al.push_back({ 6,6 }); list<A>::iterator it = Al.begin(); while (it != Al.end()) { //std::cout << (*it)._a << '/' << (*it)._b << std::endl; std::cout << it->_a << '/' << it->_b << std::endl;//it->_a ---> it->->_a == it.operator->()->_a; it++; } std::cout << std::endl;
为了可读性，编译器把it->->_a优化为了it->_a
思考：上述代码的it->->_a代表了什么？
答：it->_a —> it->->_a == it.operator->()->_a;，这里在编译器写法上理论上应该写两个箭头的，一个用于运算符重载函数的调用，另一个是为了进入到指针里面访问数据，这里编译器为了可读性将其优化为了一个箭头。
3.3链表
链表类主要结构如下：
template<typename T> class list { public: typedef list_iterator<T, T&, T*> iterator; typedef list_iterator<T, const T&, const T*> const_iterator; typedef struct ListNode<T> Node; //无参构造函数 list() { empty_init(); } void empty_init() { _head = new Node; _head->_next = _head; _head->_prev = _head; } private: Node* _head;//头节点 }
细节1：list中提供begin和end函数的理由和返回类型？
iterator begin() { return _head->_next;//隐式类型转换 //return iterator(_head->_next); } iterator end() { return _head;//隐式类型转换 //return iterator(_head); } //const + 迭代器 --> 迭代器本身不可修改 //我们需要的：迭代器指向的内容不可修改 const T*类型 而不是 T* const类型 //如果我们直接在一般迭代器前面+const,即const iterator --> 该迭代器不可修改，因为这是一个自定义类 //解决，直接再单独一个自定义const迭代器类出来 const_iterator begin() const { return _head->_next;//return iterator(_head->_next); } const_iterator end() const { return _head;//return iterator(_head); }
思考：list提供begin和end的原因：
答：
1._head是私有的。
2.更加方便的使用迭代器，在上面代码我们可以发现，返回的都是迭代器类型。
返回迭代器类型的原因：
与后面使用迭代器相兼容。
细节2：插入元素代码
//尾插 void push_back(const T& x) { insert(end(), x); } //头插 void push_front(const T& x) { insert(begin(), x); } //void push_back(const T& x) //{ // Node* newnode = new Node(x); // //找到尾巴 // Node* tail = _head->_prev; // tail->_next = newnode;//链接临近两点 // newnode->_prev = tail; // newnode->_next = _head; // _head->_prev = newnode; //} //任意插入 void insert(iterator pos, const T& val) { Node* cur = pos._node; Node* prev = cur->_prev; Node* newnode = new Node(val); prev->_next = newnode; newnode->_prev = prev; newnode->_next = cur; cur->_prev = newnode; }
细节3：删除元素代码
//任意删除 iterator erase(iterator pos) { Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; prev->_next = next; next->_prev = prev; delete cur; return iterator(next); } //尾删 void pop_back() { erase(--end()); } //头删 void pop_front() { erase(begin()); }
思考：为什么erase()要返回迭代器类型？？？
答：因为要及时对外更新迭代器指针，防止迭代器失效。
思考：为什么pop_back()没有返回迭代器类型？
答：因为pop_back()不会对外接收迭代器，不存在对外更新迭代器问题。但是erase是接收迭代器的，因而要及时更新。
思考：–end()是否会影响到_head，为什么？
答：会影响到，但是影响到的是_head的值拷贝，没有影响到“母体”。
细节4：clear()函数和析构函数
void empty_init() { _head = new Node; _head->_next = _head; _head->_prev = _head; } //清理函数 void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } } //析构函数 ~list() { clear(); delete _head; _head = nullptr; }
细节5：拷贝构造函数与赋值运算符重载
//拷贝构造 list(const list<T>& lt) { empty_init(); for (auto& e : lt) { push_back(e); } }
// lt1 = lt3 list<T>& operator=(list<T> lt)//先调用拷贝构造，构造出一个lt来 { swap(lt);//然后交换这个局部变量与this，原this中是其他的东西 return *this;//返回this本身 }
思考：为什么赋值运算符重载函数参数用list lt而不是引用呢？
答：复用拷贝构造函数，是为现代写法。
细节6：insert返回为void？
//任意插入 void insert(iterator pos, const T& val) { Node* cur = pos._node; Node* prev = cur->_prev; Node* newnode = new Node(val); prev->_next = newnode; newnode->_prev = prev; newnode->_next = cur; cur->_prev = newnode; }
在string中insert我们返回的是迭代器，但是这里为什么返回值是void呢？
答：因为string是连续空间，插入数据会挪动数据，造成迭代器失效。但是链表是由结点链接而成，插入数据不会挪动数据，不会造成迭代器失效问题。
在vector中 insert/erase因为增删都会牵扯到数据挪动问题，两个函数肯定都要去返回迭代器来更新外部迭代器。
但是对于list，insert不会挪动数据因而不会失效，但是erase时候，原结点被删除，会造成迭代器失效。
4.总结
list模拟实现核心就是一个类迭代器的实现，相比之前string、vector，list迭代器更值得细细思考与总结。
list模拟实现还一个难点在于使用类模板，应注意类模板问题。
EOF
