【C++】list的使用与模拟实现

目录

一、list介绍

二、list的使用 

1、list的构造

2、list capacity

3、list element access

4、list iterator

5、list modifiers

5.1、insert

6、list Operations

6.1、sort

7、list的迭代器失效

三、list模拟实现

1、push_back

2、iterator

3、const iterator

4、Ptr

5、insert 及其复用

6、erase 及其复用

7、clear

8、构造函数

8.1、默认构造

8.2、迭代器构造

9、拷贝构造函数

10、析构函数

11、operator=

一、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的使用 

1、list的构造

构造函数（ (constructor)）接口说明
list (size_type n, const value_type& val = value_type())构造的list中包含n个值为val的元素
list()构造空的list
list (const list& x)拷贝构造函数
list (InputIterator first, InputIterator last)用[first, last)区间中的元素构造list

2、list capacity

函数声明接口说明
empty检测list是否为空，是返回true，否则返回false
size返回list中有效节点的个数

3、list element access

函数声明接口说明
front返回list的第一个节点中值的引用
back返回list的最后一个节点中值的引用

4、list iterator

 此处，大家可暂时将迭代器理解成一个指针，该指针指向list中的某个节点。

函数声明接口说明
begin +
end		返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin +
rend		返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的
reverse_iterator,即begin位置

注意：

  1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
  2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动

5、list modifiers

函数声明接口说明
push_front在list首元素前插入值为val的元素
pop_front删除list中第一个元素
push_back在list尾部插入值为val的元素
pop_back删除list中最后一个元素
insert在list position 位置中插入值为val的元素
erase删除list position位置的元素
swap交换两个list中的元素
clear清空list中的有效元素

5.1、insert

使用方法如下：

6、list Operations

函数声明

接口说明
splice将元素从一个列表传输到另一个列表
remove删除具有特定值的元素
unique删除重复值
merge合并排序列表
sort对容器中的元素进行排序
reverse反转元素的顺序

6.1、sort

list无法使用算法库里的 sort 函数，因为算法库里的 sort 函数底层实现如下图所示：

 这里使用了减法运算，而list各个节点的地址都是不连续的，于是就发生了错误。除此之外，算法库里的 sort 函数底层使用快排实现，而快排有一个重要的组成部分：三数取中，也不适用于list。

文档里关于 sort 函数的说明，也暗示使用算法库里的 sort 函数时要传随机迭代器：

 list中的 sort 用法如下：

 功能没有任何问题，但是list的 sort 函数我们很少使用，因为它的效率非常的低。

我们使用如下代码进行证明：

 可以看到，把相同的数据先拷贝到 vector 中排序，排好了之后再拷贝回来，都要比直接使用 list 排序要快。

7、list的迭代器失效

 前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

三、list模拟实现

我们先来搭一个list的基本框架：

namespace bin
{
	template<class T>
	struct list_node
	{
		list_node<T>* _next;
		list_node<T>* _prev;
		T _data;
		
		list_node(const T& x = T())
			:_next(nullptr)
			,_prev(nullptr)
			,_data(x)
		{}
	};

	template<class T>
	class list
	{
		typedef list_node<T> node;
	public:
		list()
		{
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;
		}
	private:
		node* _head;
	};
}

 需要注意：在 list 类中定义私有成员变量时，一定要注意成员变量类型为类名 + 模板参数。

1、push_back

void push_back(const T& x)
{
	node* tail = _head->_prev;
	node* new_node = new node(x);

	tail->_next = new_node;
	new_node->_prev = tail;
	new_node->_next = _head;
	_head->_prev = new_node;
}

具体底层逻辑可以参照文章《双向链表》 。

2、iterator

 list的底层物理空间是不连续的，所以模拟实现迭代器时，就不能直接让指针 "++" 或 "--" 了，而应该实现迭代器 "++" 或 "--" 的重载：

template<class T>
struct __list_iterator
	{
	typedef list_node<T> node;
	typedef __list_iterator<T> self;
	node* _node;

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

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

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

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

 因为我们模拟实现的list类中的迭代器是使用原生指针实现的，且原生指针的类型为 _node* ，没办法直接实现，所以又定义了一个 __list_iterator 类进行封装。

 实验运行结果正确：

 红框框起的部分调用了一次拷贝构造，由于我们没有自己实现拷贝构造函数，所以这里是一次浅拷贝，而我们想要的就是浅拷贝。

 这里浅拷贝之所以没有报错，是因为我们封装的迭代器类中没有实现析构函数，因为迭代器仅仅是使用list对象节点，而不是拥有list对象节点，它没有权利释放list的对象。

 我们再来完善一下迭代器的其他功能：

template<class T>
	struct __list_iterator
	{
		typedef list_node<T> node;
		typedef __list_iterator<T> self;
		node* _node;

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

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

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

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

		self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

		self& operator--(int)
		{
			self tmp(*this);
			_node = _node->_prev;
			return tmp;
		}

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

3、const iterator

先来看一下错误的写法：

 直接在list类中定义 const 类型的成员函数。这种写法的错误之处在于，这些 const 类型成员函数所针对的是list类中的成员变量 _head ，虽然 _head 被 const 限制无法更改，但是 _head 所指向的 _data 仍然可以更改，即数据仍然可以被更改，不符合我们的预期。

 我们较为容易想到的写法是直接再另外定义一个类，在这个新类中封装 const 类型的迭代器：

 虽然这种写法可以实现功能且完全满足需求，但是代码太过于冗余，接下来我们来学习一种新的写法：

在迭代器模板中多增加了一个模板参数 Ref ，用于满足不同的调用需求。

4、Ptr

观察如下代码：

 编译器报错，因为我们没有为自定义类型 AA 实现流插入重载，所以需要写成这种形式：

 但是我们在写 C++ 代码时，一般没有写成这种形式的习惯，大多数都是通过 "->" 来实现解引用操作的，所以我们可以改变写法：

 这种写法乍一看非常难以理解，这时因为为了增强可读性的缘故，在这里少写了一个 "->" ：

 大家看一下完整版的写法就一定能够理解：

 同理，为了满足不同的调用需求，应该为list类重载一个 const 类型的成员函数，为了不造成代码冗余，同样只需要为list类模板增加一个模板参数就可以了：

5、insert 及其复用

具体实现如下： 

 list的 insert 不会导致迭代器失效。

可以使用 insert 函数的复用来实现 push_back 与 push_front ：

6、erase 及其复用

具体实现如下：

  list的 erase 会导致迭代器失效。

为了在使用 erase 函数后仍然可以找到该节点的下一个节点，我们使用返回值来返回需要的信息：

 可以使用 erase 函数的复用来实现 pop_back 与 pop_front ：

7、clear

具体实现方法如下：

 也可以使用下面这种写法：

8、构造函数

8.1、默认构造

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

list()
{
	empty_init();
}

8.2、迭代器构造

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

template <class Iterator>
list(Iterator first, Iterator last)
{
	empty_init();
	while (first != last)
	{
		push_back(*first);
		++first;
	}
}

 扩展内容：

 const 类型的对象是无法调用 empty_init() 函数的，因为这属于权限放大。那么为什么我们写如下 const 类型对象的实例化不会报错呢？

 这是因为该 const 对象在定义的时候并没有 const 属性，在该对象定义完成后，才被赋予了 const 属性，否则就没有办法对对象进行初始化操作了。

9、拷贝构造函数

传统写法如下：

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

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

这里再提供一份现代写法：

void swap(list<T>& tmp)
{
	std::swap(_head, tmp._head);
}

list(const list<T>& lt)
{
	empty_init();

	list<T> tmp(lt.begin(), lt.end());
	swap(tmp);
}

10、析构函数

实现代码如下：

~list()
{
	clear();
	delete _head;
	_head = nullptr;
}

11、operator=

实现代码如下：

void swap(list<T>& tmp)
{
	std::swap(_head, tmp._head);
}

list<T>& operator=(list<T> lt)
{
	swap(lt);
	return *this;
}

注意：这里的传参没有使用传引用传参，而是采用了传值传参。这是因为我们本来就期望在传参时发生一次拷贝构造，并把拷贝构造出的临时变量与 this 进行交换，这样不会影响到赋值运算符重载的右值本身。

关于list的使用和模拟实现的相关内容就讲到这里，欢迎同学们多多支持，如果有不对的地方欢迎大佬指正，谢谢！

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

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

相关文章

循环神经网络

循环神经网络

循环神经网络(Recurrent Neural Network&#xff0c;RNN)与卷积神经网络一样,都是深度学习中的重要部分。循环神经网络可以看作一类具有短期记忆能力的神经网络。在循环神经网络中&#xff0c;神经元不但可以接收其他神经元的信息&#xff0c;也可以接收自身的信息&#xff0c;…
阅读更多...
Python实现PDF转Word文档

Python实现PDF转Word文档

1. 模块安装 pip install pdf2docx安装时可能报错&#xff1a; 到 Microsoft C Build Tools 下载C编译环境安装即可。 2. 模块介绍 pdf2docx是一个Python模块&#xff0c;可以用来将PDF文件转换成Word文档。它是基于Python的pdfminer和python-docx库开发的&#xff0c;可以…
阅读更多...
toArray转换 java.lang.ClassCastException

toArray转换 java.lang.ClassCastException

[toArray转换踩坑 java.lang.ClassCastException] 问题 List<String> auditOptions Lists.newArrayList(); //一系列灌数据操作 auditOption.add... String[] options (String[]) auditOptions.toArray();报错信息java.lang.ClassCastException: class [Ljava.lang.O…
阅读更多...
【Blender】如何在Blender中添加HDRI环境贴图

【Blender】如何在Blender中添加HDRI环境贴图

​ 什么是HDRI环境贴图 环境贴图或HDRI贴图是在Blender中照亮3D场景并实现逼真效果的最有效和最快捷的方法之一。 HDRIs本质上是现实世界照明的快照&#xff0c;其中包含高动态范围成像&#xff08;HDRI&#xff09;的准确照明细节。HDRI是一个包含亮度信息&#xff08;从暗…
阅读更多...
ToBeWritten之IoT 技战法

ToBeWritten之IoT 技战法

也许每个人出生的时候都以为这世界都是为他一个人而存在的&#xff0c;当他发现自己错的时候&#xff0c;他便开始长大 少走了弯路&#xff0c;也就错过了风景&#xff0c;无论如何&#xff0c;感谢经历 转移发布平台通知&#xff1a;将不再在CSDN博客发布新文章&#xff0c;敬…
阅读更多...
VMware ESXi 8.0c - 领先的裸机 Hypervisor (sysin Custom Image)

VMware ESXi 8.0c - 领先的裸机 Hypervisor (sysin Custom Image)

本站发布 Dell 和 HPE 定制版 ESXi 8.0c 镜像 请访问原文链接&#xff1a;https://sysin.org/blog/vmware-esxi-8/&#xff0c;查看最新版。原创作品&#xff0c;转载请保留出处。 作者主页&#xff1a;sysin.org 产品简介 VMware ESXi&#xff1a;专门构建的裸机 Hyperviso…
阅读更多...
问卷调查怎么帮助餐饮行业？

问卷调查怎么帮助餐饮行业？

在餐饮行业中&#xff0c;顾客的口碑占据非常重要的地位&#xff0c;直接影响着门店的销售额。好口碑能一传十、十传百&#xff0c;为门店带来持续不断的流量和收益。所以&#xff0c;在顾客体验这一块&#xff0c;餐饮门店要尤为重视。 某餐饮品牌作为全球知名品牌&#xff0…
阅读更多...
MongoDB【使用场景简介体系结构数据模型特点】

MongoDB【使用场景简介体系结构数据模型特点】

目录 1&#xff1a;MongoDB相关概念 1.1&#xff1a;业务应用场景 1.2&#xff1a;MongoDB简介 1.3&#xff1a;体系结构 1.4&#xff1a;数据模型 1.5&#xff1a;MongoDB的特点 1&#xff1a;MongoDB相关概念 1.1&#xff1a;业务应用场景 传统的关系型数据库&#x…
阅读更多...
AOP原理 - 分析AnnotationAwareAspectJAutoProxyCreator源码

AOP原理 - 分析AnnotationAwareAspectJAutoProxyCreator源码

文章目录一、回顾EnableAspectJAutoProxy二、AbstractAutoProxyCreator类三、AbstractAdvisorAutoProxyCreator类四、AspectJAwareAdvisorAutoProxyCreator类五、AnnotationAwareAspectJAutoProxyCreator类一、回顾EnableAspectJAutoProxy 在上一章中&#xff0c;通过查看Enabl…
阅读更多...
Spring原理学习（三）：BeanFactory后处理器原理解析与模拟实现

Spring原理学习（三）：BeanFactory后处理器原理解析与模拟实现

一、简单认识BeanFactory后处理器 1.1 BeanFactory后处理器的作用 接前文&#xff1a;Spring原理学习&#xff08;一&#xff09;&#xff1a;BeanFactory和ApplicationContext的原理和实现 我们已经简单介绍了 BeanFactory后处理器 的作用&#xff0c;今天我们先再来再次体验…
阅读更多...
酒店拥有VR全景是一种什么样的体验？

酒店拥有VR全景是一种什么样的体验？

每一家酒店都希望自己门庭若市&#xff0c;有更多的人来&#xff0c;随着信息化和互联网的发展时代的到来&#xff0c;酒店营销也逐渐加入了更多的现代元素&#xff0c;那么&#xff0c;酒店怎么样更好地利用互联网来做宣传、来获得更多的客户呢&#xff1f;VR全景作为新兴的富…
阅读更多...
排序和分页

排序和分页

排序和分页一、排序1.简单用法3.不同字段不同排序现实二、分页1.简单分页2.order by 配合limit三、分页8.0新特性1.offset总结提示&#xff1a;以下是本篇文章正文内容 一、排序 1.简单用法 select employee_id,last_name,salary from employees order by salary;默认是升序…
阅读更多...
Maven高级-分模块开发依赖管理

Maven高级-分模块开发依赖管理

Maven高级-分模块开发&依赖管理1&#xff0c;分模块开发1.1 分模块开发设计1.2 分模块开发实现1.2.1 环境准备1.2.2 抽取domain层步骤1:创建新模块步骤2:项目中创建domain包步骤3:删除原项目中的domain包步骤4:建立依赖关系步骤5:编译maven_02_ssm项目步骤6:将项目安装本地…
阅读更多...
Memory Map

Memory Map

主要介绍AM64x的MSRAM和DDR的内存分布&#xff1a; MSRAM:总共2MB,被分成8个banks,每个256KB。 首先了解一下&#xff0c;两种Domain: In TI documentation, the MCU Domain may be referred to as “M4FSS Island”, “MCU Island”, “MCU Channel”, or “MCU Subsystem…
阅读更多...
Redis分布式缓存

Redis分布式缓存

文章目录一、 概述1. 单节点Redis存在的问题2. 单节点Redis问题针对解决方案二、Redis持久化1. RDB持久化2.RDB异步持久化原理介绍3. AOF持久化4. ROB和AOF对比三、Redis主从架构1. 搭建主从架构2. 主从数据同步原理四、Redis哨兵1. 哨兵的作用和原理2.搭建哨兵集群3. RedisTem…
阅读更多...
Linux 操作系统原理 — RSS 多队列网卡

Linux 操作系统原理 — RSS 多队列网卡

目录 文章目录目录RSS 多队列网卡RSS 技术实现原理RSS FilterRSS HASH硬中断信号绑定ethtool 操作指令RSS 多队列网卡 在以往&#xff0c;一张 NIC 只具有一个 Rx Queue&#xff0c;对应一个 CPU Core 来进行收包处理。在多核时代&#xff0c;为了充分利用 Multi-CPU Cores&am…
阅读更多...
如何使用pandas提取含有指定字符串

如何使用pandas提取含有指定字符串

这里写自定义目录标题name age state point0 Alice 24 NY 641 Bob 42 CA 922 Charlie 18 CA 70name age state point0 Alice 24 NY 642 Charlie 18 CA 700 False1 True2 TrueName: state, dtype: boolname age state point1 Bob 42 CA 922 Charlie 18 CA 700 True1 False2 True…
阅读更多...
tmall.service.settleadjustment.modify( 修改结算调整单 )

tmall.service.settleadjustment.modify( 修改结算调整单 )

&#xffe5;开放平台免费API必须用户授权 提供给服务商在对结算有异议时&#xff0c;发起结算调整单。 通过说明调整单ID&#xff0c;调整费用值&#xff0c;调整原因进行结算调整单修改。 公共参数 请求地址: 公共请求参数: 公共响应参数: 请求参数 响应参数 点击获取key和…
阅读更多...
MyBatisPlus-DML编程控制

MyBatisPlus-DML编程控制

MyBatisPlus-DML编程控制4&#xff0c;DML编程控制4.1 id生成策略控制知识点1&#xff1a;TableId4.1.1 环境构建4.1.2 代码演示AUTO策略步骤1:设置生成策略为AUTO步骤2:删除测试数据并修改自增值步骤3:运行新增方法INPUT策略步骤1:设置生成策略为INPUT步骤2:添加数据手动设置I…
阅读更多...
【hello Linux】Linux权限管理

【hello Linux】Linux权限管理

目录 1.shell命令以及运行原理 2. Linux权限的概念 3. Linux权限管理 3.1 文件访问者的分类 3.2 文件类型 3.3 访问权限 3.4 访问权限的表示方法 4. 访问权限的相关设置 4.1 chmod命令&#xff1a;修改权限 4.2 chown命令&#xff1a;修改文件的拥有者 4.3 chgrp 命令&#xff…
阅读更多...
最新文章

Copyright @ 2022~2023