【C++学习】list的使用及模拟实现

🐱作者：一只大喵咪1201
🐱专栏：《C++学习》
🔥格言：你只管努力，剩下的交给时间！

list和vector一样，也是一个非常常用的数据结构，它和vector就像左手和右手的关系，优略势互补，它的本质是一个带头双向循环列表，下面本喵来给大家详细介绍一下list。

😼构造函数

官方提供的构造函数有四个，其中包括拷贝构造函数，如上图所示。

void list_test1()
{list<int> lt1;list<int> lt2(5, 1);vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);list<int> lt3(v1.begin() + 1, v1.end() - 1);list<int> lt4(lt2);
}

通过调试的监视窗口可以看到，使用四种方法都能成功创建list对象。

为了更好的理解list，下面来模拟实现一下它。

🐵模拟实现

如上图，list是又一个又一个的节点构成，每个节点中，不仅存放数据，而且存放着前一个结点和后一个节点的指针。

所以我们需要创建一个类，这个类就是用来描述节点的。

namespace wxf
{template <class T>struct __list_node{__list_node* prev;//指向前一个节点的指针__list_node* next;//执行下一个节点的指针T data;//根据模板参数实例化，存放数据__list_node(const T& x):prev(nullptr),next(nullptr),data(x){}};
}

同样将我们自己模拟实现的部分放在命名空间wxf中。

• 这里节点类创建时，使用的关键字是struct，而不是class。
• 使用struct创建的类，默认所有成员都是公有的，如果使用class，默认所有成员是私有的，需要在所有成员变量之前加public。

每一个节点在创建时，需要进行初始化，所以在节点类中需要有一个构造函数，来初始化节点。

构造函数：

为了使用方便，将前面的节点类使用typedef重命名为node，在list类中，成员变量只有一个，就是节点的指针变量_head，也就是头节点的地址。

• 类名<模板参数>等价于类型，所以在typedef的时候，只写类名__list_node是不行的。

每创建一个list对象的时候，首先要做的事情就是new一个头节点，由于此时list是空的，所以头节点的next和prev都是指向自己的，如上图绿色框中的代码所示。

push_back()：

需要一个接口来向list中插入数据，这里先实现最常用的push_back。

每次尾插一个数据的时候，就需要动态开辟一个节点对象，然后再将_head，tail，newnode三个节点按照带头双向循环列表的规则进行链接。

如上图，在尾插一个新节点的时候，由原本绿色的链接关系变成了蓝色的链接关系。

成功的使用我们自己实现的构造函数创建了一个list对象，并且尾插了五个数字，如上图所示。

继续实现构造函数：

使用多个相同的数据来构造list对象的的构造函数，本质就是进行多次尾插，如上图中的红色框。

通过监视窗口看到，符合我们对预期。

每次构造一个对象的时候，必须先初始化头节点，为了简化代码，将头节点初始化的代码放在一个函数中。

在每个构造函数中调用这个初始化函数就可以进行头节点的初始化。

😼迭代器

先看它的使用：

void list_test2()
{list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);lt1.push_back(5);list<int>::iterator it1 = lt1.begin();while (it1 != lt1.end()){cout << *it1 << " ";++it1;}cout << endl;
}

使用迭代器成功打印出了list中的每一个数据。

无论是哪种数据结构，都有迭代器，在前面我们学习vector和string的时候就学习到了迭代器，我们知道它是一个行为上像指针一样的东西，由于vector本身的物理结构是连续的，所以它的迭代器本质上就是一个指针。

但是list的物理结构是不连续的，它的本质注定不能是一个指针，下面本喵来详细介绍。

🐵普通迭代器(iterator)模拟实现

• 迭代器有++或者–等行为，由于list的物理空间不连续，所以此时的++和–需要重新定义，也就是需要进行运算符重载。

为了让它行为上像指针一样，只能通过一个类来描述它，所以说，list的迭代器是一个类对象。

	template <class T>struct __list_iterator{typedef __list_node<T> node;node* _pnode;__list_iterator(node* p):_pnode(p){}};

创建一个迭代器类，如上面的代码，类中只有一个成员变量，用了存放节点的地址。同样为了能够直接访问，使用struct创建类。

同样，必须有构造函数，编译器自动生成的默认构造函数不能将pnode初始化为我们想要的，所以需要自己实现一个。

要想让list的迭代器也能像指针一样进行++或者–，需要对运算符进行重载。

如上图中，分别是前置的++和–以及厚置++和–的运算符重载。

• 前置++返回的是++后的结果，所以返回this指针的内容，并且使用的是引用返回，因为这里的迭代器对象不会销毁。
• 后缀++返回的是++前的结果，所以需要一个临时对象，来存放++之前的结果，然后再进行++，但是，这里不能用引用返回，临时对象出了作用域以后就会销毁。

上面四个运算符重载函数中，无论是返回类型，还行创建的临时变量，都需要写很长一个串类型名(__list_iterator)，为了简化，我们这里将其重命名成一个简单的类型名。(这一步操作后面有大用处)

typedef __list_iterator<T> Self;

并且将前面代码中的__list_iterator替换为Self。

既然像指针一样，那迭代器就必须能解引用，因为list的迭代器是一个类对象，所以解引用同样需要进行运算符重载。

由于解引用以后会对list中的数据进行访问，所以使用引用返回。

上图中是对==和!=进行的运算符重载，这俩个符合也是非常常用的。

将迭代器本身处理好以后，还需要让它在list类域中能够找到，如上图红色框中代码，在list类中，将迭代器重命名为我们熟悉的iterator。

• 这里的重命名必须设置为公有，否则我们无法创建itertator迭代器，因为私有在类外是无法访问的。

在list类中还需要提供begin和end接口，如上图所示，这是在list类中实现的，而不是在__list_iterator中实现的。

此时，我们模拟实现的迭代器同样可以正常使用了。

🐵const迭代器(const_iterator)模拟实现

当一个对象是被const修饰的时候，普通迭代器就不再适用了，需要用到const迭代器。

此时我们创建的是一个const对象，但是发现通过它的迭代器，该对象不仅可以访问，而且还可以修改，这和const的性质相悖，const修饰的对象也失去了它应有的意义。

我们首先要做的事情就是不能让它修改。此时就有一种改法：

const list<int>::iterator it = lt1.begin();

用const修饰it，此时不就行了吗？

答案是不行的。此时运行会报错，大家可以自己尝试一下。

• 此时const修饰的是it本身，会导致it不能被修改，也就是it不能进行++和减减等操作。
• 并且此时*it还行可以进行++。

这和我们使用const的初衷不符合，我们是为了防止修改it指向的对象，而不是it本身。

既然这样，我们让*it返回的数据不能被修改。

如上图，在迭代器类中，对*的运算符重载，返回的数据类型是const T&，此时就无法修改了。

道理是这么个道理，但是此时就存在了两个operator*运算符重载函数：

在运行的时候，会报错。

• 返回类型不同不能构成远算符重载。

为了解决这个问题，需要再创建一个类，创建一个const_iterator的专属类。

此时普通迭代器类和const迭代器两个类，除了类名不一样以外，只有解引用运算符重载(operator*())不一样，其他都一样。

并且在list类中，也将两种迭代器typedef为我们熟悉的样子。

此时it就不能被修改了，符合了const的性质。

虽然实现了，但是总感觉有不舒服，因为太冗余了，就是因为一个函数的返回类型而重新写了一个类，可以采用下面的办法来解决。

迭代器的类模板，使用两个模板参数，解引用运算符重载的返回类型使用第二个模板参数Ref，如上图红色框所示。

在list类中，给迭代器类不同类型的模板参数，并且使用typedef进行重命名，如上图红色框中所示。

• 此时，使用哪种迭代器，就会使用哪种模板参数进行实例化，相当于将前面我们写的俩个迭代器类的工作交给了编译器来完成。

同样还需要写上图中的两个成员函数在list类中，此时const迭代器才能正常的使用begin和end。

🐵箭头(->)运算符重载

当放入list的数据时一个结构体类型的时候，如上图红色框所示，此时想要打印出具体数据是做不到的，因为流插入运算符(<<)不支持打印结构体类型的数据，如上图中绿色框中所示。

要想打印，此时该怎么办呢？

可以像上图中那样，先将it解引用拿到结构体数据，然后使用点操作符打印出行和列。

既然迭代器it的行为像指针，理论上我们也可以通过箭头(->)操作符来访问结构体类型数据。

将像这样，但是此时很显然，是无法实现的，需要我们进行箭头运算符的重载。

在迭代器类中进行运算符重载，箭头运算符重载返回的是数据的地址，如上图所示。

此时成功打印出了一组坐标。而且使用的是箭头操作符，行为完全符合指针。

但是此时又有一个疑问：

将该运算符重载函数现实调用以后，如上图中的红色框，得到的是数据所在的地址，再加一个箭头，如上图中绿色框，才能访问到结构体中具体成员。这样来看，一共加起来两个箭头，但是直接使用重载后的运算符，只需要it->一个箭头就可以。

• 为了提高可读性，编译器进行了简化，将原本的两个箭头简化成了一个箭头。

在箭头运算符重载函数中，返回类型是T*，同样的，如果是一个const对象呢？继续使用T又不符合const的性质，const T 返回类型又构不成重载，为了解决这个问题，可以参考两种迭代器的解决办法。

将迭代器类模板的模板参数再增加一个：

将模板参数的第三个参数作为operator->()运算符重载函数的返回类型。

在list类中，普通迭代器第三个模板参数就传T*，const迭代器，第三个模板参数就传const T*，让编译器根据具体情况去实例化。

前面本喵就说过，这个地方会有大用，当模板参数有了变化以后，只需要在红色框中改变就行，在后面用到类型的时候，由于typedef的存在，直接使用Self即可。

到这里，我们就将迭代器部分模拟完了，反向迭代器本喵就不再模拟了，我们仅是为了更好的学习迭代器，并不是为了造一个更好的轮子。

使用迭代器区间的构造函数：

😼赋值运算符重载

赋值运算符重载函数只有这一个，没有重载。

上图中，创建了lt1和lt2两个list对象，其中lt2是空的，然后将lt1的值全部赋值给lt2，从运行结果中可以看到，此时两个对象的值是一样的。

🐵模拟实现

在模拟实现赋值运算符重载之前，需要做一些准备工作，同样这些接口也是我们常用的，在这里就一并模拟实现了。

erase()：

eraes的本质就是将prev，next直接链接上，从而跳过pos，并且最后释放pos所在的节点。为了防止出现迭代器失效，这里返回pos的下一个位置，也就是next节点。

clear()：

clear的作用就是只保留list的头结点，将其余节点全部释放掉。

准备工作做好以后就可以模拟实现了：

传统写法：

• 如果是自己给自己赋值的话，直接返回自己本身就可以。
• 它的本质就是被赋值一方只保留头结点，其他节点全部删除，然后再逐个尾插。
• 使用范围for的时候，为了提高效率，使用的是auto&。

现代写法：

同样需要做一个准备工作，需要写一个拷贝构造函数，也正回补上了前面的遗漏。

拷贝构造函数：

使用范围for进行尾插。

还需要我们自己实现一个交换函数，只需要交换两个list的头结点就可以。

• 算法库中的swap函数直接使用的话，会导致效率低下，因为算法库中是交换所有的内容。

• 形参不能使用list，因为不能将this的_head换给原本提供数据的list对象。
• 此时的val是一个临时变量，this中的_head和它交换以后，val会被释放。

😼析构函数

先来看析构函数的实现：

析构函数首先要做的是除了头结点以外的其他节点释放，最后再释放头结点，否则就会找不到其他节点。

🐵析构函数存在的必要性

节点类和迭代器类，就没有析构函数，这是为什么？他们不需要释放吗？

• 对于迭代器，它的成员只有一个指针，所以就存放在栈区就可以，也不会占用太多的内存，不用在堆区开辟动态空间，所以不需要析构函数。
• 对于节点类，它本身并不会创建类对象，而是list类会按照它的蓝图在堆区创建一个节点对象。所以说，它是由list类对象控制的，包括创建和释放，所以节点类本身不需要析构函数。

甚至他们仅有一个构造函数，都不用考虑深层次拷贝的问题，这是为什么？

• 对于迭代器，例如语句iterator it = lt.begin()，它本质上使用的是一个拷贝构造函数，但是我们并没有写，这是因为编译器自动生成的默认拷贝构造函数就能满足要求，此时迭代器需要的就是完全复制lt.begin()的地址。
• 对于节点类，对具体的节点操作，只有创建和销毁，还有访问，至于赋值什么的主要操作的是头结点，所以它没有必要进行深层次拷贝。

😼容量和访问操作

🐵容量操作

需要增加一个成员变量_size，用来记录节点个数。同样的，在一些增加和减少成员函数中，也要改变_size的值。

🐵访问操作

链表并不支持随机访问，只有访问头和尾的成员函数。

如上图所示，是访问头和尾的普通对象和const对象调用的成员函数。

上图是对应的运行结果。

😼增删查改操作

insert():

插入一个新的节点，本质上就是在修改新节点以及该位置前后俩个节点共三个节点的链接关系。每插入一个节点，数据个数要加1。为了防止迭代器实失效，最后返回的是新插入节点的位置。

此时push_back也可以进行复用，使用insert在末尾插入。

push_front():

同样在复用insert。

成功头插了五个数字。

pop_back()和pop_front():

这俩个函数只需要复用erase即可。

😼其他几个常用接口

sort():

list还提供了一个排序接口。

可以看到，将一组乱序的数字排成了有序。

unique():

该函数的作用就是去重，将重复的数据去掉。

• 去重之前必须先让它有序，所以要在unique之前使用sort来排序。

remove():

该函数的作用就是去除掉链表中指定的数据。

• 指定数据如果有多个，就会有多少去除掉多少。
• 指定数据如果没有，那么它什么也不会干，也不会报错。

merge():

将两个链表有序合并。

😼list和vector优劣比较

vector

优点：

1. 支持下标随机访问。
2. 尾插尾删效率高(偶尔扩容除外)。
3. cpu高速缓存命中率高。

缺点：

1. 前面部分插入删除效率低。
2. 扩容有消耗，而且存在一定的空间浪费。

list

优点：

1. 按需申请释放，不需要扩容。
2. 支持任意位置插入删除，时间复杂度是O(1)。

缺点：

1. 不支持下标随机访问。
2. cpu高速缓存命中率低。

list和vector就像左右手的关系，它们的优劣势互补。一般vector满足的场景下优先使用vector。

😼总结

list中，需要我们重点掌握的就是它的迭代器，因为这里的迭代器和之前vector已经string的不同，它是封装好的一个类。进行list的模拟实现，主要目的是为了更好的了解和使用list，并不是为了造一个更好的轮子，官方提供的STL模板已经非常完美了。