C++_list

目录

一、模拟实现list

1、list的基本结构

2、迭代器封装

2.1 正向迭代器

2.2 反向迭代器 

3、指定位置插入

4、指定位置删除

5、结语

前言：

        list是STL(标准模板库)中的八大容器之一，而STL属于C++标准库的一部分，因此在C++中可以直接使用list容器存储数据。list实质上是一个带头双向循环链表，这也使得他能够在常数的时间复杂度范围内插入和删除数据，缺点是不能像数组那样进行元素下标的随机访问。

一、模拟实现list

        在C++中可以直接调用库里的list，并且使用起来非常的简便，和使用vector、string相差无几，但是为了能够更好的了解list和其底层原理，下文会对lsit的常用接口进行模拟实现，以便对list有更深入的理解，并且list的底层实现逻辑完美的表现了面向对象的思想。

1、list的基本结构

        与实现vector和string不一样，list可以分成两个整体：链表本身、节点本身，因此需要两个类（链表类、节点类）完成list的基本实现，并且把节点类看作是一个普通的节点，而实现链表的具体功能函数都放在链表类中。

        list基本功能代码如下：

#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
using namespace std;

namespace ZH
{
	template <class T>
	struct list_node//节点类
	{
		list_node<T>* prev;
		list_node<T>* next;
		T val;

		list_node(const T& t)
			:prev(nullptr)
			, next(nullptr)
			, val(t)
		{}
	};

	template <class T>
	class list//链表类
	{
	public:
		typedef list_node<T> node;//让节点类看起来像一个普通的节点

		list()//构造函数、目的是创建哨兵位头节点
			:_node(new node(-1))
		{
			_node->next = _node;
			_node->prev = _node;
		}

		void push_front(const T& t)//头插
		{
			node* newnode = new node(t);
			node* cur = _node->next;

			_node->next = newnode;
			newnode->prev = _node;
			newnode->next = cur;
			cur->prev = newnode;
		}

		void Print()//打印数据
		{
			node* cur = _node->next;
			while (cur != _node)
			{
				cout << cur->val << " ";
				cur = cur->next;
			}
		}

		~list()//析构
		{
			node* cur = _node->next;
			node* dest = cur->next;
			while (cur != _node)
			{
				delete cur;
				cur = dest;
				dest = dest->next;
			}
			delete _node;
			_node = nullptr;
		}

	private:
		node* _node;

	};
}

int main()
{
	ZH::list<int> lt;
	lt.push_front(1);
	lt.push_front(2);
	lt.push_front(3);
	lt.push_front(4);
	lt.Print();
	return 0;
}

        运行结果：

        从上面的代码可以发现， list的底层实现和之前c语言中实现双向循环链表的逻辑一模一样，只不过用C++的方式将其进行了封装。

        这里节点类里的成员变量要放在公有域（struct定义类默认为公有域），因为在list中会改变节点前后指针的指向，因此节点的指针要设为外部可见。

2、迭代器封装

2.1 正向迭代器

        在调用库里面的list，会发现库里面list的迭代器用起来像是一个指针，因为可以对迭代器进行解引用操作以及++操作。所以在模拟实现迭代器时，我们也用一个指针来模拟迭代器的行为，不同的是指针进行++操作时，会指向该地址的下一个地址，而我们期望的迭代器++可以指向下一个节点。

        示意图如下：

        因此，如果单单的把指针看成迭代器则无法实现遍历链表的功能，所以要实现迭代器必须对指针进行又一层的封装，也就是把迭代器写成一个类，但是该类的底层还是一个节点指针，只是对该指针的操作有了新的规定。

        正向迭代器代码实现如下：

#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
using namespace std;

namespace ZH
{
	template <class T>
	struct list_node//节点类
	{
		list_node<T>* prev;
		list_node<T>* next;
		T val;

		list_node(const T& t)
			:prev(nullptr)
			, next(nullptr)
			, val(t)
		{}
	};

	template<class T>
	struct list_iterator//迭代器类
	{
		typedef list_node<T> node;
		typedef list_iterator<T> self;

		node* _node;// 成员变量

		list_iterator(node* node)
			:_node(node)
		{}

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

		self& operator++()//重载前置++
		{
			_node = _node->next;
			return *this;
		}

		T& operator*()//重载解引用
		{
			return _node->val;
		}

	};

	template <class T>
	class list//链表类
	{
	public:
		typedef list_node<T> node;//让节点类看起来像一个普通的节点
		typedef list_iterator<T> iterator;//让迭代器类看起来像一个迭代器

		list()//构造函数、目的是创建哨兵位头节点
			:_node(new node(-1))
		{
			_node->next = _node;
			_node->prev = _node;
		}

		void push_front(const T& t)//头插
		{
			node* newnode = new node(t);
			node* cur = _node->next;

			_node->next = newnode;
			newnode->prev = _node;
			newnode->next = cur;
			cur->prev = newnode;
		}

		iterator begin()
		{
			//begin返回的是一个指向头节点的下一个节点的迭代器对象
			return iterator(_node->next);//匿名对象创建并返回
		}

		iterator end()
		{
			//begin返回的是一个指向头节点的迭代器对象
			return iterator(_node);//匿名对象创建并返回
		}

		~list()//析构
		{
			node* cur = _node->next;
			node* dest = cur->next;
			while (cur != _node)
			{
				delete cur;
				cur = dest;
				dest = dest->next;
			}
			delete _node;
			_node = nullptr;
		}

	private:
		node* _node;//指向哨兵位的头节点

	};
}

int main()
{
	ZH::list<int> lt;
	lt.push_front(1);
	lt.push_front(2);
	lt.push_front(3);
	lt.push_front(4);
	ZH::list<int>::iterator it = lt.begin();
	while (it!=lt.end())
	{
		cout << *it << " ";
		++it;
	}
	return 0;
}

        运行结果：

        注意，这里的it要看成是一个对象，他的类型是 list<int>::iterator。ZH::list<int>::iterator it = lt.begin();这句代码实际上是调用了拷贝构造，用begin（）的返回对象构造了一个新的对象it。

2.2 反向迭代器 

        反向迭代器与正向迭代器的区别在于，反向迭代器是从链表的最后一个节点开始往前遍历的，并且他的逻辑和正向迭代器的逻辑是相反的，可以确定的一点是反向迭代器也是通过一个类来实现的。

        反向迭代器实现代码如下：

#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
using namespace std;

namespace ZH
{
	template <class T>
	struct list_node//节点类
	{
		list_node<T>* prev;
		list_node<T>* next;
		T val;

		list_node(const T& t)
			:prev(nullptr)
			, next(nullptr)
			, val(t)
		{}
	};

	template<class T>
	struct list_iterator//迭代器类
	{
		typedef list_node<T> node;
		typedef list_iterator<T> self;

		node* _node;// 成员变量

		list_iterator(node* node)
			:_node(node)
		{}

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

		self& operator++()//重载前置++
		{
			_node = _node->next;
			return *this;
		}

		self& operator--()//重载前置--
		{
			_node = _node->prev;
			return *this;
		}

		T& operator*()//重载解引用
		{
			return _node->val;
		}

	};

	template<class T>
	class list_reverse_iterator
	{
	public:
		typedef list_iterator<T> iterator;
		typedef list_reverse_iterator<T> rself;

		list_reverse_iterator(iterator it)
				:rit(it)
		{}

		bool operator!=(const rself& s)//重载！=
		{
			return rit!= s.rit;//复用正向迭代器的！=重载
		}

		rself& operator++()//重载前置++
		{
			--rit;//复用正向迭代器的++
			return *this;
		}

		T& operator*()//重载解引用
		{
			return *rit;//复用正向迭代器的解引用
		}

	private:
		iterator rit;
	};

	template <class T>
	class list//链表类
	{
	public:
		typedef list_node<T> node;//让节点类看起来像一个普通的节点
		typedef list_iterator<T> iterator;//让迭代器类看起来像一个迭代器
		typedef list_reverse_iterator<T> reverse_iterator;

		list()//构造函数、目的是创建哨兵位头节点
			:_node(new node(-1))
		{
			_node->next = _node;
			_node->prev = _node;
		}

		void push_front(const T& t)//头插
		{
			node* newnode = new node(t);
			node* cur = _node->next;

			_node->next = newnode;
			newnode->prev = _node;
			newnode->next = cur;
			cur->prev = newnode;
		}

		reverse_iterator rbegin()
		{
			return reverse_iterator(iterator(_node->prev));//返回最后一个节点
		}

		reverse_iterator rend()
		{
			return reverse_iterator(iterator(_node));//返回头节点
		}

		~list()//析构
		{
			node* cur = _node->next;
			node* dest = cur->next;
			while (cur != _node)
			{
				delete cur;
				cur = dest;
				dest = dest->next;
			}
			delete _node;
			_node = nullptr;
		}

	private:
		node* _node;//指向哨兵位的头节点

	};
}

int main()
{
	ZH::list<int> lt;
	lt.push_front(1);
	lt.push_front(2);
	lt.push_front(3);
	lt.push_front(4);
	ZH::list<int>::reverse_iterator rit = lt.rbegin();
	while (rit != lt.rend())
	{
		cout << *rit << " ";
		++rit;
	}
	return 0;
}

        运行结果：

        从上述代码中可以发现，反向迭代器是复用正向迭代器的成员函数达到实现的，只不过在反向迭代器类里进行又一层包装。

3、指定位置插入

        有了迭代器，就可以实现从指定位置插入了，指定位置插入代码如下：

void Insert(iterator pos, const T& val)//插入
		{
			node* newnode = new node(val);
			node* cur = pos._node;
			node* prev = cur->prev;

			prev->next = newnode;
			newnode->prev = prev;
			newnode->next = cur;
			cur->prev = newnode;
		}

         值得注意的是，list的插入不会导致迭代器失效，因为即使在该迭代器指向节点的前面插入一个数据，则该迭代器还是指向该节点的。

4、指定位置删除

        指定位置删除代码如下：

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

        删除逻辑示意图：

        删除与插入不同在于，删除之后迭代器会失效，因为此时it指向的是一块被回收的区域，不能直接访问it所指向的区域，会导致野指针问题。 

5、结语

        以上就是关于list如何实现的讲解，list的模拟实现完全体现了面向对象的思想，链表本身、节点以及迭代器都被封装成一个类，从用户的角度看，是在对象的层面上直接进行操作的，但是底层却是各种复用，依旧是通过操作内置类型来实现上层的对象之间的操作。

        最后希望本文可以给你带来更多的收获，如果本文对你起到了帮助，希望可以动动小指头帮忙点赞👍+关注😎+收藏👌！如果有遗漏或者有误的地方欢迎大家在评论区补充，谢谢大家！！

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

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

相关文章

TestNG中的DataProviders（@DataProvider annotation）

TestNG中的DataProviders（@DataProvider annotation）

目录 什么是数据提供者&#xff1f; 数据提供程序及其返回的内容 DataProvider语法 DataProvider注释的方法可以返回什么&#xff1f; 使用数据提供程序的测试用例 如何在测试用例中使用数据提供程序&#xff1f; 其他类中的数据提供程序 在DataProvider带注释的方法中…
阅读更多...
深度强化学习（王树森）笔记11

深度强化学习（王树森）笔记11

深度强化学习&#xff08;DRL&#xff09; 本文是学习笔记&#xff0c;如有侵权&#xff0c;请联系删除。本文在ChatGPT辅助下完成。 参考链接 Deep Reinforcement Learning官方链接&#xff1a;https://github.com/wangshusen/DRL 源代码链接&#xff1a;https://github.c…
阅读更多...
植物病害检测YOLOV8，OPENCV调用

植物病害检测YOLOV8，OPENCV调用

【免费】植物病害检测&#xff0c;10种类型&#xff0c;YOLOV8训练&#xff0c;转换成ONNX&#xff0c;OPENCV调用资源-CSDN文库 植物病害检测&#xff0c;YOLOV8NANO&#xff0c;训练得到PT模型&#xff0c;然后转换成ONNX&#xff0c;OPENCV的DNN调用&#xff0c;支持C,PYTH…
阅读更多...
算法——线性代数——逆序数奇偶

算法——线性代数——逆序数奇偶

一、逆序数奇偶 分析&#xff1a; 概念&#xff1a; 求一个排列的逆序数奇偶性有两种方法&#xff0c;一种是从前往后遍历数组&#xff0c;另一种是从后往前遍历数组从前往后时&#xff0c;当前数字前面大于它的数字的个数即为它的逆序数个数从后往前时&#xff0c;当前数字前…
阅读更多...
Docker的使用方式

Docker的使用方式

一、Docker概念 Docker类似于一个轻量的虚拟机。 容器和镜像是Docker中最重要的两个概念&#xff0c;镜像可以保存为tar文件&#xff0c;Dockerfile是配置文件&#xff0c;仓库保存了很多第三方已经做好的镜像。 基本指令 查找镜像 docker search nginx 拉取nginx镜像 do…
阅读更多...
Yalmip学习笔记

Yalmip学习笔记

这里写自定义目录标题 基本用法变量定义关于大MBilevel programming 注&#xff1a;这篇文章主要是留给自己查漏补缺的&#xff0c;所以从来没有使用过yalmip的读者看着会觉得跳来跳去。 基本用法 建模开始前&#xff0c;使用yalmip(clear)清空Yalmip的内部数据库。 下面是一个…
阅读更多...
少儿编程教育：培养未来创新者

少儿编程教育：培养未来创新者

在这个数字化飞速发展的时代&#xff0c;编程已经成为了一门新的通用语言。随着科技的不断进步&#xff0c;编程教育正逐渐从高等教育领域向中小学乃至幼儿园渗透。6547网认为少儿编程不仅是一种技能的培养&#xff0c;更是对孩子们逻辑思维、解决问题能力和创造力的锻炼。图形…
阅读更多...
Spring 中获取 Bean 对象的三种方式

Spring 中获取 Bean 对象的三种方式

目录 1、根据名称获取Bean 2、根据Bean类型获取Bean 3、根据 Bean 名称 Bean 类型来获取 Bean&#xff08;好的解决方法&#xff09; 假设 Bean 对象是 User&#xff0c;并存储到 Spring 中&#xff0c;注册到 xml 文件中 public class User {public String sayHi(){retur…
阅读更多...
Mac安装及配置MySql及图形化工具MySQLworkbench安装

Mac安装及配置MySql及图形化工具MySQLworkbench安装

Mac下载配置MySql mysql下载及安装 下载地址&#xff1a;https://dev.mysql.com/downloads/mysql/ 根据自己电脑确定下载x86还是ARM版本的 如果不确定&#xff0c;可以查看自己电脑版本&#xff0c;终端输入命令 uname -a 点击Download下载&#xff0c;可跳过登录注册&…
阅读更多...
Oracle 面试题 | 01.精选Oracle高频面试题

Oracle 面试题 | 01.精选Oracle高频面试题

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 &#x1f35a; 蓝桥云课签约作者、上架课程《Vue.js 和 E…
阅读更多...
python统计分析——中心极限定理

python统计分析——中心极限定理

参考资料&#xff1a;用python动手学统计学 对于任意总体分布&#xff0c;样本容量越大&#xff0c;随机变量的和的分布越接近正态分布&#xff0c;这就是中心极限定理定理。 以掷硬币为例讲解。模拟投硬币1万次中&#xff0c;正面朝上的次数的分布。 import numpy as np impo…
阅读更多...
Redis -- 开篇热身，常用的全局命令

Redis -- 开篇热身，常用的全局命令

目录 Redis重要文件 启动停止脚本 配置文件 持久化文件存储目录 核心命令 set get 全局命令 keys exists del expire ttl 过期策略是如何实现的 定时器 type 小结 Redis重要文件 启动停止脚本 /usr/bin/redis-benchmark &#xff1a; 用于对Redis做性能基准…
阅读更多...
操作系统A-第四和五章(存储器)作业解析

操作系统A-第四和五章(存储器)作业解析

目录 1、在请求分页系统中&#xff0c;某用户程序的逻辑地址空间为 16 页&#xff0c;每页 1KB&#xff0c;分配的内存空间为 8KB。假定某时刻该用户的页表如下表所示。 试问&#xff1a;(1)逻辑地址 184BH 对应的物理地址是多少&#xff1f;&#xff08;用十六进制表示&…
阅读更多...
【个人博客搭建】Hexo安装部署

【个人博客搭建】Hexo安装部署

目录 一、本地构建Hexo (一) 安装前提 1. Node.js 2. Git 3. Hexo (二) 初始化Hexo 1. 初始化博客目录 2. 配置网站基本信息 (三) 主题配置 1. 选择主题 2. 下载主题 (四) 本地启动Hexo 1. 生成静态文件 2. 启动服务 二、部署 (一) 部署到Github Pages 1. 新建…
阅读更多...
Session

Session

Session的基本使用 1.概念 Session&#xff1a;服务端会话跟踪技术&#xff1a;将数据保存到服务端。 Session是存储在服务端而Cookie是存储在客户端 存储在客户端的数据容易被窃取和截获&#xff0c;存在很多不安全的因素 存储在服务端的数据相比于客户端来说就更安全 2…
阅读更多...
人工智能(pytorch)搭建模型23-pytorch搭建生成对抗网络(GAN):手写数字生成的项目应用

人工智能(pytorch)搭建模型23-pytorch搭建生成对抗网络(GAN):手写数字生成的项目应用

大家好&#xff0c;我是微学AI&#xff0c;今天给大家介绍一下人工智能(pytorch)搭建模型23-pytorch搭建生成对抗网络(GAN):手写数字生成的项目应用。生成对抗网络&#xff08;GAN&#xff09;是一种强大的生成模型&#xff0c;在手写数字生成方面具有广泛的应用前景。通过生成…
阅读更多...
【RT-DETR有效改进】Bi-FPN高效的双向特征金字塔网络（附yaml文件+完整代码）

【RT-DETR有效改进】Bi-FPN高效的双向特征金字塔网络（附yaml文件+完整代码）

👑欢迎大家订阅本专栏，一起学习RT-DETR👑 一、本文介绍 本文给大家带来的改进机制是BiFPN双向特征金字塔网络，其是一种特征融合层的结构，也就是我们本文改进RT-DETR模型中的Neck部分，它的主要思想是通过多层级的特征金字塔和双向信息传递来提高精度。本文给大家带…
阅读更多...
走迷宫-bfs

走迷宫-bfs

package Test;import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader;public class Main {static int N 110,hh 0,tt -1,n,m;static int[][] g new int[N][N]; //用来存储迷宫static int[][] d new int[N][N]; //用来存储d[i…
阅读更多...
yarn 现代的包管理工具 介绍

yarn 现代的包管理工具 介绍

一、前言 yarn 是一个现代的包管理工具&#xff0c;它是 npm&#xff08;Node Package Manager&#xff09;的一个替代品。yarn 由 Facebook 开发&#xff0c;并在 2016 年发布。它解决了当时 npm 的一些问题&#xff0c;尤其是在性能和安全性方面。 yarn 主要用于以下几个方面…
阅读更多...
bat脚本：批量生成创建数据库的SQL语句

bat脚本：批量生成创建数据库的SQL语句

需求来源&#xff1a;使用 Navicat等数据库工具点击“转储SQL文件”会生成一个 xxx.sql 的文件&#xff0c;xxx是导出的数据库名。导出的数据库多了&#xff0c;就会一次性生成很多这样的SQL文件&#xff0c;所以需要写个脚本根据这些SQL脚本文件来批量生成创建数据库的SQL语句…
阅读更多...
最新文章

Copyright @ 2022~2023