C++：list使用以及模拟实现

list使用以及模拟实现

    • list介绍
    • list常用接口
      • 1.构造
      • 2.迭代器
      • 3.容量
      • 4.访问数据
      • 5.增删查改
      • 6.迭代器失效
    • list模拟实现
      • 1.迭代器的实现
      • 2.完整代码

list介绍

  1. list是一个类模板，加<类型>实例化才是具体的类。
  2. list是可以在任意位置进行插入和删除的序列式容器。
  3. list的底层是双向循环链表结构，链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
  4. 与其他序列式容器相比，list最大的缺陷是不支持任意位置的随机访问，比如访问第六个节点，必须从已知节点迭代到该节点。

双向链表图解：
双向链表图解



list常用接口

1.构造

函数功能
list (size_type n, const value_type& val = value_type())构造的list中包含n个值为val的节点
list()构造空的list
list (const list& x)拷贝构造
list (InputIterator first, InputIterator last)迭代器区间初始化
(模板，可以传入其它容器的迭代器区间)

2.迭代器

函数功能
begin()加end()获取第一个数据位置的iterator/const_iterator，获取最后一个数据的下一个位置的iterator/const_iterator
rbegin()加rend()反向迭代器，获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的reverse_iterator

3.容量

函数功能
size()获取有效数据个数
empty()判断是否为空(size为0为空，返回true)

4.访问数据

函数功能
front()取到头节点数据的引用
back()返回尾节点数据的引用

5.增删查改

函数功能
push_front
(const value_type& val)		头插数据val
push_back
(const value_type& val)		尾删数据val
pop_front()头删
pop_back()尾删
insert (iterator position, const value_type& val)在position位置中插入值为val的元素
erase (iterator position)删除position位置的元素
swap(list& x)交换两个list
clear()清空有效数据

6.迭代器失效

       迭代失效即迭代器所指向的节点的无效，即该节点被删除了。 因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

#include<iostream>
#include<list>
using namespace std;

//错误代码演示
int main()
{
	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	list<int> l(array, array + sizeof(array) / sizeof(array[0]));
	auto it = l.begin();
	while (it != l.end())
	{
		// erase()函数执行后，it所指向的节点已被删除
		//因此it无效，在下一次使用it时，必须先给其赋值
		it = l.erase(it); //只需要去掉++it,这里修改成it = erase(it)即可
		++it;
	}
	return 0;
}



list模拟实现

1.迭代器的实现

      有别于vector，list的迭代器并不是一个原生的指针，因为使用者需要得到的是节点中的数据而不是整个节点，而且寻找下一个节点并不能通过指针简单的++，所以需要把迭代器单独封装成一个类，通过重载*等运算符来完成需求。

namespace MyList
{
	//节点设计成结构体,方便访问
	template<typename T>
	struct list_node
	{
		list_node(const T val = T())
			:_data(val)
			, _next(nullptr)
			, _prev(nullptr)
		{}
		T _data;
		list_node<T>* _next;
		list_node<T>* _prev;
	};

	//迭代器
	//这里设计模板参数除了迭代器，还有Ref(引用)和Ptr(指针)
	//这样设计是为了同时生成普通迭代器和const对象的迭代器
	//普通对象（可读可写）：iterator<T, T&, T*>
	//const对象（可读不可写）：const_iterator<T, const T&, const T*>
	template<typename T, typename Ref, typename Ptr>
	struct __list_iterator
	{
		typedef list_node<T> Node;
		typedef __list_iterator<T, Ref, Ptr> self; //要返回迭代器需要返回实例化对象，重命名一下

		Node* _node;

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

		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->_prev;
			return tmp;
		}

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

		//返回指针可以让自定义类型自行打印，访问成员
		//->操作符，比较特殊，it->_num转换出来其实是it.operator->()->_num
		Ptr operator->()
		{
			return &(_node->_data);
		}

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

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

	//反向迭代器
	//反向迭代器需要进行封装，其实就是复用普通迭代器，然后++和--操作反过来
	
	//普通对象（可读可写）：Reverse_iterator<iterator，T&，T*>
	//const对象（可读不可写）：Reverse_iterator<const_iterator，const T&，const T*>
	template<class Iterator, class Ref, class Ptr>
	struct Reverse_iterator
	{
		typedef Reverse_iterator<Iterator, Ref, Ptr> self;
		Iterator _it;

		//构造
		Reverse_iterator(Iterator it)
			:_it(it)
		{}


		self& operator++()
		{
			_it--;
			return *this;
		}


		self operator++(int)
		{
			self tmp(*this);
			_it--;
			return tmp;
		}


		self& operator--()
		{
			_it++;
			return *this;
		}


		self operator--(int)
		{
			self tmp(*this);
			_it++;
			return tmp;
		}


		Ref operator*()
		{
			return *_it;
		}


		Ptr operator->()
		{
			return _it;
		}


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


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

2.完整代码

#pragma once
#include<iostream>
using namespace std;

namespace MyList
{
	//节点设计成结构体,方便访问
	template<typename T>
	struct list_node
	{
		list_node(const T val = T())
			:_data(val)
			, _next(nullptr)
			, _prev(nullptr)
		{}
		T _data;
		list_node<T>* _next;
		list_node<T>* _prev;
	};

	//迭代器
	//这里设计模板参数除了迭代器，还有Ref(引用)和Ptr(指针)
	//这样设计是为了同时生成普通迭代器和const对象的迭代器
	//普通对象（可读可写）：iterator<T, T&, T*>
	//const对象（可读不可写）：const_iterator<T, const T&, const T*>
	template<typename T, typename Ref, typename Ptr>
	struct __list_iterator
	{
		typedef list_node<T> Node;
		typedef __list_iterator<T, Ref, Ptr> self; //要返回迭代器需要返回实例化对象，重命名一下

		Node* _node;

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

		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->_prev;
			return tmp;
		}

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

		//返回指针可以让自定义类型自行打印，访问成员
		//->操作符，比较特殊，it->_num转换出来其实是it.operator->()->_num
		Ptr operator->()
		{
			return &(_node->_data);
		}

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

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

	//反向迭代器
	//反向迭代器需要进行封装，其实就是复用普通迭代器，然后++和--操作反过来
	
	//普通对象（可读可写）：Reverse_iterator<iterator，T&，T*>
	//const对象（可读不可写）：Reverse_iterator<const_iterator，const T&，const T*>
	template<class Iterator, class Ref, class Ptr>
	struct Reverse_iterator
	{
		typedef Reverse_iterator<Iterator, Ref, Ptr> self;
		Iterator _it;


		Reverse_iterator(Iterator it)
			:_it(it)
		{}


		self& operator++()
		{
			_it--;
			return *this;
		}


		self operator++(int)
		{
			self tmp(*this);
			_it--;
			return tmp;
		}


		self& operator--()
		{
			_it++;
			return *this;
		}


		self operator--(int)
		{
			self tmp(*this);
			_it++;
			return tmp;
		}


		Ref operator*()
		{
			return *_it;
		}


		Ptr operator->()
		{
			return _it;
		}


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


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

	template<typename 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;
		typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;
		typedef Reverse_iterator< const_iterator, const T&, const T*> reverse_const_iterator;


		//迭代器部分
		iterator begin()
		{
			return _head->_next;
		}

		iterator end()
		{
			return _head;
		}

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

		const_iterator end()const
		{
			return _head;
		}

		reverse_iterator rbegin()
		{
			return (--end());//_head->_prev
		}

		reverse_iterator rend()
		{
			return (end());//_head
		}

		reverse_const_iterator rbegin()const
		{
			return (--end());//_head->_prev
		}

		reverse_const_iterator rend()const
		{
			return (end());//_head
		}

		/// //
		/// 
	private:
		//不希望外界调用，设计成私有
		void empty_init()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
			_size = 0;
		}
	public:
		//构造、析构部分
		list()
		{
			empty_init();
		}

		list(size_t n, const T& value = T())
		{
			empty_init();
			while (n--)
			{
				push_back(value);
			}
		}

		//重载给内置类型使用,整形默认是int，不写这个会优先匹配list(Iterator first, Iterator last)
		list(int n, const T& value = T())
		{
			empty_init();
			while (n--)
			{
				push_back(value);
			}
		}

		//迭代器区间初始化
		template <class Iterator>
		list(Iterator first, Iterator last)
		{
			empty_init();
			while(first != last)
			{
				push_back(*first);
				first++;
			}
		}

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

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


		//其它
		void swap(list<T> lt)
		{
			std::swap(_size, lt._size);
			std::swap(_head, lt._head);
		}

		//使用传之传参，直接拷贝一份交换操作的底层空间就好
		list<T>& operator=(list<T> lt)
		{
			swap(lt);
			return *this;
		}

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

	
		/// /
		/

		//访问头，尾数据
		T& front()
		{
			return _head->_next->_data;
		}

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

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

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



		/// //
		/// 

		//增加删除部分
		void push_back(const T& val)
		{
			insert(end(), val);
		}

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

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

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

			++_size;
			return newnode;
		}

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

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

		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 next;
		}

		//获取有效数据量
		size_t size()
		{
			return _size;
		}

	private:
		Node* _head;  //这里存储卫兵节点，因为底层是双向循环链表，可以找到头和尾
		size_t _size; //只需要在insert和erase里面加减就可以
	};

}

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

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

相关文章

软考：中级软件设计师:网络类型与拓扑结构，网络规划与设计，ip地址与子网划分，特殊含义的IP地址

软考：中级软件设计师:网络类型与拓扑结构，网络规划与设计，ip地址与子网划分，特殊含义的IP地址

软考&#xff1a;中级软件设计师:网络类型与拓扑结构 提示&#xff1a;系列被面试官问的问题&#xff0c;我自己当时不会&#xff0c;所以下来自己复盘一下&#xff0c;认真学习和总结&#xff0c;以应对未来更多的可能性 关于互联网大厂的笔试面试&#xff0c;都是需要细心准…
阅读更多...
LAMP 配置与应用

LAMP 配置与应用

LAMP 架构的组成 LAM(M)P&#xff1a; L&#xff1a;linux A&#xff1a;apache (httpd) M&#xff1a;mysql, mariadb P&#xff1a;php, perl, python apache的功能&#xff1a; 第一&#xff1a;处理http的请求、构建响应报文等自身服务&#xff1b; 第二&#xff1a…
阅读更多...
C语言之数组题

C语言之数组题

目录 1.使用函数实现数组操作 2.冒泡排序 3.三子棋 4.【一维数组】交换数组 5.扫雷 6.概念辨析tips 我又来了&#xff0c;今天是数组题&#xff0c;本人还在补军训真的热&#xff01;&#x1f197; 1.使用函数实现数组操作 2.冒泡排序 3.三子棋 4.【一维数组】交换数组 …
阅读更多...
vscode使用anaconda自带的python环境在终端运行时报错

vscode使用anaconda自带的python环境在终端运行时报错

目录 具体报错内容官方翻译报错讲人话解决方法 具体报错内容 CommandNotFoundError: Your shell has not been properly configured to use conda activate. If your shell is Bash or a Bourne variant, enable conda for the current user with$ echo ". E:\Anaconda/e…
阅读更多...
Nginx配置文件详解

Nginx配置文件详解

Nginx配置文件详解 1、Nginx配置文件1.1主配置文件详解1.2子配置文件 2、全局配置部分2.1修改启动的工作进程数&#xff08;worker process) 优化2.2cpu与worker process绑定2.3 PID 路径修改2.4 修改工作进程的优先级2.5调试工作进程打开的文件的个数2.6关闭master-worker工作…
阅读更多...
docker使用安装教程

docker使用安装教程

docker使用安装教程 一、docker安装及下载二、使用教程2.1 镜像2.2 容器2.3 docker安装Redis 一、docker安装及下载 一、安装 安装执行命令&#xff1a;curl -fsSL https://get.docker.com | bash -s docker --mirror Aliyun 二、启停常用命令 启动docker,执行命令&#xf…
阅读更多...
自动化运维工具——ansible安装及模块介绍

自动化运维工具——ansible安装及模块介绍

目录 一、ansible——自动化运维工具 1.1 Ansible 自动运维工具特点 1.2 Ansible 运维工具原理 二、安装ansible 三、ansible命令模块 3.1 command模块 3.2 shell模块 3.3 cron模块 3.4 user模块 3.5 group 模块 3.6 copy模块 3.7 file模块 3.8 ping模…
阅读更多...
videojs 实现自定义组件(视频画质/清晰度切换) React

videojs 实现自定义组件(视频画质/清晰度切换) React

前言 最近使用videojs作为视频处理第三方库&#xff0c;用来对接m3u8视频类型。这里总结一下自定义组件遇到的问题及实现&#xff0c;目前看了许多文章也不全&#xff0c;官方文档写的也不是很详细&#xff0c;自己摸索了一段时间陆陆续续完成了&#xff0c;这是实现后的效果.…
阅读更多...
Cpp学习——编译链接

Cpp学习——编译链接

目录 ​编辑 一&#xff0c;两种环境 二&#xff0c;编译环境下四个部分的 1.预处理 2.编译 3.汇编 4.链接 三&#xff0c;执行环境 一&#xff0c;两种环境 在程序运行时会有两种环境。第一种便是编译环境&#xff0c;第二种则是执行环境。如下图&#xff1a; 在程序运…
阅读更多...
ubuntu22.04.1-live的vm虚拟机扩展磁盘

ubuntu22.04.1-live的vm虚拟机扩展磁盘

1、虚拟机分配硬盘100G&#xff0c;进系统df -h根目录只有50G 2、查看所有块设备 lsblk 3、 查看卷信息vgdisplay 4、在原有基础上增加49G lvextend -L 49G /dev/ubuntu-vg/ubuntu-lv 5、调整大小 resize2fs /dev/mapper/ubuntu--vg-ubuntu--lv
阅读更多...
TCP/IP五层模型、封装和分用

TCP/IP五层模型、封装和分用

1.网络通信基础2.协议分层OSI七层协议模型TCP/IP五层/四层协议模型【重点】 3. 封装&分用 1.网络通信基础 IP地址&#xff1a;表示计算机的位置&#xff0c;分源IP和目标IP&#xff1b;举个例子&#xff1a;买快递&#xff0c;商家从上海发货&#xff0c;上海就是源IP&…
阅读更多...
七层、四层和五层网络模型区别和联系

七层、四层和五层网络模型区别和联系

七层、四层和五层网络模型区别和联系 概述OSI网络7层模型&#xff08;概念型框架&#xff09;概述图片分析 四层模型概述常用协议OSI与TCP/IP四层的区别 五层模型概述三种网络模型对比 总结 概述 网络模型-七层模型&#xff08;OSI模型&#xff09;、五层协议体系结构和TCP/IP…
阅读更多...
【ag-grid-vue】column

【ag-grid-vue】column

网格中的每一列都使用列定义(ColDef)来定义。列根据在网格选项中指定的列定义的顺序在网格中定位。 列定义 下面的例子展示了一个定义了3列的简单网格: <template><ag-grid-vuestyle"height: 300px; width: 1000px"class"ag-theme-balham":colum…
阅读更多...
微信开发之一键创建微信群聊的技术实现

微信开发之一键创建微信群聊的技术实现

创建微信群 本接口为敏感接口&#xff0c;请查阅调用规范手册创建后&#xff0c;手机上不会显示该群&#xff0c;往该群主动发条消息手机即可显示。 请求URL&#xff1a; http://域名地址/createChatroom 请求方式&#xff1a; POST 请求头Headers&#xff1a; Content-…
阅读更多...
QT通过ODBC连接GBase 8s数据库（Windows）示例

QT通过ODBC连接GBase 8s数据库（Windows）示例

示例环境&#xff1a; 操作系统&#xff1a;Windows 10 64位数据库及CSDK版本&#xff1a;GBase 8s V8.8_3.0.0_1 64位QT&#xff1a;5.12.0 64位 1&#xff0c;CSDK安装及ODBC配置 1.1&#xff0c;免安装版CSDK 下载免安装版的CSDK驱动&#xff0c;地址&#xff1a;https:…
阅读更多...
(vue)el-table 怎么把表格列中相同的数据 合并为一行

(vue)el-table 怎么把表格列中相同的数据 合并为一行

(vue)el-table 怎么把表格列中相同的数据 合并为一行 效果&#xff1a; 文档解释&#xff1a; 写法&#xff1a; <el-table:data"tableData"size"mini"class"table-class"borderstyle"width:100%"max-height"760":span-…
阅读更多...
【应用层】网络基础 -- HTTPS协议

【应用层】网络基础 -- HTTPS协议

HTTPS 协议原理加密为什么要加密常见的加密方式对称加密非对称加密 数据摘要&&数据指纹 HTTPS 的工作过程探究方案1-只使用对称加密方案2-只使用非对称加密方案3-双方都使用非对称加密方案4-非对称加密对称加密中间人攻击-针对上面的场景 CA认证理解数据签名方案5-非对…
阅读更多...
【Django】 Task5 DefaultRouter路由组件和自定义函数

【Django】 Task5 DefaultRouter路由组件和自定义函数

文章目录 【Django】 Task5 DefaultRouter路由组件和自定义函数1.路由组件1.1路由组件介绍1.2SimpleRouter1.3DefaultRouter1.4DefaultRouter示例1.5查看访问服务接口url 2.自定义函数 【Django】 Task5 DefaultRouter路由组件和自定义函数 Task5 主要了解了DefaultRouter路由…
阅读更多...
sql语句中的ddl和dml

sql语句中的ddl和dml

操作数据库&#xff1a;CRUD C&#xff08;create&#xff09; 创建 *数据库创建出来默认字符集为utf8 如果要更改字符集就 Create database 名称 character set gbk&#xff08;字符集&#xff09; *创建数据库&#xff1a;create database 名称 *先检查是否有该数据库在…
阅读更多...
Mac常见恶意软件再现，办公应用程序潜藏风险如何防范？

Mac常见恶意软件再现，办公应用程序潜藏风险如何防范？

Mac电脑正受到臭名昭著的XLoader恶意软件的新变种的攻击&#xff0c;该恶意软件已被重写为在最好的MacBook上本地运行。 虽然XLoader至少从2015年开始出现&#xff0c;但在2021年发现macOS变体之前&#xff0c;它主要用于针对Windows PC。然而&#xff0c;该版本是作为Java程序…
阅读更多...
最新文章

Copyright @ 2022~2023