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

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

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

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

	private:
		iterator _start;
		iterator _finish;
		iterator _end_of_storage;

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

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

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

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

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

首先先请大家看一下链表中的数据是如何分布的，如下图：

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

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

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

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

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

template<class T>
// 这里用结构体是因为ListNode中的每个成员都应该可以访问 没有私有成员
// 也可以使用友元来解决这个问题
struct ListNode
{
	T _data;
	ListNode* _next;
	ListNode* _prev;

	ListNode(const T& data = T())
		:_next(nullptr)
		,_prev(nullptr)
		, _data(data)
	{}
};

	template<class T>
	class list
	{
	public:
		typedef ListNode<T> Node;
	private:
		Node* _head;
	};

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

2、实现迭代器的类

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

	// 这里加入 Ref 和 Ptr 是为了区分普通迭代器和const迭代器的区别
	// 本来要写两份迭代器，一份可修改，一份不可修改 现在直接交给编译器去做
	template<class T , class Ref, class Ptr>
	struct ListIterator
	{
		typedef ListNode<T> Node;
		typedef ListIterator<T, Ref, Ptr> 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;
		}
	};

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