C++第二十五弹---从零开始模拟STL中的list(下)

 ✨个人主页： 熬夜学编程的小林

💗系列专栏： 【C语言详解】 【数据结构详解】【C++详解】

目录

1、函数补充

2、迭代器完善

3、const迭代器

总结

1、函数补充

拷贝构造

思路：

  • 先构造一个头结点，然后将 lt 类中的元素依次尾插到新的结点上。
void empty_init()
{
	_head = new Node;
	_head->_next = _head;
	_head->_prev = _head;
	_size = 0;
}
list(const list<T>& lt)
{
	empty_init();//构造一个头结点
	for (auto& x : lt)
	{
		push_back(x);
	}
}

 {}初始化构造

思路：

  • 先构造一个头结点，然后将 il 类中的元素依次尾插到新的结点上。
list(initializer_list<T> il)
{
	empty_init();
	for (auto& x : il)
	{
		push_back(x);
	}
}

赋值操作符重载

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

大小相关函数

size_t size()
{
	return _size;
}
bool empty()
{
	return _size == 0;
}

clear()

清空list的内容，保留头结点。

//清空数据
void clear()
{
	iterator it = begin();
	while (it != end())
	{
		it = erase(it);//更新迭代器
	}
}

~list()

析构函数，清空list的内容并释放头结点。

~list()
{
	clear();//清空内容函数
	delete _head;//释放头结点
	_head = nullptr;//置空
}

2、迭代器完善

前面我们处理的都是内置类型的情况，如果我们出现自定义类型，如何解决？

自定义类型举例：

struct A
{
	int _a1;
	int _a2;
	A(int a1 = 0, int a2 = 0)
		:_a1(a1)
		, _a2(a2)
	{}
};

 首先我们先看看几种自定义类型的尾插方式:

void test_list3()
{
	list<A> lt;
	A aa1(1, 1);//实例化对象
	A aa2{ 2,2 };//多参数的隐式类型转换，C++11

	lt.push_back(aa1);//有名对象实例化
	lt.push_back(aa2);
	lt.push_back(A(3, 3));//匿名对象
	lt.push_back({ 4,4 });//多参数的隐式类型转换，C++11
}

 对自定义类型进行遍历：

list<A>::iterator it = lt.begin();
while (it != lt.end())
{
	cout << *it << " ";//自定义类型输出不了
	it++;
}
cout << endl;

A是自定义类型，不支持留插入，我们解引用得到的_data是A的对象 。在结构体中我们获取到自定义类型的对象可以通过 . 进行访问内部成员，此处我们也可以使用 . 进行访问内部成员。

cout << (*it)._a1 << ":" << (*it)._a2 << " ";

但是如果这么使用会有一点别捏，我们在自定义类型中，也可以通过自定义类型的地址来访问成员，即通过 ->访问，此处我们也可以通过 ->进行访问，因此我们需要重载一个operator->()函数 。

迭代器类中重载operator->

T* operator->()
{
    return &_node->_data;//取数据的地址
}

使用->访问元素

cout << it->_a1 << ":" << it->_a2 << " ";

使用重载函数版

cout << it.operator->()->_a1 << ":" << it.operator->()->_a2 << " ";

测试结果：

注意：

这里隐藏了一个箭头，一个是重载，一个是原生指针的访问操作。

当重载 operator->，不会直接返回成员的值，而是应该返回一个指针，这个指针指向的对象包含我们想要访问的成员。当使用 ->运算符时，C++ 会自动和透明地调用重载的 operator-> 并继续 “链式” 访问成员，而不需要程序员显示地添加多余的箭头。 

3、const迭代器

 我们上一弹写的普通迭代器对于const对象是无法编译成功的，const不能调用非const成员函数(权限放大)。

下面我们则实现一个const迭代器的类。

与普通迭代器类似，我们需要先在list类中重命名一个const迭代器

typedef ListConstIterator<T> const_iterator;//const迭代器类

const_iterator begin() const
{
	return const_iterator(_head->_next);//匿名对象
	//return _head->_next;//单参数类型转换
}
const_iterator end() const
{
	return const_iterator(_head);
}

注意：

const迭代器名字不能写成 const iterator，因为const迭代器的本质是迭代器指向的内容不能修改，而不是迭代器本身不能修改，const_iterator这样定义是迭代器不能修改，内容还是可以修改的

实现const_iterator类有两种方式，如下：

方式一(单独实现一个新的类，修改普通迭代器的部分地方)：

template<class T>
struct ListConstIterator
{
	typedef ListConstIterator<T> Self;//对迭代器类重定义

	typedef ListNode<T> Node;
	Node* _node;

	//构造
	ListConstIterator(Node* node)
		:_node(node)
	{}

	const T& operator*()//只能访问，不能修改值
	{
		return _node->_data;
	}
	const T* operator->()
	{
		return &_node->_data;//返回指针
	}
	//前置++ 
	Self& operator++()
	{
		_node = _node->_next;
		return *this;
	}
	//后置++
	Self operator++(int)
	{
		Self tmp(*this);
		_node = _node->_next;
		return *this;
	}
	Self& operator--()
	{
		_node = _node->_prev;
		return *this;
	}
	Self operator--(int)
	{
		Self tmp(*this);
		_node = _node->_prev;
		return tmp;
	}
	bool operator!=(const Self& it)
	{
		return _node != it._node;
	}
	bool operator==(const Self& it)
	{
		return _node == it._node;
	}
};

我们可以看到，const迭代器与普通迭代器的区间只在operator*与operator->的返回的类型上，那么我们是不是可以将两个类封装成一个模板类呢？？？

//普通迭代器和const迭代器只有两个返回值不同，因此我们使用模板封装
template<class T, class Ref, class Ptr>//reference引用 point指针
struct ListIterator
{
	typedef ListIterator<T, Ref, Ptr> Self;//对迭代器类重定义

	typedef ListNode<T> Node;
	Node* _node;

	//构造
	ListIterator(Node* node)
		:_node(node)
	{}

	//T& operator*()//遍历及修改
	Ref operator*()
	{
		return _node->_data;
	}
	//T* operator->()
	Ptr 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& it)
	{
		return _node != it._node;
	}
	bool operator==(const Self& it)
	{
		return _node == it._node;
	}
};

合并之后的三个类模板参数：

  • T：链表结点存储_data值的数据类型
  • Ref：通过迭代器访问数据时的返回类型，可以是T&或者const T&。
  • Ptr：通过迭代器访问数据的指针类型，可以是T*或者const T*。

链表实例化如下：

typedef ListIterator<T, T&, T*> iterator;//普通迭代器类

typedef ListIterator<T, const T&, const T*> const_iterator;//const迭代器类

 list实现全部代码

namespace lin
{
	//链表基本结构
	template<class T>
	struct ListNode
	{
		ListNode<T>* _prev;
		ListNode<T>* _next;
		T _data;

		ListNode(const T& val = T())//初始化值构造
			:_prev(nullptr)
			,_next(nullptr)
			,_data(val)
		{}

	};
	//原版普通迭代器
	//迭代器操作类 方法都要被访问，使用struct
	//template<class T>
	//struct ListIterator
	//{
	//	typedef ListIterator<T> Self;//对迭代器类重定义

	//	typedef ListNode<T> Node;
	//	Node* _node;

	//	//构造
	//	ListIterator(Node* node)
	//		:_node(node)
	//	{}

	//	T& operator*()//遍历及修改
	//	{
	//		return _node->_data;
	//	}
	//	T* operator->()
	//	{
	//		return &_node->_data;//返回指针
	//	}
	//	//前置++ 
	//	Self& operator++()
	//	{
	//		_node = _node->_next;
	//		return *this;
	//	}
	//	//后置++
	//	Self operator++(int)
	//	{
	//		Self tmp(*this);
	//		_node = _node->_next;
	//		return *this;
	//	}
	//	bool operator!=(const Self& it)
	//	{
	//		return _node != it._node;
	//	}
	//	bool operator==(const Self& it)
	//	{
	//		return _node == it._node;
	//	}
	//};

	//原版const迭代器
	//template<class T>
	//struct ListConstIterator
	//{
	//	typedef ListConstIterator<T> Self;//对迭代器类重定义

	//	typedef ListNode<T> Node;
	//	Node* _node;

	//	//构造
	//	ListConstIterator(Node* node)
	//		:_node(node)
	//	{}

	//	const T& operator*()//只能访问，不能修改值
	//	{
	//		return _node->_data;
	//	}
	//	const T* operator->()
	//	{
	//		return &_node->_data;//返回指针
	//	}
	//	//前置++ 
	//	Self& operator++()
	//	{
	//		_node = _node->_next;
	//		return *this;
	//	}
	//	//后置++
	//	Self operator++(int)
	//	{
	//		Self tmp(*this);
	//		_node = _node->_next;
	//		return *this;
	//	}
	//	Self& operator--()
	//	{
	//		_node = _node->_prev;
	//		return *this;
	//	}
	//	Self operator--(int)
	//	{
	//		Self tmp(*this);
	//		_node = _node->_prev;
	//		return tmp;
	//	}
	//	bool operator!=(const Self& it)
	//	{
	//		return _node != it._node;
	//	}
	//	bool operator==(const Self& it)
	//	{
	//		return _node == it._node;
	//	}
	//};

	//普通迭代器和const迭代器只有两个返回值不同，因此我们使用模板封装
	template<class T, class Ref, class Ptr>//reference引用 point指针
	struct ListIterator
	{
		typedef ListIterator<T,Ref,Ptr> Self;//对迭代器类重定义

		typedef ListNode<T> Node;
		Node* _node;

		//构造
		ListIterator(Node* node)
			:_node(node)
		{}

		//T& operator*()//遍历及修改
		Ref operator*()
		{
			return _node->_data;
		}
		//T* operator->()
		Ptr 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& it)
		{
			return _node != it._node;
		}
		bool operator==(const Self& it)
		{
			return _node == it._node;
		}
	};

	
	template<class T>
	class list
	{
		typedef ListNode<T> Node;//将链表结构重命名

	public:
		//普通版本
		//typedef ListIterator<T> iterator;//需要被访问，放在public内

		//typedef ListConstIterator<T> const_iterator;//const迭代器类

		//类模板
		typedef ListIterator<T,T&,T*> iterator;//需要被访问，放在public内

		typedef ListIterator<T,const T&,const T*> const_iterator;//const迭代器类

		//构造哨兵结点
		void empty_init()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}

		list()//默认构造
		{
			empty_init();//创建哨兵头结点
		}
		size_t size()
		{
			return _size;
		}
		void clear()//清空数据，不销毁哨兵头结点
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}
		~list()//析构函数
		{
			clear();
			delete _head;
			_head = nullptr;
		}

		list(const list<T>& lt)//拷贝构造
		{
			empty_init();//创建头结点，然后进行尾插
			for (auto& x : lt)
			{
				push_back(x);
			}
		}
		void swap(list<T>& lt)
		{
			std::swap(_head, lt._head);
			std::swap(_size, lt._size);
		}
		list<T>& operator=(list<T> lt)
		{
			swap(lt);
			return *this;
		}

		iterator begin() 
		{
			return iterator(_head->_next);//匿名对象
			//return _head->_next;//单参数类型转换
		}
		iterator end() 
		{
			return iterator(_head);
		}
		//解决打印修改值问题
		const_iterator begin() const
		{
			return const_iterator(_head->_next);//匿名对象
			//return _head->_next;//单参数类型转换
		}
		const_iterator end() const
		{
			return const_iterator(_head);
		}

		//单独实现的尾插
		//void push_back(const T& val)
		//{
		//	//tail 
		//	Node* newnode = new Node(val);
		//	Node* tail = _head->_prev;

		//	tail->_next = newnode;
		//	newnode->_prev = tail;
		//	newnode->_next = _head;
		//	_head->_prev = newnode;
		//}
		
		void insert(iterator pos, const T& val)//在pos位置前插入val
		{
			Node* cur = pos._node;
			Node* newnode = new Node(val);
			Node* prev = cur->_prev;

			//prev newnode cur
			newnode->_next = cur;
			cur->_prev = newnode;
			prev->_next = newnode;
			newnode->_prev = prev;

			_size++;
		}
		iterator erase(iterator pos)//删除pos位置，防止迭代器失效，返回迭代器后一个位置
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;

			//prev next
			prev->_next = next;
			next->_prev = prev;
			delete cur;
			_size--;
			return iterator(next);
		}
		//调用insert函数
		void push_back(const T& val)
		{
			//insert(--begin(),val);//不能使用+n，在--begin前面插入
			insert(end(), val);//end()前面
		}
		void push_front(const T& val)
		{
			insert(begin(), val);//begin()前面插入
		}
		void pop_back()
		{
			erase(--end());//end()前面删除
		}
		void pop_front()
		{
			erase(begin());//begin()位置删除
		}
	private:
		Node* _head;//链表成员变量
		size_t _size;//链表大小
	};
}

总结


本篇博客就结束啦，谢谢大家的观看，如果公主少年们有好的建议可以留言喔，谢谢大家啦！

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

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

相关文章

深入探索：十种流行的深度神经网络及其运作原理

深入探索：十种流行的深度神经网络及其运作原理

算法 深入探索&#xff1a;十种流行的深度神经网络及其运作原理一、卷积神经网络&#xff08;CNN&#xff09;基本原理工作方式 二、循环神经网络&#xff08;RNN&#xff09;基本原理工作方式 三、长短期记忆网络&#xff08;LSTM&#xff09;基本原理工作方式 四、门控循环单…
阅读更多...
.net core 使用js，.net core 使用javascript，在.net core项目中怎么使用javascript

.net core 使用js，.net core 使用javascript，在.net core项目中怎么使用javascript

.net core 使用js&#xff0c;.net core 使用javascript&#xff0c;在.net core项目中怎么使用javascript 我项目里需要用到“文字编码”&#xff0c;为了保证前端和后端的编码解码不处bug, 所以&#xff0c;我在项目中用了这个 下面推荐之前在.net F4.0时的方法 文章一&#…
阅读更多...
js--hasOwnProperty()讲解与使用

js--hasOwnProperty()讲解与使用

@TOC 前言 hasOwnProperty(propertyName)方法 是用来检测属性是否为对象的自有属性 object.hasOwnProperty(propertyName) // true/false 讲解 hasOwnProperty() 方法是 Object 的原型方法（也称实例方法），它定义在 Object.prototype 对象之上，所有 Object 的实例对象都会继…
阅读更多...
下载中心表设计

下载中心表设计

文件表 有哪些文件需要异步生成 文件夹表 添加文件夹功能时使用 权限表 文件权限绑定 对用户来说&#xff0c;下载文件和配置下载管理是两个可直接交互的功能。下载文件包括&#xff1a; 1&#xff09;添加下载任务&#xff08;手动开始&#xff09;。 2&#xff09;开始…
阅读更多...
安卓约束性布局学习

安卓约束性布局学习

据说这个布局是为了解决各种布局过度前套导致代码复杂的问题的。 我想按照自己想实现的各种效果来逐步学习&#xff0c;那么直接拿微信主页来练手&#xff0c;用约束性布局实现微信首页吧。 先上图 先实现顶部搜索框加号按钮 先实现 在布局中添加一个组件&#xff0c;然后摆放…
阅读更多...
Java学习54-关键字this的使用

Java学习54-关键字this的使用

this是什么 this的作用&#xff1a; 它在方法(准确的说是实例方法或非static的方法)内部使用&#xff0c;表示调用该方法的对象 它在构造器内部使用&#xff0c;表示该构造器正在初始化的对象 this可以调用的结构&#xff1a;成员变量、方法和构造器 什么时候使用this 实…
阅读更多...
安徽代理记账公司的专业服务和创新理念

安徽代理记账公司的专业服务和创新理念

在当今竞争激烈的市场环境中&#xff0c;为了提升企业的运营效率&#xff0c;许多企业开始寻找专业的代理记账公司进行财务管理和记账&#xff0c;本文将介绍一家名为安徽代理记账公司的专业服务和创新理念。 安徽代理记账公司是一家专注于为企业提供全方位会计服务的公司&…
阅读更多...
[ 网络通信基础 ]——网络的传输介质(双绞线,光纤,标准,线序)

[ 网络通信基础 ]——网络的传输介质(双绞线,光纤,标准,线序)

&#x1f3e1;作者主页&#xff1a;点击&#xff01; &#x1f916;网络通信基础TCP/IP专栏&#xff1a;点击&#xff01; ⏰️创作时间&#xff1a;2024年6月8日14点23分 &#x1f004;️文章质量&#xff1a;94分 前言—— 在现代通信网络中&#xff0c;传输介质是数据传…
阅读更多...
江西代理记账公司的专业服务和优质品质

江西代理记账公司的专业服务和优质品质

作为一家专业的代理记账公司&#xff0c;我们始终以“专业、公正、公平”为宗旨&#xff0c;为客户提供全方位的会计咨询服务&#xff0c;我们的服务内容包括但不限于以下几点&#xff1a; 1、代理记账服务&#xff1a;我们拥有丰富的经验和专业知识&#xff0c;能够为企业提供…
阅读更多...
【ARM Cache 系列文章 1.2 -- Data Cache 和 Unified Cache 的详细介绍】

【ARM Cache 系列文章 1.2 -- Data Cache 和 Unified Cache 的详细介绍】

请阅读【ARM Cache 及 MMU/MPU 系列文章专栏导读】 及【嵌入式开发学习必备专栏】 文章目录 Data Cache and Unified Cache数据缓存 (Data Cache)统一缓存 (Unified Cache)数据缓存与统一缓存的比较小结 Data Cache and Unified Cache 在 ARM架构中&#xff0c;缓存&#xff08…
阅读更多...
一次改SQLMAP的操作

一次改SQLMAP的操作

前言 sqlmap这个工具&#xff0c;相信各位大佬们都不陌生&#xff0c;但sqlmap虽好&#xff0c;也时常会有些实际存在但无法注入的地方&#xff0c;这时候就需要我们改它的配置了&#xff0c;今天就以本人遇到的事件进行阐述。 正文 确认注入点 通过一系列测试最终确定这里…
阅读更多...
论文高级图表绘制（Python语言，局部放大图）

论文高级图表绘制（Python语言，局部放大图）

本文将通过一个具体的示例，展示如何使用Python语言和Matplotlib库来绘制高级图表，包括局部放大图的制作。适用于多条曲线绘制在同一个图表中，但由于数据量过大，导致曲线的细节看不清，需要对细节进行局部放大。如下图： 环境准备 首先，确保你的Python环境中已经安装了以…
阅读更多...
PHP超详细安装及应用

PHP超详细安装及应用

目录 所需安装包如下 一、PHP安装 依赖包安装 安装扩展工具&#xff08;先将PHP所需的软件包全部拖进centos根目录下&#xff09; 安装libmcrypt 安装mhash 安装mcrypt 安装PHP 二、设置LAMP组件环境&#xff08;要保证mysql、http都安装完成了&#xff09; Php.ini的建…
阅读更多...
附录二-nmap基本用法

附录二-nmap基本用法

参考 黑客工具—Nmap的使用_哔哩哔哩_bilibili nmap是扫描IP和端口的&#xff0c;相当于攻击前的索敌步骤。不止网络安全方面会用到&#xff0c;平时运维的时候也会用到nmap 1 下载nmap nmap官网 https://nmap.org/ 点击下载&#xff0c;然后点你用的平台就行了 往下滚可以…
阅读更多...
Linux环境在非root用户中搭建(java-tomcat-redis)

Linux环境在非root用户中搭建(java-tomcat-redis)

注: 本文在内网(离线)环境&#xff0c;堡垒机中搭建&#xff0c;服务器不同可能有所差异&#xff0c;仅供参考 本文安装JDK-20.0.1版本&#xff0c;apache-tomcat-10.1.10版本&#xff0c;redis-6.2.15版本 本文服务器IP假设&#xff1a;192.168.88.133 root用户创建子用户并…
阅读更多...
stack overflow复现

stack overflow复现

当你在内存的栈中&#xff0c;存放了太多元素&#xff0c;就有可能在造成 stack overflow这个问题。 今天看看如何复现这个问题。 下图&#xff0c;是我写的程序&#xff0c;不断的创造1KB的栈&#xff0c;来看看执行了多少次&#xff0c;无限循环。 最后结果是7929kB时, 发…
阅读更多...
Echarts 可视化图库案例（Make A Pie）

Echarts 可视化图库案例（Make A Pie）

1、Made A Pie Made A Pie 2、可视化社区 &#xff08;Made A Pie 替代&#xff09; 可视化社区
阅读更多...
标准价与移动平均价简介

标准价与移动平均价简介

一、移动平均价 移动平均价优点&#xff1a; a.移动平均价格可反应”实时的”加权平均价格,特别是物料价格涨跌幅度大时物料的价格不会被差异扭曲。 b.因为是基于交易的实时加权平均计算价格,一般情况下,移动平均价不产生差异&#xff0c;价格相对真实。 c.如果所有的物料都使用…
阅读更多...
算法学习笔记（7.7）-贪心算法（Dijkstra算法-最短路径问题）

算法学习笔记（7.7）-贪心算法（Dijkstra算法-最短路径问题）

目录 1.最短路径问题 2.Dijkstra算法介绍 3.Dijkstra算法演示 4.Dijkstra算法的代码示例 1.最短路径问题 图论中的一个经典问题&#xff0c;通常是指在一个加权图中找到从一个起始顶点到目标顶点的最短路径。 单源最短路径问题&#xff1a;给定一个加权图和一个起始顶点&…
阅读更多...
AI三巨擘或面临反垄断审查 | 百能云芯

AI三巨擘或面临反垄断审查 | 百能云芯

据纽约时报与路透社披露&#xff0c;有内部消息人士指出&#xff0c;美国的相关监管机构已达成共识&#xff0c;计划对OpenAI、微软及英伟达在人工智能&#xff08;AI&#xff09;领域的领导地位展开反垄断审查。这一动作被视为AI监管力度加强的明显信号。 根据此项共识&#x…
阅读更多...
最新文章

Copyright @ 2022~2023