9.【CPP】List （迭代器的模拟实现||list迭代器失效||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迭代器的实现

普通迭代器

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

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

	template<class T>
	struct __list_iterator
	{
		typedef list_node<T> node;
		typedef __list_iterator<T> iterator;

		node* _node;

		__list_iterator(node* n)
			:_node(n)
		{}

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

		iterator& operator++()
		{
			_node = _node->_next;
			return *this;
		}

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

		iterator operator--(int)
		{
			iterator tmp(*this);
			_node = _node->_prev;
			return tmp;
		}
		bool operator!=(const iterator& it )const
		{
			return _node != it._node;
		}

		bool operator==(const iterator& it)const
		{
			return _node == it._node;
		}
	};

const迭代器

看下面这段代码能否编译通过
在这里插入图片描述
如果传一个const对象，那么就需要实现对应的const迭代器，否则会出现权限的放大，是会报错的。
在这里插入图片描述
如果声明成这样呢？

typedef const iterator const_iterator

这是错误的。这就相当于iterator本身是const，那么就不能执行++操作，迭代器不能动还叫啥迭代器。所以我们处理的方法是返回一个const迭代器，重新实现一个const_iterator类。基本都复用普通迭代器的代码，就解引用时返回const T&。

template<class T>
	struct __list_const_iterator
	{
		typedef list_node<T> node;
		typedef __list_const_iterator<T> const_iterator;

		node* _node;

		__list_const_iterator(node* n)
			:_node(n)
		{}

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

		const_iterator& operator++()
		{
			_node = _node->_next;
			return *this;
		}

		const_iterator operator++(int)
		{
			const_iterator tmp(*this);
			_node = _node->_next;
			return tmp;
		}

		const_iterator& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

		const_iterator operator--(int)
		{
			const_iterator tmp(*this);
			_node = _node->_prev;
			return tmp;
		}
		bool operator!=(const const_iterator& it)const
		{
			return _node != it._node;
		}

		bool operator==(const const_iterator& it)const
		{
			return _node == it._node;
		}
	};

这样我们代码就不报错，顺利打印出了数据

在这里插入图片描述

成员函数屁股后的const

	const iterator begin()const//后面的const修饰的是this指针指向的内容（*this），即_head本身不能被改变，指向对象的内容可变
		{
			return const iterator(_head->_next);
		}

改进代码

const迭代器还要去实现一个几乎相同的类，就改了个名字叫const_iterator，除了解引用返回T的引用时不同（const T&），那么我们在实现iterator迭代器类的时候加一个模版参数Ref表示引用，typedef不同的迭代器实例化不同的Ref即可解决。
在这里插入图片描述
在这里插入图片描述
不得不说想出这种写法的人真的是个天才

list反向迭代器位置

在这里插入图片描述

list迭代器失效

前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的**，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响**

list模拟实现代码

注意反向迭代器的实现是复用了正向迭代器

#include<iostream>
#include<cassert>

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

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

	template<class T,class Ref,class Ptr>
	struct __list_iterator
	{
		typedef list_node<T> node;
		typedef __list_iterator<T,Ref,Ptr> iterator;

		node* _node;

		__list_iterator(node* n)
			:_node(n)
		{}

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

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

		iterator& operator++()
		{
			_node = _node->_next;
			return *this;
		}

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

		iterator operator--(int)
		{
			iterator tmp(*this);
			_node = _node->_prev;
			return tmp;
		}
		bool operator!=(const iterator& it )const
		{
			return _node != it._node;
		}

		bool operator==(const iterator& it)const
		{
			return _node == it._node;
		}
	};

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

		ReverseIterator(Iterator it)
			:_cur(it){}

		Self& operator++()
		{
			--_cur;
			return *this;
		}

		Self& operator++(int)
		{
			Iterator tmp(_cur);
			--_cur;
			return tmp;
		}

		Self& operator--()
		{
			++_cur;
			return *this;
		}

		Self& operator--(int)
		{
			Iterator tmp(_cur);
			++_cur;
			return tmp;
		}

		 Ref operator*()
		{
			Iterator tmp = _cur;
			--tmp;
			return *tmp;
		}

		bool operator!=(const Self& s)
		{
			return _cur != s._cur;
		}
	};

	template<class T>
	class list
	{
	public:
		typedef __list_iterator<T,T&,T*> iterator;
		typedef __list_iterator<T,const T&,const T*> const_iterator;
		typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
		typedef ReverseIterator<iterator, const T&, const T*> const_reverse_iterator;

		typedef list_node<T> node;

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

		list()
		{
			empty_init();
		}

		template<class Iterator>
		list(Iterator first, Iterator last)
		{
			empty_init();
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

		//lt2(lt1)
		/*list(const list<T>& lt)
		{
			empty_init();
			for (auto e : lt)
			{
				push_back(e);
			}
		}*/
		//现代写法
		void swap(list<T>& lt)
		{
			std::swap(_head, lt._head);
		}

		list(const list<T>& lt)
		{
			empty_init();

			list<T> tmp(lt.begin(), lt.end());
			swap(tmp);
		}

		list<T>& operator=(list<T> lt)
		{
			swap(lt);
			return *this;
		}


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

		const_iterator begin()const//后面的const修饰的是this指针指向的内容（*this），即_head本身不能被改变，指向对象的内容可变
		{
			return const_iterator(_head->_next);
		}

		iterator end()
		{
			return iterator(_head);
		}

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

		reverse_iterator rbegin()
		{
			return reverse_iterator(end());
		}

		reverse_iterator rend()
		{
			return reverse_iterator(begin());
		}


		void push_back(const T& val)
		{
			node* tail = _head->_prev;
			node* newnode = new node(val);
			tail->_next = newnode;
			newnode->_prev = tail;
			newnode->_next = _head;
			_head->_prev = newnode;
		}

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

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

		iterator erase(iterator pos)
		{
			assert(pos != end());
			node* prev = pos._node->_prev;
			node* next = pos._node->_next;

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

			return iterator(next);
		}

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

		void clear()//不清理头节点
		{
			iterator it = begin();
			while (it != end())
			{
				it=erase(it);//或者erase(it++);返回的是it++前的拷贝
				it++;
			}
		}

		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}
	private:
		node* _head;
	};

	struct AA
	{
		int _a1;
		int _a2;

		AA(int a1=0,int a2=0)
			:_a1(a1),_a2(a2)
		{}
	};
	void test_list2()
	{
		list<AA> lt;
		lt.push_back(AA(1, 2));
		lt.push_back(AA(1, 3));
		lt.push_back(AA(1, 4));

		list<AA>::iterator it = lt.begin();
		while (it != lt.end())
		{
			std::cout << it->_a1 << ":" << it->_a2 << std::endl;
			it++;
		}
		lt.clear();
	}


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

	}

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

	}

	void test_list3()
	{
		list<int> lt1;
		lt1.push_back(1);
		lt1.push_back(2);
		lt1.push_back(3);
		list<int> lt2(lt1);
		for (auto e : lt2)
		{
			std::cout << e << std::endl;
		}
	}

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

		auto rit =lt.rbegin();
		while (rit != lt.rend())
		{
			std::cout << *rit << " ";
			++rit;
		}
	}
}

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

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

相关文章

文件压缩炸弹，想到有点后怕

文件压缩炸弹，想到有点后怕

今天了解到一个概念&#xff0c;压缩炸弹。 参考&#xff1a; https://juejin.cn/post/7289667869557178404 https://www.zhihu.com/zvideo/1329374649210302464 什么是压缩炸弹 压缩炸弹&#xff08;也称为压缩文件炸弹、炸弹文件&#xff09;是一种特殊的文件&#xff0c;它…
阅读更多...
年假作业10

年假作业10

一、选择题 BBDBACCCAD 二、填空题 1,4,13,40 3715 358 5 2 6 1 5 4 8 2 0 2 三、编程题 1、 #include <iostream> #include<array> #include <limits> using namespace std; int main() {array<int,10> score;array<int,10>::iterat…
阅读更多...
黑马程序员——移动Web——day01

黑马程序员——移动Web——day01

目录&#xff1a; 平面转换 简介平移定位居中案例-双开门旋转转换原点案例-时钟多重转换缩放案例-播放特效倾斜渐变 线性渐变案例-产品展示径向渐变综合案例 导航-频道渐变按钮轮播图猜你喜欢 1.平面转换 简介 作用&#xff1a;为元素添加动态效果&#xff0c;一般与过渡配…
阅读更多...
鸿蒙开发系列教程（十七）--路由Router

鸿蒙开发系列教程（十七）--路由Router

页面路由指在应用程序中实现不同页面之间的跳转和数据传递 1、页面跳转 跳转模式 router.pushUrl()&#xff1a;目标页不会替换当前页&#xff0c;而是压入页面栈。这样可以保留当前页的状态&#xff0c;并且可以通过返回键或者调用[router.back()]方法返回到当前页。router…
阅读更多...
MATLAB|【免费】高比例可再生能源电力系统的调峰成本量化与分摊模型

MATLAB|【免费】高比例可再生能源电力系统的调峰成本量化与分摊模型

目录 主要内容 部分代码 结果一览 下载链接 主要内容 程序复现文献《高比例可再生能源电力系统的调峰成本量化与分摊模型》&#xff0c;从净负荷波动的角度出发&#xff0c;建立了调峰成本的量化与分摊模型&#xff0c;构造了无调峰需求的替代场景&#xff0c;将…
阅读更多...
Vulnhub靶机：DC4

Vulnhub靶机：DC4

一、介绍 运行环境&#xff1a;Virtualbox 攻击机&#xff1a;kali&#xff08;10.0.2.15&#xff09; 靶机&#xff1a;DC4&#xff08;10.0.2.57&#xff09; 目标&#xff1a;获取靶机root权限和flag 靶机下载地址&#xff1a;https://www.vulnhub.com/entry/dc-4,313/…
阅读更多...
勒索DASH币CrySiS最新变种的同源分析

勒索DASH币CrySiS最新变种的同源分析

前言 CrySiS勒索病毒&#xff0c;又称为Dharma勒索病毒&#xff0c;首次出现于2016年&#xff0c;2017年5月此勒索病毒万能密钥被公布之后&#xff0c;导致此勒索病毒曾消失过一段时间&#xff0c;不过随后该勒索病毒就开发了它的最新的一款变种样本&#xff0c;并于2018年开始…
阅读更多...
Linux中signal/kill/raise/abort函数（信号函数）

Linux中signal/kill/raise/abort函数（信号函数）

signal函数&#xff1a; 函数作用&#xff1a;注册信号捕捉函数 函数原型&#xff1a; typedef void (*sighandler_t)(int); sighandler_t signal(int signum, sighandler_t handler); 函数参数&#xff1a; signum:信号编号handler:信号处理函数 测试&#xff1a;给没有读…
阅读更多...
669. 修剪二叉搜索树

669. 修剪二叉搜索树

给你二叉搜索树的根节点 root &#xff0c;同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树&#xff0c;使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即&#xff0c;如果没有被移除&#xff0c;原有的父代子代关系都应当保留)。…
阅读更多...
【小记】MacOS Install golang

【小记】MacOS Install golang

问题 - command not found: go ➜ brew install golang ➜ go version go version go1.21.7 darwin/arm64写在最后&#xff1a;若本文章对您有帮助&#xff0c;请点个赞啦 ٩(๑•̀ω•́๑)۶
阅读更多...
【Linux】基础命令 第二篇

【Linux】基础命令 第二篇

目录 echo 输出重定向:(本质都是写入) 输入重定向cat more 指令 && less指令 head && tail && 管道初步使用 grep&#xff1a;行文本过滤工具&#xff08;文本按行搜索&#xff09; date&#xff1a;获取时间 date 命令用于 显示 或 设置系统的…
阅读更多...
政安晨：在Jupyter中【示例演绎】Matplotlib的官方指南（四）{Artist tutorial}·{Python语言}

政安晨：在Jupyter中【示例演绎】Matplotlib的官方指南（四）{Artist tutorial}·{Python语言}

第一次看到我的演绎文章的小伙伴&#xff0c;如果需要&#xff0c;可以先看一下我这篇文章的前三篇&#xff0c;包括准备环境等等&#xff1a; 政安晨&#xff1a;在Jupyter中【示例演绎】Matplotlib的官方指南&#xff08;一&#xff09;{Pyplot tutorial}https://blog.csdn.…
阅读更多...
c++Qt网络操作

c++Qt网络操作

1、基础概念 1.1 TCP/UDP TCP 是一种面向连接的传输层协议&#xff0c;它能提供高可靠性通信(即数据无误、数据无丢失、 数据无失序、数据无重复到达的通信) 适用情况&#xff1a; 1.SN/QQ等即时通讯软件的用户登录账户管理相关的功能通常采用TCP协议 2、适合于对传输质量要求较…
阅读更多...
【HTML】情人节给npy一颗炫酷的爱心

【HTML】情人节给npy一颗炫酷的爱心

闲谈 兄弟们&#xff0c;这不情人节快要到了&#xff0c;我该送女朋友什么&#x1f381;呢&#xff1f;哦&#xff0c;对了&#xff0c;差点忘了&#xff0c;我好像没有女朋友。不过这不影响我们要过这个节日&#xff0c;我们可以学习技术。举个简单的&#x1f330;&#xff1…
阅读更多...
寒假作业2024.2.14

寒假作业2024.2.14

1.请编程实现二维数组的杨辉三角 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #include <unistd.h> int main(int argc, const char *argv[]) {int n;printf("please enter n:");scanf("%d&…
阅读更多...
数据库基本操作2

数据库基本操作2

一.DML&#xff08;Data Manipulation Language&#xff09; 用来对数据库中表的数据记录进行更新 关键字&#xff1a;增删改 插入insert 删除delete 更新update 1.数据插入 insert into 表&#xff08;列名1&#xff0c;列名2&#xff0c;列名3……&#xff09;values&a…
阅读更多...
【STM32 CubeMX】STM32中断体系结构

【STM32 CubeMX】STM32中断体系结构

文章目录 前言一、中断体系的比喻二、中断的内部结构2.1 EXTI触发方式 2.2 NVIC2.3 cpu与中断2.4 外部中断控制器框图上升沿触发选择寄存器屏蔽/使能寄存器等待处理寄存器 2.5 中断优先级 总结 前言 一、中断体系的比喻 STM32中断体系如下图所示&#xff1a; 一座大型建筑物…
阅读更多...
VueCLI核心知识1：ref属性、props配置、mixin混入

VueCLI核心知识1：ref属性、props配置、mixin混入

1 ref 属性 ref属性类似于js原生获取DOM元素 <template><div><h1 v-text"msg" ref"title"></h1><button click"showDom">点我输出上方的Dom元素</button><School ref"sch"></School>…
阅读更多...
AutoGen实战应用(三)：多代理协作的数据可视化

AutoGen实战应用(三)：多代理协作的数据可视化

之前我完成了关于AutoGen的两篇博客&#xff0c;还没有读过这两篇博客的朋友可以先阅读以下&#xff0c;这样有助于对AutoGen的初步了解&#xff1a; AutoGen实战应用(一)&#xff1a;代码生成、执行和调试_autogen 支持的model-CSDN博客 AutoGen实战应用(二)&#xff1a;多代…
阅读更多...
详解结构体内存对齐及结构体如何实现位段~

详解结构体内存对齐及结构体如何实现位段~

目录 ​编辑 一&#xff1a;结构体内存对齐 1.1对齐规则 1.2.为什么存在内存对齐 1.3修改默认对齐数 二.结构体实现位段 2.1什么是位段 2.2位段的内存分配 2.3位段的跨平台问题 2.4位段的应用 2.5位段使用的注意事项 三.完结散花 悟已往之不谏&#xff0c;知来者犹可…
阅读更多...
最新文章

Copyright @ 2022~2023