[C++进阶[六]]list的相关接口模拟实现

news/2024/9/22 15:42:56/

1.前言

本章重点

list模拟实现的过程中,主要是感受list的迭代器的相关实现,这是本节的重点和难点。

 2.list接口的大致框架

 list是一个双向循环链表,所以在实现list之前,要先构建一个节点类

template <class T>
struct ListNode
{T _val;ListNode* _prev;ListNode* _next;ListNode(const T& val = T())//构造函数:_prev(nullptr), _next(nullptr),_val(val){}
};

节点中存储一个T模板类型的值和
上一个节点的地址和下一个节点的地址

在List类中,由于链表都是些链接关系,所以List类中的成员变量只需要定义一个那就是头节点head,知道head的链接关系。就能够知道list类对象中存放的内容!

template <class T>
class List
{public:typedef ListNode<T> Node;private://带头节点的无参构造一个随机值void CreateHead(){_pnode = new Node;_pnode->_prev = _pnode;_pnode->_next = _pnode;}Node* _pnode;
};

解释:给头节点pnode开辟一份空间后,头节点的指向最开始都是指向自身:

3.list的构造和析构函数

构造函数

此处介绍三种构造函数:空构造;构造n个值为val的节点;用迭代器区间来进行构造

无参构造:

//构造函数1
List()
{CreateHead();
}

构造n个值为val的节点

//构造函数2:创建n个值为val的节点
List(int n, const T& val = T())
{CreateHead();for (int i = 0; i < n; i++){push_back(val);}
}

这个地方使用了push_back先用着,后续再实现

迭代器区间来进行构造:

//构造函数3:迭代器区间来进行构造
template <class InputerIterator>
List(InputerIterator first, InputerIterator last)
{CreateHead();while (first != last){push_back(*first);first++;}
}

ps:注意,这里不管是什么构造,在最开始时都需要构造一个带哨兵卫的头节点,所以说都要先使用CreateHead函数来进行构建。

析构函数

由于链表是一块一块的空间,通过某种形式把他连接起来。所以在析构函数时,要先把这些空间全部释放掉,然后再删除带哨兵卫的头结点。

//析构函数
void clear()
{iterator it = begin();while (it != end()){it = erase(it);}
}
~List()
{clear();delete _pnode;_pnode = nullptr;
}

这里使用到了迭代器来进行遍历,后续会实现迭代器相关的功能。

4.拷贝构造函数和赋值重载函数

拷贝构造函数

直接使用简单快速的写法来完成深拷贝。

	//拷贝构造函数List(const List<T>& node){CreateHead();List<T> tmp(node.begin(), node.end());Swap(tmp);}void Swap(List<T>& node){swap(_pnode,node._pnode);}

赋值重载函数

	//赋值重载函数List<T>& operator=(const List<T>& node){List<T>tmp(node.begin(), node.end());Swap(tmp);return *this;}

这样的写法有两个精妙之处:

1.它先定义一个临时变量tmp来接受node的所有值,然后再将临时变量tmp
的pnode和拷贝的pnode交换,这样一来就完成了拷贝构造函数,并且tmp变量是构造函数初始化的,它是深拷贝,所以lt2对于lt1也是深拷贝。

2.tmp是临时变量,除了作用域会销毁,也就是出了此拷贝构造函数后会销毁,销毁时会调用析构函数,然而要构造的pnode以及和tmp的pnode交换了,所以tmp销毁时实际上是在帮原先的要构造的pnode销毁内存!

5.与容量有关的函数

size和empty

bool empty()
{return size() == 0;
}size_t size()
{size_t sz = 0;iterator it =begin();while (it!= end()){sz++;it++;}return sz;
}

6.迭代器的模拟实现

其实仔细分析下来,发现链表是无法进行*和++,--以及->这些相关操作的。那么想让链表和迭代器一样进行++,--,*和->这些相关的操作,那么只需要封装一个类,把这些函数进行重写就可以了。

迭代器的大体结构如下:

template<class T>
struct List_iterator 
{typedef ListNode<T>* PNode;typedef List_iterator<T> Self;PNode _node;
};

构造函数

List_iterator(const PNode& node=nullptr):_node(node)
{}

拷贝构造

//拷贝构造
List_iterator(const Self& l)
{_node=l._node;
}

ps:由于这里把迭代器相关类型重命名成了self,所以这里给出的就直接使用了self

++和--函数

Self& operator++()//前置++
{_node = _node->_next;return *this;
}
Self& operator--()//前置--
{_node = _node->_prev;return *this;
}
Self operator++(int) //后置++
{List_iterator<T> tmp(*this);_node = _node->_next;return tmp;
}
Self operator--(int) //后置--
{List_iterator<T> tmp(*this);_node = _node->_prev;return tmp;
}

==和!=函数

bool operator==(const Self& node)
{return _node == node._node;
}
bool operator!=(const Self& node)
{return _node != node._node;
}

解引用和箭头->函数

迭代器的使用就像指针一样,所以解引用后应该直接得到节点的数据!

	T& operator*(){return _node->_val;}T* operator->(){return &(_node->_val);}

解释:解引用大家肯定都能理解。那么对用箭头->函数理解起来可能就有难度了。

举个例子来帮助我们理解

list容器当中的每个结点存储的不是内置类型,而是自定义类型,例如日期类,那么当我们拿到一个位置的迭代器时,我们可能会使用->运算符访问Date的成员:

	list<Date> lt;Date d1(2021, 8, 10);Date d2(1980, 4, 3);Date d3(1931, 6, 29);lt.push_back(d1);lt.push_back(d2);lt.push_back(d3);list<Date>::iterator pos = lt.begin();cout << pos->_year << endl; //输出第一个日期的年份

注意: 使用pos->_year这种访问方式时,需要将日期类的成员变量设置为公有。

对于->运算符的重载,我们直接返回结点当中所存储数据的地址即可。

T* operator->()
{return &_pnode->_val; //返回结点指针所指结点的数据的地址
}

讲到这里,可能你会觉得不对,按照这种重载方式的话,这里使用迭代器访问日期类当中的成员变量时不是应该用两个->吗?

这里本来是应该有两个->的,第一个箭头是pos ->去调用重载的operator->返回Date* 的指针,第二个箭头是Date* 的指针去访问对象当中的成员变量_year。

但是一个地方出现两个箭头,程序的可读性太差了,所以编译器做了特殊识别处理,为了增加程序的可读性,省略了一个箭头。

7.插入删除相关函数

有了迭代器之后插入删除相关函数就好实现了。

插入函数insert

//在pos位置前插入值为val的节点
iterator insert(iterator pos,const T&val)
{//创建节点Node* newnode = new Node(val);Node* cur = pos._node;Node* prev = pos._node->_prev;//开始插入prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;return iterator(newnode);
}

这里我实现的是在插入一个值之后,并把这个值的的迭代器位置返回去。

erase函数

//删除pos节点,然后返回下一个节点
iterator erase(iterator pos)
{assert(pos != end());Node* cur = pos._node;Node* next = pos._node->_next;Node* prev = pos._node->_prev;delete cur;prev->_next = next;next->_prev = prev;return iterator(next);
}

如果这里不返回一个合法的迭代器位置的话,那么就会有可能出现迭代器失效。

push_back和pop_back


push_back和pop_back函数分别用于list的尾插和尾删,在已经实现了insert和erase函数的情况下,我们可以通过复用函数来实现push_back和pop_back函数。

push_back函数就是在头结点前插入结点,而pop_back就是删除头结点的前一个结点。

	void push_back(const T& val){insert(end(), val);}void pop_back(){erase(--end());}

8.总结

总的来说,list的底层实现较于vector来说要复杂一点,这其中的底层原因
就是list的迭代器还需要一层封装,而vector的迭代器不需要额外封装。但是在我们使用的角度来看,这两者并没有什么区别。

C++的强大就在于把复杂的底层全部封装起来了,而表面的使用上
list和vector并无太大区别,这就是C++封装的魅力!

 list模拟实现全部代码如下:

simulate_list/simulate_list · 青酒余成/初识数据结构 - 码云 - 开源中国 (gitee.com)


http://www.ppmy.cn/news/1528887.html

相关文章

Unity 高亮插件Highlight Plus快速入门

通常你可能只是想简单的为某个物体高亮显示 我将介绍最简单快速的方法 如果你想了解更多 Unity 高亮插件HighlightPlus介绍-CSDN博客 情景一 如果你只是想某个物体被鼠标覆盖显示高亮效果,鼠标离开高亮效果消失的话,你甚至不需要写一句代码! 为物体添加这两个脚本(添加T…

开源 AI 智能名片小程序:开启内容营销新境界

摘要&#xff1a;本文深入探讨了在当今数字化时代&#xff0c;内容营销的重要性以及如何实现让用户主动找你的最佳效果。通过引入开源 AI 智能名片小程序这一创新工具&#xff0c;阐述了其在明确目标用户群体、迎合用户需求痛点和打造风格特色方面的独特优势&#xff0c;为企业…

【Qt】实现模拟触摸屏 上下滑动表格 的两种方式

QScroller Qt QTableWidget 触摸屏上滑动效果 代码 // 创建 QScroller 对象并与 tableWidget 关联.QScroller *pScroller QScroller::scroller(ui->tableView);// 捕获滚动手势.pScroller->grabGesture(ui->tableView, QScroller::LeftMouseButtonGesture);// 设置…

javascript数据结构

在 JavaScript 中&#xff0c;数据结构的选择和实现对于编写高效、可维护的代码至关重要。JavaScript 提供了一系列内置的数据结构&#xff0c;同时也支持自定义复杂的数据结构。以下是 JavaScript 中常用的一些数据结构及其基本介绍&#xff1a; 内置数据结构 1. 数组&#…

JavaScript发送邮件:实现前端触发的教程?

JavaScript发送邮件的方式&#xff1f;怎么使用JavaScript发信&#xff1f; 无论是用户反馈、联系表单还是自动通知&#xff0c;前端触发的邮件发送功能都能极大地提升用户体验。AokSend将详细介绍如何通过JavaScript发送邮件&#xff0c;实现前端触发的邮件发送功能。 JavaS…

Unity 百度AI实现无绿幕拍照抠像功能(详解版)

目录 一、前言 1.抠像效果 2.去哪找百度ai抠图 3.基础流程跳过 二、获取AccessToken 1.什么是Token 2.为什么要获取Token 3.如何获取token 4.解析json 5.完整代码 三、抠像 1.准备地址 2.建立链接&#xff0c;和基本配置 3.图片格式转换 4.开始上传 5.获取回复…

IPsec-Vpn

网络括谱图 IPSec-VPN 配置思路 1 配置IP地址 FWA:IP地址的配置 [FW1000-A]interface GigabitEthernet 1/0/0 [FW1000-A-GigabitEthernet1/0/0]ip address 10.1.1.1 24 [FW1000-A]interface GigabitEthernet 1/0/2 [FW1000-A-GigabitEthernet1/0/2]ip address

No operations allowed after statement closed

错误信息&#xff1a; The last packet successfully received from the server was 3,576,246 milliseconds ago. The last packet sent successfully to the server was 3,576,247 milliseconds ago. 参考解决方案 https://github.com/alibaba/druid/issues/5549 如果修改…