💪 今日博客励志语录：
当你觉得累的时候，说明你在走上坡路
★★★ 本文前置知识：
模版
那么在之前的学习中，我们已经学习了string和vector这两种容器，而今天我们要学的新的容器便是我们的list，那么有了之前学习string以及vector这两个容器的基础，那么对于上手list来说，那么想必也是不那么困难，因为stl规定每一个容器的很多的成员函数是相似的，那么废话不多说，让我们进入list的学习
1.引入
那么list这个容器其实对我们来说并不陌生，那么list的本质其实就是我们的链表，而这里的list的底层则是采取的带头双向循环链表来实现的，那么所谓的带头双向循环链表，就是会有一个哨兵节点，哨兵节点作为头节点，但是其并不存储任何有效的数据，它的作用只是为了能够让我们访问定位到该链表，而该链表中的每一个节点具有两个指针域，分别指向逻辑上相邻的前驱节点以及后继节点，并且该链表的最后一个节点还会与哨兵节点相连，这也是它的名字为什么带有循环两个字，那么带头双向循环链表的这一个结构，我们就可以形象的用一圈环形的跑道到来理解，那么起点线位置处就是我们的哨兵节点，那么终点位置处就在起点位置处后方
那么正是由于list采取的是带头双向循环链表，所以能够让我们访问链表中的节点可以向前或者向后访问，而不是像单链表那样的只能单向的遍历，那么这就是带头双向循环链表的优势，也是为什么c++的设计者选择用带头双向循环链表作为我们list的底层实现而不是采取单链表或者双向不循环链表，那么知道了list的底层是采取的何种数据结构还不够，那么我们要完整的了解与掌握list，那么我们就得知道list的三个方面的内容，分别是list的成员变量以及list的成员函数以及list的迭代器，那么接下来后文的内容我会分为两个维度来解析list，分别是list本身的成员变量以及函数的介绍和list的模拟实现也就是尝试自己造一个list，那么一旦你成功模拟实现了list，那么你就可以更为熟悉以及使用list
list成员变量
我们知道list的底层是采取的带头双向循环链表，那么上文我们介绍了带头双向循环链表，那么我们要访问带头双向循环链表，那么我们只需要知道一个节点的地址即可，那么该节点就是哨兵节点，而这也就是哨兵节点的作用，就是用来定位以及访问该带头双向循环链表，所以它不存储任何的数据，而list的类中就只有一个成员变量，那么便是哨兵节点的地址，也就是维护一个指向该带头双向循环链表的哨兵节点的指针，那么我们访问遍历该带头双向循环链表，那么就只能从哨兵节点位置开始，可以沿着两个方向，要么往前遍历，要么往后遍历
那么这里list是一个模版类，其中封装了关于围绕带头双向循环链表增删改查等功能的成员函数和一个指向一个哨兵节点的指针，但是我们却发现这里list内部还缺少了一个东西，那么就是关于该带头双向循环链表的节点，我们并没有给出节点的定义，因为list是一个模版类，那么到时候它会被编译器实例化，编译器会识别在代码中list对象存储的数据类型从而根据模版然后实例化对应的一个list类，但是由于list类内部只有一个指向节点的指针，那么到时候编译器在实例化该模版类的时候，肯定会寻找该节点的定义，所以这里就需要我们给出节点的定义，并且对于节点来说，我们也要定义成模版，因为到时候节点究竟存储的是哪种数据类型的数据，那么我们并不清楚，所以需要我们定义一个节点的模版类，那么我们定义节点的模版类有两种方式，那么第一种方式就是我们利用模版的嵌套，也就是在list模版类内部再嵌套定义一个list_node模版类，这种方式可行是可行，到时候实例化list模版类的同时会先实例化list_node模版类，但是对于我来说，我更喜欢第二种方式，便是将list_node单独声明成一份独立的模版，而我们的list的模版类中就定义一个指向list_node模版类的节点的指针
那么这种方式就需要我们注意一个细节，那么一旦我们的模版内部使用了外部定义的模版函数或者模版类，那么此时使用了外部模版的该模版类或者函数便作为主模版，当我们编译器是实例化主模版的时候，那么编译器并不是立刻实例化，因为编译器知道，在主模版中可能会用到外模版的函数或者类，所以这里编译器会采取先优先实例化外模版的函数或者类，如果外模版还使用了其他的外模版，那么编译器会构建一棵实例化树，最后再来实例化主模版，所以这里在定义的时候，就要求我们使用外模版的函数或者类，那么我们一定要在后面加模版参数，比如我们的外模版是一个list_node类，那么list类中的成员变量使用了list_node外模版类作为其数据类型，那么这里我们list类中声明该成员变量的时候，一定得是：
template<typename T> class list_node { }; template<typename T> class list { list_node<T>* node };那么这个list类中的成员变量前面数据类型 的 < T > 模版参数是必须要带的，如果你不带，而是写成list_node* node，那么此时编译器会将该成员变量视作一个自定义类型，那么它会到全局域中去寻找该自定义类型的定义而不会去寻找模版类，同理对于函数也是一样
其次就是如果遇到这样的场景，也就是我们的外部模版它是一个嵌套类型，也就是它里面还定义了一个模版类或者函数，比如：template<typename T> class node1 { template<typename u> class node2 { template<typename o> class node3 { } } }那么此时如果说我们的主模版中要用到外模版中的嵌套类型，比如这里我主模版要用到外模版中嵌套在最里层的node3，那么这里我主模版在声明的时候，光是写模版参数还不够，那么还得告诉编译器它是一个嵌套的模版，那么就需要我们手动添加typename以及template关键字
比如：
template<typename T> class main_tem { typename node1<T>::template node2<U>::template node3<o> member; }那么typename则是在数据类型的最前面，那么它告诉编译器，我typename之后的内容代表着一个数据类型，那么template则是声明在嵌套的模版类之前，那么这里之所以要加template则是因为要告诉编译器我后面的 <> 的内容是模版参数，而不要给我识别成运算符<以及 > ，而这里对于我们list主模版类来说，那么我们没有使用嵌套的模板类或者函数，就不需要添加typename以及template关键字
那么该list_iterator模版具有三个成员变量，分别是两个指针prev和next，分别指向前驱节点以及后继节点，还有一个数据域val，那么我们这里还要定义构造函数，分别定义一个无参数的构造函数，也就是将两个指针初始化为nullptr将数据域初始化为默认值（内置类型为0，自定义类型调用其默认构造函数），而带参数的构造函数则是接收一个参数，那么该参数就是用来初始化数据域，那么这就是我们的list_node模板类的构造函数，还要注意的就是这里我们list_node类中的成员变量的访问权限得设置为public,因为到时候我们list肯定有删除以及添加节点，需要修改指针，那么这里之所以设置public是因为我们到时候list类能够直接访问list_node的成员变量从而直接修改其值，如果你硬要设置成private，那么则需要你在额外定义相关修改的接口，那样显然麻烦并且没有必要，因为到时候，我们的list的成员变量也就是指向哨兵节点的指针会设置为private，那么其实不用担心外部访问到list_node的成员变量
template<typename T>
struct list_node
{
struct list_node<T>* next;
struct list_node<T>* prev;
T val;
list_node()
:next(nullptr)
, prev(nullptr)
, val(T())
{
}
list_node(const T& data)
:next(nullptr)
, prev(nullptr)
, val(data)
{
}
};
template<typename T>
class list
{
private:
list_node<T>* head;
}
list成员变量
那么我上文介绍了list的成员变量，那么下一部分内容就是介绍list的成员函数，那么list的成员函数的功能主要围绕着增删改查，那么在介绍这些相关功能的函数之前，那么我们首先应该认识的，就是list的构造函数
构造函数
那么我们知道list的成员变量是一个指向哨兵节点的指针，那么list类也重载了多个版本的构造函数来满足用户的不同的初始化需求，那么首先就是无参数的构造函数，那么该构造函数完成的内容，就是得到一个空链表，那么所谓的空链表不是一个节点都没有，而是只有一个哨兵节点，所以无参的构造函数所做的工作，就是开辟一个哨兵节点并且让哨兵节点的前驱以及后继指针都指向自己
list()
{
head = new list_node<T>;
head->next = head;
head->prev = head;
}
那么接下来就是带参数的构造函数，那么首先就是list可以接收两个参数，分别是你要设置改带头双向循环链表的节点的数量，以及这每一个节点的val值，那么如果你没给val值，那么则是提供一个缺省参数，给其设置默认值，内置类型为0，自定义类型则是其调用默认构造函数，那么它的实现原理，就是首先还是给哨兵节点开辟空间，接着，我们在定义一个变量prevnode来指向其前驱节点，然后定义一个循环，循环n次，每次创建一个节点，然后将其与前驱节点链接，最后退出循环后，此时的prevnode就是最后一个节点，然后再与哨兵节点连接即可
list(size_t n, const T& val)
{
head = new list_node<T>;
node prevnode = head;
while (n--)
{
node newnode = new list_node<T>(val);
prevnode->next = newnode;
newnode->prev = prevnode;
prevnode = newnode;
}
prevnode->next = head;
head->prev = prevnode;
}
接着就是支持一个迭代器区间初始化的构造函数，那么实现原理则是首先为哨兵节点开辟空间，然后还是额外定义一个prevnode变量指向要链接的前驱节点，然遍历迭代器区间，拷贝迭代器区间的节点的数据，然后创建新节点并且与前驱节点prevnode链接，退出循环后，此时prevnode就指向的是尾节点，再与哨兵节点链接
list(iterator first, iterator last)
{
head = new list_node<T>;
node prevnode = head;
iterator it = first;
while (it != last)
{
node newnode = new list_node<T>(it.re_node()->val);
prevnode->next = newnode;
newnode->prev = prevnode;
prevnode = newnode;
it++;
}
prevnode->next = head;
head->prev = prevnode;
}
拷贝构造函数
那么对于拷贝构造函数来说，那么它的作用也是用来初始化list，那么我们可以用一个已经初始化好的list对象来初始化一个还未初始化的list对象，那么对于拷贝构造函数的实现原理，那么首先还是给哨兵节点开辟空间，然后我们在依次遍历初始化好的list对象，每次遍历会创建新的节点，拷贝对应的已经初始化好的节点的数据，然后再处理链接关系即可，那么实现思路和上文的构造函数是大体一致的，只不过这里我偷了个懒，复用了push_back函数
list(const list<T>& l1)
{
head = new list_node<T>;
head->next = head;
head->prev = head;
const_iterator it = l1.begin();
while (it != l1.end())
{
push_back(*it);
++it;
}
}
迭代器
那么我们知道容器中的数据都是被定义为了私有属性，那么我们在外部是无法直接访问到容器内部的数据，那么为了让外部能够访问到容器内部的数据，那么容器都统一对外提供了迭代器来让我们通过迭代器来访问容器里面的数据，在此前我们学习了string以及vector，那么我们知道由于string以及vector的底层结构采取的是数组的方式来实现，所以对于string以及vector迭代器来说，那么它们就可以采取原生指针来实现，因为数组的物理空间是连续的，而指针的算术运算比如自增以及自减运算，那么都是向前以及向后移动移动的长度其指向的数据类型的大小一样，所以对于vector来说，那么它的迭代器就可以直接利用原生指针本身的自增以及自减就能够达到访问到下一个元素的效果，所以它的迭代器就可以直接采取原生指针来实现其随机访问的一个特性
那么对于list来说，由于list的底层结构采取的是带头双向循环链表的方式来实现，那么对于链表来说，我们知道它的每一个节点的在物理内存并不是连续的，那么由于节点的物理位置不连续，那么list的迭代器就不能单纯按照之前vector以及string那样还是采取原生指针，因为指针的自增向后移动的单位的长度是其指向的数据类型的大小，但是链表的节点的物理位置是随机分布的，所以这些节点是逻辑上相邻而并非物理上相邻，而要访问逻辑上相邻的节点就只能将指针指向的节点的next指针的值赋给它从而访问到下一个节点，其次就是* 运算符，那么它是解引用迭代器所指向的节点，也就是获取迭代器指向的节点的数据域里面的内容，而我们的每一个节点是一个结构体，其中包含三个成员变量，那么如果是原生指针，那么直接解引用的是无法得到该结构体的成员变量的值的，那么结构体指针解引用得通过->运算符获取成员变量的值。
所以根据上文的分析，我像明确的一个道理就是：list是无法单纯仅仅采取原生指针来实现的，但是我们还是想要实现关于list迭代器的自增以及自减和解引用，而自增和自减的目的就是为了访问到逻辑上相邻的节点，那么单纯靠原生指针的自增以及自减是无法做到，那么必然就需要我们利用运算符重载，来重写这些运算符的行为，所以list的迭代器将其封装成了一个list_iterator类，里面封装了各种适应list也就是带头双向链表结构的各种运算符重载的成员函数
成员变量
那么既然我们list的迭代器被封装成了list_iterator类，那么接下来我们就得需要知道该list_iterator的成员变量以及成员函数，那么list_iterator的成员变量就是一个指向节点的指针，因为我们知道list的迭代器只是无法单纯的采取指针的算术运算，需要我们重载一些指针运算相关的运算符重载函数
成员函数
构造函数
那么list的成员函数首先谈的肯定就是我们的构造函数，那么由于迭代器的成员变量只有一个指向节点的指针，那么迭代器的构造函数首先就是无参数的构造函数，那么将其成员变量初始化为nullptr，然后还有一个带参的构造函数，接受一个list_node < T >*的参数，来初始化成员变量
list_iterator()
:node(nullptr)
{
}
list_iterator(list_node<T>* l1)
:node(l1)
{
}
自增运算符重载函数
那么该运算符重载函数的作用就是能够让迭代器指向下一个逻辑上相邻的节点，那么就需要我们将该迭代器指向的节点的next指针赋值给迭代器也就是作为返回值，但是注意的是，这里我们的返回值类型是一个迭代器，而next指针的类型是一个list_node< T>*,所以就需要我们对该返回值进行数据类型的转化，而我们的迭代器有一个支持单参数的list_node< T> *的构造函数，那么就可以直接利用隐式类型转化即可
self_iterator& operator++()
{
node = node->next;
return *this;
}
//这里将迭代器类型typedef为了self_iterator
那么刚才所说的前置自增，那么对于后置自增运算符来说，那么则需要我们首先在参数列表中显示的添加一个int来区分前置自增，由于后置自增是先返回在自增，那么这里我们就得定义一个变量prevnode来保存成员变量node的值，然后剩余步骤和前置一样，最后返回值就是prevnode返回
self_iterator& operator++(int)
{
self_iterator prev = list_iterator(node);
node = node->next;
return prev;
}
自减运算符重载函数
那么自减运算符重载函数和自增的实现原理几乎一样，不同就在于这里是返回前一个节点
self_iterator& operator--()
{
node = node->prev;
return *this;
}
self_iterator& operator--(int)
{
list_node<T>* prev = node->prev;
node = node->prev;
return prev;
}
*运算符重载函数
那么我们知道由于迭代器指向的是一个结构体，而我们*解引用运算符的目的是为了能够得到返回其节点的数据域的内容，而迭代器内部的成员变量就是指向该结构体的指针，那么我们直接解引用该指针返回val里面的内容即可
ref operator*() const
{
return node->val;
}
那么这里的ref返回值是什么，那么下文会有解释，你在这就先理解为T&
->运算符重载函数
那么我们这里还重载了->运算符，那么这个运算符我们很熟悉，那么是给结构体指针用来访问结构体内部的成员变量，而我们发现*运算符重载函数的作用就是返回节点数据域里面的内容，但是要注意的就是我们节点的数据域val的数据类型不一定是内置类型，也可以是自定义类型，那么对于自定义类型来说，那么我们访问自定义类型的数据肯定是访问其中的某个成员变量，所以这里就需要重载->运算符来得到该结构体val的某个成员变量
ptr operator->() const //这里的返回值ptr先理解为T*，至于这个ptr是什么，那么我下文会有解释
{
return &(node->val);
}
re_node函数
那么之所以定义这个函数的原因是因为到时候，我们list内部的成员函数会涉及到修改节点的链接关系，那么其中传递的都是迭代器，那么我们知道节点的next以及prev指针的数据类型都是list_node< T> * ，那么修改指针的时候，我们就不能直接将迭代器的值赋给next或者prev指针，因为迭代器是无法转换list_node< T> *的，所以这里我们定义了一个re_node函数，那么它的返回值就是list_node< T > *,也就是成员变量，就是为了解决刚才数据类型不匹配的问题
list_node<T>* re_node() const
{
return node;
}
补充
那么这里我们知道有的list对象可能会被const给修饰，那么有的list对象则不被const修饰，那么对于被const修饰的list来说，那么它只能被const的迭代器来访问，而非const修饰的list的对象，则既可以被const的迭代器所访问也可以被非const的迭代器所访问，而const的迭代器的区别就是这里对于一些运算符重载函数的返回值，比如*运算符以及自增自减等返回值，都要返回被const所修饰
那么有的小伙伴实现const的迭代器的思路就是我直接在为const迭代器定义一个单独的模版类即可，那么这种方式可以，但是缺点就是这个const迭代器的模版类和非const迭代器的模板类，他们的代码逻辑是相同的，唯一的区别就是一些数据类型比如返回值不同，那么这就存在明显的代码冗余并且不便于维护的问题，所以第二种方式就是只用一个模板类来表示出const和非const迭代器，因为我们知道模版的应用场景就是根据不同的数据类型来实例化出不同的模版类，所以这里我们可以为list_iterator模版类定义三个模版参数，分别是数据域的数据类型T以及引用ref和指针ptr，而const和非const的迭代器的ref和ptr肯定是不同的，分别是T&和const T&以及T * 和 const T *，那么就可以实例化成不同的模版类
template<typename T, typename ref, typename ptr>
class list_iterator
{
........
}；
template<typename T>
class list
{
public:
typedef list_iterator<T,T&,T*> iterator;
typedef list_iterator<T,const T&,const T*> const_iterator;
};
注意的实typedef也会受到访问限定符的修饰，那么为了让外部能够访问到迭代器，这个typedef一定不能是被private修饰，否则我们无法在类外部定义迭代器
begin函数
那么begin函数就是返回哨兵节点之后下一个节点，那么begin函数返回值是一个迭代器，那么由于list对象可能被const修饰，所以这里的begin有两个重载版本分别是返回const迭代器以及非const迭代器
iterator begin()
{
return head->next;
}
const_iterator begin() const
{
return head->next;
}
end函数
那么end函数则是返回哨兵节点，同样也有两个版本，分别返回const迭代器以及非const迭代器
iterator end()
{
return head;
}
const_iterator end() const
{
return head;
}
insert函数
那么这里insert函数就是插入函数，那么list类重载了几个版本的insert函数，那么最为常见的一个版本就是接收一个迭代器和一个val值，也就是插入一个节点，那么insert函数具体的实现原理就是首先得定义一个变量prevnode来保存迭代器指向的节点的前驱节点，然后我们再new一个新的节点，然后修改节点之间的链接关系，也就是让前驱节点的next指针指向新插入的节点，然后让新插入的节点的prev指针指向前驱节点，而新插入的节点与迭代器指向的节点的链接关系的修改也是同理
void insert(iterator pos, const T& data)
{
node newnode = new list_node<T>(data);
node prevnode = pos.re_node()->prev;
prevnode->next = newnode;
newnode->prev = prevnode;
newnode->next = pos.re_node();
pos.re_node()->prev = newnode;
}
第二个重载版本则是则是插入一个迭代器区间，那么这里的insert的函数实现和上面的区别就是，这里我们要用一个循环，来遍历这个迭代器的区间，在遍历之前我们还是会定义一个prevnode来保存新插入的节点的前驱节点，然后每一次循环，我们会创建一个与对应迭代器区间的节点的数据相同的新节点，然后就建立prevnode与新插入的节点之间的链接关系，并且更新prevnode，最后退出循环的时候，prevnode则是指向最后一个新建的节点，那么我们再将其与pos位置指向的迭代器相连接即可
void insert(iterator pos, iterator first, iterator last)
{
node prevnode = pos.re_node()->prev;
iterator it = first;
while (it != last)
{
node newnode = new list_node<T>(it.re_node()->val);
prevnode->next = newnode;
newnode->prev = prevnode;
prevnode = newnode;
++it;
}
prevnode->next = pos.re_node();
pos.re_node()->prev = prevnode;
return;
}
那么有的小伙伴可能注意到，我在创建节点时候，我需要拷贝迭代器区间中对应节点的值，也就是获取其中的val然后传递给构造函数，但是这里我是先调用了迭代器的re_node函数然后再解引用获取val，为什么这里我不直接解引用得到val，也就是it->val而是写成 it.re_node()->val呢？
那么这里我就要解释一下，假设我们有一个迭代器it，由于我们的list_iterator类中定义了->运算符重载函数，而我们知道该运算符重载函数是返回一个指向节点的成员变量val的指针，而如果val是一个自定义类型的话，那么我们要访问val中的成员变量比如member1意味着我们还需要再依次解引用返回的该指向val的指针，所以我们在写对应的代码时候，理论上应该是这种形式：it->->member1，但是编译器对此进行了优化，也就是你只需要写一次->即可，那么编译器它会自动的先调用->运算符重载函数，然后再在后面再进行一次解引用：
it->member1;//你的视角 (it.operator->())->member1;//编译器的视角那么有了前面的铺垫我们就能知道为什么it->val不行，这里之所以有的小伙伴会这么写，可能还是习惯了把迭代器当做了一个指向结构体的指针，他认为val就是node结构体中的一个成员变量，所以这么写，但是由于->运算符重载函数的存在，那么这里会被解析为：
(it.operator->())->val也就是返回一个指向的val的指针，再对该指针解引用，那么这里如果val是一个内置类型，那么你按照结构体指针那样的解引用，那么编译器会报错，如果val是自定义类型，那么编译器就会尝试寻找其成员变量名为val然后返回
而之前我定义的re_node函数就能派上用场，那么它是返回一个指向node的指针，而node是结构体，那么我再解引用就可以获取其成员变量val
it.re_node()->val
erase函数
那么erase函数就是删除该链表的节点，那么它有不同的重载版本，首先就是只删除其中一个节点，那么它会接受一个迭代器，那么实现原理也很简单，就是保存删除节点的前一个位置的节点，然后修改链接关系，让前一个节点指向删除节点的之后的一个节点，最后在delete掉迭代器指向的节点
iterator erase(iterator pos)
{
if (pos != end()) {
node prevnode = pos.re_node()->prev;
node nextnode = pos.re_node()->next;
node to_delete = pos.re_node();
prevnode->next = nextnode;
nextnode->prev = prevnode;
delete to_delete;
return iterator(nextnode);
}
else
{
return begin();
}
}
那么注意的就是对于list的insert函数，那么其不会像vector那样出现迭代器失效的问题，因为不需要扩容，节点都是按需申请按需释放，但是对于erase来说，那么这里就涉及到迭代器失效的问题，因为我们的传进去的参数也就是迭代器是传值拷贝，那么形参的改变不影响实参，所以这里我们发现erase会有一个返回值，返回被删除的下一个节点，所以不能在使用传进去的迭代器继续访问
接着就是删除一个迭代器区间，那么会接受两个迭代器first和last，注意的就是删除的区间是左闭右开的，也就是[first,last)，那么思路就是可以复用之前删除一个节点的erase函数即可
iterator erase(iterator first, iterator last)
{
while (first != last)
{
first = erase(first);
}
return last;
}
push_back函数
那么push_back就是尾插函数，那么尾插函数就是在尾节点之后添加一个新节点，那么这里我们就可以直接利用函数的复用，调用实现好的insert函数来实现
void push_back(const T& val)
{
insert(end(), val);
}
pop_front函数
那么头删函数就是可以复用之前实现好的erase函数来实现
void pop_front()
{
erase(begin());
}
size函数
那么size函数就是返回该链表中节点的数量其中不包括哨兵节点，那么这里我们首先定义一个变量size来记录，然后遍历该链表利用迭代器即可
size_t size() const
{
size_t count = 0;
const_iterator it = begin();
while (it != end())
{
count++;
it++;
}
return count;
}
empty函数
那么empty函数就是确认该链表为空链表，那么链表为空意味着该链表只有哨兵节点而不是一个节点都没有，那么判断的条件就是哨兵节点的next或者prev指针是否指向自己
bool empty()
{
if (head->next == head)
{
return true;
}
return false;
}
clear函数
那么clear函数就是清空所有非哨兵节点，那么我们还是遍历该链表，复用我们的erase函数
void clear()
{
erase(begin(), end());
}
赋值运算符重载函数
那么赋值运算符重载函数则是复制拷贝新的节点，那么这里我们首先得释放我们原本的节点，那么这一步我们可以复用clear函数，然后只剩哨兵节点，然后我们再遍历目标链表
list<T>& operator=(const list<T>& l1)
{
clear();
const_iterator it = l1.begin();
node prevnode = head;
while (it != l1.end())
{
node newnode = new list_node<T>(it.re_node()->val);
prevnode->next = newnode;
newnode->prev = prevnode;
prevnode = newnode;
it++;
}
prevnode->next = head;
head->prev = prevnode;
return *this;
}
那么有的小伙伴可能会有一个疑问，因为它有vector的实现经验，之前实现vector的赋值运算符重载函数，那么涉及到浅拷贝的问题，也就是说假设这里我们的目标链表节点的val是一个自定义类型比如是string，那么这里浅拷贝就会导致析构两次等问题，那么这样的担心是没错的，但是这里每一个自定义类型肯定会有实现了深拷贝的拷贝构造函数，那么这里我new的时候，实参传递给形参就会调用拷贝构造，所以不用担心浅拷贝问题
析构函数
那么析构函数则是释放我们该链表申请的所有节点，其中包括哨兵节点，这一步我们可以复用clear函数，最后再将成员变量也就是head置为nullptr即可
~list()
{
clear();
delete head;
head = nullptr;
}
源码
list.h
#pragma once
namespace wz
{
template<typename T>
struct list_node
{
struct list_node<T>* next;
struct list_node<T>* prev;
T val;
list_node()
:next(nullptr)
, prev(nullptr)
, val(T())
{
}
list_node(const T& data)
:next(nullptr)
, prev(nullptr)
, val(data)
{
}
};
template<typename T, typename ref, typename ptr>
class list_iterator
{
public:
list_node<T>* node;
typedef list_iterator<T, ref, ptr> self_iterator;
list_iterator()
:node(nullptr)
{
}
list_iterator(list_node<T>* l1)
:node(l1)
{
}
self_iterator& operator++()
{
node = node->next;
return *this;
}
self_iterator& operator++(int)
{
self_iterator prev = list_iterator(node);
node = node->next;
return prev;
}
list_node<T>* re_node() const
{
return node;
}
self_iterator& operator--()
{
node = node->prev;
return *this;
}
self_iterator& operator--(int)
{
list_node<T>* prev = node->prev;
node = node->prev;
return prev;
}
bool operator!=(const self_iterator& it) const
{
return node != it.node;
}
bool operator==(const self_iterator& it) const
{
return node == it.node;
}
ref operator*() const
{
return node->val;
}
ptr operator->() const
{
return &(node->val);
}
};
template<typename T>
class list
{
private:
typedef list_node<T>* node;
node head;
public:
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;
list()
{
head = new list_node<T>;
head->next = head;
head->prev = head;
}
list(size_t n, const T& val)
{
head = new list_node<T>;
node prevnode = head;
while (n--)
{
node newnode = new list_node<T>(val);
prevnode->next = newnode;
newnode->prev = prevnode;
prevnode = newnode;
}
prevnode->next = head;
head->prev = prevnode;
}
list(iterator first, iterator last)
{
head = new list_node<T>;
node prevnode = head;
iterator it = first;
while (it != last)
{
node newnode = new list_node<T>(it.re_node()->val);
prevnode->next = newnode;
newnode->prev = prevnode;
prevnode = newnode;
it++;
}
prevnode->next = head;
head->prev = prevnode;
}
list(const list<T>& l1)
{
head = new list_node<T>;
head->next = head;
head->prev = head;
const_iterator it = l1.begin();
while (it != l1.end())
{
push_back(*it);
++it;
}
}
~list()
{
clear();
delete head;
head = nullptr;
}
iterator begin()
{
return head->next;
}
iterator end()
{
return head;
}
const_iterator begin() const
{
return head->next;
}
const_iterator end() const
{
return head;
}
size_t size() const
{
size_t count = 0;
const_iterator it = begin();
while (it != end())
{
count++;
it++;
}
return count;
}
list<T>& operator=(const list<T>& l1)
{
clear();
const_iterator it = l1.begin();
node prevnode = head;
while (it != l1.end())
{
node newnode = new list_node<T>(it.re_node()->val);
prevnode->next = newnode;
newnode->prev = prevnode;
prevnode = newnode;
it++;
}
prevnode->next = head;
head->prev = prevnode;
return *this;
}
void clear()
{
erase(begin(), end());
}
bool empty()
{
if (head->next == head)
{
return true;
}
return false;
}
void push_back(const T& val)
{
insert(end(), val);
}
void push_front(const T& val)
{
insert(begin(), val);
}
void pop_front()
{
erase(begin());
}
void pop_back()
{
iterator end = iterator(head->prev);
erase(end);
}
void insert(iterator pos, const T& data)
{
node newnode = new list_node<T>(data);
node prevnode = pos.re_node()->prev;
prevnode->next = newnode;
newnode->prev = prevnode;
newnode->next = pos.re_node();
pos.re_node()->prev = newnode;
}
void insert(iterator pos, iterator first, iterator last)
{
node prevnode = pos.re_node()->prev;
iterator it = first;
while (it != last)
{
node newnode = new list_node<T>(it.re_node()->val);
prevnode->next = newnode;
newnode->prev = prevnode;
prevnode = newnode;
++it;
}
prevnode->next = pos.re_node();
pos.re_node()->prev = prevnode;
return;
}
iterator erase(iterator pos)
{
if (pos != end()) {
node prevnode = pos.re_node()->prev;
node nextnode = pos.re_node()->next;
node to_delete = pos.re_node();
prevnode->next = nextnode;
nextnode->prev = prevnode;
delete to_delete;
return iterator(nextnode);
}
else
{
return begin();
}
}
iterator erase(iterator first, iterator last)
{
while (first != last)
{
first = erase(first);
}
return last;
}
};
}
list.cpp
#include "list.h"
#include <iostream>
#include <cassert>
using std::cout;
using std::endl;
void test_basic_operations() {
wz::list<int> lst;
// 测试空链表
assert(lst.empty());
assert(lst.size() == 0);
assert(lst.begin() == lst.end());
// 测试尾部插入
lst.push_back(1);
lst.push_back(2);
assert(*lst.begin() == 1);
assert(*(++lst.begin()) == 2);
assert(lst.size() == 2);
// 测试头部插入
lst.push_front(0);
assert(*lst.begin() == 0);
assert(lst.size() == 3);
// 测试删除
lst.pop_front();
assert(*lst.begin() == 1);
lst.pop_back();
assert((++lst.begin()) == lst.end());
}
void test_iterator_and_insert() {
wz::list<std::string> words;
words.push_back("hello");
words.push_back("world");
// 测试迭代器遍历
auto it = words.begin();
assert(*it == "hello");
++it;
assert(*it == "world");
++it;
assert(it == words.end());
// 测试范围插入
wz::list<std::string> new_words;
new_words.insert(new_words.end(), words.begin(), words.end());
assert(new_words.size() == 2);
assert(*new_words.begin() == "hello");
}
void test_copy_and_splice() {
wz::list<int> source;
source.push_back(10);
source.push_back(20);
// 测试拷贝构造
wz::list<int> copy1(source);
assert(copy1.size() == 2);
assert(*copy1.begin() == 10);
// 测试拷贝赋值
wz::list<int> copy2;
copy2 = source;
assert(copy2.size() == 2);
// 测试自插入
copy2.insert(copy2.begin(), copy2.begin(), copy2.end());
assert(copy2.size() == 4);
}
void test_edge_cases() {
wz::list<int> lst;
// 测试在空链表插入
lst.insert(lst.end(), 42);
assert(*lst.begin() == 42);
// 测试删除唯一元素
lst.pop_back();
assert(lst.empty());
// 测试自引用
lst.push_back(1);
lst.insert(lst.begin(), *lst.begin());
assert(lst.size() == 2);
assert(*lst.begin() == 1);
}
int main() {
// 基础功能测试
test_basic_operations();
// 迭代器和插入测试
test_iterator_and_insert();
// 拷贝和拼接测试
test_copy_and_splice();
// 边界条件测试
test_edge_cases();
// 可视化测试
wz::list<int> l1;
l1.push_back(1);
l1.push_back(2);
l1.push_back(3);
l1.pop_front();
wz::list<int> l2 (l1.begin(),l1.end());
l1.insert(l1.begin(), l2.begin(), l2.end());
cout << "Final list contents:" << endl;
wz::list<int>::iterator it = l2.begin();
while (it != l2.end()) {
cout << *it << endl;
++it;
}
cout << "All tests passed!" << endl;
return 0;
}
运行截图：
结语
那么这就是本篇文章的所有内容，那么带你从两个维度全面解析list，那么也建议读者看完本文后，读者下来也可以自己模拟实现list，加深你对list的理解并且还能巩固类和对象等知识，那么我会持续更新，希望大家能够多多关注，那么我的下一篇文章，会讲解栈和队列，那么如果本文对你有帮组的话，还请多多支持，你的支持就是我创作的最大的动力！
