STL list的主要接口模拟实现

devtools/2024/10/18 10:14:14/

list_1">STL-list是什么

STL里面的list本质上就是一个双向带头循环链表,如果不知道什么是双链表的话可以去看看这篇文章双链表
就像下面这种C语言双链表结构
在这里插入图片描述在这里插入图片描述

只不过在这个原有的基础之上添加了增删查改的功能，让他变得更高级更实用
相当于把这个list封装了一遍，让我们可以调用他的接口，更加方便快捷，下面我们来看看具体怎么实现

list_8">list的模拟实现

在list里面有点麻烦的就是他的迭代器，这个和string还有vector的迭代器有点不一样，他的内存空间不是连续的，我们不能随机访问
所以我们把list分为3个部分写成两个struct和一个class，（struct的默认是公有的，这样我们在调用迭代器，还有创建节点的时候会方便一**些不像class默认是私有的）第一个是节点，这里定义了节点的数据域，还有指向前驱和后继指针的指针域，第二个是迭代器，这里我们可以简单的把迭代器理解成一个指针，用来对list进行操作，**最后一个用来定义list本身。
下面我们看看代码

	template<class type>struct list_node{type data;list_node<type>* _next;list_node<type>* _prev;list_node(const type& val = type()):data(val), _next(nullptr), _prev(nullptr){}};

这里就是节点本身有数据域和指针域，这里我们用了一个模板，让编译器自动推导，这样的好处是可以存放任何数据，使用性更加广泛，
这里我们用了初始化列表，来作为默认构造函数

list_node(const type& val = type()):data(val), _next(nullptr), _prev(nullptr){}

**const type& val = type()**这里我们用了一个匿名对象来进行我们链表节点的构造，这样的好处就是，我们在构造节点的时候不用去手动去拿一个类去构造对象，这里的匿名对象自动去调用属于他自己的默认构造，列如int会去调用int的默认构造，匿名对象只在当前行起作用，出了当前行就自动销毁。

list_38">list的迭代器

	template<class type, class ref, class ptr>struct list_iterator{list_node<type>* _node;list_iterator(list_node<type>* node):_node(node){}list_iterator<type, ref, ptr>& operator++(){this->_node = _node->_next;return *this;}list_iterator<type, ref, ptr>& operator--(){this->_node = _node->_prev;return *this;}list_iterator<type, ref, ptr> operator++(int){list_iterator<type, ref, ptr> temp = *this;this->_node = _node->_next;return temp;}list_iterator<type, ref, ptr> operator--(int){list_iterator<type, ref, ptr> temp = *this;this->_node = _node->_prev;return temp;}// l1 != l2bool operator !=(list_iterator<type, ref, ptr> l2){if (this->_node != l2._node){return true;}else{return false;}}bool operator == (list_iterator<type, ref, ptr> l2){return this->_node == l2._node;}ref operator*(){return this->_node->data;}ptr operator->(){&_node->data;}};

这里我们实现了主要的常用的迭代器的功能

template<class type, class ref, class ptr>

这里的定义的模板参数需要讲一下，这里，实现了类模板给编译器，给了编译器不同的参数，编译器实例化了两个不同的类第一个是type就是数据类型，下面这个ref就是引用,ptr就是指针，这样是为了方便const调用,ref,ptr具体是什么不用管，编译器会根据传的数据类型来推导创建相对应的类，传const引用就是const ref ,const ptr，不传就是普通指针，普通引用，如果不用模板，就要写两个非常相似的类，这样就太冗余了，非常麻烦

list_node<type>* _node;list_iterator(list_node<type>* node):_node(node){}

这里就是迭代器的默认构造，也是走的初始化列表，这里传了一个list_node类型的数据，也就是创建的节点来当构造参数，这里的迭代器我们可以把他理解成一个为我们list服务的专有指针，所以是list_node* _node类型，这个_node就是指针

list_iterator<type, ref, ptr>& operator++(){this->_node = _node->_next;return *this;}

这里就是实现迭代器++我们需要返回引用，因为要改变当前的迭代器的位置，这里的++不像vector还有string那样可以用原生指针，list的内存空间不连续，但他有指向前一个和下一个的指针
在这里插入图片描述
所以我们++就要返回当前迭代器指向的下一个地址就行了

list_iterator<type, ref, ptr>& operator--(){this->_node = _node->_prev;return *this;}

迭代器–也同理
下面是后置++迭代器，后置++，这里他会改变当前迭代器指向的位置，但会返回原来迭代器的位置，所以我们要创建一个temp变量来存放当前迭代器的值

	list_iterator<type, ref, ptr> operator++(int){list_iterator<type, ref, ptr> temp = *this;this->_node = _node->_next;return temp;}

迭代器–也同理

	bool operator !=(list_iterator<type, ref, ptr> l2){if (this->_node != l2._node){return true;}else{return false;}}

这里是判断两个迭代器的是不是不相等的，用当前迭代器指向的位置来判断，
判断相等也同理

	bool operator == (list_iterator<type, ref, ptr> l2){return this->_node == l2._node;}

这里是对*的运算符重载，返回当前迭代器下面的数据域，这里就体现模板的作用了，这里的ref是没有被定义的可以返回普通的，也可以是const的

ref operator*()
{return this->_node->data;
}

我们可以来试一下
在这里插入图片描述
这里迭代器就讲解完了，我们来说说list

list_173">list

下面是代码

template<class type, class ref, class ptr>
class list
{
public:void init_empty(){_head = new list_node<type>;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){init_empty();}//l2(l1)list(const list<type, ref, ptr>& l1){init_empty();list_iterator<type, const ref, const ptr> it = l1.const_begin();while (it.operator!=(l1.const_end())){this->push_back(*it);it++;}}void swap(list<type, ref, ptr>& li){std::swap(this->_head, li._head);std::swap(this->_size, li._size);}// l1                             l2list<type, ref, ptr>& operator=(list<type, ref, ptr>& li){swap(li);return *this;}void clear(){auto it = this->begin();while (it != this->end()){it = this->erase(it);}}~list(){clear();delete this->_head;this->_head = nullptr;}list_iterator<type, ref, ptr> begin(){return _head->_next;}list_iterator<type, ref, ptr> end(){return _head;}list_iterator<type, const ref, const ptr> const_begin() const{return _head->_next;}list_iterator<type, const ref, const ptr> const_end() const{return _head;}//tail newnode headvoid push_back(const type& input){list_node<type>* newnode = new list_node<type>(input);list_node<type>* tail = this->_head->_prev;newnode->_next = this->_head;newnode->_prev = tail;tail->_next = newnode;this->_head->_prev = newnode;_size++;}//pos newnode nextvoid insert(list_iterator<type, ref, ptr> pos, const type& input){list_node<type>* newnode = new list_node<type>(input);list_node<type>* next = pos._node->_next;list_node<type>* poser = pos._node;newnode->_next = next;newnode->_prev = poser;pos._node->_next = newnode;next->_prev = newnode;_size++;}// prev pos nextlist_iterator<type, ref, ptr> erase(list_iterator<type, ref, ptr> pos){list_node<type>* poser = pos._node;list_node<type>* next = poser->_next;list_node<type>* prev = poser->_prev;delete poser;prev->_next = next;next->_prev = prev;return next;}void pop_fornt(){erase(this->begin());}void pop_back(){erase(this->end()--);}size_t size(){return this->_size;}size_t size() const{return this->_size;}bool is_empty(){return this->_size == 0;}
private:size_t _size;list_node<type>* _head;
};

这里，因为我们是双向循环带头链表，在初始化的时候就需要创建一个头节点，这个头节点不存放任何东西

void init_empty(){_head = new list_node<type>;_head->_next = _head;_head->_prev = _head;_size = 0;}

所以我们的默认构造函数，就要调用init_empty()来满足这个双向链表的结构特点

list()
{init_empty();
}

在有头节点之后，我们在进行对数据的插入，修改等
下面是拷贝构造函数

	//l2(l1)list(const list<type, ref, ptr>& l1){init_empty();list_iterator<type, const ref, const ptr> it = l1.const_begin();while (it.operator!=(l1.const_end())){this->push_back(*it);it++;}}

这个拷贝构造函数很巧妙，用了一个尾插来解决，把原始list里面的值复制一份拿下来，这里的必须是 const ref, const ptr，因为拷贝构造传的参数必须是const对类类型的对象的引用，这段代码用了迭代器来完成拷贝构造，it获取最先开始的位置，依次++直到最后一个迭代器位置
在这里插入图片描述
接下来就是赋值运算符重载

	// l1                             l2list<type, ref, ptr>& operator=(list<type, ref, ptr>& li){swap(li);return *this;}void swap(list<type, ref, ptr>& li){std::swap(this->_head, li._head);std::swap(this->_size, li._size);}

这里很巧妙，直接交换两个对象指向的指针，还有大小，就行了，假设把l2复制给l1，this指针是指向l1，交换完之后this就是指向l2了，当swap函数结束之后，l1会自动销毁，带走l1所指向的链表，直接返回*this就可以了,就完成了赋值，
下面是析构函数

		void clear(){auto it = this->begin();while (it != this->end()){it = this->erase(it);}}~list(){clear();delete this->_head;this->_head = nullptr;}

这里我们通过erase(it)这个函数来实现析构，这个函数就是删除当前节点函数，也是通过两个迭代器来控制区间，最后就是删除头节点
下面这些就是非常简单的小函数了，返回开始和结束的迭代器，还有const版本

list_iterator<type, ref, ptr> begin()
{return _head->_next;
}
list_iterator<type, ref, ptr> end()
{return _head;
}
list_iterator<type, const ref, const ptr> const_begin() const
{return _head->_next;
}
list_iterator<type, const ref, const ptr> const_end() const
{return _head;
}

下面我们来说说erase

list_iterator<type, ref, ptr> erase(list_iterator<type, ref, ptr> pos)
{list_node<type>* poser = pos._node;list_node<type>* next = poser->_next;list_node<type>* prev = poser->_prev;delete poser;prev->_next = next;next->_prev = prev;return next;
}

这里我们可以画图来理解一下
在这里插入图片描述
像push_back和insert可以看看开头给的文章链接，里面有更详细的讲解

	void pop_fornt(){erase(this->begin());_size--;}void pop_back(){erase(this->end()--);_size--;}size_t size(){return this->_size;}size_t size() const{return this->_size;}bool is_empty(){return this->_size == 0;}

这些小函数就不需要过多的讲解了删除头部，和删除尾部都可以调用erase来解决，判空可以判断_size是不是为0，size，我们在对链表中push_back ，insert, 等，里面都有对size进行统计，这样统计size更加方便，不用在去新写一个函数进行对size进行统计
print打印函数

template<class print_type>
void print(print_type& p1)
{list_iterator<int, int&, int*> it = p1.begin();while (it != p1.end()){cout << *it << " ";it++;}cout << endl;
}

这里，我们创建了一个模板类，这里和上面一样可以传不同的数据类型进来进行打印，不同的数据类型实例化不同的类型，提高了函数的利用性
以上就是对list的主要接口的实现，如果有什么问题欢迎指正！
完


http://www.ppmy.cn/devtools/93953.html

相关文章

8.12-基于gtids的主从复制搭建+lvs

8.12-基于gtids的主从复制搭建+lvs

一、LVS 1.角色 主机名ip地址功能web01192.168.2.101rsweb02192.168.2.102realserveenat内网:192.168.2.103 外网:192.168.2.120directorserver,ntpdns192.168.2.105dns 2..web服务器 [rootweb01 ~]# yum -y install nginx ​ [rootweb01 ~]# echo "web01" > …
阅读更多...
RabbitMq的事务机制

RabbitMq的事务机制

RabbitMQ中与事务机制有关的方法有三个&#xff1a;txSelect(), txCommit()以及txRollback(), txSelect用于将当前channel设置成transaction模式&#xff0c;txCommit用于提交事务&#xff0c;txRollback用于回滚事务&#xff0c;在通过txSelect开启事务之后&#xff0c;我们便…
阅读更多...
Java中的人机交互（HCI）：构建交互式应用程序

Java中的人机交互（HCI）：构建交互式应用程序

人机交互&#xff08;Human-Computer Interaction, HCI&#xff09;是研究人类与计算机系统之间交互的学科。在Java编程中&#xff0c;HCI不仅涉及用户界面的设计&#xff0c;还包括用户体验的优化、交互技术的实现以及用户输入的处理。本文将深入探讨如何在Java中实现高效的人…
阅读更多...
学习STM32（2）--STM32单片机GPIO应用

学习STM32（2）--STM32单片机GPIO应用

目录 1 引 言 2 实验目的 3 实验内容 3.1掌握STM32F103的GPIO控制 3.1.1 GPIO的分组 3.1.2 GPIO的常用功能 3.1.3 STM32单片机GPIO位结构 3.1.4 STM32单片机GPIO工作模式 3.1.5 STM32的GPIO 输出-点亮LED编程要点 使用GPIO时&#xff0c;按下面步骤进行&#xff1…
阅读更多...
【SpringBoot 属性加载机制】

【SpringBoot 属性加载机制】

SpringBoot 属性加载 一个 SpringBoot 应用的配置属性可以有多种不同的来源, 比如可以来自操作系统的环境变量, 比如可以来自 application.yaml 文件; 每一种不同的属性来源, 都会被 SpringBoot 封装成一个PropertySource对象, 保存在 Environment 对象的 PropertySources 类型…
阅读更多...
死信队列.

死信队列.

“死信”是指在RabbitMQ中那些因为某些原因无法被正常处理的消息。
阅读更多...
从零开始实现循环神经网络

从零开始实现循环神经网络

本节我们通过使用MXnet&#xff0c;来从零开始的实现一个含有隐藏状态的循环神经网络。 前序工作 数据集预处理进行采样 实现循环神经网络 完成前序工作后&#xff0c;即可开始实现循环神经网络。本文首先构建一个具有隐状态的循环神经网络。其结构如图所示&#xff1a; 接…
阅读更多...
C语言指针详解-包过系列（二）目录版

C语言指针详解-包过系列（二）目录版

C语言指针详解-包过系列&#xff08;二&#xff09;目录版 1、数组名的深入理解1.1、数组名的本质1.2、数组名本质的两个例外1.2.1、sizeof&#xff08;数组名&#xff09;1.2.2、&数组名 2、使用指针访问数组3、一维数组传参本质4、二级指针4.1、二级指针介绍4.2、二级指针…
阅读更多...
最新文章

Copyright @ 2022~2023