【list的模拟实现】—— 我与C++的模拟实现（十四）

一、list节点

​ list是一个双向循环带头的链表，所以链表节点结构如下：

	template<class T>
	struct ListNode
	{
		T val;
		ListNode* next;
		ListNode* prve;
		ListNode(int x)
		{
			val = x;
			next = prve = this;
		}
	};

二、list迭代器

2.1、list迭代器与vector迭代器区别

​ list迭代器与vector迭代器不一样，不能使用简单的原生指针了；

vector中迭代器可以使用原生指针，因为vector的存储空间是连续的，可以通过指针+/-/++/–找到下一个（上一个）位置；而list(链表)我们知道存储空间是不连续的，不能通过指针++/—找到下一个（上一个）节点；那我们就不能使用原生指针。

2.2、list迭代器实现

​ 既然原生指针不能满足我们的需求，那我们就要用其他的方法来实现迭代器，这时候类的封装的意义就体现出来了；我们只需要对原生指针进行封装，然后使用运算符重载来修改迭代器++/–这些行为，这样就可以满足我们的需求了。

具体代码如下：

	template<class T, class Ref, class Str>
	class list_iterator
	{
		typedef ListNode Node;
		typedef list_iterator iterator;
	public:
		list_iterator(Node* node)
		{
			_node = node;
		}
		//前置++
		iterator operator++()
		{
			Node tmp(_node);
			_node = _node->_next;
			return tmp;
		}
		//后置++
		iterator operator++(int)
		{
			_node = _node->_next;
			return *this;
		}
		//前置--
		iterator operator--()
		{
			Node tmp(_node);
			_node = _node->_prve;
			return tmp;
		}
		iterator operator--(int)
		{
			_node = _node->_prve;
			return *this;
		}
		bool operator==(const iterator& it)
		{
			return _node == it._node;
		}
		bool operator!=(const iterator& it)
		{
			return _node != it._node;
		}
		Ref operator*()
		{
			return _node->val;
		}
		Ptr operator->()
		{
			return &(_node->_val);
		}
	private:
		Node* _node;
	};

三、list实现

3.1、构造函数

在这里插入图片描述

先看一下list构造函数的接口

构造函数接口说明
list()默认构造函数，构造一个空的list
list (size_type n, const value_type& val =value_type())用n个val值构造list
list (InputIterator first, InputIterator last)还有一段迭代器区间初始化
list (const list& x)拷贝构造函数

​ 这里我们实现的list是带头双向循环链表，具体结构与之前的双向链表相同。

在构造之前，我们需要先构造一个头结点，这里就写一个函数 empty_init 来构造这个头结点。

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

默认构造函数

list()
{
	empty_init();
	_size = 0;
}

用n个val值构造

list(size_t n, const T& val)
{
	/*_head = new Node();
	_head->_next = _head;
	_head->_prve = _head;*/
	empty_init();
	for (size_t i = 0; i < n; i++)
	{
		Node* newnode = new Node(val);

		newnode->_next = _head->_next;
		newnode->_prve = _head->_next;
		_head->_next->_prve = newnode;
		_head->_next = newnode;
	}
	_size = n;
}

迭代器区间构造

​ 使用迭代器区间构造，这里复用一下后面的push_back直接尾插来构造。

template<class InputIterator>
list(InputIterator first, InputIterator last)
{
	empty_init();
	_size = 0;
	while (first != last)
	{
		push_back(*first);
		_size++;
	}
}
void push_back(const T& val)
{
	Node* newnode = new Node(val);
	newnode->_next = _head;
    newnode->_prve = _head->_prve;
	_head->_prve->_next = newnode;
	_head->_prve = newnode;
}

拷贝构造函数

​ 拷贝构造，这里直接复用上面迭代器构造即可。

		list(const list& l)
		{
			empty_init();
			list(l.begin(), l.end());
			_size = l.size();
		}

3.2、迭代器

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

​ 这里迭代器返回值，可以直接返回节点指针（因为单参数的构造函数支持隐式类型转换）。

3.3、Capacity

在这里插入图片描述

​ 主要就是empty和size（判断空和数据个数）

		//Capacity
		bool empty()
		{
			return _head == _head->_next;
		}
		size_t size()
		{
			/*size_t ret = 0;
			Node* ptail = _head->_next;
			while (ptail != head)
			{
				ret++;
				ptail = ptail->_next;
			}
			return ret;*/
			return _size;
		}

​ 这里遍历链表来计算数据个数，代价太大了，我们直接写一个成员变量，在初始化，插入和删除时修改，会方便很多。

3.4、增删查改

在这里插入图片描述

​ 这里增删查改就实现其中的一部分，其他的不太常用。

3.4.1、push_back、push_front、pop_back、pop_front

​ 头插尾插，头删尾删，对于list而言，只需要修改指针的指向；

void push_back(const T& val)
{
	Node* newnode = new Node(val);
	newnode->_next = _head;
	newnode->_prve = _head->_prve;
	_head->_prve->_next = newnode;
	_head->_prve = newnode;
}
void push_front(const T& val)
{
	Node* newnode = new Node(val);
	newnode->_next = _head->_next;
	newnode->_prve = _head;
	_head->_next->_prve = newnode;
	_head->_next = newnode;
}

//删
void pop_back()
{
	if (!empty())
	{
		Node* del = _head->_prve;
		_head->_prve->_prve->_next = _head;
		_head->_prve = _head->_prve->_prve;
		delete del;
	}
}
void pop_front()
{
	if (!empty())
	{
		Node* del = _head->_next;
		_head->_next->_next->_prve = _head;
		_head->_next = _head->_next->_next;
		delete del;
	}
}

3.4.2、insert

在这里插入图片描述

​ insert在指定位置插入数据，看它的参数列表，大概就知道，要在迭代器position 迭代器位置（之前）插入数据（1个或者n个），或者插入一段迭代器区间的数据。

//insert
void insert(iterator pos, const T& val)
{
	Node* newnode = new Node(val);
	Node* tmp = pos._node;
	newnode->_next = tmp;
	newnode->_prve = tmp->_prve;

	tmp->_prve->_next = newnode;
	tmp->_prve = newnode;
    ++_size;
}
void insert(iterator pos, size_t n, const T& val)
{
	for(size_t i = 0; i < n; i++)
	{
		Node* newnode = new Node(val);
		Node* tmp = pos._node;
		newnode->_next = tmp;
		newnode->_prve = tmp->_prve;

		tmp->_prve->_next = newnode;
		tmp->_prve = newnode;
	}
    _size+=n;
}
void insert(iterator pos, int n, const T& val)
{
	for(size_t i = 0; i < n; i++)
	{
		Node* newnode = new Node(val);
		Node* tmp = pos._node;
		newnode->_next = tmp;
		newnode->_prve = tmp->_prve;

		tmp->_prve->_next = newnode;
		tmp->_prve = newnode;
	}
}

这里需要注意：

​ 看到这里可能会疑惑，为什么实现了两个插入n个数据 的insert函数；

​ 因为，当数据类型是int时，下面模版实例化出的函数（iterator , int , int）比这里实现的(iterator , size_t , int)更加匹配；编译器就会去调用更加匹配的函数，就会出错。这里就是为了防止这种出错。

​ 插入迭代器的数据，与使用迭代器区间构造初始化相似，list只需改变指针指向即可。

		template<class InputIterator>
		void insert(iterator pos, InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				Node* newnode = new Node(*first);
				Node* tmp = pos._node;
				newnode->_next = tmp;
				newnode->_prve = tmp->_prve;

				tmp->_prve->_next = newnode;
				tmp->_prve = newnode;
				++first;
			}
		}

3.4.3、erase

​ erase删除一个节点，我们要修改前后节点的指针指向。

iterator erase(iterator pos)
{
	assert(pos != end());
	Node* del = pos._node;
	Node* next = del->_next;
	Node* prve = del->_prve;
	next->_prve = prve;
	prve->_next = next;
	delete del;
	return next;
}

​ 在我们删除节点之后，之前的迭代器就会失效，为了解决迭代器失效问题，我们就使用返回值，返回新的迭代器。

3.4.4、swap

​ 这里实现的list只有一个成员函数（头结点的指针），直接交换即可。

		void swap(list& l)
		{
			std::swap(_head, l._head);
		}

3.4.5、clear

​ clear函数，清理数据，（保留头结点）。

		//清除数据
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}

3.5、析构函数

​ 析构函数相对就比较简单了，我们清理完数据，再释放头结点即可。

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

到这里，list的模拟实现就完成了；这里只是实现了其中的一部分内容，感兴趣的可以继续深入了解学习。

我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=2oul0hvapjsws
ear函数，清理数据，（保留头结点）。

		//清除数据
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}

3.5、析构函数

​ 析构函数相对就比较简单了，我们清理完数据，再释放头结点即可。

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

到这里，list的模拟实现就完成了；这里只是实现了其中的一部分内容，感兴趣的可以继续深入了解学习。

我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=2oul0hvapjsws

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

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

相关文章

QString 转 char*问题与方法（const_cast的使用问题)

QString 转 char*问题与方法（const_cast的使用问题)

1、背景:今天有QString的变量&#xff0c;将QString的值传递给void func(char * ptr)&#xff0c;于是就有了类似下面这一段离谱的代码 当时我还在想为什么var的值为空了&#xff0c;为什么呢。 2、原因:就是因为右边函数返回的是一个临时指针对象&#xff0c;给到了右边&…
阅读更多...
每天五分钟机器学习：支持向量机算法数学基础之核函数

每天五分钟机器学习：支持向量机算法数学基础之核函数

本文重点 从现在开始，我们将开启支持向量机算法的学习，不过在学习支持向量机算法之前，我们先来学习一些支持向量机所依赖的数学知识，这会帮助我们更加深刻的理解支持向量机算法，本文我们先来学习核函数。 定义 核函数（Kernel Function）是一种在支持向量机（SVM）、高…
阅读更多...
云原生之运维监控实践-使用Prometheus与Grafana实现对Nginx和Nacos服务的监测

云原生之运维监控实践-使用Prometheus与Grafana实现对Nginx和Nacos服务的监测

背景 如果你要为应用程序构建规范或用户故事&#xff0c;那么务必先把应用程序每个组件的监控指标考虑进来&#xff0c;千万不要等到项目结束或部署之前再做这件事情。——《Prometheus监控实战》 去年写了一篇在Docker环境下部署若依微服务ruoyi-cloud项目的文章&#xff0c;当…
阅读更多...
MiniMates：一款轻量级的图片数字人驱动框架

MiniMates：一款轻量级的图片数字人驱动框架

随着数字人技术的不断发展，越来越多的应用场景开始涌现，从虚拟主播到AI伴侣，数字人的应用范围越来越广。然而，现有的数字人驱动框架往往存在性能瓶颈、依赖性强、定制难度高等问题。近期，我发现了一款名为 MiniMates 的轻量级图片数字人驱动框架，它在性能、个性化定制和终…
阅读更多...
SpringBoot3_Web开发

SpringBoot3_Web开发

4. 内容协商 一套系统适配多端数据返回 移动端&#xff1a;返回JSON数据第三方&#xff1a;返回XMLIoT&#xff1a;返回自定义协议数据 1. 默认规则 1. SpringBoot 多端内容适配 基于请求头内容协商 【默认】 客户端向服务端发送请求&#xff0c;携带HTTP标准的 Accept 请求…
阅读更多...
C++ —— 剑斩旧我 破茧成蝶—C++11

C++ —— 剑斩旧我 破茧成蝶—C++11

江河入海&#xff0c;知识涌动&#xff0c;这是我参与江海计划的第2篇。 目录 1. C11的发展历史 2. 列表初始化 2.1 C98传统的{} 2.2 C11中的{} 2.3 C11中的std::initializer_list 3. 右值引用和移动语义 3.1 左值和右值 3.2 左值引用和右值引用 3.3 引用延长生命周期…
阅读更多...
mysql复习题（实验7-8）

mysql复习题（实验7-8）

建立一个学生入学信息管理&#xff08;x_y&#xff09;数据库&#xff0c;设计其数据库模式为&#xff1a; 学生表&#xff08;学号&#xff0c;姓名&#xff0c;性别&#xff0c;入学成绩&#xff0c;籍贯&#xff0c;院系编号&#xff09; 院系表&#xff08;院系编号&…
阅读更多...
详细分析ipvsadm负载均衡的命令

详细分析ipvsadm负载均衡的命令

目录 前言1. 基本知识2. 命令参数3. 拓展 前言 LVS四层负载均衡架构详解Lvs推荐阅读&#xff1a;添加链接描述 1. 基本知识 ipvsadm 是用于管理和配置 Linux 服务器上 IP Virtual Server (IPVS) 的工具&#xff0c;是 Linux 提供的一个负载均衡模块&#xff0c;支持多种负载…
阅读更多...
反向代理模块

反向代理模块

1 概念 1.1 反向代理概念 反向代理是指以代理服务器来接收客户端的请求&#xff0c;然后将请求转发给内部网络上的服务器&#xff0c;将从服务器上得到的结果返回给客户端&#xff0c;此时代理服务器对外表现为一个反向代理服务器。 对于客户端来说&#xff0c;反向代理就相当于…
阅读更多...
大数据新视界 -- Impala 性能突破：复杂数据类型处理的优化路径（上）（25 / 30）

大数据新视界 -- Impala 性能突破：复杂数据类型处理的优化路径（上）（25 / 30）

&#x1f496;&#x1f496;&#x1f496;亲爱的朋友们&#xff0c;热烈欢迎你们来到 青云交的博客&#xff01;能与你们在此邂逅&#xff0c;我满心欢喜&#xff0c;深感无比荣幸。在这个瞬息万变的时代&#xff0c;我们每个人都在苦苦追寻一处能让心灵安然栖息的港湾。而 我的…
阅读更多...
Excel使用-弹窗“此工作簿包含到一个或多个可能不安全的外部源的链接”的发生与处理

Excel使用-弹窗“此工作簿包含到一个或多个可能不安全的外部源的链接”的发生与处理

文章目录 前言一、探讨问题发生原因1.引入外部公式2.引入外部数据验证二、问题现象排查及解决1.排查公式2.排查数据验证3.特殊处理方式总结前言 作为一种常用的办公软件，Excel被大家所熟知。尽管使用了多年，有时候在使用Excel时候也会发生一些不太常见的现象，需要用心核查下…
阅读更多...
【小程序】dialog组件

【小程序】dialog组件

这个比较简单 我就直接上代码了 只需要传入title即可&#xff0c; 内容部分设置slot 代码 dialog.ttml <view class"dialog-wrapper" hidden"{{!visible}}"><view class"mask" /><view class"dialog"><view …
阅读更多...
跨平台WPF框架Avalonia教程 一

跨平台WPF框架Avalonia教程 一

安装 安装 Avalonia UI 模板​ 开始使用 Avalonia 的最佳方式是使用模板创建一个应用程序。 要安装 Avalonia 模板&#xff0c;请运行以下命令&#xff1a; dotnet new install Avalonia.Templates 备注 对于 .NET 6.0 及更早版本&#xff0c;请将 install 替换为 --inst…
阅读更多...
JSON.stringify的应用说明

JSON.stringify的应用说明

前言 JSON.stringify() 方法将 JavaScript 对象转换为字符串,在日常开发中较常用&#xff0c;但JSON.stringify其实有三个参数&#xff0c;后两个参数&#xff0c;使用较少&#xff0c;今天来介绍一下后两个参数的使用场景和示例。 语法及参数说明 JSON.stringify()&#xf…
阅读更多...
家庭网络常识：猫与路由器

家庭网络常识：猫与路由器

这张图大家应该不陌生——以前家庭网络的连接方式。 图1 家庭网络连接示意图 来说说猫/光猫&#xff1a; 先看看两者的图片。 图2 猫 图3 光猫 这个东西因为英文叫“modem”&#xff0c;类似中文的“猫”&#xff0c;所以简称“猫”。 猫和光猫的区别就是&#xff0c;一…
阅读更多...
core 不可变类型 线程安全 record

core 不可变类型 线程安全 record

当一个类型的对象在创建时被指定状态后&#xff0c;就不会再变化的对象&#xff0c;我们称之为不可变类型。这种类型是线程安全的&#xff0c;不需要进行线程同步&#xff0c;非常适合并行计算的数据共享。它减少了更新对象会引起各种bug的风险&#xff0c;更为安全。 System.D…
阅读更多...
机器学习 ---线性回归

机器学习 ---线性回归

目录 摘要&#xff1a; 一、简单线性回归与多元线性回归 1、简单线性回归 2、多元线性回归 3、残差 二、线性回归的正规方程解 1、线性回归训练流程 2、线性回归的正规方程解 &#xff08;1&#xff09;适用场景 &#xff08;2&#xff09;正规方程解的公式 三、衡量…
阅读更多...
基于Java Springboot甘肃旅游管理系统

基于Java Springboot甘肃旅游管理系统

一、作品包含 源码数据库设计文档万字PPT全套环境和工具资源部署教程 二、项目技术 前端技术&#xff1a;Html、Css、Js、Vue、Element-ui 数据库&#xff1a;MySQL 后端技术&#xff1a;Java、Spring Boot、MyBatis 三、运行环境 开发工具&#xff1a;IDEA/eclipse 数据…
阅读更多...
uniApp项目运行到鸿蒙手机，应用图标一直是H,应用名一直是HBuilder问题

uniApp项目运行到鸿蒙手机，应用图标一直是H,应用名一直是HBuilder问题

项目运行到鸿蒙手机&#xff0c;应用图标一直是H,应用名一直是HBuilder问题 应用运行到鸿蒙手机和鸿蒙模拟器&#xff0c;应用图标一直是H,应用名一直是HBuilder&#xff0c;在自动生成的harmony-configs文件夹下也没有配置的文件&#xff0c; 这时候需要你将DevEco Studio 下…
阅读更多...
Spring：IOC/DI注解开发管理第三方bean

Spring：IOC/DI注解开发管理第三方bean

前面定义bean的时候都是在自己开发的类上面写个注解就完成了&#xff0c;但如果是第三方的类&#xff0c;这些类都是在jar包中&#xff0c;我们没有办法在类上面添加注解&#xff0c;这个时候该怎么办? 遇到上述问题&#xff0c;我们就需要有一种更加灵活的方式来定义bean,这…
阅读更多...
最新文章

Copyright @ 2022~2023