C++初阶之list的使用和模拟以及反向迭代器的模拟实现

个人主页：点我进入主页

专栏分类：C语言初阶  C语言进阶  数据结构初阶    Linux    C++初阶    算法

欢迎大家点赞，评论，收藏。

一起努力，一起奔赴大厂

一.list简介

        list是一个带头双向链表，在数据结构的时候，我写过关于带头双向循环链表的实现，可以看博客https://yangking.blog.csdn.net/article/details/134495668，我们可以看下面的图，是list的存储结构，

本次的内容包括list的使用，list的模拟实现，list的迭代器以及反向迭代器的原理，模拟实现和使用，最重要的是迭代器和反向迭代器的内容，在前面string和vector中迭代器是原生的指针，但是在这里不是，具体是什么样子的我们可以看后面的内容。 

二.一个简易的list

2.1.单个节点

template<class T>
struct ListNode
{
	typedef  ListNode<T>  Node;
		
	Node* _next;
	Node* _prev;
	T _data;
	ListNode(const T& val = T())
		: _next(nullptr)
		, _prev(nullptr)
		, _data(val)
	{}
};

在这里我们可以使用strcut结构体来创建一个节点

2.2.默认构造

void empty_init()
{
	_head = new Node;
	_head->_next = _head;
	_head->_prev = _head;
	_size = 0;
}
list()
{
	empty_init();
}

我们创建一个头节点， 让它指向自己。

2.3push_back

void push_back(const T& val)
{
	Node* newnode = new Node(val);
	Node* prev = _head._node->_prev;
	Node* cur = _head._node;

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

在这里我们就是简单的插入操作，不给具体的解释。到这里我们简易的list就完成了，我们依次插入1234可以看到

void test()
{
	list<int> l;
	l.push_back(1);
	l.push_back(2);
	l.push_back(3);
	l.push_back(4);
}

三.迭代器

        我们封装一个迭代器的类，我们的迭代器需要支持

list<int>::iterator it = lt1.begin();
while (it != lt1.end())
{
	cout << *it << " ";
	++it;
}
cout << endl;

所以我们里面需要包括!=,*it,++it,以及begin和end这些内容，我们需要知道迭代器模仿的是Node*这个行为，我们看一下模拟代码：

template <class T>
struct ListIterator
{
	typedef ListNode<T>  Node;
	typedef ListIterator<T> Self;
	Node* _node;
	ListIterator(Node* node)
		:_node(node)
	{}
	bool operator==(const Self& it)
	{
		return _node == it._node;
	}
	bool operator!=(const Self& it)
	{
		return _node != it._node;
	}


	Self& operator--()
	{
		_node = _node->_prev;
		return *this;
	}
	Self operator--(int)
	{
		Self tmp(_node);
		_node = _node->_prev;
		return *tmp;
	}
	Self& operator++()
	{
		_node = _node->_next;
		return *this;
	}
	Self operator++(int)
	{
		Self tmp(_node);
		_node = _node->_next;
		return tmp;
	}
	T& operator*()
	{
		return _node->_data;
	}
};

我们在list类里面加入

iterator begin()
{
	return _head->_next;
}
iterator end()
{
	return _head;
}

我们运行测试代码

void test()
{
	list<int> l;
	l.push_back(1);
	l.push_back(2);
	l.push_back(3);
	l.push_back(4);
	list<int>::iterator it = l.begin();
	while (it != l.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
}

运行结果为

四.insert和erase以及复用

4.1insert

 在这里我们的insert用迭代器进行插入，给以个位置，插入它的前面，

 我们的代码如下：

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

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

有了我们的insert我们的push_back可以复用我们的insert，可以改为

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

在这里我们的insert不会造成迭代器失效，因为指针指向的位置不会发生改变，它是插入到pos位置的前面。

4.2erase以及迭代器失效

对于返回值为什么是iterator，这和我们的迭代器失效有关，我们先用void来展示其中的问题。

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

	delete pos._node;
	prev->_next = next;
	next->_prev = prev;
	_size--;
}

我们的测试代码如下：
 

void test()
{
	list<int> l;
	l.push_back(1);
	l.push_back(2);
	l.push_back(3);
	l.push_back(4);
	list<int>::iterator it = l.begin();
	while (it != l.end())
	{
		if (*it % 2 == 0) l.erase(it);
		else it++;
	}
	it = l.begin();
	while (it != l.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
}

在这里会出现错误，原因是迭代器失效，野指针的引用，所以我们需要对迭代器进行维护，所以有了返回值，我们改为

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

	delete pos._node;
	prev->_next = next;
	next->_prev = prev;
	_size--;
	return next;
}

4.3复用

有了这两个，我们的pop_back，pop_front,push_front就可以有了

void pop_back()
{
	erase(--end());
}
void pop_front()
{
	erase(begin());
}
void push_front(const T& val)
{
	insert(begin(), val);
}

五.operator->（）

        我们的T是一个结构体

struct A
{
	int a = 1;
	int b = 2;
};
void test()
{
	list<A> l;
	l.push_back({ 1,2 });
	l.push_back({ 2,3 });
	l.push_back({ 3,4 });
	l.push_back({ 4,5 });
	list<A>::iterator it = l.begin();

	while (it != l.end())
	{
	/*	cout << (*it).a << " " << (*it).b << endl;*/
		cout << it._node->_data.a << " " << it._node->_data.b << endl;
		it++;
	}
}

 我们的解引用是不是看的非常难受，所有我们需要operator一下，

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

 我们改为

cout << it->a << " " << it->b << endl;

六.const迭代器

        有了我们的非const版本的，那么我们就需要我们的const版本的，const版本就是将所有的都复制一份，然后operator*返回const的

template <class T>
struct ListConstIterator
{
	typedef ListNode<T>  Node;
	typedef ListConstIterator<T> Self;
	Node* _node;
	ListConstIterator(Node* node)
		:_node(node)
	{}
	bool operator==(const Self& it)
	{
		return _node == it._node;
	}
	bool operator!=(const Self& it)
	{
		return _node != it._node;
	}


	Self& operator--()
	{
		_node = _node->_prev;
		return *this;
	}
	Self operator--(int)
	{
		Self tmp(_node);
		_node = _node->_prev;
		return *tmp;
	}
	Self& operator++()
	{
		_node = _node->_next;
		return *this;
	}
	Self operator++(int)
	{
		Self tmp(_node);
		_node = _node->_next;
		return tmp;
	}
	const T& operator*()
	{
		return _node->_data;
	}
	const T* operator->()
	{
		return &_node->_data;
	}
};

由于这个会和非fonst很多内容一样，会造成代码冗余，所以我们可以利用模板来简化我们的代码，我们非const的代码函数的返回值为Self，T&,T*，const版本的是Self，const T&，const T*，所以我们可以写成模板

template <class T,class Ref,class Ptr>
struct ListIterator
{
	typedef ListNode<T>  Node;
	typedef ListIterator< T, Ref, Ptr> Self;
	Node* _node;
	ListIterator(Node* node)
		:_node(node)
	{}
	bool operator==(const Self& it)
	{
		return _node == it._node;
	}
	bool operator!=(const Self& it)
	{
		return _node != it._node;
	}


	Self& operator--()
	{
		_node = _node->_prev;
		return *this;
	}
	Self operator--(int)
	{
		Self tmp(_node);
		_node = _node->_prev;
		return *tmp;
	}
	Self& operator++()
	{
		_node = _node->_next;
		return *this;
	}
	Self operator++(int)
	{
		Self tmp(_node);
		_node = _node->_next;
		return tmp;
	}
	Ref operator*()
	{
		return _node->_data;
	}
	Ptr operator->()
	{
		return &_node->_data;
	}
};

我们在list类里面写入

typedef ListIterator<T,T&,T*> iterator;
typedef ListIterator<T,const T&,const T*> const_iterator;

这样我们由我们自己写改为了编译器去写。

七.反向迭代器

        我们的反向得带起是使用正向迭代器进行写的，它的rbegin是正向迭代器的end，rend是正向迭代器的begin，所以它的operator*是解引用前一个的。

template <class Iterator, class Ref, class Ptr>
struct ReverseIterator
{
	typedef ReverseIterator<Iterator, Ref, Ptr> Self;

	Iterator _it;
		
	ReverseIterator(Iterator it)
		:_it(it)
	{}
	Ref operator*()
	{
		Iterator tmp = _it;
		--tmp;
		return *tmp;
	}
	Ptr operator->()
	{
		return _it.operator->();
	}

	Self rbegin()
	{
		return ReverseIterator(_it.end());
	}
	Self rend()
	{
		return ReverseIterator(_it.begin());
	}
	Self operator++()
	{
		--_it;
		return *this;
	}
	Self operator++(int)
	{
		Iterator tmp = _it;
		--_it;
		return tmp;
	}
	Self operator--()
	{
		++_it;
		return *this;
	}
	Self operator--(int)
	{
		Iterator tmp = _it;
		tmp = _it;
		++_it;
		return tmp;
	}
	bool operator!=(Self it)
	{
		return _it != it._it;
	}

};

到这里我们的内容结束了。

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

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

相关文章

44 网络基础

44 网络基础

本章重点 了解网络发展背景&#xff0c;对局域网/广域网的概念有基本认识 了解网络协议的意义&#xff0c;重点理解TCP/IP五层结构模型 学习网络传输的基本流程&#xff0c;理解封装和分用 目录 1.网络发展 2.协议 3.OSI七层模型 4.TCP/IP五层模型 5.网络传输流程图 6.网络中…
阅读更多...
VMP 简单源码分析（.net）

VMP 简单源码分析（.net）

虚拟机 获取CPU的型号 实现了一个指令集解释器&#xff0c;每个操作码对应一个特定的处理函数&#xff0c;用于执行相应的指令操作。在执行字节码时&#xff0c;解释器会根据操作码查找并调用相应的处理函数来执行指令。 截获异常 先由虚拟机处理 处理不了再抛出异常 priva…
阅读更多...
开源投票系统源码及搭建 在线投票活动创建系统的设计与开发

开源投票系统源码及搭建 在线投票活动创建系统的设计与开发

在当今数字化时代&#xff0c;在线投票活动已成为各类组织、企业和个人不可或缺的一部分。无论是选举、问卷调查、产品评选还是其他需要收集公众意见的场景&#xff0c;一个高效、稳定且易于使用的在线投票系统都至关重要。 分享一款基于开源投票系统源码的在线投票活动创建系…
阅读更多...
设计模式Java实现-建造者模式

设计模式Java实现-建造者模式

楔子 小七在2019年的时候&#xff0c;就想写一个关于设计模式的专栏&#xff0c;但是最终却半途而废了。粗略一想&#xff0c;如果做完一件事要100分钟&#xff0c;小七用3分钟热情做的事&#xff0c;最少也能完成10件事情了。所以这一次&#xff0c;一定要把他做完&#xff0…
阅读更多...
ICode国际青少年编程竞赛- Python-1级训练场-综合训练1

ICode国际青少年编程竞赛- Python-1级训练场-综合训练1

ICode国际青少年编程竞赛- Python-1级训练场-综合训练1 1、 Spaceship.turnLeft() for i in range(2):Spaceship.turnLeft()Spaceship.step(3) Dev.step(-1) Spaceship.step(4) Spaceship.turnLeft() Spaceship.step(3)2、 Spaceship.step() Spaceship.turnLeft() Spaceship.…
阅读更多...
学QT的第一天~

学QT的第一天~

#include "mywidget.h" MyWidget::MyWidget(QWidget *parent) : QWidget(parent) { //窗口相关设置// this->resize(427,330); this->setFixedSize(427,330); //设置图标 this->setWindowIcon(QIcon("C:\\Users\\Admin\\Desktop\\pictrue\\dahz.jpg&q…
阅读更多...
【面试经典 150 | 分治】建立四叉树

【面试经典 150 | 分治】建立四叉树

文章目录 写在前面Tag题目来源解题思路方法一&#xff1a;递归 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法&#xff0c;两到三天更新一篇文章&#xff0c;欢迎催更…… 专栏内容以分析题目为主&#xff0c;并附带一些对于本题涉及到的数据结构等内容进行回顾…
阅读更多...
C语言写的LLM训练

C语言写的LLM训练

特斯拉前 AI 总监、OpenAI 创始团队成员 Andrej Karpathy 用 C 代码完成了 GPT-2 大模型训练过程&#xff1a;karpathy/llm.c: LLM training in simple, raw C/CUDA (github.com) 下载源码 git clone --recursive https://github.com/karpathy/llm.c.git下载模型 从HF-Mirro…
阅读更多...
JavaScript中的RegExp和Cookie

JavaScript中的RegExp和Cookie

个人主页&#xff1a;学习前端的小z 个人专栏&#xff1a;JavaScript 精粹 本专栏旨在分享记录每日学习的前端知识和学习笔记的归纳总结&#xff0c;欢迎大家在评论区交流讨论&#xff01; 文章目录 &#x1f506;RegExp &#x1f3b2; 1 什么是正则表达式 &#x1f3b2;2 创建…
阅读更多...
组件化开发根组件

组件化开发根组件

目录 一、组件化开发介绍 二、根组件 一、组件化开发介绍 组件化&#xff1a;一个页面可以拆分成一个个组件&#xff0c;每个组件有着自己独立的结构、样式、行为。 好处&#xff1a;便于维护&#xff0c;利于复用&#xff0c;提升开发效率。 二、根组件 组件分类&#xff…
阅读更多...
MindSponge分子动力学模拟——安装与使用

MindSponge分子动力学模拟——安装与使用

技术背景 昇思MindSpore是由华为主导的一个&#xff0c;面向全场景构建最佳昇腾匹配、支持多处理器架构的开放AI框架。MindSpore不仅仅是软件层面的工具&#xff0c;更重要的是可以协同华为自研的昇腾Ascend平台&#xff0c;做到软硬件一体的行业解决方案。基于MindSpore的高通…
阅读更多...
Gin 框架的使用

Gin 框架的使用

1、Gin 快速开发 1.1、环境准备 1.1.1、导入 gin 依赖 这里就叫 gin 依赖了&#xff0c;在 Goland 命令行中输入下面的命令&#xff1a; go get -u github.com/gin-gonic/gin 1.1.2、设置代理 如果下载失败&#xff0c;最好设置一下代理&#xff0c;在 cmd 命令行中输入下…
阅读更多...
react【实用教程】 搭建开发环境（2024版）Vite+React （官方推荐）

react【实用教程】 搭建开发环境（2024版）Vite+React （官方推荐）

以项目名 reactDemo为例 1. 下载脚手架 在目标文件夹中打开命令行 npm create vite2. 安装项目依赖 cd reactDemo npm i若安装失败&#xff0c;则修改下载源重试 npm config set registry https://registry.npmmirror.com3. 启动项目 npm run dev4. 预览项目 浏览器访问 http…
阅读更多...
亚马逊FBA头程多少钱一公斤?FBA头程怎么收费?

亚马逊FBA头程多少钱一公斤?FBA头程怎么收费?

在亚马逊的电商生态中&#xff0c;FBA服务已经成为许多卖家提升客户满意度和销售效率的重要工具&#xff0c;然而&#xff0c;对于使用FBA服务的卖家来说&#xff0c;选择一家合适的物流合作伙伴并了解其FBA头程的收费标准和计费方式同样至关重要&#xff0c;亚马逊FBA头程多少…
阅读更多...
Elsevier——投稿系统遇到bug时的解决方法

Elsevier——投稿系统遇到bug时的解决方法

重要&#xff1a;找期刊客服&#xff01;&#xff01;&#xff01; 一、方法&#xff1a; 1. 点击进入与官方客服的对话 2. 按要求输入个人信息 3. 输入遇到的问题 比如&#xff1a; 主题&#xff1a;The Current Status is jammed. 详细描述&#xff1a;The Current State o…
阅读更多...
XSS-Labs 靶场通过解析（上）

XSS-Labs 靶场通过解析（上）

前言 XSS-Labs靶场是一个专门用于学习和练习跨站脚本攻击&#xff08;XSS&#xff09;技术的在线平台。它提供了一系列的实验场景和演示&#xff0c;帮助安全研究人员、开发人员和安全爱好者深入了解XSS攻击的原理和防御方法。 XSS-Labs靶场的主要特点和功能包括&#xff1a;…
阅读更多...
数据结构：线性表(详解)

数据结构：线性表(详解)

线性表 线性表的知识框架&#xff1a; 线性表的定义&#xff1a; 线性表是具有相同数据类型的n(n > 0)个数据元素的有限序列&#xff0c;当n 0时线性表为一个空表。 若用L命名为线性表&#xff0c;则数据集合为L {a1,a2,…,an}&#xff0c;其中a1称为表头元素&#xff0c…
阅读更多...
【方法】如何创建RAR格式压缩文件？

【方法】如何创建RAR格式压缩文件？

为了方便存储或者传输文件&#xff0c;我们经常会把文件打包成不同格式的压缩包&#xff0c;那如果想创建的是RAR格式的压缩包&#xff0c;要如何做呢&#xff1f; RAR是WinRAR软件独有的压缩格式&#xff0c;所以我们可以通过WinRAR软件来创建RAR格式压缩包。下面分享两种创建…
阅读更多...
02_SpringBoot程序快速启动

02_SpringBoot程序快速启动

目录 打包命令启动启动成功测试结果 打包 点击package打包命令&#xff0c;会生成target目录&#xff0c;目录下会有生成的jar包 命令启动 打开cmd命令窗口&#xff0c;进入子项目的target目录下,输入命令后&#xff0c;回车… java -jar .\note-boot-core-1.0-SNAPSHOT.j…
阅读更多...
一起深度学习

一起深度学习

CIFAR-10 卷积神经网络 下载数据集构建网络运行测试 下载数据集 batchsz 32cifar_train datasets.CIFAR10(data,trainTrue,transformtorchvision.transforms.Compose([torchvision.transforms.Resize((32,32)),torchvision.transforms.ToTensor()]),downloadTrue)cifar_train …
阅读更多...
最新文章

Copyright @ 2022~2023