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

embedded/2024/9/23 0:05:24/

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/embedded/113828.html

相关文章

HTTPS是如何保证安全传输的

我们都知道https是保证安全传输的&#xff0c;那么究竟是如何保证的呢&#xff1f; 答&#xff1a;通过使⽤对称加密、⾮对称加密、数字证书等⽅式来保证数据的安全传输。 下面&#xff0c;就让我们来详细了解一下&#xff0c;具体是如何做的&#xff1a; 客户端向服务端发送数…

PPT技巧:如何在幻灯片中生成目录?

PPT文件如何制作目录&#xff0c;如何点击目录标题立即跳转到相应幻灯片&#xff1f;今天小奥超人和大家一起来学习一下。 现在幻灯片里制作好目录页&#xff0c;制作好目录之后&#xff0c;选中一个目录&#xff0c;点击插入 – 链接 在插入链接界面中&#xff0c;选择【本文…

前端项目优化:极致最优 vs 相对最优 —— 深入探索与实践

在前端开发的广阔天地中&#xff0c;项目优化是每位开发者不可回避的课题。随着Web应用的复杂度和用户需求的不断提升&#xff0c;如何在保证用户体验的同时&#xff0c;提升页面加载速度、降低资源消耗、增强应用的稳定性和可维护性&#xff0c;成为了前端优化的核心目标。在这…

[项目][WebServer][CGI Task]详细讲解

目录 0.CGI程序主要干什么&#xff1f;1.数据处理2.任务处理 0.CGI程序主要干什么&#xff1f; CGI数据处理主要由外部CGI程序负责&#xff0c;HttpServer只负责将拿到的参数交给CGI程序 即&#xff1a;CGI程序既需要数据处理又需要任务处理&#xff0c;最后将结果传递回HttpS…

白月光git

感觉bug好多干脆直接从头到脚梳理 感冒不嘻嘻 近况是&#xff1a; 早起学习 开车去沟里 把蜜蜂拍到狗身上 把车开回来 吃席 安装git和VScode 都是从官网上装的&#xff0c;不说那么多咯&#xff0c;之前说过&#xff1a; 进程间也要唠一唠-CSDN博客https://blog.csdn.net…

【时时三省】tessy 单元测试 集成测试 专栏 文章阅读说明

目录 1&#xff0c;关于更新 2&#xff0c;关于文章阅读 3&#xff0c;关于文章分类 1&#xff0c;单元测试 2&#xff0c;集成测试 3&#xff0c;通用便捷操作 4&#xff0c;编译问题集锦 5&#xff0c;需求管理 6&#xff0c;CTE的使用 7&#xff0c;tessy自动化执…

JAVA惊喜连连无限可能沉浸式盲盒商城系统小程序源码

&#x1f381;惊喜连连&#xff0c;无限可能&#xff01;沉浸式盲盒商城系统&#xff0c;等你来探索&#x1f50d; &#x1f389;【开篇&#xff1a;盲盒热潮&#xff0c;席卷而来】&#x1f389; 在这个充满未知与惊喜的时代&#xff0c;盲盒文化正以前所未有的速度席卷全球…

详解“c:/work/src/components/a/b.vue“‘ has no default export报错原因

前情提要 在一个vue文件中需要引入定义的b.vue文件&#xff0c;但是提示b文件没有默认导出&#xff0c;对于vue2文件来说有export default &#xff0c;在 <script setup> 中&#xff0c;所有定义的变量、函数和组件都会自动被视为默认导出的组件内容。因此&#xff0c;不…