[C++]list的迭代器模拟实现

        下面是简单的实现list的迭代器功能，底层是带头双向循环的链表，主要关注的是list的迭代器问题。没有涉及内存池等复杂算法来提高效率。

一、list的概述

（一）、抽象数据类型的定义

（二）、成员变量 

//链表的节点
template<class T>
struct ListNode
{
	T _val;
	ListNode* _pPrev;
	ListNode* _pNext;
	//生成一个链表结点并用x进行初始化
	ListNode(const T& x = T())
	{
		_val = x;
		_pPrev = this;
		_pNext = this;//该结点一开始前后指针都指向自身
	}
};


template<class T>
class list
{
public:
	typedef ListNode Node;
private:
	Node* _pHead;//指向哨兵位
};

二、具体实现 

        由于带头双向循环链表增删改操作比较简单，代码不进行具体讲解，只重点讲一下list的迭代器的具体实现。

（一）、list的迭代器

        list不像vector一样，vector存储的数据在内存中是连续的，可以使用数组的指针加减就可以完成vector的遍历，而list的数据在逻辑结构上是有序的，但是在其内存的存储上一般都是不连续的，无法使用指针的加减来对链表进行遍历，不能够使用原生数组的指针来作为list的迭代器，这个时候我们就需要使用类来帮助我们实现list的迭代器的功能，让其行为符合我们迭代器的需求。

1、正向迭代器

        在正向迭代器中，对迭代器进行++的操作，就是让迭代器指向当前结点的下一个结点，对迭代器进行--的操作，就是让迭代器指向当前结点的上一个结点，对迭代器进行解引用，得到该结点存储的数据。要满足这样的行为，需要自定义类型来实现。

具体代码如下：

//声明定义正向迭代器
//Ref和Ptr用于辨别是普通迭代器还是const迭代器
template<class T,class Ref,class Ptr>
struct ListIterator
{
public:
	typedef ListIterator<T,Ref,Ptr> Self;
	typedef ListNode<T> Node;
	Node* _pNode;//迭代器指向当前结点的地址
	//默认构造
	ListIterator(Node* pNode = nullptr) :_pNode(pNode){; }

	//重载
	//前置++
	Self& operator++()
	{
		_pNode = _pNode->_pNext;//迭代器指向当前结点的下一个结点
		return *this;
	}
	//后置++
	Self operator++(int)
	{
		Self temp(_pNode);
		_pNode = _pNode->_pNext;//迭代器指向当前结点的下一个结点
		return temp;
	}

	//前置--
	Self& operator--()
	{
		_pNode = _pNode->_pPrev;
		return *this;
	}
	//后置--
	Self operator--(int)
	{
		Self temp(_pNode);
		_pNode = _pNode->_pNext;
		return temp;
	}

	//重载解引用
	Ref operator*()
	{
		return _pNode->_val;
	}
	//重载->操作符
	Ptr operator->()
	{
		return &(_pNode->_val);
	}

	//迭代器的比较方法(用来判断迭代停止)
	bool operator==(Self it) 
	{
		return _pNode == it._pNode;
	}
	bool operator!=(Self it)
	{
		return _pNode != it._pNode;
	}
};

2、反向迭代器

        在反向迭代器中，对迭代器进行++的操作，就是让迭代器指向当前结点上一个结点，对迭代器进行--的操作，就是让迭代器指向当前结点下一个结点，对迭代器进行解引用，得到该结点存储的数据。

具体代码如下： 

//适配反向迭代器
template<class T, class Ref, class Ptr>
struct ListReverseIterator
{
public:
	typedef ListReverseIterator<T, Ref, Ptr> Self;
	typedef ListNode<T> Node;
	typedef ListNode<T>* PNode;
	PNode _pNode;

	ListReverseIterator(PNode pNode = nullptr) :_pNode(pNode){; }

	//重载++
	Self& operator++()
	{
		_pNode = _pNode->_pPrev;
		return *this;
	}
	Self operator++(int)
	{
		Self tem(_pNode);
		_pNode = _pNode->_pPrev;
		return tem;
	}

	//重载--
	Self& operator--()
	{
		_pNode = _pNode->_pNext;
		return *this;
	}
	Self operator--(int)
	{
		Self tem(_pNode);
		_pNode = _pNode->_pNext;
		return tem;
	}

	//重载解引用
	Ref operator*() 
	{
		return _pNode->value;
	}
	//重载->
	Ptr operator->() 
	{
		return &(_pNode->value);
	}

	bool operator==(const Self& it) 
	{
		return _pNode == it._pNode;
	}
	bool operator!=(const Self& it) 
	{
		return _pNode != it._pNode;
	}
};

        注意：正向迭代器和反向迭代器之间由于类型不同，是不能直接进行比较的。

        在定义迭代器模板类时，指明其引用类型和指针类型，可以避免写重复的代码段。

（二）、list的具体实现

//带头双向循环list容器
template<class T>
class list
{
public:
	typedef ListNode<T> Node;
	typedef ListNode<T>* PNode;

	//迭代器
	typedef ListIterator<T, T&, T*> iterator;
	typedef ListIterator<T, const T&, const T*> const_iterator;
	//反向迭代器
	typedef ListReverseIterator<T, T&, T*> reverse_iterator;
	typedef ListReverseIterator<T, const T&, const T*> const_reverse_iterator;

	//初始化
	list()
	{
		_pHead = new Node;
		_pHead->_pNext = _pHead;
		_pHead->_pPrev = _pHead;
	}

	list(int n, const T& value = T()) :list()
	{
		for (int i = 0; i < n; i++)
		{
			push_back(value);
		}
	}
	template <class Iterator>
	list(Iterator first, Iterator last) :list()
	{
		while (first != last)
		{
			push_back(*first);
			first++;
		}
	}
	//参数初始化列表初始化
	list(std::initializer_list<T> ini_list) :list()
	{
		for (auto& e : ini_list)
		{
			push_back(e);
		}
	}
	//拷贝构造
	list(const list<T>& l) :list()
	{
		
		for (auto& e : l)
		{
			push_back(e);
		}
	}
	//赋值构造
	list<T>& operator=(const list<T>& l)
	{
		list<T> tem(l);
		swap(tem);
		return *this;
	}

	//析构函数
	~list()
	{
		PNode pcur = _pHead->_pNext;
		PNode ptem;//记录销毁节点的下一个节点
		//std::cout << "销毁:";
		while (pcur != _pHead)
		{
			ptem = pcur->_pNext;
			//cout << (pcur->value) << "->";
			delete pcur;
			pcur = ptem;
		}
		//std::cout << "nullptr" << std::endl;
		_pHead = nullptr;
	}

	//迭代器
	iterator begin()
	{
		return iterator(_pHead->_pNext);
	}
	iterator end()
	{
		return iterator(_pHead);
	}
	const_iterator begin() const
	{
		return const_iterator(_pHead->_pNext);
	}
	const_iterator end() const
	{
		return const_iterator(_pHead);
	}

	//反向迭代器
	reverse_iterator rbegin()
	{
		return reverse_iterator(_pHead->_pPrev);
	}
	reverse_iterator rend()
	{
		return reverse_iterator(_pHead);
	}
	const_reverse_iterator rbegin() const
	{
		return const_reverse_iterator(_pHead->_pPrev);
	}
	const_reverse_iterator rend() const
	{
		return const_reverse_iterator(_pHead);
	}


	// List Capacity
	size_t size()const
	{
		PNode pcur = _pHead->_pNext;
		size_t n = 0;
		while (pcur != _pHead)
		{
			n++;
			pcur = pcur->_pNext;
		}
		return n;
	}
	bool empty()const
	{
		return _pHead == _pHead->_pNext;
	}

	// List Access
	T& front()
	{
		if (!empty())
			return _pHead->_pNext->value;
		else
			return _pHead->value;
	}
	const T& front()const
	{
		if (!empty())
			return _pHead->_pNext->value;
		else
			return _pHead->value;
	}
	T& back()
	{
		if (!empty())
			return _pHead->_pPrev->value;
		else
			return _pHead->value;
	}
	const T& back()const
	{
		if (!empty())
			return _pHead->_pPrev->value;
	}
	//Modify
	//尾插
	void push_back(const T& x)
	{
		//找到尾结点
		PNode pTail = _pHead->_pPrev;
		PNode newNode = new Node(x);
		newNode->_pNext = _pHead;
		newNode->_pPrev = pTail;
		pTail->_pNext = newNode;
		_pHead->_pPrev = newNode;
	}

	//尾删
	void pop_back()
	{
		if (empty())
			return;

		PNode tail = _pHead->_pPrev;
		tail->_pPrev->_pNext = tail->_pNext;
		tail->_pNext->_pPrev = tail->_pPrev;
		delete tail;
	}
	//头插
	void push_fornt(const T& x)
	{
		PNode newNode = new Node(x);
		newNode->_pPrev = _pHead;
		newNode->_pNext = _pHead->_pNext;
		_pHead->_pNext->_pPrev = newNode;
		_pHead->_pNext = newNode;
	}
	//头删
	void pop_fornt()
	{
		if (empty())
			return;


		PNode pDel = _pHead->_pNext;
		pDel->_pPrev->_pNext = pDel->_pNext;
		pDel->_pNext->_pPrev = pDel->_pPrev;
		delete pDel;
	}
	//指定位置插入
	//不存在迭代器失效问题
	iterator insert(iterator pos, const T& x)
	{
		PNode newNode = new Node(x);
		newNode->_pNext = pos._pNode;
		newNode->_pPrev = pos._pNode->_pPrev;
		pos._pNode->_pPrev->_pNext = newNode;
		pos._pNode->_pPrev = newNode;
		return iterator(newNode);
	}
	//指定位置删除
	//返回删除位置的下一个节点的迭代器，因为会存在迭代器失效问题
	iterator erase(iterator pos)
	{
		iterator itNext(pos._pNode->_pNext);
		//连接前后节点
		pos._pNode->_pPrev->_pNext = pos._pNode->_pNext;
		pos._pNode->_pNext->_pPrev = pos._pNode->_pPrev;
		delete pos._pNode;
		return itNext;
	}
	//交换两个链表内容的操作
	void swap(list<T>& v1)
	{
		std::swap(_pHead, v1._pHead);
	}
private:
	//头节点指针
	PNode _pHead;
	//size_t _length;
};

        注意：在指定位置插入一个结点不会存在迭代器失效问题，而删除指定位置的结点时，就会存在迭代器失效的问题，此时迭代器指向不存在的结点。因此，在删除指定位置的结点时，应将其下一个结点的迭代器作为返回值返回，更新迭代器的值，防止迭代器失效问题。