【C++干货铺】list的使用 | 模拟实现

=========================================================================

个人主页点击直达:小白不是程序媛

C++专栏:C++干货铺

代码仓库:Gitee

=========================================================================

目录

list的介绍及使用

list的介绍

list的使用

list的构造

list迭代器的使用

list的增删查改

list的模拟实现

结点的封装

迭代器的封装

list成员变量

构造函数

拷贝构造函数

operator=

析构函数和清理空间

insert

erase

push_back、push_front、pop_back、pop_front

begin+end、cbegin+cend

list和vector的对比


list的介绍及使用

list的介绍

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。

2. list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素。

3. list与forward_list非常相似:最主要的不同在于forward_list是单链表,只能朝前迭代,已让其更简单高效。

4. 与其他的序列式容器相比(array,vector,deque),list通常在任意位置进行插入、移除元素的执行效率更好。

5. 与其他序列式容器相比,list和forward_list最大的缺陷是不支持任意位置的随机访问,比如:要访问list的第6个元素,必须从已知的位置(比如头部或者尾部)迭代到该位置,在这段位置上迭代需要线性的时间开销;list还需要一些额外的空间,以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

list的使用

list的构造

函数名称       函数作用
list(size_t type n,const value_type构造的list中包含n个值为val的元素
list()构造空list
list(const list&x)拷贝构造函数
list(first,last)迭代器区间中的元素构造list
	list<int> lt1(10, 1);
	list<int> lt2;
	list<int> lt3(lt1);
	list<int> lt4(lt3.begin(), lt3.end());
	list<int>::iterator lt = lt4.begin();
	while (lt != lt4.end())
	{
		cout << *lt << " ";
		lt++;
	}
	cout << endl;
	for (auto e : lt4)
	{
		cout << e << " ";
	}
	cout << endl;

list迭代器的使用

函数名称函数作用
begin+end返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin+rend返回第一个元素的reverse_iterator,即end位置,返回最后一个元素下一个位置的
reverse_iterator,即begin位置

list的增删查改

函数名称函数作用
push_back在list尾部插入值为val的元素
push_front在list首元素前插入值为val的元素
pop_back删除list中最后一个元素
pop_front删除list中第一个元素
insert在list position 位置中插入值为val的元素
erase删除list position位置的元素
	list<int> lt(5,9);
	//头插
	lt.push_front(1);
	//尾插
	lt.push_back(2);
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
	//尾删
	lt.pop_back();
	//头删
	lt.pop_front();
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
	lt.insert(lt.begin(), 30);
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
	lt.erase(lt.begin());
	for (auto e : lt)
	{
		cout << e << " ";
	}

 


list的模拟实现

list通过一个一个结构体的结点实现,节点中包括指向下一个位置、指向前一个位置的指针和有效数值组成。

结点的封装

使用struct而不是class是因为默认为公开的

	template<class T>
	//封装结点
	struct list_node
	{
		list_node(const T& x=T())
			:_data(x)
			,_next(nullptr)
			,_prev(nullptr)
		{
		}
		T _data;
		list_node* _next;
		list_node* _prev;
	};

迭代器的封装

list和顺序表最大的不同是list物理上不连续,需要使用指针进行移动直线下一个或者指向其他的操作,而不像顺序表物理上是连续的,++、--都可以拿到有效数据;因此需要对迭代器单独封装。

//迭代器封装
	template<class T, class Ref, class Ptr>
	struct __list_iterator
	{
		typedef list_node<T> Node;
		typedef __list_iterator<T, Ref, Ptr> self;
		Node* _node;

		__list_iterator(Node* node)
			:_node(node)
		{}

		self& operator++()
		{
			_node = _node->_next;
			return *this;
		}

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

		self operator++(int)
		{
			self tmp(*this);
			_node = _node->_next;

			return tmp;
		}

		self operator--(int)
		{
			self tmp(*this);
			_node = _node->_prev;

			return tmp;
		}

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

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

		bool operator!=(const self& s)
		{
			return _node != s._node;
		}

		bool operator==(const self& s)
		{
			return _node == s._node;
		}
	};

list成员变量

指向结构体节点的指针和有效数据的个数

		Node* _node;
		size_t _size;

构造函数

		typedef list_node<T> Node;
	public:
		typedef __list_iterator<T, T&, T*> iterator;
		typedef __list_iterator<T, const T&, const T*> const_iterator;
		void empty_init()
		{
			_node = new Node;
			_node->_next = _node;
			_node->_prev = _node;
			_size = 0;
		}
		list()
		{
			empty_init();
		}

拷贝构造函数

	list(list<T>& x)
		{
			empty_init();
			for (auto e : x)
			{
				push_back(e);
			}
		}

operator=

		void swap(list<T>& lt)
		{
			std::swap(_node, lt._node);
			std::swap(_size, lt._size);
		}
		list<int>& operator=(list<int> lt)
		{
			swap(lt);

			return *this;
		}

析构函数和清理空间

		~list()
		{
			clear();

			delete _node;
			_node = nullptr;
		}

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

insert

		void insert(iterator pos, const T& x)
		{
			Node* cur = pos._node;
			Node* newnode = new Node(x);
			Node* prev = cur->_prev;

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

			cur->_prev = newnode;
			newnode->_prev = prev;
			_size++;

		}

erase

iterator erase(iterator pos)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;

			prev->_next = next;
			next->_prev = prev;
			return next;
		}

push_back、push_front、pop_back、pop_front

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

		void pop_front()
		{
			erase(begin());
		}
		void pop_back()
		{
			erase(--end());
		}

begin+end、cbegin+cend

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

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

list和vector的对比

vectorlist



动态顺序表,一段连续空间带头结点的双向循环链表


访
支持随机访问,访问某个元素效率O(1)不支持随机访问,访问某个元素
效率O(N)




任意位置插入和删除效率低,需要搬移元素,时间复杂
度为O(N),插入时有可能需要增容,增容:开辟新空
间,拷贝元素,释放旧空间,导致效率更低
任意位置插入和删除效率高,不
需要搬移元素,时间复杂度为
O(1)




底层为连续空间,不容易造成内存碎片,空间利用率
高,缓存利用率高
底层节点动态开辟,小节点容易
造成内存碎片,空间利用率低,
缓存利用率低


原生态指针对原生态指针(节点指针)进行封装




在插入元素时,要给所有的迭代器重新赋值,因为插入
元素有可能会导致重新扩容,致使原来迭代器失效,删
除时,当前迭代器需要重新赋值否则会失效
插入元素不会导致迭代器失效,
删除元素时,只会导致当前迭代
器失效,其他迭代器不受影响
使


需要高效存储,支持随机访问,不关心插入删除效率大量插入和删除操作,不关心随
机访问

今天对list的介绍和底层模拟实现的分享到这就结束了,希望大家读完后有很大的收获,也可以在评论区点评文章中的内容和分享自己的看法。您三连的支持就是我前进的动力,感谢大家的支持!! !

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

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

相关文章

22LLMSecEval数据集及其在评估大模型代码安全中的应用:GPT3和Codex根据LLMSecEval的提示生成代码和代码补全,CodeQL进行安全评估

LLMSecEval: A Dataset of Natural Language Prompts for Security Evaluations 写在最前面主要工作 课堂讨论大模型和密码方向&#xff08;没做&#xff0c;只是一个idea&#xff09; 相关研究提示集目标NL提示的建立NL提示的建立流程 数据集数据集分析 存在的问题 写在最前面…

一篇五分生信临床模型预测文章代码复现——Figure 10.机制及肿瘤免疫浸润(六)

之前讲过临床模型预测的专栏,但那只是基础版本,下面我们以自噬相关基因为例子,模仿一篇五分文章,将图和代码复现出来,学会本专栏课程,可以具备发一篇五分左右文章的水平: 本专栏目录如下: Figure 1:差异表达基因及预后基因筛选(图片仅供参考) Figure 2. 生存分析,…

【开源】基于Vue和SpringBoot的高校宿舍调配管理系统

项目编号&#xff1a; S 051 &#xff0c;文末获取源码。 \color{red}{项目编号&#xff1a;S051&#xff0c;文末获取源码。} 项目编号&#xff1a;S051&#xff0c;文末获取源码。 目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能需求2.1 学生端2.2 宿管2.3 老师端 三、系统…

C语言每日一题(35)有效的括号

力扣网 20 有效的括号 题目描述 给定一个只包括 (&#xff0c;)&#xff0c;{&#xff0c;}&#xff0c;[&#xff0c;] 的字符串 s &#xff0c;判断字符串是否有效。 有效字符串需满足&#xff1a; 左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右…

黑马React18: Redux

黑马React: Redux Date: November 19, 2023 Sum: Redux基础、Redux工具、调试、美团案例 Redux介绍 Redux 是React最常用的集中状态管理工具&#xff0c;类似于Vue中的Pinia&#xff08;Vuex&#xff09;&#xff0c;可以独立于框架运行 作用&#xff1a;通过集中管理的方式管…

Vue生成二维码并进行二维码图片下载

1、安包 npm install vue-qr --save2、引入 // vue2.0 import VueQr from vue-qr // vue3.0 import VueQr from vue-qr/src/packages/vue-qr.vue new Vue({components: {VueQr} })<!-- 设备二维码 对话框 270px--><el-dialog title"点位二维码" :visible.…

【Java 进阶篇】Redis:打开缓存之门

介绍 Redis&#xff08;Remote Dictionary Server&#xff09;是一个高性能的键值对存储系统&#xff0c;被广泛用作缓存、消息中间件和数据库。它以其快速的读写能力、支持多种数据结构和丰富的功能而闻名。在这篇博客中&#xff0c;我们将深入了解Redis的概念、安装以及基本…

阿里云 ACK 新升级,打造智算时代的现代化应用平台

云布道师 今天&#xff0c;能想到的或是想不到的领域&#xff0c;对容器和 Kubernetes 的需求都居高不减&#xff0c;使这项技术正在真正走向无处不在。 在 2023 云栖大会上&#xff0c;阿里云云原生产品线容器服务负责人易立关于容器服务 ACK 在本届亚运会上应用的介绍&#…

系列七、ThreadLocal为什么会导致内存泄漏

一、ThreadLocal为什么会导致内存泄露 1.1、ThreadLocalMap的基本结构 ThreadLocalMap是ThreadLocal的内部类&#xff0c;没有实现Map接口&#xff0c;用独立的方式实现了Map的功能&#xff0c;其内部的Entry也是独立实现的。源码如下&#xff1a; 1.2、ThreadLocal引用示意图…

ChinaSoft 论坛巡礼 | 高可信嵌入式软件智能化开发与测试论坛

2023年CCF中国软件大会&#xff08;CCF ChinaSoft 2023&#xff09;由CCF主办&#xff0c;CCF系统软件专委会、形式化方法专委会、软件工程专委会以及复旦大学联合承办&#xff0c;将于2023年12月1-3日在上海国际会议中心举行。 本次大会主题是“智能化软件创新推动数字经济与社…

MS9708/MS9710/MS9714高速、低功耗数模转换器,可替代ADI的

产品简述 MS9708/MS9710/MS9714 是一个 8-Bit/10-Bit/14-Bit 高速、低功耗 D/A 转换器。当采样速率达到 125MSPS 时&#xff0c; MS9708/MS9710/MS9714 也能提供优越的 AC 和 DC 性能。 MS9708/MS9710/MS9714 的正常工作电压范围为 2.7V 到 5.5V &#xff0c;…

每日一题 2304. 网格中的最小路径代价(中等,动态规划)

由于他每一行的每一个值都可以到下一行的所有节点&#xff0c;且路径的代价没有什么相关性&#xff0c;所以只能用 O(mn2) 的动态规划求解 class Solution:def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:m, n len(grid), len(grid[0])…

Attention is All You Need:Transformer各模块详解

Transformer encoder-decoder架构 Encoder&#xff1a;将输入序列转换为一个连续向量空间中的表示。Encoder通常是一个循环神经网络&#xff08;RNN&#xff09;或者卷积神经网络&#xff08;CNN&#xff09;&#xff0c;通过对输入序列中的每个元素进行编码&#xff0c;得到…

51单片机按键控制LED灯亮灭的N个玩法

51单片机按键控制LED灯亮灭的N个玩法 1.概述 这篇文章介绍按键的使用&#xff0c;以及通过控制LED灯的小实验&#xff0c;发现按键中存在的问题&#xff0c;然后思考并解决这些问题。达到熟练使用按键控制元器件。 2.搭建硬件环境 1.硬件准备 名称型号数量单片机STC12C205…

3d标签云实现过程(tagcloud.js)同步原生和 vue

写在前面 本来是没有准备写这个知识点&#xff0c;但是下载这个 js 的时候发现很多都是要钱或者是积分的&#xff0c;我就不明白了一个开源了这么久的 js 怎么还有人拿来挣钱的&#xff0c;同时还有一些只有原生 html 的例子&#xff0c;但是现在都是 框架主导的一些项目&#…

Find My音箱|苹果Find My技术与音箱结合,智能防丢,全球定位

音箱市场规模正在不断扩大。随着人们生活品质的提高&#xff0c;对音乐体验的需求也在不断升级。消费者对于蓝牙音箱的需求&#xff0c;已经从单纯的音质扩展到了功能、设计和价格等多个方面。随着移动化、即时化的视听娱乐需求的增长&#xff0c;蓝牙音箱性能、质量、外观设计…

嵌入式主板购买需要考虑哪些内容?

众所周知&#xff0c;各种先进电子器件和计算机处理技术在我国自动化工业生产中的应用&#xff0c;极大地提高了发展的效率和发展水平。而嵌入式主板以其多元化的设计特点在我国工业系统的控制中表现得越来越明显&#xff0c;消费者在选择这种嵌入式主板时必须注意以下几点考虑…

2023 年 亚太赛 APMCM 国际大学生数学建模挑战赛 |数学建模完整代码+建模过程全解全析

当大家面临着复杂的数学建模问题时&#xff0c;你是否曾经感到茫然无措&#xff1f;作为2022年美国大学生数学建模比赛的O奖得主&#xff0c;我为大家提供了一套优秀的解题思路&#xff0c;让你轻松应对各种难题。 cs数模团队在亚太赛 APMCM前为大家提供了许多资料的内容呀&…