C++修炼之路之list模拟实现--C++中的双向循环链表

目录

引言 

一:STL源代码中关于list的成员变量的介绍

二:模拟实现list

1.基本结构

2.普通迭代器 +const迭代器的结合

3.构造+拷贝构造+析构+赋值重载 +清空

4.insert+erase+头尾插入删除 

 5.打印不同数据类型的数据《使用模板加容器来完成》

三:全部代码加测试用例链接 

接下来的日子会顺顺利利,万事胜意,生活明朗-----------林辞忧

引言 

在前面的数据结构中已经实现了c版本的list-双向循环链表,但在c++中注重的是分装,对于操作进行封装处理,对于我们使用便是方便了不少,但模拟实现的话还是有许多要注意的细节点,尤其是list的迭代器较复杂,需要认真理解

一:STL源代码中关于list的成员变量的介绍

在源代码中使用一个头结点的指针来 模拟实现的,但在文档中只介绍list是一个双向链表的容器,并没有说明是否带哨兵位了,之时就得观察初始化函数和构造函数等来观察

 所以从这里就可以看出list的结构就是一个带头循环双向链表,接下来我们就开始模拟实现

二:模拟实现list

1.基本结构

template<class T>//泛型编程
struct list_node
{
	T _data;
	list_node<T>* _prev;
	list_node<T>* _next;

	list_node(const T &x=T())//缺省值为匿名对象
		:_data(x)
		,_prev(nullptr)
		,_next(nullptr)
	{}
};

template<class T>
class list
{
	typedef list_node<T> node;
public:

private:
	node* head;
	size_t size;//方便size()接口,省去便利的开销
};

2.普通迭代器 +const迭代器的结合

对于用迭代器来遍历list的数据,就不能像vector和string那样,直接使用,因为

list<int>::iterator it=lt1.begin();

while(it!=lt1.end())

{

     cout<<*it<<" ";

     ++it;

}

cout<<endl;

对于这里面的*it和++it和it!=lt1.end()这些操作是不能直接支持的,因为*it是要取data的数据,++it就是要使_node=_node->next等,这些是和vector,string是不一样的,所以得自己手动支持,运用运算符重载+函数封装,我们先来观察源代码中的实现

我们先来实现普通迭代器

 

template<class T>
struct _list_iterator
{
	typedef list_node<T> Node;
	typedef _list_iterator<T> self;
	Node* node;

	_list_iterator(Node*node)
		:_node(node)
	{}

	self& operator++()
	{
		_node = _node->next;
		return *this;
	}
	self& operator--()
	{
		_node = _node->prev;
		return *this;
	}
	self operator++(int)
	{
		self tmp(*this);
		_node = _node->next;
		return tmp;
	}
	self operator--(int)
	{
		self tmp(*this);
		_node = _node->prev;
		return tmp;
	}
	T& operator*()
	{
		return _node->data;
	}
	T* operator->()
	{
		return &_node->data;
	}
	bool operator!=(const self& s)
	{
		return _node != s._node;
	}
	bool operator==(const self& s)
	{
		return _node == s._node;
	}

};
template<class T>
class list
{
	typedef list_node<T> node;
public:
	typedef _list_iterator<T> iterator;
	iterator begin()
	{
		//return iterator(_head->_next);
		return _head->_next;
	}
	iterator end()
	{
		return _head;
	}

对于这个结构可以这样来理解

 

 我们知道const对象使用的是const迭代器那么在iterator之前加const的话,这样const iterator指的是迭代器本身不能修改,但在遍历过程迭代器本身是要改变的,如++it等,所以不能这样写

应该为const_iterator这是一个重新定义的一个类型,要做到迭代器本身可以改变,但迭代器指向的内容不能改变

在原来普通迭代器的基础上重载出一份const迭代器的版本如

但这样的话对于普通迭代器和const迭代器两份代码是由许多相同的代码的,比较冗余,所以在源代码中提出了一份更好的解决方案来解决这个问题 

在原来基础上多添加两个参数,这样对于同一个类模板,实例化参数不同就是不同的类型

对于上面的代码就要优化为更完善的代码,展示主要优化的代码

 

template<class T,class Ref,class Ptr>
struct _list_iterator
{
	typedef list_node<T> Node;
	typedef _list_iterator<T,Ref,Ptr> self;
	Node* node;
	
	Ref operator*()
	{
		return _node->data;
	}
	Ptr operator->()
	{
		return &_node->data;
	}
	
	typedef _list_iterator<T,T&,T*> iterator;
	typedef _list_iterator<T, const T&, const T*> const_iterator;
	//typedef __list_const_iterator<T> const_iterator;
	iterator begin()
	{
		//return iterator(_head->_next);
		return _head->_next;
	}
	iterator end()
	{
		return _head;
	}
	const_iterator begin()const
	{
		//return iterator(_head->_next);
		return const_iterator(_head->_next);
	}
	const_iterator end()const
	{
		return const_iterator(_head);
	}

对于->编译器是做处理的,将两个->优化为一个详细看代码及测试 用例3中

3.构造+拷贝构造+析构+赋值重载 +清空

构造时要使用带头循环双向循环链表的初始化操作,观看https://blog.csdn.net/Miwll/article/details/136593441?spm=1001.2014.3001.5502

 

void empty_init()
{
	_head = new Node;
	_head->_next = _head;
	_head->_prev = _head;
	_size = 0;
}
list()
{
	empty_init();
}
list(const list<T>& t)//拷贝构造实现为深拷贝
{
	empty_init();
	for (auto e : t)
	{
		push_back(e);
	}
}
/*list<int>& operator=(const list<int>& lt)
{
	if (this != &lt)
	{
		clear();
		for (auto e : lt)
		{
			push_back(e);
		}
	}
	return *this;
}*/
void swap(list<T>& t)
{
	std::swap(_head,t._head);
	std::swap(_size, t._size);
}
list<int>& operator=(const list<int>& lt)
{
	swap(lt);
	return *this;
}
~list()
{
	clear();
	delete _head;
	_head =nullptr;
}
void clear()
{
	iterator it = begin();
	while (it != end())
	{
		it = erase(it);
	}
}

4.insert+erase+头尾插入删除 

void push_back(const T& x)
{
	insert(end(), x);
}

void push_front(const T& x)
{
	insert(begin(), x);
}

void pop_front()
{
	erase(begin());
}

void pop_back()
{
	erase(--end());
}
iterator insert(iterator pos, const T& x)
{
	Node* cur = pos._node;
	Node* newnode = new Node(x);
	Node* prev = cur->_prev;

	prev->_next = newnode;
	newnode->_prev = prev;
	newnode->_next = cur;
	cur->_prev = newnode;
	++_size;
	return iterator(newnode);
}
iterator erase(iterator pos)
{
	Node* cur = pos._node;
	Node* next = cur->_next;
	Node* prev = cur->_prev;

	delete cur;
	prev->_next = next;
	next->_prev = prev;
	--_size;
	return iterator(next);
}
size_t size()
{
	return _size;
}

 5.打印不同数据类型的数据《使用模板加容器来完成》

使用模板来打印自定义类型数据,注意这里加的typename

list<T>未实例化的类模板,编译器不能去他里面去找
编译器就无法list<T>::const_iterator是内嵌类型,还是静态成员变量
前面加一个typename就是告诉编译器,这里是一个类型,等list<T>实例化
再去类里面去取

三:全部代码加测试用例链接 

https://gitee.com/lin-ciyu/cplusplus/tree/master/my_list/my_list

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/547026.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

SQLite、MySQL 和 PostgreSQL 数据库速度比较(本文阐述时间很早比较,不具有最新参考性)(二十五)

返回&#xff1a;SQLite—系列文章目录 上一篇&#xff1a;用于 SQLite 的异步 I/O 模块&#xff08;二十四&#xff09; 下一篇&#xff1a;SQLite—系列文章目录 注意&#xff1a;本文档非常非常旧。它描述了速度比较 SQLite、MySQL 和 PostgreSQL 的古老版本。 这里…

学习一门语言的方法和套路(B站转述)

视频链接 up虽然长相英(ping)俊(ping)&#xff0c;但是讲的干活&#xff0c;没恰饭。 学习流程&#xff1a; 1.快速阅读&#xff0c;掌握概况 2.深入细节内容 例如&#xff1a;java (JDBC)、html 、netty 不管三七二十一&#xff0c;先了解套路&#xff0c;再深入研究。 高…

安装CUDNN详细过程

cuDNN&#xff08;CUDA Deep Neural Network library&#xff09;是由NVIDIA开发的深度学习GPU加速库。 cuDNN包含了许多针对神经网络操作进行高度优化的函数&#xff0c;旨在使深度学习框架能够在NVIDIA的GPU上实现最佳性能&#xff0c;这个库提供了高效计算和加速&#xff0c…

牛客网刷题 :BC50 你是天才吗

描述 据说智商140以上者称为天才&#xff0c;KiKi想知道他自己是不是天才&#xff0c;请帮他编程判断。输入一个整数表示一个人的智商&#xff0c;如果大于等于140&#xff0c;则表明他是一个天才&#xff0c;输出“Genius”。 输入描述&#xff1a; 多组输入&#xff0c;每…

在 PyCharm 中使用系统安装的 Python 和 Anaconda 的 Python什么区别

virtualenv environment &#xff1a; virtualenv 是一个用于创建独立 Python 环境的工具。它可以在同一个系统上创建多个相互独立的 Python 环境&#xff0c;每个环境都有自己的 Python 解释器和包库&#xff0c;从而可以实现不同项目之间的依赖隔离和版本控制。coda environm…

vue快速入门(二十五)本地存储与初始化使用

注释很详细&#xff0c;直接上代码 上一篇 新增内容 本地获取数据数据存储到本地 源码 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial…

2024蓝桥杯——宝石问题

先展示题目 声明 以下代码仅是我的个人看法&#xff0c;在自己考试过程中的优化版&#xff0c;本人考试就踩了很多坑&#xff0c;我会—一列举出来。代码可能很多&#xff0c;但是总体时间复杂度不高只有0(N) 函数里面的动态数组我没有写开辟判断和free&#xff0c;这里我忽略…

频率域滤波基础(离散傅里叶变换使用填充的缺陷)

本来是个很简单的问题&#xff0c;作者硬是写的这么复杂&#xff0c;翻译还搞错了。重点是我发现作者真正有用的东西没讲到&#xff0c;比如相位和谱如何影响图像。连个转换公式都没有&#xff0c;我只能说作者是在混字数。 首先看关于中心对称是什么意思&#xff1f;我木太明白…

MySql 视图 存储过程 触发器

文章目录 视图数据库对象视图的理解创建、查看、更新、删除 存储过程和存储函数概述分类存储过程的创建和调用存储函数的创建和调用存储过程和存储函数的对比存储过程和存储函数的查看、修改、删除 变量GLOBAL 与 SESSION 变量的使用会话用户变量和局部变量的使用 定义条件与处…

【机器学习300问】70、向量化技术来计算神经网络时维度如何确保正确?

一、向量化技术在进行神经网络计算时的优势 向量化是一种优化技术&#xff0c;通过使用数组操作代替for循环&#xff0c;可以大大提高代码的性能和效率。在深度学习中尤其明显&#xff0c;可以提高计算效率、简化代码、优化内存使用。 二、如何确保计算时维度是正确的&#xf…

中标了,Trojan/Hijack.v木马病毒怎么解决?

火绒只是提示有病毒木马&#xff0c;并未解决。 经过不断尝试.。。。。。。 往下拉找到 Internet选项 连接 – 局域网设置 把前面的勾选取消 发现以上办法网络上出现的搜索注册表关键字等办法都无法解决。。。 解决方法一&#xff1a; 电脑进入安全模式&#xff0c;然后进…

【vue】v-model 双向数据绑定

:value&#xff1a;单向数据绑定v-model&#xff1a;双向数据绑定 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0">…

STM32 MPU配置参数

TXE LEVEL一般只用MPU_TEX_LEVEL0 1 - 1 - 1 -0性能最强&#xff08;TEX - C - B- S&#xff09;. #define MPU_TEX_LEVEL0 ((uint8_t)0x00) #define MPU_TEX_LEVEL1 ((uint8_t)0x01) #define MPU_TEX_LEVEL2 ((uint8_t)0x02) 基于上表进行常用配置 &#xff…

Wpf 使用 Prism 实战开发Day19

待办事项功能页面完善以及优化 概要&#xff1a; 由于待办事项功能页&#xff0c;数据已正常渲染出来了。但页面新增&#xff0c;查询&#xff0c;修改&#xff0c;删除等功能还未实现。本章节来实现页面的请求后台实现CURD&#xff08;增删改查&#xff09; 一.待办事项查询…

泰迪智能科技携手韩山师范学院“企业微专业合作办学招生宣讲”圆满结束

为进一步深化校企合作&#xff0c;落实高校应用型人才培养。2024年4月11日&#xff0c;泰迪智能科技携手韩山师范学院开展企业微专业合作办学招生宣讲会在韩山师范学院顺利举行&#xff0c;本次宣讲会旨在与韩山师范学院学子深入讲解数字经济时代下的企业用工需求&#xff0c;着…

ins视频批量下载,instagram批量爬取视频信息

简介 Instagram 是目前最热门的社交媒体平台之一,拥有大量优质的视频内容。但是要逐一下载这些视频往往非常耗时。在这篇文章中,我们将介绍如何使用 Python 编写一个脚本,来实现 Instagram 视频的批量下载和信息爬取。 我们使用selenium获取目标用户的 HTML 源代码,并将其保存…

数据结构 -- 二分查找

本文主要梳理了二分查找算法的几种实现思路&#xff0c;基本概念参考 顺序、二分、哈希查找的区别及联系_生成一个大小为10万的有序数组,随机查找一个元素,分别采用顺序查找和二分查找方式-CSDN博客 1、基本概念 &#xff08;1&#xff09;前提条件&#xff1a;待查找数据必须…

解决调用相同url数据不刷新问题

原代码 原因 谷歌浏览访问相同接口默认调用缓存数据 解决方案 添加时间戳

WebKit简介及工作流程

文章目录 一、WebKit简介二、WebKit结构三、Webkit工作流程四、WebKit常见问题五、WebKit优点六、相关链接 一、WebKit简介 WebKit是一个开源的浏览器引擎&#xff0c;它的起源可以追溯到2001年&#xff0c;当时苹果公司推出了其首款基于Unix的操作系统Mac OS X。在2002年&…

科大讯飞星火开源大模型iFlytekSpark-13B GPU版部署方法

星火大模型的主页&#xff1a;iFlytekSpark-13B: 讯飞星火开源-13B&#xff08;iFlytekSpark-13B&#xff09;拥有130亿参数&#xff0c;新一代认知大模型&#xff0c;一经发布&#xff0c;众多科研院所和高校便期待科大讯飞能够开源。 为了让大家使用的更加方便&#xff0c;科…