【C++】“list”的介绍和常用接口的模拟实现

【C++】“list”的介绍和常用接口的模拟实现

  • 一. list的介绍
    • 1. list常见的重要接口
    • 2. list的迭代器失效
  • 二. list常用接口的模拟实现（含注释）
  • 三. list与vector的对比

一. list的介绍

  1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
  2. list的底层是双向带头链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
  3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
  4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
  5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息。

在这里插入图片描述

1. list常见的重要接口

在这里插入图片描述
在这里插入图片描述

  1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
  2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动

在这里插入图片描述

2. list的迭代器失效

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

二. list常用接口的模拟实现（含注释）

#include<assert.h>
#include<iostream>
using std::cout;
using std::endl;
namespace wch
{
	//由于list中的val支持多种类型，定义模板参数T
	template<class T>
	struct list_node
	{
		list_node<T>* _next;
		list_node<T>* _prev;
		T _val;

		//T(),针对自定义类型会去调用它的构造函数，针对内置类型无影响
		list_node(const T& val = T())
			:_next(nullptr)
			, _prev(nullptr)
			, _val(val)
		{}
	};

	// typedef __list_iterator<T, T&, T*> iterator;
	// typedef __list_iterator<T, const T&, const T*> const_iterator;
	//此处定义多个模板参数针对返回值类型
	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)
		{}

		Ref operator*() const//重载普通对象解引用
		{
			return _node->_val;
		}

		Ptr operator->() const//重载指针对象解引用
		{
			return &_node->_val;
		}

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

		//尽量使用引用形参， 避免拷贝开销。同时在不需要修改实参时，通过指定const 引用形参来限制。
		bool operator!=(const self& it) const
		{
			return _node != it._node;
		}

		bool operator==(const self& it) const
		{
			return _node == it._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;

		// 这样设计const迭代器是不行的，因为const迭代器期望指向内容不能修改
		// 这样设计是迭代器本身不能修改
		// T* const ptr2;

		iterator begin() 
		{
			//return _head->_next;//单参构造函数支持隐式类型转换
			return iterator(_head->_next);
		}

		iterator end() 
		{
			return _head;//单参构造函数支持隐式类型转换
			//return iterator(_head);
		}

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

		const_iterator end() const
		{
			return _head;
			//return const_iterator(_head);
		}

		void empty_init()
		{
			_head = new Node;
			_head->_prev = _head;
			_head->_next = _head;

			_size = 0;
		}

		list()//无参默认构造函数
		{
			empty_init();
		}

		// lt2(lt1)
		list(const list<T>& lt)//拷贝构造
			//list(const list& lt)//不加类型也可以，不建议
		{
			empty_init();

			for (auto& e : lt)//深拷贝
			{
				push_back(e);
			}
		}

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

		list<T>& operator=(list<T> lt)//赋值运算符重载
			//list& operator=(list lt)//不加类型也可以，不建议
		{
			swap(lt);

			return *this;
		}

		~list()//析构函数
		{
			clear();

			delete _head;
			_head = nullptr;
		}

		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);//带位置返回值的erase函数，防止迭代器失效
			}

			_size = 0;
		}

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

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

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

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

		// pos位置之前插入
		iterator insert(iterator pos, const T& x)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* newnode = new Node(x);

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

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

			++_size;

			return newnode;
		}

		//删除pos处节点
		iterator erase(iterator pos)
		{
			assert(pos != end());//不可删除头节点

			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()
		{
			/*size_t sz = 0;
			iterator it = begin();
			while (it != end())
			{
				++sz;
				++it;
			}

			return sz;*/

			return _size;
		}

	private:
		Node* _head;
		size_t _size;
	};

	void Print(const list<int>& lt)
	{
		list<int>::const_iterator it = lt.begin();
		while (it != lt.end())
		{
			//(*it) += 1;
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}

	void test_list1()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);

		list<int>::iterator it = lt.begin();

		//由于链表的各个节点地址是不连续的，前一个节点的地址可能比后一个地址大，所以不可已写为 it < it.end();
		while (it != lt.end())
		{
			(*it) += 1;
			cout << *it << " ";
			++it;
		}
		cout << endl;

		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;

		Print(lt);
	}

	struct A
	{
		A(int a1 = 0, int a2 = 0)
			:_a1(a1)
			, _a2(a2)
		{}

		int _a1;
		int _a2;
	};

	void test_list2()
	{
		list<A> lt;
		lt.push_back(A(1, 1));
		lt.push_back(A(2, 2));
		lt.push_back(A(3, 3));
		lt.push_back(A(4, 4));

		list<A>::iterator it = lt.begin();
		while (it != lt.end())
		{
			//cout << (*it)._a1 << " " << (*it)._a2 << endl;
			//it->->_a1, it->->_a2,特殊处理为一个->
			cout << it->_a1 << " " << it->_a2 << endl;

			++it;
		}
		cout << endl;
	}

	void test_list3()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		lt.push_front(5);
		lt.push_front(6);
		lt.push_front(7);
		lt.push_front(8);
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;

		lt.pop_front();
		lt.pop_back();

		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;

		lt.clear();
		lt.push_back(10);
		lt.push_back(20);
		lt.push_back(30);
		lt.push_back(40);
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;

		cout << lt.size() << endl;
	}

	void test_list4()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);

		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;

		list<int> lt1(lt);
		for (auto e : lt1)
		{
			cout << e << " ";
		}
		cout << endl;

		list<int> lt2;
		lt2.push_back(5);
		lt2.push_back(6);
		lt2.push_back(7);
		lt2.push_back(8);

		for (auto e : lt2)
		{
			cout << e << " ";
		}
		cout << endl;

		lt1 = lt2;

		for (auto e : lt1)
		{
			cout << e << " ";
		}
		cout << endl;
	}
}

三. list与vector的对比

vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其主要不同如下：
在这里插入图片描述

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

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

相关文章

2025 年 IT 前景：机遇与挑战并存，人工智能和云计算成重点

2025 年 IT 前景：机遇与挑战并存，人工智能和云计算成重点

云计算de小白 投资人工智能&#xff1a;平衡潜力与实用性 到 2025 年&#xff0c;人工智能将成为 IT 支出的重要驱动力&#xff0c;尤其是在生成式人工智能领域。人工智能的前景在于它有可能彻底改变业务流程、增强决策能力并开辟新的收入来源。然而&#xff0c;现实情况更加微…
阅读更多...
SpringCloud源码：服务端分析（二）- EurekaServer分析

SpringCloud源码：服务端分析（二）- EurekaServer分析

背景 从昨日的两篇文章&#xff1a;SpringCloud源码&#xff1a;客户端分析&#xff08;一&#xff09;- SpringBootApplication注解类加载流程、SpringCloud源码&#xff1a;客户端分析&#xff08;二&#xff09;- 客户端源码分析。 我们理解了客户端的初始化&#xff0c;其实…
阅读更多...
Python画笔案例-071 绘制闪闪的红星

Python画笔案例-071 绘制闪闪的红星

1、绘制通闪闪的红星 通过 python 的turtle 库绘制 闪闪的红星，如下图： 2、实现代码 绘制闪闪的红星，以下为实现代码： """闪闪的红星.py """ import time import turtledef xsleep(n):"""防
阅读更多...
通信工程学习：什么是MAC媒体接入控制

通信工程学习：什么是MAC媒体接入控制

MAC&#xff1a;媒体接入控制 MAC&#xff08;Medium Access Control&#xff09;&#xff0c;即媒体接入控制&#xff0c;是计算机网络中数据链路层的一个重要组成部分&#xff0c;负责协调多个发送和接收站点对一个共享传输媒体的占用。以下是关于MAC的详细解释&#xff1a; …
阅读更多...
系统架构设计师-知识产权与标准化

系统架构设计师-知识产权与标准化

目录 一、保护范围与对象 二、保护期限 三、知识产权人确定 四、侵权判断 五、标准化 一、保护范围与对象 知识产权是权利人依法就下列课题享有的专有权利&#xff1a; &#xff08;一&#xff09;作品&#xff08;著作&#xff09; &#xff08;二&#xff09;发明、实用…
阅读更多...
泰勒图 ——基于相关性与标准差的多模型评价指标可视化比较-XGBoost、sklearn

泰勒图 ——基于相关性与标准差的多模型评价指标可视化比较-XGBoost、sklearn

1、基于相关性与标准差的多模型评价指标可视化比较 # 数据读取并分割 import pandas as pd import numpy as np import matplotlib.pyplot as plt from sklearn.model_selection import train_test_split plt.rcParams[font.family] = Times New Roman plt.rcParams[axes.unic…
阅读更多...
针对考研的C语言学习（2019链表大题）

针对考研的C语言学习（2019链表大题）

题目解析&#xff1a; 【考】双指针算法&#xff0c;逆置法&#xff0c;归并法。 解析&#xff1a;因为题目要求空间复杂度为O(1)&#xff0c;即不能再开辟一条链表&#xff0c;因此我们只能用变量来整体挪动原链表。 第一步先找出中间节点 typedef NODE* Node; Node find_m…
阅读更多...
Linux-基础篇-磁盘分区，挂载

Linux-基础篇-磁盘分区，挂载

Linux 分区 原理介绍 Linux 来说无论有几个分区&#xff0c;分给哪一目录使用&#xff0c;它归根结底就只有一个根目录&#xff0c;一个独立且唯一的文件结构 , Linux 中每个分区都是用来组成整个文件系统的一部分。 Linux 采用了一种叫 “ 载入 ” 的处理方法&#xff0c;…
阅读更多...
为什么有必要由母语人士翻译应用程序界面

为什么有必要由母语人士翻译应用程序界面

在当今技术已成为我们生活不可或缺的一部分的世界中&#xff0c;移动应用接口在我们与数字空间的互动中发挥着关键作用。然而&#xff0c;无论应用程序本身多么完美&#xff0c;它的有效性可能会因糟糕地翻译而大大降低。这就是为什么&#xff0c;为了翻译应用程序界面&#xf…
阅读更多...
在线css像素px到Em的转换器

在线css像素px到Em的转换器

具体请前往&#xff1a;在线Px转Em工具--将绝对像素(px)长度单位转换为相对长度em
阅读更多...
Android SystemUI组件（09）唤醒亮屏 锁屏处理流程

Android SystemUI组件（09）唤醒亮屏 锁屏处理流程

该系列文章总纲链接&#xff1a;专题分纲目录 Android SystemUI组件 本章关键点总结 & 说明&#xff1a; 说明&#xff1a;本章节持续迭代之前章节的思维导图&#xff0c;主要关注左侧上方锁屏分析部分 唤醒亮屏 即可。 Power按键的处理逻辑最终是由PhoneWindowManager来…
阅读更多...
VMware ESXi Centos7网卡名称 ens192 变更eth0

VMware ESXi Centos7网卡名称 ens192 变更eth0

1.在 /etc/sysconfig/network-scirpts/ 文件夹下 创建一个ifcfg-eth0的文件&#xff0c; 最简单的方式是 mv ifcfg-ens192 ifcfg-eth0 然后 vi ifcfg-eth0 把DEVICE改成 DEVICEeth0 wq! 保存 2. vi /etc/sysconfig/grub # 在位置添加 net.ifnames0 biosdevname0 参数 完…
阅读更多...
了解芯片光刻与OPC

了解芯片光刻与OPC

欢迎关注更多精彩 关注我&#xff0c;学习常用算法与数据结构&#xff0c;一题多解&#xff0c;降维打击。 参考资料&#xff1a; 光刻技术与基本流程 https://www.bilibili.com/video/BV1tP4y1j7BA OPC https://www.bilibili.com/video/BV1o94y1U7Td 论文&#xff1a;计算…
阅读更多...
macOS安装Redis教程, 通过brew命令, 时间是2024年9月26日, redis版本是0.7.2

macOS安装Redis教程, 通过brew命令, 时间是2024年9月26日, redis版本是0.7.2

搜索: brew search redis安装Redis: brew install redis关于启动命令的提示: To start redis now and restart at login:brew services start redis Or, if you dont want/need a background service you can just run:/opt/homebrew/opt/redis/bin/redis-server /opt/home…
阅读更多...
Python数据分析篇--NumPy--进阶

Python数据分析篇--NumPy--进阶

人有一种天生的、难以遏制的欲望&#xff0c;那就是在理解之前就评判。 -- 米兰昆德拉 多维数组 1. 一维数组只有行&#xff0c;二维数组相比一维数组多了列这个维度&#xff0c;而三维数组则类似多个二维数组堆叠在一起&#xff0c;形如一个立方体。 二维数组的创建 1. 二…
阅读更多...
.scl文件导入

.scl文件导入

.SCL的文件怎么导入博图-SIMATICS7-1200系列-找答案-西门子中国 从源生成块
阅读更多...
MongoDB微服务部署

MongoDB微服务部署

一、安装MongoDB 1.在linux中拉去MongoDB镜像文件 docker pull mongo:4.4.18 2. 2.创建数据挂载目录 linux命令创建 命令创建目录: mkdir -p /usr/local/docker/mongodb/data 可以在sshclient工具查看是否创建成功。 进入moogodb目录&#xff0c;给data赋予权限777 cd …
阅读更多...
IT新秀系列：Erlang语言的兴起原因分析和前景观望

IT新秀系列：Erlang语言的兴起原因分析和前景观望

Erlang语言的兴起原因 Erlang 是一种通用并发编程语言和运行环境&#xff0c;最早由瑞典电信公司爱立信&#xff08;Ericsson&#xff09;在1986年开发&#xff0c;旨在处理高度并发、分布式和容错系统。Erlang 的主要设计目标是创建一个能够在电信系统中实现高可用性和实时性能…
阅读更多...
Linux：LCD驱动开发

Linux：LCD驱动开发

目录 1.不同接口的LCD硬件操作原理 应用工程师眼中看到的LCD 1.1像素的颜色怎么表示 ​编辑 1.2怎么把颜色发给LCD 驱动工程师眼中看到的LCD 统一的LCD硬件模型 8080接口 TFTRGB接口 什么是MIPI Framebuffer驱动程序框架 怎么编写Framebuffer驱动框架 硬件LCD时序分析…
阅读更多...
【经典机器学习算法】谱聚类算法及其实现（python）

【经典机器学习算法】谱聚类算法及其实现（python）

&#x1f308; 个人主页&#xff1a;十二月的猫-CSDN博客 &#x1f525; 系列专栏&#xff1a; &#x1f3c0;深度学习_十二月的猫的博客-CSDN博客 &#x1f4aa;&#x1f3fb; 十二月的寒冬阻挡不了春天的脚步&#xff0c;十二点的黑夜遮蔽不住黎明的曙光 目录 1. 前言 2. 前…
阅读更多...
最新文章

Copyright @ 2022~2023