【C++】手搓 list 容器

在这里插入图片描述
送给大家一句话:

若结局非你所愿,就在尘埃落定前奋力一搏。—— 《夏目友人帐》

手搓 list 容器

  • 1 前言
    • 1.1 底层结构
    • 1.2 使用场景
    • 1.3 功能简介
  • 2 框架搭建
    • 2.1 节点类
    • 2.2 list 类
    • 2.3 迭代器类
  • 3 功能实现
    • 3.1 begin() 与 end()
    • 3.2 插入操作
    • 3.3 删除操作
    • 3.4 拷贝构造
    • 3.5 析构函数
    • 3.6 其他函数
  • 4 总结
  • Thanks♪(・ω・)ノ谢谢阅读!!!
  • 下一篇文章见!!!

1 前言

List是C++标准模板库(STL)中的一个成员,其本质为带头双向循环链表。不同于连续的、紧密排列的数组容器Vector,List容器的内部是由双向链表构成的,使得它在插入和删除操作上,就如同行云流水一般顺畅,不需移动其它元素。

1.1 底层结构

List容器的底层结构,是一个经典的带头双向循环链表。每个节点包含:

  1. 数据
  2. 指向前一个节点的指针
  3. 指向后一个节点的指针。

这种结构赋予了List灵动的特性:它能够轻松地在任意位置增加或移除元素,而这种操作几乎是与容器大小无关的,体现了时间复杂度上的优势。但这种优势的代价是,与数组相比,List在访问元素时的速度会较慢,因为它需要从头开始遍历。这也决定了list的更适合频繁插入的动态数据。
来看STL源码中的节点结构:

template <class T>
struct __list_node {
  typedef void* void_pointer;
  void_pointer next;
  void_pointer prev;
  T data;
};

1.2 使用场景

List最适合的场景是那些需要频繁进行插入和删除操作的场合。
例如,如果你正在管理一个动态变化的列表,如任务调度、人员排队等场景,List的特性将大放异彩。但是如果你的应用场景更多地需要随机访问元素,那么向量(Vector)或者数组可能是更佳的选择。因为List的顺序访问性能相比之下会显得有些力不从心。

  • 所以如果需要频繁随机的访问数据,那么选择vector容器
  • 如果需要频繁插入删除数据,那么选择list容器
  • 排序不要选择list !!!其删除节点的过程就决定了其速度不会太快。

1.3 功能简介

功能简介我们可以参考STL官方库 :list文档介绍

  1. 插入与删除:List的插入和删除操作非常高效,它可以在任意位置快速地添加或移除元素,而不需要像连续内存容器那样进行大量元素的移动。
  2. 多种构造:类都应该包含多种构造函数
  3. 支持迭代器:迭代器是C++重要的特性,我们写的list 也一定要支持迭代器。

2 框架搭建

现在我们开始实现list 容器,首先先要思考一下框架结构:

  1. 首先我们需要一个节点结构体(类似源码中的节点)
  2. 其次我们的list 类要带一个头结点,让我们更方便进行插入删除操作

基本就是这样,现在我们开始手搓

2.1 节点类

// 节点 结构体
template<class T>
struct ListNode
{
	ListNode* _next;
	ListNode* _prev;
	T _data;

	ListNode(T x = T()) :
		_next(nullptr),
		_prev(nullptr),
		_data(x)
	{}
	//ListNode(T x = T()) 
	//{
	//	_next = nullptr;
	//	_prev = nullptr;
	//	_data = x;
	//}	
	~ListNode()
	{
		_next = nullptr;
		_prev = nullptr;
	}
};

这里使用模版来适配更多的情景,然后基本的数据,前后指针都很简单。在编写一个构造函数,==构造函数使用初始化列表,并不是必须使用。析构函数避免野指针出现,将指针赋值为nullptr就可以了。

2.2 list 类

我们先进行简单的框架书写,构造函数需要创建一个头结点,因为我们要创建双向循环链表,所以头尾都要指向头结点本身。 _size赋初值。

template<class T>
class list
{
public:
	//设置适配的节点
	typedef ListNode<T> Node;
	//空初始化
	void empty_init()
	{
		_head = new Node;
		_head->_next = _head;
		_head->_prev = _head;
		_size = 0;
	}
	//构造函数
	list() :
	_head(nullptr)
	{
		empty_init();
	}
private:
	Node* _head;
	size_t _size;
};

接下来我们来逐步完成功能书写,由于我们还没有进行迭代器的书写

2.3 迭代器类

我们思考一下这里能不能使用原生指针来完成迭代器的操作(++ == != --)当然是不能的,因为链表的物理地址并不是连续的,对原生指针的++或–操作是没有意义的,所以我们需要自行编写迭代器类,对原生指针进行封装,来满足我们特殊的++和–操作。

	//这里的模板可以再次升级  先简单写一下
	template<class T>
	class ListIterator 
	{
	public:
		//重命名方便书写
		typedef ListNode<T> Node;
		typedef ListIterator<T> Self;
		Node* _node;
		ListIterator(Node* x ):
			_node(x)
		{}
		//操作符重载 前置++ 与 后置++的区别是参数是否带(int)
		//++t
		Self operator++()
		{
			_node = _node->_next;
			return *this;
		}
		//t++
		Self operator++(int)
		{
			Self tmp(*this);//浅拷贝即可
			_node = _node->_next;
			return tmp;
		}
		//--t
		Self operator--()
		{
			_node = _node->_prev;
			return *this;
		}
		//t--
		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;
		}
		// 解引用操作 *it 返回节点数据的引用 可以进行修改
		T& operator*()
		{
			return  _node->_data;
		}
		//因为指针才能使用-> 所以->要返回地址(指针)		
		T* operator->()//编译器会进行省略->
		{
			return &_node->_data;
		}
	};

这样迭代器类就大致写好了,那么一般我们的迭代器应该还要支持const,不然我们传入一个不可修改的链表(const list l),就会反生报错,那么我们还要书写一份const版的迭代器。如果进行编写,那么是不是会有大部分与刚才我们书写的迭代器重复(++ -- == != 都是一样的),只有operator*()operator->()返回值不一致:

  • 因为是常迭代器,使用场景是对const list<T> l进行操作,那么节点数据不可改变,所以不影响++ -- == != 这些操作,受影响的是operator*()operator->()返回值(该情况下链表本身是只读的,又因为不能将权限进行扩大,所以返回值应该也是只读的(const))。
  • 那这样就发现了不同常迭代器应该为 const T& operator*()const T* operator->() ,所以有没有一种办法可以简单解决呢,当然有了,我们设置一个新模版(带有三个参数),创建的时候就传入对应参数

我们将模版修改为这样,

 //reference 引用  pointer 指针
template<class T , class Ref ,class Ptr>

对应返回值也改变:

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

那么类实例化的时候传入对应参数就好了:

typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T*> const_iterator;

这样就实现了迭代器的创建,是不是就非常简洁了呢

3 功能实现

3.1 begin() 与 end()

使用迭代器即可,注意end()是头结点,因为遍历过程中,全部遍历后会回到头结点,所以直接判断是否为头结点就能控制结束位置。

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

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

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

3.2 插入操作

插入操作我们很熟悉,步骤是创建一个新节点,然后通过改变指针指向来完成插入操作:
来看尾插操作,

void push_back(const T& x = T())
{
	//创建新节点
	Node* node = new Node(x);
	//找尾
	Node* tail = _head->_prev;
	//进行插入
	node->_next = _head;
	node->_prev = tail;
	
	tail->_next = node;
	_head->_prev = node;
	//别忘记大小++
	_size++;
}

任意位置插入,操作思路依然是对前后节点与新节点的指针指向进行操作,来完成插入。

void insert(iterator pos = begin(), T x = T())
{
	//创建新节点
	Node* node = new Node(x);
	//前节点 后节点
	Node* prev = pos._node->_prev;
	Node* next = pos._node;
	//处理新节点
	node->_prev = prev;
	node->_next = next;
	//出现前后节点
	prev->_next = node;
	next->_prev = node;
	//别忘记大小++
	_size++;
}		

头插,直接干脆调用insert就可以了

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

3.3 删除操作

删除操作,同样是使用指针操作,来达到删除的效果。注意要对删除的节点进行释放空间操作(delete),不然会发生内存泄漏!!!

尾删
void pop_back()
{
	Node* tail = _head->_prev;
	Node* prev = tail->_prev;

	prev->_next = _head;
	_head->_prev = prev;

	delete tail;
	_size--;
}
//头删
void pop_front()
{
	Node* head = _head->_next;
	Node* next = head->_next;

	_head->_next = next;
	next->_prev = _head;

	delete head;
	_size--;
}
//任意位置删除
iterator erase(iterator pos)
{
	Node* cur = pos._node;
	Node* prev = cur->_prev;
	Node* next = cur->_next;

	prev->_next = next;
	next->_prev = prev;
	delete cur;

	_size--;
	return iterator(next);
}

需要注意的是,任意位置删除因为使用了迭代器,删除后会造成迭代器失效,所以需要更新迭代器,返回被删除节点的下一个节点的迭代器即可。

3.4 拷贝构造

拷贝构造直接将数据一个一个插入到该链表中即可:

list(const list<T>& l)
{
	empty_init();
	iterator it = l.begin();
	while (it != l.end())
	{
		push_back(*it);
		it++;
	}
}

这样十分方便快捷!!!

3.5 析构函数

void clear()
{
	//依次释放
	iterator it = begin();
	while (it != end())
	{
		
		it = erase(it);
	}
}
~list()
{
	clear();
	//需要单独释放头结点空间
	delete _head;
	_head = nullptr;
}

3.6 其他函数

返回大小:

size_t size() const { return _size; }

判断是否为空:

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

清空数据:

void clear()
{
	iterator it = begin();
	while (it != end())
	{
		it = erase(it);
	}
}

4 总结

本文我们实现了STL库中重要的list 的模拟实现,其中最重要莫过于迭代器的封装类的书写,这是前所未有的操作(对于我来说,我是第一次使用这种结构)。通过list 的模拟实现也帮我们巩固了类与对象的知识,也强化了指针操作的思路。欢迎大家讨论分析。

Thanks♪(・ω・)ノ谢谢阅读!!!

下一篇文章见!!!

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

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

相关文章

云原生之旅第一课(2站搜索K8s成神之路)

自己动手搭建Kubernetes集群&#xff0c;学习如何自定义CRD&#xff0c;以及使用Kubebuilder快速搭建Operator项目&#xff0c;云原生之旅第一课。从一开始准备录制课程&#xff0c;到如今已经有了500位忠实粉丝&#xff0c;我感到无比欣慰。这门课程完全开源&#xff0c;每一集…

FPN网络

FPN&#xff08;Feature Pyramid Network&#xff09;是一种用于目标检测和语义分割等计算机视觉任务的网络结构。它旨在解决不同尺度下的特征信息不足的问题&#xff0c;提高模型对小目标和远距离目标的检测能力。在目标检测任务中&#xff0c;由于目标的尺度和形状各异&#…

聚观早报 | 百度文心一言上线新功能;腾势Z9GT将发布

聚观早报每日整理最值得关注的行业重点事件&#xff0c;帮助大家及时了解最新行业动态&#xff0c;每日读报&#xff0c;就读聚观365资讯简报。 整理丨Cutie 4月08日消息 百度文心一言上线新功能 腾势Z9GT将发布 华为将举办鸿蒙春季沟通会 苹果与Shutterstock达成协议 O…

ebpf+perfetto实现调度延迟记录与展示

1.背景 需要分析生产环境的调度问题,如线程的调度延迟有多少,在哪些时间点延迟比较明显,影响其调度的主要原因是什么?其次,我们希望可以比较直观的展示调度延迟情况。最好能对接perfetto的UI和后处理,因为perfetto已经用于分析比较多的性能数据,可以和调度数据进行整合.我们…

Dify开源大语言模型(LLM) 应用开发平台如何使用Docker部署与远程访问

文章目录 1. Docker部署Dify2. 本地访问Dify3. Ubuntu安装Cpolar4. 配置公网地址5. 远程访问6. 固定Cpolar公网地址7. 固定地址访问 本文主要介绍如何在Linux Ubuntu系统以Docker的方式快速部署Dify,并结合cpolar内网穿透工具实现公网远程访问本地Dify&#xff01; Dify 是一款…

性能优化 - 你知道开发React项目中,可以做哪些性能优化吗

难度级别:中高级及以上 提问概率:75% 在React项目开发中,面临着比较大的问题就是组件更新以及重复渲染的问题,基于这两点,我们可以在日常开发工作中,可以通过以下几点,来提升React的性能,加快组件更新对比,避免过多的重复渲染问题。 …

用国内版Devin:DevOpsGPT开发一个简易官网

前言&#xff1a; 世界上第一个AI程序员Devin想必已经给大家带来了不小的震撼&#xff0c;这种L4级的技术也许已经昭示着AGI离我们或许真的不远了。 这里先给大家普及一个概念&#xff1a; L4是谷歌对AGI划分的第四个等级&#xff0c;把代码丢给 AI 改这个是 L1 或者 L2 级别的…

iOS-获取Xcode工程中文件的路径

1、使用Create folder references的Add folders的方式把文件或者文件夹拖到Xcode工程中 拖入时的设置参考下图 注意拖入到工程之后文件夹是蓝色的&#xff08;Xcode10.1环境&#xff09; 2、代码具体实现&#xff1a; 使用NSBundle的API&#xff0c;然后拼接具体路径即可 NS…

RabbitMQ基本使用及企业开发中注意事项

目录 一、基本使用 二、使用注意事项 1. 生产者重连机制 - 保证mq服务是通的 2. 生产者确认机制 - 回调机制 3. MQ的可靠性 4. Lazy Queue模式 5. 消费者确认机制 一、基本使用 部署完RabbitMQ有两种使用方式&#xff1a; 网页客户端Java代码 MQ组成部分&#xff1a;…

uniapp开发笔记----配置钉钉小程序

uniapp开发笔记----配置钉钉小程序 1. 项目根目录添加package.json文件2. 之后点击运行就可以看到已经添加了钉钉小程序3. 如果首次使用需要配置 其他功能待开发。。。 接上一章之后&#xff0c;我想要把项目配置成钉钉小程序 官方文档点击这里 1. 项目根目录添加package.json…

专业140+总410+国防科技大学831信号与系统考研经验国防科大电子信息与通信,真题,大纲,参考书。

应群里同学要求&#xff0c;总结一下我自己的复习经历&#xff0c;希望对大家有所借鉴&#xff0c;报考国防科技大学&#xff0c;专业课831信号与系统140&#xff0c;总分410&#xff0c;大家以前一直认为国防科技大学时军校&#xff0c;从而很少关注这所军中清华&#xff0c;现…

第七篇:3.6 其他评估考虑/4.审计指南/5. 通用报告规范/6.披露指南、参考标准及其他 - IAB/MRC及《增强现实广告效果测量指南1.0》

翻译计划 第一篇概述—IAB与MRC及《增强现实广告效果测量指南》之目录、适用范围及术语第二篇广告效果测量定义和其他矩阵之- 3.1 广告印象&#xff08;AD Impression&#xff09;第三篇广告效果测量定义和其他矩阵之- 3.2 可见性 &#xff08;Viewability&#xff09;第四篇 …

【网络】什么是RPC

RPC 是Remote Procedure Call的缩写&#xff0c;译为远程过程调用。是一个计算机通信协议。 1、为什么需要远程调用 在如何给女朋友解释什么是分布式这一篇文章中介绍过&#xff0c;为了提升饭店的服务能力&#xff0c;饭店从一开始只有一个负责所有事情的厨师发展成有厨师、切…

Mac清理缓存哪些文件夹可以清理 Mac清理缓存怎么操作 Mac清理缓存快捷键 cleanmymac值不值得买

缓存文件属于电脑临时保存数据的一种文件&#xff0c;它的存在可以帮助电脑快速打开网页&#xff0c;减少缓存的时间。但是如果用户不主动清除这些缓存&#xff0c;时间一长它们会占用磁盘空间&#xff0c;影响系统性能和稳定性。因此&#xff0c;养成定期给Mac做内存缓存垃圾清…

C++奇迹之旅:我与类和对象相遇

文章目录 &#x1f4dd;面向过程和面向对象初步认识&#x1f320; 类&#x1f309;类的引入&#x1f309;类的定义 &#x1f320;类的访问限定符&#x1f320;访问限定符 &#x1f320;类的两种定义方式&#x1f309;封装 &#x1f6a9;总结 &#x1f4dd;面向过程和面向对象初…

python+django+flask+vue贫困地区儿童资助网站22pk7

Python 中存在众多的 Web 开发框架&#xff1a;Flask、Django、Tornado、Webpy、Web2py、Bottle、Pyramid、Zope2 等。近几年较为流行的&#xff0c;大概也就是 Flask 和 Django 了 一开始&#xff0c;本文就对系统内谈到的基本知识&#xff0c;从整体上进行了描述&#xff0c…

【鸿蒙开发】系统组件Row

Row组件 Row沿水平方向布局容器 接口&#xff1a; Row(value?:{space?: number | string }) 参数&#xff1a; 参数名 参数类型 必填 参数描述 space string | number 否 横向布局元素间距。 从API version 9开始&#xff0c;space为负数或者justifyContent设置为…

万界星空科技工时管理系统功能介绍

一、工时管理系统的功能 1、工时记录与统计 工时管理系统提供了便捷的工时记录和统计功能。员工可以通过系统记录每天的上班时间、下班时间以及休息时间&#xff0c;系统会自动计算工作时长并生成工时统计报表。这一功能不仅能够准确记录员工的工作时间&#xff0c;还能够帮助…

基于大数据的汽车信息可视化分析预测与推荐系统

温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长 QQ 名片 :) 1. 项目简介 本项目通过集成网络爬虫技术&#xff0c;实时获取海量汽车数据&#xff1b;运用先进的ARIMA时序建模算法对数据进行深度挖掘和分析&#xff1b;结合flask web系统和echarts可视化工具&#xff0c;…

如何在Rust中操作JSON

❝ 越努力&#xff0c;越幸运 ❞ 大家好&#xff0c;我是「柒八九」。一个「专注于前端开发技术/Rust及AI应用知识分享」的Coder。 前言 我们之前在Rust 赋能前端-开发一款属于你的前端脚手架中有过在Rust项目中如何操作JSON。 由于文章篇幅的原因&#xff0c;我们就没详细介绍…