本节博客先对list进行用法介绍，再在库的基础上简化其内容和形式，简单进行模拟实现，有需要借鉴即可。
目录
- 1.list介绍
- 1.1 list概述
- 1.2相关接口的介绍
- 2.简化模拟实现
- 3.各部分的细节详述
- 3.1结点
- 3.2迭代器
- 细节1：迭代器用原生指针还是专门设计为类的问题
- 细节2：迭代器++、--行为重载的返回类型问题
- 细节3：迭代器解引用返回类型
- 细节4：迭代器operator->重载
- 3.3链表
- 细节1：list中提供begin和end函数的理由和返回类型？
- 细节2：插入元素代码
- 细节3：删除元素代码
- 细节4：clear()函数和析构函数
- 细节5：拷贝构造函数与赋值运算符重载
- 细节6：insert返回为void？
- 4.总结
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);}// 拷贝vectorint begin1 = clock();vector<int> v(lt2.begin(), lt2.end());// 排序sort(v.begin(), v.end());// 拷贝回lt2lt2.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已经变了}//*itRef 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 = lt3list<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
