【STL_list 模拟】——打造属于自己的高效链表容器

一、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;
	_size++;
}
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;
	_size++;
}

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

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/907112.html

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

相关文章

《Qwen2-VL》论文精读【上】：发表于2024年10月 Qwen2-VL 迅速崛起 | 性能与GPT-4o和Claude3.5相当

《Qwen2-VL》论文精读【上】：发表于2024年10月 Qwen2-VL 迅速崛起 | 性能与GPT-4o和Claude3.5相当

1、论文地址Qwen2-VL: Enhancing Vision-Language Model’s Perception of the World at Any Resolution 2、Qwen2-VL的Github仓库地址 该论文发表于2024年4月&#xff0c;是Qwen2-VL的续作&#xff0c;截止2024年11月&#xff0c;引用数24 文章目录 1 论文摘要2 引言3 实验3.…
阅读更多...
LiveQing视频点播流媒体RTMP推流服务功能-支持电子放大拉框放大直播视频拉框放大录像视频流拉框放大电子放大

LiveQing视频点播流媒体RTMP推流服务功能-支持电子放大拉框放大直播视频拉框放大录像视频流拉框放大电子放大

LiveQing视频点播流媒体RTMP推流服务功能-支持电子放大拉框放大直播视频拉框放大录像视频流拉框放大电子放大 1、鉴权直播2、视频点播3、RTMP推流视频直播和点播流媒体服务 1、鉴权直播 云直播服务-》鉴权直播 -》播放 &#xff0c;左键单击可以拉取矩形框&#xff0c;放大选中…
阅读更多...
Zypher Research：服务器抽象叙事，GameFi 赛道的下一个热点？

Zypher Research：服务器抽象叙事，GameFi 赛道的下一个热点？

继链抽象、账户抽象的概念后&#xff0c;Zypher Network 进一步提出了服务器抽象的概念&#xff0c;并基于 zk 技术率先推出了应用于 Web3 游戏领域的服务器抽象方案。基于该方案&#xff0c;游戏开发者能够在完全去中心化的环境下创建、运行游戏&#xff0c;而不需要依赖传统的…
阅读更多...
【SpringCloud详细教程】-01-一文了解微服务

【SpringCloud详细教程】-01-一文了解微服务

精品专题&#xff1a; 01.《C语言从不挂科到高绩点》课程详细笔记 https://blog.csdn.net/yueyehuguang/category_12753294.html?spm1001.2014.3001.5482 02. 《SpringBoot详细教程》课程详细笔记 https://blog.csdn.net/yueyehuguang/category_12789841.html?spm1001.20…
阅读更多...
在使用 AMD GPU 的 PyTorch 中实现自动混合精度

在使用 AMD GPU 的 PyTorch 中实现自动混合精度

Automatic mixed precision in PyTorch using AMD GPUs — ROCm Blogs 随着模型规模的增加&#xff0c;训练它们所需的时间和内存——以及因此而产生的成本——也在增加。因此&#xff0c;采取任何措施来减少训练时间和内存使用都是非常有益的。这就是自动混合精度&#xff08;…
阅读更多...
基于布局的3D场景生成技术：SceneCraft

基于布局的3D场景生成技术：SceneCraft

1. 概述 随着室内设计和虚拟现实技术的快速发展，快速生成高质量的3D室内场景成为行业需求的重要方向。SceneCraft是一种新型的3D场景生成技术，旨在根据用户提供的布局和文本描述，一键生成详细的室内3D场景。该技术不仅简化了设计流程，还大大提高了设计效率和用户体验。 2…
阅读更多...
【Python爬虫实战】深入解析 Selenium：从元素定位到节点交互的完整自动化指南

【Python爬虫实战】深入解析 Selenium：从元素定位到节点交互的完整自动化指南

#1024程序员节&#xff5c;征文# &#x1f308;个人主页&#xff1a;易辰君-CSDN博客 &#x1f525; 系列专栏&#xff1a;https://blog.csdn.net/2401_86688088/category_12797772.html ​ 前言 Selenium 是进行网页自动化操作的强大工具&#xff0c;在测试、数据抓取、用户行…
阅读更多...
数据库-＞联合查询

数据库-＞联合查询

目录 一、联合查询 1.联合查询 2.多表联合查询时MYSQL内部是如何进⾏计算的 3.多表联合查询 3.1语法 3.2指定多个表&#xff0c;进行联合查询 3.3通过表与表中的链接条件过滤掉无效数据 3.4通过指定列查询&#xff0c;精简查询结果​编辑 3.5可以通过给表起别名的方式&…
阅读更多...
k8s知识点总结

k8s知识点总结

docker 名称空间 分类 Docker中的名称空间用于提供进程隔离&#xff0c;确保容器之间的资源相互独立。主要分类包括&#xff1a; PID Namespace&#xff1a;进程ID隔离&#xff0c;使每个容器有自己的进程树&#xff0c;容器内的进程不会干扰其他容器或主机上的进程。 NET Nam…
阅读更多...
C++11（1）——右值引用、统一初始化、C++发展史

C++11（1）——右值引用、统一初始化、C++发展史

一、C的发展史 1.C的产生 C的起源可以追溯到1979年&#xff0c;当时本贾尼&#xff08;C创始人&#xff09;在贝尔实验室从事计算机科学与软件工程的研究工作。面对项目中复杂的软件开发任务&#xff0c;特别是模拟和操作系统的开发工作&#xff0c;他感受到了现有语言&#…
阅读更多...
计算机毕业设计Spark+大模型知识图谱中药推荐系统 中药数据分析可视化大屏 中药爬虫 机器学习 中药预测系统 中药情感分析 大数据毕业设计

计算机毕业设计Spark+大模型知识图谱中药推荐系统 中药数据分析可视化大屏 中药爬虫 机器学习 中药预测系统 中药情感分析 大数据毕业设计

温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 作者简介&#xff1a;Java领…
阅读更多...
javascript-Web APLs （三）

javascript-Web APLs （三）

事件流 指的是事件完整执行过程中的流动路 说明&#xff1a;假设页面里有个div&#xff0c;当触发事件时&#xff0c;会经历两个阶段&#xff0c;分别是捕获阶段、冒泡阶段 简单来说&#xff1a;捕获阶段是 从父到子 冒泡阶段是从子到父 实际工作都是使用事件冒泡为主 事件…
阅读更多...
11.Three.js使用indexeddb前端缓存模型优化前端加载效率

11.Three.js使用indexeddb前端缓存模型优化前端加载效率

11.Three.js使用indexeddb前端缓存模型优化前端加载效率 1.简述 在使用Three.js做数字孪生应用场景时&#xff0c;我们常常需要用到大量模型或数据。在访问我们的数字孪生应用时&#xff0c;每次刷新都需要从web端进行请求大量的模型数据或其他渲染数据等等&#xff0c;会极大…
阅读更多...
keepalive+mysql8双主

keepalive+mysql8双主

1.概述 利用keepalived实现Mysql数据库的高可用&#xff0c;KeepalivedMysql双主来实现MYSQL-HA&#xff0c;我们必须保证两台Mysql数据库的数据完全一致&#xff0c;实现方法是两台Mysql互为主从关系&#xff0c;通过keepalived配置VIP&#xff0c;实现当其中的一台Mysql数据库…
阅读更多...
C++ 实现俄罗斯方块游戏

C++ 实现俄罗斯方块游戏

✅作者简介&#xff1a;2022年博客新星 第八。热爱国学的Java后端开发者&#xff0c;修心和技术同步精进。 &#x1f34e;个人主页&#xff1a;Java Fans的博客 &#x1f34a;个人信条&#xff1a;不迁怒&#xff0c;不贰过。小知识&#xff0c;大智慧。 &#x1f49e;当前专栏…
阅读更多...
项目实战：基于Linux的Flappy bird游戏开发

项目实战：基于Linux的Flappy bird游戏开发

一、项目介绍 项目总结 1.按下空格键小鸟上升&#xff0c;不按小鸟下落 2.搭建小鸟需要穿过的管道 3.管道自动左移和创建 4.小鸟撞到管道游戏结束 知识储备 1.C语言 2.数据结构-链表 3.Ncurses库 4.信号机制 二、Ncurses库介绍 Ncurses是最早的System V Release 4.0 (SVr4)中…
阅读更多...
nginx上传文件超过限制大小、响应超时、反向代理请求超时等问题解决

nginx上传文件超过限制大小、响应超时、反向代理请求超时等问题解决

1、文件大小超过限制 相关配置&#xff1a; client_max_body_size&#xff1a; Syntax:client_max_body_size size;Default:client_max_body_size 1m;Context:http, server, location 2、连接超时: proxy_read_timeout&#xff1a; Syntax:proxy_read_timeout time;Default…
阅读更多...
C++ --- 多线程的使用

C++ --- 多线程的使用

目录 一.什么是线程&#xff1f; 线程的特点&#xff1a; 线程的组成&#xff1a; 二.什么是进程&#xff1f; 进程的特点&#xff1a; 进程的组成&#xff1a; 三.线程与进程的关系&#xff1a; 四.C的Thread方法的使用&#xff1a; 1.创建线程&#xff1a; 2.join(…
阅读更多...
基于Spring Boot的医疗陪护系统设计与实现(源码+定制+开发）病患陪护管理平台、医疗服务管理系统、医疗陪护信息平台

基于Spring Boot的医疗陪护系统设计与实现(源码+定制+开发）病患陪护管理平台、医疗服务管理系统、医疗陪护信息平台

博主介绍&#xff1a; ✌我是阿龙&#xff0c;一名专注于Java技术领域的程序员&#xff0c;全网拥有10W粉丝。作为CSDN特邀作者、博客专家、新星计划导师&#xff0c;我在计算机毕业设计开发方面积累了丰富的经验。同时&#xff0c;我也是掘金、华为云、阿里云、InfoQ等平台…
阅读更多...
ViT面试知识点

ViT面试知识点

文章目录 VITCLIPSAMYOLO系列问题 VIT 介绍一下Visual Transformer&#xff1f; 介绍一下自注意力机制&#xff1f; 介绍一下VIT的输出方式 介绍一下VIT做分割任务 VIT是将NLP的transformer迁移到cv领域&#xff0c;他的整个流程大概如下&#xff1a;将一张图片切成很多个pat…
阅读更多...
最新文章

Copyright @ 2022~2023