C++初阶（十四）list

在这里插入图片描述


📘北尘_：个人主页

🌎个人专栏:《Linux操作系统》《经典算法试题 》《C++》 《数据结构与算法》
☀️走在路上，不忘来时的初心

文章目录

  • 一、 list的介绍
  • 二、list的模拟实现
    • 1、list的节点
    • 2、list 的迭代器
    • 3、list
    • 4、打印
    • 5、完整代码

一、 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的模拟实现

1、list的节点

template<class T>
	struct list_node
	{
		T _data;
		list_node<T>* _prev;
		list_node<T>* _next;

		list_node(const T& x = T())
			:_data(x)
			, _next(nullptr)
			, _prev(nullptr)
		{}
	};

2、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;
		}
	};

3、list

template<class T>
	class list
	{
		typedef list_node<T> Node;
	public:
		typedef __list_iterator<T, T&, T*> iterator;
		typedef __list_iterator<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;
		}
		void empty_init()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
			_size = 0;
		}
		list()
		{
			empty_init();
		}
		list(list<T>& lt)
		{
			empty_init();
			for (auto e : lt)
			{
				push_back(e);
			}
		}
		list<T>& operator=(list<T> lt)
		{
			swap(lt);
			return *this;
		}
		void swap(list<T> lt)
		{
			std::swap(_size, lt._size);

			std::swap(_head, lt._head);
		}
		
		iterator insert(iterator pos, const T& x)
		{
			Node* cur = pos._node;
			Node* newnode = new Node(x);

			Node* prev = cur->_prev;

			prev->_next = newnode;
			newnode->_prev = prev;

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

			return iterator(newnode);
		}
		iterator erase(iterator pos)
		{
			Node* cur = pos._node;

			Node* prev = cur->_prev;
			Node* next = cur->_next;
			delete cur;
			prev->_next = next;
			next->_prev = prev;
			--_size;
		}
		size_t size()
		{
			return _size;
		}
		void clear()
		{
			iterator it = begin();
			while (it != end)
			{
				it = erase(it);
			}
		}
		void push_back(const T& x)
		{
			insert(end(), x);
		}
		void push_front(const T& x)
		{
			insert(begin(), x);
		}
		void push_back()
		{
			erase(end());
		}
		void pop_back()
		{

			erase(begin());
		}
		

		
	private:
		Node* _head;
		size_t _size;


	};

4、打印

template<typename Container>
	void print_container(const Container& con)
	{
		typename Container::const_iterator it = con.begin();
		while (it != con.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}
	void test_list()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		lt.push_back(5);
	
		print_container(lt);

		list<string> lt1;
		lt1.push_back("1111111111111");
		lt1.push_back("1111111111111");
		lt1.push_back("1111111111111");
		lt1.push_back("1111111111111");
		lt1.push_back("1111111111111");
		
		print_container(lt1);

		vector<string> v;
		v.push_back("222222222222222222222");
		v.push_back("222222222222222222222");
		v.push_back("222222222222222222222");
		v.push_back("222222222222222222222");
		
		print_container(v);
		
	}
}
int main()
{
	bit::test_list();
	return 0;
}

5、完整代码

#include<iostream>
#include<string>
#include<vector>
using namespace std;
namespace bit
{
	template<class T>
	struct list_node
	{
		T _data;
		list_node<T>* _prev;
		list_node<T>* _next;

		list_node(const T& x = T())
			:_data(x)
			, _next(nullptr)
			, _prev(nullptr)
		{}
	};
	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;
		}
	};
	template<class T>
	class list
	{
		typedef list_node<T> Node;
	public:
		typedef __list_iterator<T, T&, T*> iterator;
		typedef __list_iterator<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;
		}
		void empty_init()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
			_size = 0;
		}
		list()
		{
			empty_init();
		}
		list(list<T>& lt)
		{
			empty_init();
			for (auto e : lt)
			{
				push_back(e);
			}
		}
		list<T>& operator=(list<T> lt)
		{
			swap(lt);
			return *this;
		}
		void swap(list<T> lt)
		{
			std::swap(_size, lt._size);

			std::swap(_head, lt._head);
		}
		
		iterator insert(iterator pos, const T& x)
		{
			Node* cur = pos._node;
			Node* newnode = new Node(x);

			Node* prev = cur->_prev;

			prev->_next = newnode;
			newnode->_prev = prev;

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

			return iterator(newnode);
		}
		iterator erase(iterator pos)
		{
			Node* cur = pos._node;

			Node* prev = cur->_prev;
			Node* next = cur->_next;
			delete cur;
			prev->_next = next;
			next->_prev = prev;
			--_size;
		}
		size_t size()
		{
			return _size;
		}
		void clear()
		{
			iterator it = begin();
			while (it != end)
			{
				it = erase(it);
			}
		}
		void push_back(const T& x)
		{
			insert(end(), x);
		}
		void push_front(const T& x)
		{
			insert(begin(), x);
		}
		void push_back()
		{
			erase(end());
		}
		void pop_back()
		{

			erase(begin());
		}
		

		
	private:
		Node* _head;
		size_t _size;


	};

	template<typename Container>
	void print_container(const Container& con)
	{
		typename Container::const_iterator it = con.begin();
		while (it != con.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}
	
	void test_list()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		lt.push_back(5);
	
		print_container(lt);

		list<string> lt1;
		lt1.push_back("1111111111111");
		lt1.push_back("1111111111111");
		lt1.push_back("1111111111111");
		lt1.push_back("1111111111111");
		lt1.push_back("1111111111111");
		
		print_container(lt1);

		vector<string> v;
		v.push_back("222222222222222222222");
		v.push_back("222222222222222222222");
		v.push_back("222222222222222222222");
		v.push_back("222222222222222222222");
		
		print_container(v);
		
	}
}
int main()
{
	bit::test_list();
	return 0;
}

在这里插入图片描述

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

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

相关文章

数据表记录的操作

数据表记录的操作

一、数据添加 1、打开SSMS&#xff0c;附加数据库&#xff08;数据库文件在自己的文件夹下面&#xff09;&#xff0c;并进行下面的设置&#xff1a; &#xff08;1&#xff09;设置“部门信息”表中的“编号”为主键&#xff08;SSMS&#xff09; 首先建立好所需的数据库库…
阅读更多...
Grounding DINO、TAG2TEXT、RAM、RAM++论文解读

Grounding DINO、TAG2TEXT、RAM、RAM++论文解读

提示&#xff1a;Grounding DINO、TAG2TEXT、RAM、RAM论文解读 文章目录 前言一、Grounding DINO: Marrying DINO with Grounded Pre-Training for Open-Set Object Detection1、摘要2、背景3、部分文献翻译4、贡献5、模型结构解读a.模型整体结构b.特征增强结构c.解码结构 6、实…
阅读更多...
python画动漫形象（魔法少女小圆晓美焰,super beautiful）

python画动漫形象（魔法少女小圆晓美焰,super beautiful）

1.源代码 import turtle as te import time WriteStep 15 # 贝塞尔函数的取样次数 Speed 5 Width 600 # 界面宽度 Height 500 # 界面高度 Xh 0 # 记录前一个贝塞尔函数的手柄 Yh 0 def Bezier(p1, p2, t): # 一阶贝塞尔函数 return p1 * (1 - t) p2 * t def Bezier_2(x1…
阅读更多...
智能优化算法应用：基于蜻蜓算法3D无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用：基于蜻蜓算法3D无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用&#xff1a;基于蜻蜓算法3D无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用&#xff1a;基于蜻蜓算法3D无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.蜻蜓算法4.实验参数设定5.算法结果6.参考文献7.MA…
阅读更多...
计算机毕业设计 SpringBoot的二手物品交易平台 二手商城系统 Javaweb项目 Java实战项目 前后端分离 文档报告 代码讲解 安装调试

计算机毕业设计 SpringBoot的二手物品交易平台 二手商城系统 Javaweb项目 Java实战项目 前后端分离 文档报告 代码讲解 安装调试

&#x1f34a;作者&#xff1a;计算机编程-吉哥 &#x1f34a;简介&#xff1a;专业从事JavaWeb程序开发&#xff0c;微信小程序开发&#xff0c;定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事&#xff0c;生活就是快乐的。 &#x1f34a;心愿&#xff1a;点…
阅读更多...
C++初阶-vector的介绍及使用

C++初阶-vector的介绍及使用

vector的介绍及使用 一、vector的介绍1.1 vector的概念 二、vector的使用2.1 vector的定义2.2 vector iterator的使用2.3 vector空间增长问题2.4 vector的增删改查2.5 vector的整体代码实现2.5.1 vector的常用内置函数使用2.5.2 vector的访问方式及测试函数 三、vector迭代器失…
阅读更多...
windows系统安装RocketMQ_dashboard

windows系统安装RocketMQ_dashboard

1.下载源码 按照官网说明下载源码 官网 官网文档 2.源码安装 2.1.① 编译rocketmq-dashboard 注释掉报错的maven插件frontend-maven-plugin、maven-antrun-plugin mvn clean package -Dmaven.test.skiptrue2.2.② 运行rocketmq-dashboard java -jar target/rocketmq-…
阅读更多...
API测试基础之http协议

API测试基础之http协议

http简介&#xff1a; http&#xff08;超文本传输协议&#xff09;是一个简单的请求-响应协议&#xff0c;它通常运行在TCP&#xff08;传输控制协议&#xff09;之上。它指定了客户端可能发送给服务器什么样的消息以及得到什么样的响应。请求和响应消息的头以ASCII码形式给出…
阅读更多...
分布式分布式事务分布式锁分布式ID

分布式分布式事务分布式锁分布式ID

目录 分布式分布式系统设计理念目标设计思路中心化去中心化 基本概念分布式与集群NginxRPC消息中间件&#xff08;MQ&#xff09;NoSQL&#xff08;非关系型数据库&#xff09; 分布式事务1 事务2 本地事务3 分布式事务4 本地事务VS分布式事务5 分布式事务场景6 CAP原理7 CAP组…
阅读更多...
论文阅读[2023ICME]Edge-FVV: Free Viewpoint Video Streaming by Learning at the Edge

论文阅读[2023ICME]Edge-FVV: Free Viewpoint Video Streaming by Learning at the Edge

Edge-FVV: Free Viewpoint Video Streaming by Learning at the Edge 会议信息&#xff1a; Published in: 2023 IEEE International Conference on Multimedia and Expo (ICME) 作者&#xff1a; 1 背景 FVV允许观众从多个角度观看视频&#xff0c;但是如果所选视点的视频…
阅读更多...
12. MySQL 锁机制

12. MySQL 锁机制

目录 概述 MylSAM引擎 InnoDB引擎 概述 锁是计算机协调多个进程或线程并发访问某一资源的机制&#xff08;避免争抢&#xff09;。在数据库中&#xff0c;除传统的计算资源(如CPU、RAM、I/O等&#xff09;的争用以外&#xff0c;数据也是一种供许多用户共享的资如何保证数据…
阅读更多...
Edge 中的msedgewebview2总想联网

Edge 中的msedgewebview2总想联网

目录预览 一、问题描述二、原因分析三、解决方案四、参考链接 一、问题描述 使用Edge浏览器的时候&#xff0c;右下角火绒总会弹出“msedgewebview2”想要联网的弹窗&#xff0c;如下 点击发起程序&#xff0c;找到路径如下&#xff1a; C:\Program Files (x86)\Microsoft\…
阅读更多...
LangChain 24 对本地文档的搜索RAG检索增强生成Retrieval-augmented generation

LangChain 24 对本地文档的搜索RAG检索增强生成Retrieval-augmented generation

LangChain系列文章 LangChain 实现给动物取名字&#xff0c;LangChain 2模块化prompt template并用streamlit生成网站 实现给动物取名字LangChain 3使用Agent访问Wikipedia和llm-math计算狗的平均年龄LangChain 4用向量数据库Faiss存储&#xff0c;读取YouTube的视频文本搜索I…
阅读更多...
【网络安全】vulhub靶场搭建与一个漏洞的简单示例

【网络安全】vulhub靶场搭建与一个漏洞的简单示例

vulhub是一个经典的靶场&#xff0c;里面大约包含了200个不同的漏洞&#xff0c;可以说是安全从业者必刷。 无需docker知识&#xff0c;简单执行一条命令即可编译、运行一个完整的漏洞靶场镜像。 我的环境是CentOS 7。 先安装docker sudo curl -L "https://github.com…
阅读更多...
【漏洞复现】华脉智联指挥调度平台/script_edit/fileread.php文件读取漏洞

【漏洞复现】华脉智联指挥调度平台/script_edit/fileread.php文件读取漏洞

Nx01 产品简介 深圳市华脉智联科技有限公司&#xff0c;融合通信系统将公网集群系统、专网宽带集群系统、不同制式、不同频段的短波/超短波对讲、模拟/数字集群系统、办公电话系统、广播系统、集群单兵视频、视频监控系统、视频会议系统等融为一体&#xff0c;集成了专业的有线…
阅读更多...
二叉树算法专栏一《理论基础》

二叉树算法专栏一《理论基础》

下面我会介绍一些我在刷题过程中经常用到的二叉树的一些基础知识&#xff0c;所以我不会教科书式地将二叉树的基础内容通通讲一遍。 二叉树的种类 在我们解题过程中二叉树有两种主要的形式&#xff1a;满二叉树和完全二叉树。 满二叉树 满二叉树是一种特殊的二叉树&#xf…
阅读更多...
【头歌系统数据库实验】实验5 SQL的多表查询-1

【头歌系统数据库实验】实验5 SQL的多表查询-1

目录 第1关&#xff1a;等值连接&#xff1a;求S表和J表城市相同的等值连接(列顺序还是按照S、J表) 第2关&#xff1a;查询供应情况&#xff0c;并显示供应商、零件和工程三者的名称 第3关&#xff1a;找出上海厂商供应的所有零件号码 第4关&#xff1a;找出使用上海产的零…
阅读更多...
VSCode Keil Assintant 联合开发STM32

VSCode Keil Assintant 联合开发STM32

文章目录 VSCodeKeil AssistantUV5&#x1f947;软件下载&#x1f947;配置环境&#x1f947;插件安装&#x1f948;C/C Extension Pack&#x1f949;C/C Extension Pack介绍&#x1f949;插件安装 &#x1f948;Keil Assistant&#x1f949;Keil Assistant介绍&#x1f949;插…
阅读更多...
CSS-自适应导航栏（flex | grid）

CSS-自适应导航栏（flex | grid）

目标&#xff1a;实现左右各有按钮&#xff0c;中间是内容&#xff0c;自适应显示中间的内容导航栏&#xff0c;即 根据中间的宽度大小显示内容。 自适应导航栏 总结&#xff1a;推荐 flex布局 / grid布局 flex布局&#xff1a; 两侧 flex:1; ----->中间自适应 grid布局&…
阅读更多...
Docker容器的可视化管理工具—DockerUI本地部署与远程访问

Docker容器的可视化管理工具—DockerUI本地部署与远程访问

文章目录 前言1. 安装部署DockerUI2. 安装cpolar内网穿透3. 配置DockerUI公网访问地址4. 公网远程访问DockerUI5. 固定DockerUI公网地址 前言 DockerUI是一个docker容器镜像的可视化图形化管理工具。DockerUI可以用来轻松构建、管理和维护docker环境。它是完全开源且免费的。基…
阅读更多...
最新文章

Copyright @ 2022~2023