C++中链表的底层迭代器实现

2024-07-21 1085阅读

大家都知道在C++的学习中迭代器是必不可少的,今天我们学习的是C++中的链表的底层迭代器的实现,首先我们应该先知道链表的底层迭代器和顺序表的底层迭代器在实现上有什么区别,为什么顺序表的底层迭代器更加容易实现,而链表的底层迭代器不容易实现,接下来小编再来告诉大家如何来实现链表的底层迭代器,学完今天这篇我相信大家对C++中的迭代器一定会有一个更加深刻的认识!大家先看今天学习的内容:C++中链表的底层迭代器实现

一、顺序表和链表的底层迭代器的区别

为了知道它们两个的区别,先得告诉大家顺序表的底层迭代器是如何实现的,首先大家先得明白顺序表私有成员都有什么,好方便大家来理解它们的底层迭代器是如何实现的,请看下图顺序表的私有成员变量:C++中链表的底层迭代器实现

	private:
		iterator _start;
		iterator _finish;
		iterator _end_of_storage;

如图就是顺序表的私有成员变量 第一个 _start 是记录顺序表的起始位置的指针类型是 T*

_finish记录的是顺序表内末尾元素的下一个位置的指针类型是T*,_end_of_storage记录的是顺序表的目前的所有容量的下一个位置类型也是T*。

在明白了顺序表的私有成员变量的意义,并且顺序表的储存是连续的空间有点类似于数组的数据储存,所以大家也应该明白了顺序表的底层迭代器是如何实现的了吧,如果不懂请看下图操作及注释,如下图:C++中链表的底层迭代器实现

但是由于链表的物理结构不是连续的,所以想顺序表一样的底层迭代器实现方法是行不通的,这也是为什么在底层实现链表的迭代器中,不能通过给迭代器++来做到迭代器指向下一个元素的地址,因为链表的数据在空间中分布式随意的。那该如何去设计链表的底层迭代器呢,请大家继续往下看。

二、链表的底层迭代器该如何实现

首先先请大家看一下链表中的数据是如何分布的,如下图:C++中链表的底层迭代器实现

如图,可见链表中的数据是随意分布的,但是我们仍然可以用前一个节点找到下一个节点,但为什么这样子不行,不算迭代器呢,因为在C++中迭代器的定义就是通过 ++ 来找到下一个元素,接通过 * 号来拿到他这个位置的数据,这才是迭代器的规定,如下段代码的遍历效果:

C++中链表的底层迭代器实现

如上链表的分布图,虽然我们可以拿到下一个节点的位置和这个节点的数据,但我们不是通过 ++ 和 * 来实现的,所以通过这样的方式做出的迭代器是不对的。那我们该如何实现呢,小编新学了一个方法,就是把迭代器底层封装成一个类,让它内部进项运算符重载来达到 ++ 实现像迭代器一样遍历的过程,* 实现像迭代器一样拿出数据的过程,那么该如何实现呢,请大家继续往下看。

三、链表底层迭代器的实现

上面说到把迭代器封装成一个类,然后用运算符重载来达到 ++ 和 * 的过程,把它彻底改变为一个正规的迭代器,现在大家就和我一起实现这个迭代器的类:

1、首先大家要明白链表(带头双向循环链表)的结构,如下代码:

template
// 这里用结构体是因为ListNode中的每个成员都应该可以访问 没有私有成员
// 也可以使用友元来解决这个问题
struct ListNode
{
	T _data;
	ListNode* _next;
	ListNode* _prev;
	ListNode(const T& data = T())
		:_next(nullptr)
		,_prev(nullptr)
		, _data(data)
	{}
};
	template
	class list
	{
	public:
		typedef ListNode Node;
	private:
		Node* _head;
	};

如上图代码,在这里我们已经知道下一步需要把链表独特的遍历方式(用前一个指针找到后一个指针)用运算符重载的改为 ++  和 *  来实现遍历和拿到数据,保证它和迭代器的实现和用法一模一样。那该如何实现这个类呢。

2、实现迭代器的类

我们需要定义一个迭代器的类,因为有普通迭代器和不可修改的迭代器,它们两个的函数大多数相同,为了减少代码量,我们加入两个模板参数来帮我们减轻代码量

	// 这里加入 Ref 和 Ptr 是为了区分普通迭代器和const迭代器的区别
	// 本来要写两份迭代器,一份可修改,一份不可修改 现在直接交给编译器去做
	template
	struct ListIterator
	{
		typedef ListNode Node;
		typedef ListIterator Self;
		// 链表的迭代器应该是 Node* 类型的指针
		Node* _node;
		ListIterator(Node* node)
			:_node(node)
		{}
		// 前置++
		Self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		//前置--
		Self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}
		Self operator++(int)
		{
			Self tem(*this);
			_node = _node->_next;
			return tem;
		}
		Self operator--(int)
		{
			Self tem(*this);
			_node = _node->_prev;
			return tem;
		}
		Ptr operator->()
		{
			return &(_node->_data);
		}
		Ref operator*()
		{
			return _node->_data;
		}
		bool operator!=(const Self& it)
		{
			return _node != it._node;
		}
		bool operator==(const Self& it)
		{
			return _node == it._node;
		}
	};

以上就是今天的所有内容,希望大家会喜欢!!!

VPS购买请点击我

免责声明:我们致力于保护作者版权,注重分享,被刊用文章因无法核实真实出处,未能及时与作者取得联系,或有版权异议的,请联系管理员,我们会立即处理! 部分文章是来自自研大数据AI进行生成,内容摘自(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供学习参考,不准确地方联系删除处理! 图片声明:本站部分配图来自人工智能系统AI生成,觅知网授权图片,PxHere摄影无版权图库和百度,360,搜狗等多加搜索引擎自动关键词搜索配图,如有侵权的图片,请第一时间联系我们,邮箱:ciyunidc@ciyunshuju.com。本站只作为美观性配图使用,无任何非法侵犯第三方意图,一切解释权归图片著作权方,本站不承担任何责任。如有恶意碰瓷者,必当奉陪到底严惩不贷!

目录[+]