双向循环链表(list)复习

template<class _Ty>
class ListIterator
{
public:
	template<class _Ty>friend class List;
	using NodePointer = ListNode<_Ty>*;

	ListIterator(NodePointer p) :_p(p) {}

	ListIterator(const ListIterator& rhs) :_p(rhs._p) {}

	ListIterator& operator=(const ListIterator& rhs)
	{
		if (this != &rhs)
		{
			_p = rhs->_p;
		}
		return *this;
	}

	NodePointer getListNodePointer()const
	{
		return _p;
	}

	virtual ~ListIterator()noexcept {}

	_Ty& operator*()const
	{
		return _p->data;
	}

	_Ty* operator->()const
	{
		return &(_p->data);
	}

	ListIterator& operator++()
	{
		_p = _p->_next;
		return *this;
	}

	const ListIterator operator++(int)
	{
		ListIterator tmp(*this);
		++(*this);
		return tmp;
	}

	bool operator ==(const ListIterator& rhs)const
	{
		return this->_p == rhs._p;
	}

	bool operator !=(const ListIterator& rhs)const
	{
		return !(*this == rhs);
	}

protected:
	NodePointer _p;
};



template<class _Ty>
class ListConstIterator : public ListIterator<_Ty>
{
public:
	template<class _Ty>friend class List;
	using NodePointer = ListNode<_Ty>*;

	ListConstIterator(NodePointer p): ListIterator<_Ty>(p){}

	ListConstIterator(const ListConstIterator&rhs): ListIterator<_Ty>(rhs){}

	ListConstIterator& operator =(const ListConstIterator& rhs)
	{
		if (this != &rhs)
		{
			ListIterator<_Ty>::operator= (rhs);
		}
		return *this;
	}

	~ListConstIterator()noexcept{}

	const _Ty& operator*()const
	{
		return this->_p->data;
	}

	const _Ty* operator->()const
	{
		return &(this->_p->data);
	}

	ListConstIterator& operator++()
	{
		this->_p = this->_p->_next;
		return *this;
	}

	const ListConstIterator operator++(int)
	{
		ListConstIterator tmp(*this);
		++(*this);
		return tmp;
	}

	bool operator==(const ListConstIterator& rhs) const
	{
		return this->_p == rhs._p;
	}

	bool operator!=(const ListConstIterator& rhs) const
	{
		return !(*this == rhs);
	}

};



template<class _Ty>
class ListReverseIterator : public ListIterator<_Ty>
{
public:
	template<class _Ty>friend class List;
	using NodePointer = ListNode<_Ty>*;

	ListReverseIterator(NodePointer p):ListIterator<_Ty>(p){}

	ListReverseIterator(const ListReverseIterator&rhs):ListIterator<_Ty>(rhs) {}

	~ListReverseIterator()noexcept{}

	ListReverseIterator& operator=(const ListReverseIterator& rhs)
	{
		if (this != &rhs)
		{
			ListIterator<_Ty>::operator=(rhs);
		}
		return *this;
	}

	_Ty& operator*()const
	{
		return this->_p->data;
	}

	_Ty* operator->()const
	{
		return &(this->_p->data);
	}

	ListReverseIterator& operator++()
	{
		this->_p = this->_p->_pre;
		return *this;
	}

	const ListReverseIterator operator++(int)
	{
		ListReverseIterator tmp(*this);
		++(*this);
		return tmp;
	}

	bool operator==(const ListReverseIterator& rhs)const
	{
		return this->_p == rhs._p;
	}

	bool operator!=(const ListReverseIterator& rhs)const
	{
		return !(*this == rhs);
	}


};



template<class _Ty>
class ListReverseConstIterator :public ListIterator<_Ty>
{
public:
	template<class _Ty>friend class List;
	using NodePointer = ListNode<_Ty>*;

	ListReverseConstIterator(NodePointer p):ListIterator<_Ty>(p){}

	ListReverseConstIterator(const ListReverseConstIterator&rhs):ListIterator<_Ty>(rhs){}

	ListReverseConstIterator& operator=(const ListReverseConstIterator& rhs)
	{
		if (this != &rhs)
		{
			ListIterator<_Ty>::operator=(rhs);
		}
		return *this;
	}

	ListReverseConstIterator& operator++()
	{
		this->_p = this->_p->_pre;
		return *this;
	}

	const ListReverseConstIterator operator++(int)
	{
		ListReverseConstIterator tmp(*this);
		++(*this);
		return tmp;
	}

	const _Ty& operator*()const
	{
		return this->_p->data;
	}

	const _Ty* operator->()const
	{
		return &(this->_p->data);
	}

	bool operator==(const ListReverseConstIterator& rhs)const
	{
		return this->_p == rhs._p;
	}

	bool operator!=(const ListReverseConstIterator& rhs)const
	{
		return !(*this == rhs);
	}

};



template<class _Ty>
class ListNode
{
public:
	template<class _Ty>friend class List;
	template<class _Ty>friend class ListIterator;
	template<class _Ty>friend class ListConstIterator;
	template<class _Ty>friend class ListReverseConstIterator;
	template<class _Ty>friend class ListReverseIterator;

	using   NodePointer = ListNode<_Ty>*;

	ListNode():_next(0),_pre(0),data(_Ty()){}

	ListNode(const ListNode<_Ty>&rhs):data(rhs.data),_next(rhs._next),_pre(rhs._pre){}

	ListNode& operator=(const ListNode<_Ty>& rhs)
	{
		if (this != &rhs)
		{
			data = rhs.data;
			_next = rhs._next;
			_pre = rhs._pre;
		}
		return *this;
	}

	~ListNode()noexcept{}

	bool operator ==(const ListNode<_Ty>& rhs)
	{
		return data == rhs.data && _next == rhs._next && _pre == rhs._pre;
	}

	bool operator !=(const ListNode<_Ty>& rhs)
	{
		return !(*this == rhs);
	}

protected:
	NodePointer _next;
	NodePointer _pre;
	_Ty data;
};



template<class _Ty>
class List
{
public:

	using constIterator = const ListConstIterator<_Ty>;
	using iterator = ListIterator<_Ty>;
	using reverseIterator = ListReverseIterator<_Ty>;
	using constReverseIterator = const ListReverseConstIterator<_Ty>;
	using NodePointer = ListNode<_Ty>*;

	List():_head(allocateNode()),sizes(0)
	{
		_head->_next = _head;
		_head->_pre = _head;
		construct_at(&_head->data, _Ty());
	}

	~List()noexcept
	{
		try
		{
			clear();
			destroyNode(_head);
		}
		catch (...)
		{

		}
	}

	List& operator=(const List& rhs) = delete;

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

	constIterator cbegin()const
	{
		return constIterator(_head->_next);
	}

	void push_back(const _Ty& rhs)
	{
		NodePointer lastNode = _head->_pre;
		NodePointer newNode = allocateNode();
		construct_at(&newNode->data, rhs);
		lastNode->_next = newNode;
		newNode->_pre = lastNode;
		newNode->_next = _head;
		_head->_pre = newNode;
		++sizes;
	}

	void push_front(const _Ty&rhs)
	{
		NodePointer newNode = allocateNode();
		construct_at(&newNode->data, rhs);
		NodePointer headNextNode = _head->_next;
		_head->_next = newNode;
		newNode->_pre = _head;
		newNode->_next = headNextNode;
		headNextNode->_pre = newNode;
		++sizes;
	}

	void pop_back()
	{
		erase(iterator(_head->_pre));
	}

	void pop_front()
	{
		erase(iterator(_head->_next));
	}

	void clear()
	{
		if (sizes == 0)
		{
			
		}
		else
		{
			NodePointer tmp = 0;
			NodePointer cur = _head->_next;
			while (cur != _head)
			{
				tmp = cur;
				cur = cur->_next;
				destroyNode(tmp);
			}
		}
		_head->_next = _head;
		_head->_pre = _head;
		sizes = 0;
	}

	const size_t size()const
	{
		return sizes;
	}

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

	constIterator cend()const
	{
		return constIterator(_head);
	}
	
	iterator find(const _Ty& val)const
	{
		NodePointer tmp = _head->_next;
		while (tmp != _head)
		{
			if (tmp->data == val)
			{
				return iterator(tmp);
			}
			tmp = tmp->_next;
		}
		return iterator(_head);
	}

	void erase(const iterator& pos)
	{
		if (pos._p == _head)
		{
			return;
		}
		NodePointer shouldDeletePrev = pos._p->_pre;
		NodePointer shouldDeleteNext = pos._p->_next;
		shouldDeletePrev->_next = shouldDeleteNext;
		shouldDeleteNext->_pre = shouldDeletePrev;
		destroyNode(pos._p);
		--sizes;
	}

	void erase(const _Ty& val)
	{
		iterator shouldDelete = find(val);
		if (shouldDelete._p != _head)
		{
			erase(shouldDelete);
		}
	}

	reverseIterator rbegin()const
	{
		return reverseIterator(_head->_pre);
	}

	reverseIterator rend()const
	{
		return reverseIterator(_head);
	}

	constReverseIterator crbegin()const
	{
		return constReverseIterator(_head->_pre);
	}

	constReverseIterator crend()const
	{
		return constReverseIterator(_head);
	}

protected:

	NodePointer allocateNode()
	{
		return  static_cast<NodePointer>(operator new(sizeof(ListNode<_Ty>)));
	}

	void destroyNode(NodePointer p)
	{
		if (p)
		{
			destroy_at(&p->data);
			operator delete(p);
		}
	}

private:
	NodePointer _head;
	size_t sizes;
};