C++ List底层实现

文章目录

  • 前言
  • 成员变量
  • 成员函数
    • 迭代器
      • self& operator++()前置++
      • self operator++(int)后置++
      • self operator--()前置--
      • self operator--(int)后置--
      • bool operator!=(const self & tmp)判断是否相等
      • T* operator*() 解引用操作
    • list()初始化
    • iterator begin()
    • iterator end()
    • const_iterator begin()const
    • const_iterator end()const
    • iterator insert(iterator pos, const T& val)在pos位置插入val
    • void push_back(const T& val)在尾部位置后插入
    • void push_front(const T& val)在头部位置插入
    • iterator erase(iterator pos)
    • void pop_back()//删除最后一个元素
    • void pop_front()删除第一个元素
    • list(list<T>& tmp)拷贝构造
    • void swap(list<int>&tmp)交换两个list
    • list< T>& operator=(list< T> it)赋值
    • int size()判断有多少元素
    • bool empty() 判断list是否为空
    • T& front()取首元素
    • T& back()取尾元素
    • void clear()清空元素
    • ~list()析构
    • 再谈迭代器
  • 完整代码
  • 总结

前言

我们都清楚c++中的容器list，本质上就是一个带头双向循环链表，接下来我们实现一下list的底层，帮助我们更深层次的了解list的结构和使用

成员变量

我们知道这个节点有三部分构成 _prev,_next,_val;每个节点看作list的一个元素，这又是一个双向带头循环链表，那么我们如果仅仅知道头节点，就可以访问遍历链表中的所有元素。

//类模板
template < class T>
struct ListNode
{
ListNode(const T& val=T()) //初始化
:_prev(nullptr)
,_next(nullptr)
,_data(val)
{ }
ListNode* _prev;//指向前一个元素
ListNode* _next;//指向后一个元素
T _data;//当前节点的值
};

有了这个结点之后，我们在实现list是创建一个头节点就可以控制这个链表了

template
class list
{
    //模板+类–》类型
    typedef ListNode Node;
private:
    Node* _head;
};

在class类中，默认为私有的，在struct中默认为公有，只有将这个节点定义为公有，我们才可以访问。

那这里采用内部类的方法不行吗？？
答案是不行的，如果我们吧struct定义在内部类中，外部list类就无法访问struct中的元素了。

成员函数

迭代器

我们在实现vector中，迭代器我们并没有实现，或者说我们不需要实现，因为vector容容器的结构很特殊，是一块连续的物理空间。加加，解引用等方式很容易实现。

我们看一下迭代器，是一个个地址不连续的指针
在这里插入图片描述

那我们怎末实现呢
我们很清楚迭代器的实质就是一个指针，在这个list中就是哟个listNode的指针。
我们要实现迭代器的操作，可以采用运算符重载的方式实现，但是这里又出现了新的问题，迭代器是一个内置类型，只有自定义类型才可以实现自定义类型重载，所以我们需要都这个指针进行封装，变成一个自定义类型

template< class T >
struct ___list_iterator
{
  typedef ListNode< T> Node;//方便我们使用
  typedef ___list_iterator< T> self;//方便使用，我们会用到
  ___list_iterator(Node* x)//初始化
    :_node(x)
    {}
  Node* _node;//成员变量
};

在这里面实现我们需要的功能，

list::const_iterator it = lt.begin();
while (it != lt.end())
{
std::cout << *it << " ";
++it;
}
std::cout << std::endl;

我们需要实现前置++,后置++,前置- -，后置- -，解引用，判断是否相等。我们依此来看一下

self& operator++()前置++

self& operator++()//++返回的是一个
{
   _node = _node->_next;//我们仅需要让指针往后移动一个节点就可以
  return *this;
}

self operator++(int)后置++

这里只能用self,不能用self&，因为返回的是一个临时对象
self operator++(int)//后置++也是返回一个节点，
{
  self tmp(*this);//首先拷贝一份
  _node = _node->next;//指针向后移动一个节点
  return tmp;//返回拷贝的值
}

self operator–()前置–

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

self operator–(int)后置–

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

bool operator!=(const self & tmp)判断是否相等

bool operator!=(const self & tmp)
{
   return _node != tmp._node;//判断两个指针是否指向同一块空间就可以
}

T* operator*() 解引用操作

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

list()初始化

list()
{
   我们初始化仅仅初始化头节点就可以
   empty_list();//我们可以通过调用这个函数创建头节点
}
void empty_list()
{
   _head = new Node;
   _head->_next = _head;
   _head->_prev = _head;
}

iterator begin()

iterator begin()
{
   return _head->_next;//第一个元素就是头节点后面的那个元素
}

iterator end()

iterator end()
{
   return _head;//最后一个元素的下一个就是head
}

const_iterator begin()const

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

const_iterator end()const

const_iterator end()const
{
   return _head;
}

iterator insert(iterator pos, const T& val)在pos位置插入val

iterator insert(iterator pos, const T& val)
{
   Node* cur = pos._node;//我们首先需要取到迭代器中的元素
   Node* newnode = new Node(val);//创建新节点
   Node* prev = cur->_prev;//保留之前的节点
   prev->_next = newnode;//改变指向
   newnode->_prev = prev;
   newnode->_next = cur;
   cur->_prev = newnode;
   return newnode;//返回新节点
}

在这里插入图片描述
我们来看一下这里的insert有没有迭代器失效的问题？？

void push_back(const T& val)在尾部位置后插入

void push_back(const T& val)
{
   insert(end(), val);//我们可以直接进行复用
}

void push_front(const T& val)在头部位置插入

void push_front(const T& val)
{
   insert(begin(), val);
}

iterator erase(iterator pos)

iterator erase(iterator pos)
{
   assert(pos != end());//断言一下，不是删除头节点
   Node* cur = pos._node;//取到迭代器中的元素
   Node* prev = cur->_prev;//记录前一个位置
   Node* next = cur->_next;//记录后一个位置
   delete cur;//释放当前元素
   prev->_next = next;//改变指向
   next->_prev = prev;
   return next;//返回删除元素的下一个位置
}

我们来看一下这里会不会有迭代器失效的问题??
我们发现这里存在迭代器失效的问题，并且很大，这个元素删除了之后，之后很可能还需要用到这个元素，继续删除，如果不及时更新，就会出现大问题。

void pop_back()//删除最后一个元素

void pop_back()
{
   erase(–end());//我们要注意end是哪个位置
}

void pop_front()删除第一个元素

void pop_front()
{
   erase(begin());
}

list(list& tmp)拷贝构造

在这里我们有很多方式实现，我们来看一种比较简单的
list(list< T>& tmp)
{
   empty_list();//首先创建一个头节点
   //遍历
   for (const auto& e : tmp)
   {
   push_back(e);//取数据依次插入这个新的头结点中
   }
}

void swap(list&tmp)交换两个list

void swap(list< int>&tmp)
{
   std::swap(_head, tmp._head);//我们仅仅改变两个list的指针就可以
}

list< T>& operator=(list< T> it)赋值

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

我们再来看一下这个过程，我们假设lt1=lt2;
因为list< T> it这里，lt2会产生一份临时拷贝it
在这里插入图片描述
我们swap(it)，本质就是将it与lt1的内容进行交换
在这里插入图片描述
it是临时变量，出了作用域就销毁了，我们就完成了赋值任务

int size()判断有多少元素

int size()
{
   int count = 0;//记录一个变量，一个个统计即可
   for (const auto& e : *this)
   {
   count++;
   }
   return count;
}

bool empty() 判断list是否为空

bool empty()
{
   return size() == 0;//我们只需要判断list是否有元素
}

T& front()取首元素

T& front()
{
   return _head->_next->_data;
}

T& back()取尾元素

T& back()
{
   return _head->_prev->_data;
}

void clear()清空元素

一个个删除元素即可
void clear()
{
   iterator it = begin();
   while (it != end())
   {
   it = erase(it);
   }
}

~list()析构

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

再谈迭代器

我们已经实现了普通迭代器，但是对于const都迭代器，我们还需要实现。
我们再来看一下const迭代器，并不是这个迭代器指针不可以修改，而是迭代器指针所指向的内容不可以修改。
那我们是不是可以在普通迭代器的基础上再新增一个const迭代器，我们仅需要修改解引用的那块操作就可以，其他实现的功能都是相同的。

template<class T >
struct ___list_const_iterator
{
	typedef ListNode<T>  Node;
	typedef ___list_const_iterator<T> self;
	___list_const_iterator(Node* x)
		:_node(x)
	{}
	//不等于
	bool operator!=(const self& tmp)
	{
		return _node != tmp._node;
	}
	//解引用
	const 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->perv;
		return tmp;
	}
	//需要返回一个地址
	T* operator->()
	{
		return &_node->_data;
	}

	Node* _node;
};

虽然这样可以完成我们的功能，但是总感觉代码有点冗余，const迭代器和普通迭代器有太多重复内容，那我们可不可以通过一种方法将这两种迭代器进行合并呢？？

我们来看一下！！！
我们注意到，const T& operator*()和T& operator*()仅仅是返回值不同，我们又不能把两个方法放在同一个迭代器中，我们可以利用传参的方式进行解决，我们来看一下这种操作
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

模板传递的是类型，根据传参的不同调用自己合适的模板参数，这两个是完全不同的类型，我们这样就可以轻松完成我们的工作，仅仅使用一个迭代器就完成了两个功能

完整代码

namespace peng
{
	template <class T>
	struct ListNode
	{
		ListNode(const T& val=T())
			:_prev(nullptr)
			,_next(nullptr)
			,_data(val)
		{	}
		ListNode* _prev;
		ListNode* _next;
		T _data;
	};
	//
	//迭代器
	//不连续,
	template<class T,class Ref  >
	struct ___list_iterator
	{
		typedef ListNode<T>  Node;
		typedef ___list_iterator<T,Ref> self;
		___list_iterator(Node* x)
			:_node(x)
		{}
			//不等于
			bool operator!=(const self & tmp)
			{
				return _node != tmp._node;
			}
			//解引用
			Ref 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->perv;
				return tmp;
			}
			//需要返回一个地址
			T* operator->()
			 {
				return &_node->_data;
				
			 }
		
	    Node* _node;
	};


	//默认私有
	template<class T>
	class list
	{
		//模板+类--》类型
		typedef ListNode<T> Node;
	public:
	//	typedef ___list_iterator<T, T&,T*> iterator;
	//	typedef ___list_iterator<T, const T&,const T*> const_iterator;

	 	typedef ___list_iterator<T,T&> iterator;
		typedef ___list_iterator<T,const T&>  const_iterator;

		list()
		{			empty_list();
		}
		void empty_list()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}
		//l1(l2)
		list(list<T>& tmp)
		{
			empty_list();
			//遍历
			for (const auto& e : tmp)
			{
				push_back(e);
			}
		}
		iterator begin()
		{
			return _head->_next;
		}
		iterator end()
		{
			return _head;
		}
		const_iterator begin()const
		{
			return _head->_next;
		}
		const_iterator end()const
		{
			return _head;
		}
		void swap(list<int>&tmp)
		{
			std::swap(_head, tmp._head);
		}
		list<T>&  operator=(list<T> it)
		{
			swap(it);
			return *this;
		}
		int size()
		{
			int count = 0;
			for (const auto& e : *this)
			{
				count++;
			}
			return count;
		}
		bool empty()
		{
			return size() == 0;
		}
		iterator insert(iterator pos, const T& val)
		{
			Node* cur = pos._node;
			Node* newnode = new Node(val);
			Node* prev = cur->_prev;
			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;
			return newnode;
		}
		void push_back(const T& val)
		{
			insert(end(), val);
		}
		void push_front(const T& val)
		{
			insert(begin(), val);
		}
		iterator erase(iterator pos)
		{
			assert(pos != end());
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;
			delete cur;
			prev->_next = next;
			next->_prev = prev;
			return next;
		}
		T& front()
		{
			return _head->_next->_data;
		}
		T& back()
		{
			return _head->_prev->_data;
		}
		void pop_back()
		{
			erase(--end());
		}

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

总结

以上就是今天要讲的内容，本文仅仅详细介绍了C++list的模拟实现，希望对大家的学习有所帮助，仅供参考 如有错误请大佬指点我会尽快去改正 欢迎大家来评论~~ 😘 😘 😘

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

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

相关文章

视频无水印批量下载软件|抖音视频提取工具

视频无水印批量下载软件|抖音视频提取工具

视频无水印批量下载软件 在当今社交媒体充斥着大量优质视频内容的时代&#xff0c;很多用户都希望能够轻松下载自己喜爱的视频进行收藏或分享。为了满足用户的需求&#xff0c;我们特别推出了一款专业的视频无水印批量下载软件&#xff0c;让您可以方便快捷地获取喜爱的视频内容…
阅读更多...
鸿蒙Harmony应用开发—ArkTS-转场动画（共享元素转场）

鸿蒙Harmony应用开发—ArkTS-转场动画（共享元素转场）

当路由进行切换时&#xff0c;可以通过设置组件的 sharedTransition 属性将该元素标记为共享元素并设置对应的共享元素转场动效。 说明&#xff1a; 从API Version 7开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。 属性 名称参数参数描述…
阅读更多...
springboot企业级抽奖项目业务二（用户模块）

springboot企业级抽奖项目业务二（用户模块）

书接上回&#xff0c;梅开二度 开发流程 该业务基于rouyi生成好了mapper和service的代码&#xff0c;现在需要在controller层写接口 实际操作流程&#xff1a; 看接口文档一>controller里定义函数一>看给出的工具类一>补全controller里的函数一>运行测试 接口…
阅读更多...
练习 9 Web [SUCTF 2019]CheckIn (未拿到flag)

练习 9 Web [SUCTF 2019]CheckIn (未拿到flag)

上传图片格式的木马文件&#xff1a; 返回 <? in contents!,存在PHP代码检测 上传非图片格式文件&#xff1a; 返回 不允许非image 修改木马PHP代码规避检测 <? ?> 改为 < script language“php”>< /script ><?php eval($_POST[shell]);?>…
阅读更多...
鸿蒙实战开发：【相机和媒体库】

鸿蒙实战开发：【相机和媒体库】

介绍 在ArkTS中调用相机拍照和录像&#xff0c;以及如何使用媒体库接口进行媒体文件的增、删、改、查操作。本示例用到了 权限管理能力相机模块能力接口图片处理接口音视频相关媒体业务能力接口媒体库管理接口设备信息能力接口文件存储管理能力接口弹窗能力接口 效果预览 首…
阅读更多...
virtualBox镜像复制

virtualBox镜像复制

镜像复制 有一个镜像后&#xff0c;图方便&#xff0c;想直接使用这个vdi文件&#xff0c;但vdi有个uuid值&#xff0c;同一个虚拟机中不能同时存在两个同样的uuid的介质的&#xff0c;普通的复制文件所得到的uuid是一样的 &#xff0c;所以需要用到自带的方法复制vdi文件&…
阅读更多...
SpringCloud中的@EnableDiscoceryClient和@EnableFeignClients注解的作用解析、RPC远程过程调用

SpringCloud中的@EnableDiscoceryClient和@EnableFeignClients注解的作用解析、RPC远程过程调用

目录 EnableDiscoveryClient 服务发现的核心概念 服务注册中心 EnableDiscoveryClient注解的作用 服务心跳健康检查 使用示例 EnableFeignClients Feign简介 EnableFeignClients注解的作用 RPC&#xff08;Remote Procedure Call&#xff09; 参考链接 Spring Cloud…
阅读更多...
Cache缓存：HTTP缓存策略解析

Cache缓存：HTTP缓存策略解析

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 &#x1f35a; 蓝桥云课签约作者、上架课程《Vue.js 和 E…
阅读更多...
【Kotlin】扩展属性、扩展函数

【Kotlin】扩展属性、扩展函数

1 类的扩展 Kotlin 提供了扩展类或接口的操作&#xff0c;而无需通过类继承或使用装饰器等设计模式&#xff0c;来为某个类添加一些额外的属性或函数&#xff0c;我们只需要通过一个被称为扩展的特殊声明来完成。通过这种机制&#xff0c;我们可以将那些第三方类不具备的功能强…
阅读更多...
Gateway新一代网关

Gateway新一代网关

Gateway新一代网关 1、概述 ​ Cloud全家桶中有个很重要的组件就是网关&#xff0c;在1.x版本中都是采用的Zuul网关&#xff1b; ​ 但在2.x版本中&#xff0c;zuul的升级一直跳票&#xff0c;SpringCloud最后自己研发了一个网关SpringCloud Gateway替代Zuul。 ​ 官网&…
阅读更多...
HarmonyOS/OpenHarmony应用开发-HDC环境变量设置

HarmonyOS/OpenHarmony应用开发-HDC环境变量设置

hdc&#xff08;HarmonyOS Device Connector&#xff09;是 HarmonyOS 为开发人员提供的用于调试的命令行工具&#xff0c;通过该工具可以在 windows/linux/mac 系统上与真实设备或者模拟器进行交互。 hdc 工具通过 HarmonyOS SDK 获取&#xff0c;存放于 /Huawei/Sdk/openhar…
阅读更多...
责任链模式（处理逻辑解耦）

责任链模式（处理逻辑解耦）

前言 使用设计模式的主要目的之一就是解耦&#xff0c;让程序易于维护和更好扩展。 责任链则是将处理逻辑进行解耦&#xff0c;将独立的处理逻辑抽取到不同的处理者中&#xff0c;每个处理者都能够单独修改而不影响其他处理者。 使用时&#xff0c;依次调用链上的处理者处理…
阅读更多...
RK3399 android10 移植SiS-USB触摸驱动

RK3399 android10 移植SiS-USB触摸驱动

一&#xff0c;SiS USB触摸简介 SiS USB 触摸屏通常是一种外接式触摸屏设备&#xff0c;通过 USB 接口连接到计算机或其他设备上。这种触摸屏设备可以提供触摸输入功能&#xff0c;用户可以通过手指或触控笔在屏幕上进行操作&#xff0c;实现点击、拖动、缩放等操作。 SiS USB…
阅读更多...
双向链表增删改查、遍历、倒置、销毁等——数据结构——day3

双向链表增删改查、遍历、倒置、销毁等——数据结构——day3

首先&#xff0c;我先把我的头节点写出来&#xff0c;里面有整理好的结构体 #ifndef __DOULINK_H__ #define __DOULINK_H__#include<stdio.h> #include<stdlib.h> #include<string.h>typedef struct student {int id;char name[50];int score; }DATA_TYPE; …
阅读更多...
【数据可视化】Echarts中的其它图表

【数据可视化】Echarts中的其它图表

个人主页 &#xff1a; zxctscl 如有转载请先通知 文章目录 1. 前言2. 绘制散点图2.1 绘制基本散点图2.2 绘制两个序列的散点图2.3 绘制带涟漪特效的散点图 3. 绘制气泡图3.1 绘制标准气泡图3.2 绘制各国人均寿命与GDP气泡图3.3 绘制城市A、城市B、城市C三个城市空气污染指数气…
阅读更多...
负数，小数转换二进制

负数，小数转换二进制

负数转换二进制 例&#xff1a;在带符号整数signed char的情况下&#xff0c;-57如何被表示成负数呢&#xff1f;在计算机中又是如何计算66-57呢&#xff1f; 解析 考虑int占有32位太长&#xff0c;因此使用只占8位的signed char类型来举例。57用二进制表示位00111001&#…
阅读更多...
28-5 文件上传漏洞 - 图片马

28-5 文件上传漏洞 - 图片马

一、文件内容检测 解析漏洞定义 控制文件是否被当做后端脚本处理 二、图片马绕过 图片马；在图片中包含一句话木马。利用解析漏洞如.htaccess 或文件包含漏洞，对图片马进行解析，执行其中的恶意代码。优势在于可以绕过多种防护机制。 三、图片马制作方法: # 一句话马示例…
阅读更多...
nRF Sniffer在wireshark下的环境搭建

nRF Sniffer在wireshark下的环境搭建

一、准备 nRF Sinffer 安装包&#xff1a; 直接下载&#xff1a;https://nsscprodmedia.blob.core.windows.net/prod/software-and-other-downloads/desktop-software/nrf-sniffer/sw/nrf_sniffer_for_bluetooth_le_4.1.1.zip 官网下载&#xff1a; nRF Sniffer for Bluetooth…
阅读更多...
Elasticsearch - Docker安装Elasticsearch8.12.2

Elasticsearch - Docker安装Elasticsearch8.12.2

前言 最近在学习 ES&#xff0c;所以需要在服务器上装一个单节点的 ES 服务器环境&#xff1a;centos 7.9 安装 下载镜像 目前最新版本是 8.12.2 docker pull docker.elastic.co/elasticsearch/elasticsearch:8.12.2创建配置 新增配置文件 elasticsearch.yml http.host…
阅读更多...
实现防抖函数并支持第一次立刻执行（vue3 + ts环境演示）

实现防抖函数并支持第一次立刻执行（vue3 + ts环境演示）

1、先看一效果&#xff1a; 2、实现思路&#xff1a; 使用定时器setTimeout和闭包实现常规防抖功能&#xff1b;增加immediate字段控制第一次是否执行一次函数&#xff08;true or false&#xff09;&#xff1b;增加一个flag标识&#xff0c;在第一次执行时&#xff0c;将标…
阅读更多...
最新文章

Copyright @ 2022~2023