当前位置: 首页 > article >正文

C++中list的使用与实现

一、list的使用

1.1创建

创建的方式与vector很想,也支持

initializer_list

类型的数组快捷创建

1.2迭代器只支持++与--,不再支持+和-

因为+和-涉及到数据的随机访问,链表的随机访问效率很低,因此不再支持

1.3排序

不再支持库里的sort排序,但是重载了一个无参成员函数sort(),默认排升序,可以通过传仿函数来排降序(仿函数本质是类模板,greater<int>就是有符号整形排降序的参数)

(注)

但是

我们最好不要随意使用sort(),他的效率实在太低(底层实际是归并排序),就算经过:把list的值拷贝给vector,在vector中调用库函数里的sort,排序完成之后再拷贝回list 这样一个过程,它的效率还是比直接调用sort()高

1.4unique去重

前提是排序完成,可以把相邻的,值相等的重复节点删去只留一个

1.5assign更新

可以把原来链表中的数据全部清除,把新的数据拷贝上去

1.6splice转接

它的作用更像一种剪切,原声明为

void splice (iterator position, list& x);

可以把x转接到pos位置之前,而x中数据清空

二、list的模拟实现

2.1本质

list的本质是一个带头双向循环链表

2.2尾插

按照双向链表的思路实现尾插,此时不需要区分原来list是否为空两种情况,因为实现过程都一样

2.2补:按需实例化

这是编译器一种保证效率的做法,即在运行程序过程中,当一个函数不被调用的时候,即使其中有一些错误也不会报错,因为函数因为不使用没有被实例化

2.3存节点用的类模板⭐

为了储存各种类型的数据以及前后指针,我们需要设计一个类模板

template<class T>
class ListNode

{  

    //......

    ListNode<T>* _pPre;
    ListNode<T>* _pNext;
    T _val;

}

来存储节点,因为在list中我没还需要频繁调用节点类的成员函数,所以我们不可以把他们设置为private,

结合来看,我们完全可以不写class,而用struct代替,这也是源码库中的做法。

2.4遍历

list中,我们的遍历不可以再用下标访问+[]了,因为不支持随机访问,

因此,我们只支持使用迭代器

2.5迭代器对应的类模板⭐

2.5.1出现原因

按照之前在vector中的做法,我们把ListNode<T>* 进行重命名为iterator,可是这时候问题来了:

链表节点之间的空间不再连续,iterator++的值与我们希望的完全不一样了,该怎么办呢?

为此,我们希望有一个方法可以即存储节点,又可以按照我们想要的方式进行++与--等操作,这时我们不妨将他们封装为一个类ListIterator。

此时我们只要在类中存储节点,重载++ -- *等符号即可

2.5.1补:

需求说明:

++是想要返回下一个节点,但是Node*进行++返回的是物理上的下一个节点

!=是想要看节点的地址是否相同,不重载只会去看迭代器类实例化的对象所在地址是否相同

*是想要得到节点中的值,Node*进行*只会返回节点对象

2.5.2封装:不同容器,相同的iterator

在写完迭代器类以后,回到list中我们有两种选择:

//①
ListIterator<int> it=it1.begin();
//②
list<int>::iterator it=it1.begin();

很显然,

其一、我们在实现其他容器的时候知道对应的类模板不难,但是知道对应的迭代器类模板并不简单。

其二、因为迭代器类模板的特殊性,在实现的过程中我们常在容器得类里使用迭代器的成员变量,源码中把迭代器类设置为了struct,即成员共有,为了保护迭代器的成员变量不被篡改,封装为统一的iterator势在必行。

综上,在任何支持迭代器的容器中,我们全部在容器类中把迭代器类重命名为iterator,时刻体现着封装的思想。

2.5.3迭代器类模板中的成员变量

关于迭代器类模板中存储的成员变量类型,我们可以结合string的值访问方式来迁移理解:

string中我们存数组名_str,通过解引用可以直接访问到值

迭代器中我们存结点指针Node*,通过解引用可以访问节点,节点可以直接访问到值

2.5.4析构

因为存储成员变量属于节点类,所以无需显式实现,因为程序结束节点早已释放完毕

2.5.5拷贝构造,赋值重载

他们两个都不需要显式实现,也不能显示实现:

试想我们把一个迭代器赋值给另一个迭代器的场景,不就是为了让另一个迭代器也可以直接修改原来位置的值吗?一旦深拷贝了,其中的指针成员变量自然就不是指向原来位置了

2.5.6链表中数值的*后修改

为了保证*后可以修改数值,如*it=10;

我们把operator*的返回值设置为T&,以此达到目的

2.5.7一个特殊的重载符号->

它的返回值是T*

它的存在是为了让迭代器可以直接访问数据T

例:

假设数据T的类型是一个自定义类型,我们要修改其中的成员变量_r

我们有两个选择:

//①
(*it)->_r;
//②
it->_r;

很明显第二种更加方便,其实第二种的本质是

it.operator->()->_r;

但是为了程序的可读性,我们删去了一个->

2.5.7补:++begin()可以运行的原因

begin()返回的是临时对象,临时对象可以去调用非静态的成员函数:operator++

这里的临时对象具有常性(const),但是这里的const与我们直接定义

const int i=10;

中的const不一样,他们都不可以直接引用,但是自行定义的限制比临时对象返回的更大

如:

//这是不可以的

list<A> iterator& it=lt1.begin();

//这是可以的(特殊情况)

list<A> iterator it=++lt1.begin();

2.5.8const迭代器

const迭代器本意是自身可以修改,但是指向的内容不能修改,类似

const T* p;

要实现它,我们需要单独再写一个类const_ListIterator,其中*和->的重载函数需要把返回值改为const修饰的类型,其他函数都不变,再在list类中重新命名其为const_iterator来与其他容器统一即可

2.5.8补:常规思维不可行的原因

起初处理这一问题我们想到的当然不会是重写一个类,而是直接加上const

typedef ListIterator<const T> const_iterator;

但是把这种想法带入到实现中会发现,这样只会改变Node的类型,但不会改变list中的T,匹配下来会发生错乱

2.5.9const迭代器的简化方法

再实现一个类,大多函数还都是一样的实在有些冗余,那有没有方法更简便一些呢?

有的,因为只有*和->的返回值有改变,那我们完全可以把这种改变体现在模板参数当中,

template <class T,class Ref,class Ptr>

而在list中重命名的时候直接

typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T&> const_iterator;

就可以解决这一问题

2.6 list中的拷贝构造和赋值重载

在list不能只进行浅拷贝,否则会出现:

创建l1,

l2(l1)

在l1中插入一个数据

此时会导致l2中也插入一个数据,但这并不是我们想要的,因此我们需要通过循环尾插来进行深拷贝。

2.7clear清除数据与list的析构

clear目的是清楚当前所有数据,但是容器结构不变,也就是仍然保留头节点

而析构就是在clear完毕以后delete掉头节点,彻底释放空间

2.7补:范围for使用的习惯

在使用范围for的时候,如果不确定具体类型,为了避免效率的浪费,我们推荐

for(const auto& arr)
{//...}

2.8赋值重载实现技巧

在书写赋值重载的时候,我们可以通过传值传参来获取一个list类型的拷贝,然后直接进行头节点互换,此时结束代码书写还有一个隐藏的作用:出作用域时该拷贝生命周期结束,自动进行销毁(析构)。

2.9关于std中的迭代器

我们的迭代器只存了一个节点指针,但是如果我们对std中的迭代器进行sizeof的话(64位),会意外的发现结果是12

其实之所以多出来4个字节的大小,是因为其中还有一个用作标记的成员变量,前文我们已经知道了在insert和erase以后会出现迭代器失效的问题,此标记就是为了区分迭代器是否失效

2.10模板构造函数:迭代器构造(数组首尾指针的兼容)

以往我们使用迭代器构造都会想当然的以为只能传begin和end的返回值过去,但实际上当我们传数组首位指针的时候,STL会自动构建一个迭代器,从头指针一直到尾指针的位置开始遍历数组元素,每遍历一个数组元素会把它尾插入list


http://www.kler.cn/a/371633.html

相关文章:

  • 【vue】Mammoth.js的使用:将.docx和doc 文件转换成HTML
  • 使用Docker Compose简化微服务部署
  • 驱动和芯片设计哪个难
  • 架构师备考专栏-导航页
  • 采用STM32CubeMX和HAL库的定时器应用实例
  • 【云原生】云原生后端详解:架构与实践
  • 在IDEA中运行Mybatis后发现取出的password值为null
  • 地理征服营销与开源 AI 智能名片 2 + 1 链动模式 S2B2C 商城小程序的融合创新
  • 06.动态代理设计模式
  • 【GL07】C语言要点
  • 探索PDFMiner:Python中的PDF解析利器
  • Spring三级缓存解决循环依赖?构造方法的循环依赖问题解决(原理、详细过程、面试题)
  • 【容器】容器化详解:提升开发与运维效率的关键技术
  • Java面对对象第七天(实训学习整理资料(六)Java中的面向对象(oop))
  • Junit5中用Excel进行数据驱动
  • ELK + Filebeat + Spring Boot:日志分析入门与实践(二)
  • 【机器学习】14. 集成学习 ensemble: bagging, boosting, 随机森林 random forest
  • 压力测试指南-压力测试中的性能瓶颈定位与优化
  • C语言——字符串指针和字符串数组
  • 【数据结构与算法】第6课—数据结构之栈
  • 【问题记录】当机器人存在多个串口需要绑定时udevadm的作用
  • 【案例77】Npart部署页签失效
  • VQ-VAE(2018-05:Neural Discrete Representation Learning)
  • 中间件安全(三)
  • SpringBoot技术:闲一品交易平台的新选择
  • vue使用element ui绘制界面