list的介绍及其模拟实现

今天我们了解list，list在python中是列表的意思 ，但是在C++中它是一个带头双向循环链表：

list的介绍
  1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
  2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
  3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
  4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
  5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)
list的模拟实现

有了前面的string和vector的模拟实现，我们的list的模拟实现算是轻车熟路了，我们要想模拟实现list就需要了解list在库里面的源码，我们用everything查找一下
在这里插入图片描述
在这里插入图片描述
可以看到，在list的类里面成员参数只有一个，但是这个参数是此前定义的一个结构体，它包含了，next，prev和当前节点存储的data，所以我们同样需要去自定义一个结构体

我们首先把定义一个结构体，就是list的节点的结构，同时在里面定义一个构造新节点的函数：

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)
	{}
};

然后我们就可以在命名空间内定义list类了：
为了可读性和代码的简洁，我就用Node来作为list_node的重命名了

namespace jh
{
	template <class T>
	struct list_node
	{
		T _data;
		list_node* _prev;
		list_node* _next;

		list_node(const T& x = T())
			:_data(x)
			, _prev(nullptr)
			, _next(nullptr)
		{}
	};
	template <class T>
	class list
	{
		
		typedef list_node<T> Node;
	private:
		Node* _head;
		size_t _size;
	};
}

我们首先就拿下最难啃的一块骨头：

迭代器

我们再次查看list的源码就会发现：
迭代器同样地使用了一个结构体来构造，所以这里我们也采用结构体
在这里插入图片描述
我们先整体地构造一个框架：
至于模块的地方为什么有多个参数我稍后做讲解，这是一个很重要的点
迭代器就是一个节点，我们同时定义一个拷贝构造的函数

	template <class T,class Ref,class Ptr>
	struct __list_iterator
	{
		typedef list_node<T> Node;
		typedef __list_iterator<T,Ref,Ptr> self;
		Node* _node;
		__list_iterator(Node* node)
			:_node(node)
		{}
	};

++和–的重载：
迭代器最常用的点就是++和–，因为我们需要用迭代器来初始化等等，我们就首先在结构体内重载++和–：
括号后面又int的我们之前的博客也进行学习过，它是后置，编译器会自动识别的，temp就是一个匿名参数，他的生命周期只有一行，这里的->运算符我们之后也要做重载，不然不能用
这里还有一个需要注意的点：
前置是返回对象本身，所以用引用返回减少拷贝，但是后置返回的是对象temp临时变量，是一个常量，不能用引用

self& operator++()
{
	_node = _node->_next;
	return *this;
}
self& opetrator--()
{
	_node = _node->prev;
	return *this;
}
self operator++(int)
{
	self temp(*this);
	_node = _node->next;
	return temp;
}
self operator--(int)
{
	self temp(*this);
	_node = _node->prev;
	return temp;
}

*和->的重载：
*是解引用，就是返回迭代器所存储的数据，返回data就是
—>操作符前的是一个地址，所以就取地址就可以了，这里的Ref和Ptr就派上用场了

Ref operator*()
{
	return _node->_data;
}

Ptr operator->()
{
	return &_node->data;
}

!=和==操作符重载：
这里用bool类型就可以了，直接返回它们之间的关系即可

bool operator!=(const self& s)
{
	return _node != s._node;
}

bool operator==(const self& s)
{
	return _node == s._node;
}

迭代器就完成了：
增加Ref和Ptr的作用就是为了随时适应，例如需要const T或者const T*这种，这样就省去了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;

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

		self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		self& operator--()
		{
			_node = _node->prev;
			return *this;
		}
		self operator++(int)
		{
			self temp(*this);
			_node = _node->next;
			return temp;
		}
		self operator--(int)
		{
			self temp(*this);
			_node = _node->prev;
			return temp;
		}

		Ref operator*()
		{
			return _node->_data;
		}

		Ptr operator->()
		{
			return &_node->data;
		}

		bool operator!=(const self& s)
		{
			return _node != s._node;
		}

		bool operator==(const self& s)
		{
			return _node == s._node;
		}

	};

迭代器解决后我们就可以将其应用到list类里了：
这里大家记住：
begin就是头节点head的下一个节点
end就是head节点

const_iterator begin() const
{
	return const_iterator(_head->_next);
}
const_iterator end() const
{
	return const_iterator(_head);
}
iterator begin()
{
	return iterator(_head->_next);
}
iterator end()
{
	return iterator(_head);
}
构造函数

构造函数我们必须有一个头节点head，同时我们要知道当list为空时，head的next和prev都是head本身

void empty_init()
{
	_head = new Node;
	_head->_next = _head;
	_head->_prev = _head;
}

list()
{
	empty_init();
}
insert函数

insert函数要做的就是首先构造一个新的节点，然后插入，插入很简单，我们在数据结构中学过，这里不做过多的讲解：
记住最后要返回插入的那个新节点！

iterator insert(iterator pos, const T& x = T())
{
	Node* cur = pos._node;
	Node* newnode = new Node(x);
	Node* prev = cur->_prev;
	prev->_next = newnode;
	newnode->_next = cur;
	cur->_prev = newnode;
	newnode->_prev = prev;
	return iterator(newnode);
}
erase函数

erase函数同样地也是用数据结构的知识来操作，但是erase函数返回的是删除pos位置的下一个位置的迭代器：

iterator erase(iterator pos)
{
	Node* cur = pos._node;
	Node* prev = cur->_prev;
	Node* next = cur->_next;
	delete cur;
	prev->_next = next;
	next->_prev = prev;
	return iterator(next);
}
尾删和头删，尾插和头插

这些我们在有了解决了erase和insert之后可以直接复用了：

void push_back(const T& x)
{
	insert(end(), x);
}
void push_front(const T& x)
{
	insert(begin(), x);
}
void pop_back()
{
	erase(end());
}
void pop_front()
{
	erase(begin());
}
拷贝构造函数

拷贝构造函数我们依旧用pushback和语法糖来实现：
逐一将lt中的元素尾插进入即可

list(const list<t>T& lt)
{
	empty_init();
	for (auto e : lt)
	{
		push_back(e);
	}
}
赋值操作符重载

赋值操作符重载我们用swap解决，直接调用std库里的swap函数即可：

void swap(list<T>& lt)
{
	std::swap(_head, lt._head);
}
list<T>& operator=(list<T> lt)
{
	swap(lt);
	return *this;
}
析构函数

我们先定义一个clear函数用于清理空间，然后复用，记住将head节点释放：

void clear()
{
	iterator it = begin();
	while (it != end())
	{
		it = erase(it);//erase每次返回的都是it的next，故可以这样写
	}
}
~list()
{
	clear();
	delete _head;
	_head = nullptr;
}

到这里，list的模拟实现差不多就结束了，感谢大家的支持！

完整代码如下：

using namespace std;
namespace jh
{
	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 Ref, class Ptr>
	struct __list_iterator
	{
		typedef list_node<T> Node;
		typedef __list_iterator<T, Ref, Ptr> 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 temp(*this);
			_node = _node->_next;
			return temp;
		}
		self operator--(int)
		{
			self temp(*this);
			_node = _node->_prev;
			return temp;
		}

		Ref operator*()
		{
			return _node->_data;
		}

		Ptr 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, const T&, const T*> iterator;
		typedef __list_iterator<T, const T&, const T*> const_iterator;

		const_iterator begin() const
		{
			return const_iterator(_head->_next);
		}
		const_iterator end() const
		{
			return const_iterator(_head);
		}
		iterator begin()
		{
			return iterator(_head->_next);
		}
		iterator end()
		{
			return iterator(_head);
		}

		void empty_init()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}

		list()
		{
			empty_init();
		}

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

		iterator erase(iterator pos)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;
			delete cur;
			prev->_next = next;
			next->_prev = prev;
			return iterator(next);
		}
		
		void push_back(const T& x)
		{
			insert(end(), x);
		}
		void push_front(const T& x)
		{
			insert(begin(), x);
		}
		void pop_back()
		{
			erase(end());
		}
		void pop_front()
		{
			erase(begin());
		}

		list(const list<T>& lt)
		{
			empty_init();
			for (auto e : lt)
			{
				push_back(e);
			}
		}

		void swap(list<T>& lt)
		{
			std::swap(_head, lt._head);
		}
		list<int>& operator=(list<int> lt)
		{
			swap(lt);
			return *this;
		}

		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}

	private:
		Node* _head;
		size_t _size;
	};
}

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

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

相关文章

Cuda笔记1

Cuda笔记1

1、培训001 1 1…100&#xff0c;CPU是串行执行&#xff0c;GPU是分成几部分同时计算&#xff0c;如123,456… 2、培训002 一来一回 每种定义有对应的调用位置&#xff0c;和执行位置&#xff0c;不对会报错。 下图是用NVPROF时间分析 下图是资源分析 1&#xff09; CUDA…
阅读更多...
W3School离线手册(2017.03.11版)

W3School离线手册(2017.03.11版)

点击下载 W3School离线手册(2017.03.11版)
阅读更多...
企业软件项目成果-图像识别

企业软件项目成果-图像识别

下面图像识别仅仅使用了OpenCV库而已&#xff0c;并没有涉及深度学习、机器学习。 整盘样本的拍照识别结果&#xff08;识别准确率达100%&#xff09;&#xff1a; 宫颈刷图像识别的测试结果&#xff08;识别准确率达100%&#xff09;&#xff1a;
阅读更多...
springboot druid数据库配置密码加密

springboot druid数据库配置密码加密

1.使用的druid版本 <!-- 阿里数据库连接池 --> <dependency><groupId>com.alibaba</groupId><artifactId>druid-spring-boot-3-starter</artifactId><version>1.2.21</version> </dependency> 2.配置文件 # Spring配置 …
阅读更多...
Linux文件管理技术实践

Linux文件管理技术实践

shell shell的种类(了解) shell是用于和Linux内核进行交互的一个程序&#xff0c;他的功能和window系统下的cmd是一样的。而且shell的种类也有很多常见的有c shell、bash shell、Korn shell等等。而本文就是使用Linux最常见的bash shell对Linux常见指令展开探讨。 内置shell…
阅读更多...
大模型相关学习资料整理【长久更新】

大模型相关学习资料整理【长久更新】

笔者学习和收集大模型相关资料&#xff0c;只收集&#xff1a;官方 OR 易懂 OR 全面。 且后续我会针对大模型的名词和新机制做专门易懂的博客讲解&#xff0c;可以点个关注。等待后续更新。 目前整理资料如下&#xff1a; 1. 核心应用开发框架 1. semantic-kernel【微软】 …
阅读更多...
vue3-elementPlus部分组件样式修改

vue3-elementPlus部分组件样式修改

前提&#xff1a;在less语言下使用/deep/&#xff1b;在sass语言下使用 ::v-deep 替换 /deep/ 但::v-deep的写法已经废弃&#xff0c;建议使用:deep(css选择器) elementUI样式修改&#xff1a;vue2-elementUI部分组件样式修改_vue2 圆圈选中样式-CSDN博客 el-dropdown //下拉…
阅读更多...
如何修复HP打印机黄灯故障灯？这里提供详细步骤

如何修复HP打印机黄灯故障灯？这里提供详细步骤

HP打印机配备了两个黄色指示灯，一个在“恢复”按钮上，另一个在打印头警报图标上。此类指示灯主要出现在HP Deskjet、Smart Tank和Envy系列打印机上。 当打印头警报图标亮起黄色时，问题主要出现在墨盒。它表示墨盒内的墨芯液位低，或者是时候清洁打印头了。如果“恢复”按钮…
阅读更多...
lumen自定义封装api限流中间件

lumen自定义封装api限流中间件

背景 现在公司重构api项目&#xff0c;针对有些写入和请求的接口需要进行限制设置。比如说一分钟60次等。看了网上的都是laravel的throttle限流&#xff0c;但是没有针对lumen的&#xff0c;所以需要自己重新封装。 实现 1.在App\Http\Middleware下创建一个自定义的中间件&a…
阅读更多...
CS BOF文件编写/改写

CS BOF文件编写/改写

Beacon Object File(BOF) cs 4.1后添加的新功能&#xff0c; Beacon在接收执行obj前&#xff0c;Cobalt Strike会先对这个obj文件进行一些处理&#xff0c;比如解析obj文件中一些需要的段.text&#xff0c;.data&#xff0c;在处理一些表比如IMAGE_RELOCATION&#xff0c;IMAGE…
阅读更多...
QT入门篇---无门槛学习

QT入门篇---无门槛学习

1.1 什么是 Qt Qt 是⼀个 跨平台的 C 图形⽤⼾界⾯应⽤程序框架 。它为应⽤程序开发者提供了建⽴艺术级图形界⾯所需的所有功能。它是完全⾯向对象的&#xff0c;很容易扩展。Qt 为开发者提供了⼀种基于组件的开发模式&#xff0c;开发者可以通过简单的拖拽和组合来实现复杂的…
阅读更多...
RUST笔记 FireDBG｜ Rust 代码调试器

RUST笔记 FireDBG｜ Rust 代码调试器

安装https://firedbg.sea-ql.org/blog/2023-12-12-introducing-firedbg/ 更新VSCODE sudo dpkg -i code_1.85.2-1705561292_amd64.deb 安装FireDBG binaries (base) pddpdd-Dell-G15-5511:~$ curl https://raw.githubusercontent.com/SeaQL/FireDBG.for.Rust/main/install.sh …
阅读更多...
[极客大挑战 2019]PHP1

[极客大挑战 2019]PHP1

知识点&#xff1a; 1.序列化的属性个数大于实际属性个数可以绕过_wakeup() 详见[CTF]PHP反序列化总结_ctf php反序列化-CSDN博客 2.private属性类名和属性名前都会有多一个NULL&#xff0c;phpstorm运行结果可以显示出来&#xff0c;但是复制出去会变成空格&#xff0c;要手动…
阅读更多...
【Single Cell Genomics】Part2 Deep representation learning (form theislab)

【Single Cell Genomics】Part2 Deep representation learning (form theislab)

文章目录 7 Deep representation learning in single cell genomics7.1 scanpy7.2 DCA7.3 scGen: predicting single-cell perturbation effects7.4 Human cell atlas 来自Manolis Kellis教授&#xff08;MIT计算生物学主任&#xff09;的课 YouTube&#xff1a;Single Cell Ge…
阅读更多...
关于达梦认证DCA DCP，TIDB认证PCTA PCTP考试那点事儿

关于达梦认证DCA DCP，TIDB认证PCTA PCTP考试那点事儿

文章最后有彩蛋&#xff0c;一定要看到最后... 一、正确的道路上遇到正确的你 伴随中国数据库领域的快速技术进步&#xff0c;国内数据库生态蓬勃发展&#xff0c;并不断涌现出极具创新力的产品&#xff0c;推动了数据库应用的遍地开花。截至2024年1月&#xff0c;墨天轮数据社…
阅读更多...
SWMM模型INP解析

SWMM模型INP解析

.INP文件解析 [OPTIONS]&#xff1a;SWMM软件运行前需要设置的参数 [RAINGAGES]雨水节点&#xff0c;核心设置雨水时间序列&#xff0c;可为INP内部数据也可为外部txt数据&#xff0c;TIMESERIES对应【TIMESERIES】模块&#xff0c;TS_1为时间序列名称 [TIMESERIES]&#xff0…
阅读更多...
红黑树底层实现

红黑树底层实现

什么是红黑树 红黑树&#xff0c;是一种二叉搜索树&#xff0c;但在每个结点上增加一个存储位表示结点的颜色&#xff0c;可以是Red&#xff08;红&#xff09;或Black&#xff08;黑&#xff09;&#xff0c;它是一种比AVL树在使用上更优秀的树&#xff0c;通过对任何一条从根…
阅读更多...
微信小程序开发position等于static、relative、absolute、fixed、stricky时元素显示详细介绍

微信小程序开发position等于static、relative、absolute、fixed、stricky时元素显示详细介绍

No Position 不设置position时显示，以红色元素做测试： Static 元素根据界面正常流进行定位。top、right、bottom、left 和 z-index 属性不起作用。这是默认值。 红色元素设置position: static，显示如下： Relative 元素根据界面正常流进行定位。以元素当前位置为基准，根…
阅读更多...
g2o--ba代码解析

g2o--ba代码解析

概要 g2o是常用的图优化理论c库&#xff0c;其自带了很多example讲解如何使用该库文件&#xff0c;本文分析其中ba的示例代码。 所谓的图优化&#xff0c;就是把一个常规的优化问题&#xff0c;以图&#xff08;Graph&#xff09;的形式来表述。 在图中&#xff0c;以顶点表…
阅读更多...
单片机介绍

单片机介绍

本文为博主 日月同辉&#xff0c;与我共生&#xff0c;csdn原创首发。希望看完后能对你有所帮助&#xff0c;不足之处请指正&#xff01;一起交流学习&#xff0c;共同进步&#xff01; > 发布人&#xff1a;日月同辉,与我共生_单片机-CSDN博客 > 欢迎你为独创博主日月同…
阅读更多...
最新文章

Copyright @ 2022~2023