沧浪网站建设,中小企业网站建设 网络营销,临海做网站的公司,网站建设合同定义#x1f431;作者#xff1a;一只大喵咪1201 #x1f431;专栏#xff1a;《C学习》 #x1f525;格言#xff1a;你只管努力#xff0c;剩下的交给时间#xff01; list的使用及模拟实现#x1f63c;构造函数#x1f435;模拟实现#x1f63c;迭代器#x1f435;… 作者一只大喵咪1201 专栏《C学习》 格言你只管努力剩下的交给时间 list的使用及模拟实现构造函数模拟实现迭代器普通迭代器(iterator)模拟实现const迭代器(const_iterator)模拟实现箭头(-)运算符重载赋值运算符重载模拟实现析构函数析构函数存在的必要性容量和访问操作容量操作访问操作增删查改操作其他几个常用接口list和vector优劣比较总结list和vector一样也是一个非常常用的数据结构它和vector就像左手和右手的关系优略势互补它的本质是一个带头双向循环列表下面本喵来给大家详细介绍一下list。
构造函数 官方提供的构造函数有四个其中包括拷贝构造函数如上图所示。
void list_test1()
{listint lt1;listint lt2(5, 1);vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);listint lt3(v1.begin() 1, v1.end() - 1);listint lt4(lt2);
}通过调试的监视窗口可以看到使用四种方法都能成功创建list对象。
为了更好的理解list下面来模拟实现一下它。
模拟实现 如上图list是又一个又一个的节点构成每个节点中不仅存放数据而且存放着前一个结点和后一个节点的指针。
所以我们需要创建一个类这个类就是用来描述节点的。
namespace wxf
{template class Tstruct __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。 每次尾插一个数据的时候就需要动态开辟一个节点对象然后再将_headtailnewnode三个节点按照带头双向循环列表的规则进行链接。 如上图在尾插一个新节点的时候由原本绿色的链接关系变成了蓝色的链接关系。 成功的使用我们自己实现的构造函数创建了一个list对象并且尾插了五个数字如上图所示。
继续实现构造函数 使用多个相同的数据来构造list对象的的构造函数本质就是进行多次尾插如上图中的红色框。 通过监视窗口看到符合我们对预期。
每次构造一个对象的时候必须先初始化头节点为了简化代码将头节点初始化的代码放在一个函数中。 在每个构造函数中调用这个初始化函数就可以进行头节点的初始化。
迭代器
先看它的使用
void list_test2()
{listint lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);lt1.push_back(5);listint::iterator it1 lt1.begin();while (it1 ! lt1.end()){cout *it1 ;it1;}cout endl;
}使用迭代器成功打印出了list中的每一个数据。
无论是哪种数据结构都有迭代器在前面我们学习vector和string的时候就学习到了迭代器我们知道它是一个行为上像指针一样的东西由于vector本身的物理结构是连续的所以它的迭代器本质上就是一个指针。
但是list的物理结构是不连续的它的本质注定不能是一个指针下面本喵来详细介绍。
普通迭代器(iterator)模拟实现 迭代器有或者–等行为由于list的物理空间不连续所以此时的和–需要重新定义也就是需要进行运算符重载。 为了让它行为上像指针一样只能通过一个类来描述它所以说list的迭代器是一个类对象。 template class Tstruct __list_iterator{typedef __list_nodeT node;node* _pnode;__list_iterator(node* p):_pnode(p){}};创建一个迭代器类如上面的代码类中只有一个成员变量用了存放节点的地址。同样为了能够直接访问使用struct创建类。
同样必须有构造函数编译器自动生成的默认构造函数不能将pnode初始化为我们想要的所以需要自己实现一个。
要想让list的迭代器也能像指针一样进行或者–需要对运算符进行重载。 如上图中分别是前置的和–以及厚置和–的运算符重载。 前置返回的是后的结果所以返回this指针的内容并且使用的是引用返回因为这里的迭代器对象不会销毁。后缀返回的是前的结果所以需要一个临时对象来存放之前的结果然后再进行但是这里不能用引用返回临时对象出了作用域以后就会销毁。 上面四个运算符重载函数中无论是返回类型还行创建的临时变量都需要写很长一个串类型名(__list_iterator)为了简化我们这里将其重命名成一个简单的类型名。(这一步操作后面有大用处)
typedef __list_iteratorT 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 listint::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的本质就是将prevnext直接链接上从而跳过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
优点
支持下标随机访问。尾插尾删效率高(偶尔扩容除外)。cpu高速缓存命中率高。
缺点
前面部分插入删除效率低。扩容有消耗而且存在一定的空间浪费。
list
优点
按需申请释放不需要扩容。支持任意位置插入删除时间复杂度是O(1)。
缺点
不支持下标随机访问。cpu高速缓存命中率低。
list和vector就像左右手的关系它们的优劣势互补。一般vector满足的场景下优先使用vector。
总结
list中需要我们重点掌握的就是它的迭代器因为这里的迭代器和之前vector已经string的不同它是封装好的一个类。进行list的模拟实现主要目的是为了更好的了解和使用list并不是为了造一个更好的轮子官方提供的STL模板已经非常完美了。
