反復器標準容器List

反復器による双方向チェーンテーブルの実現

//      List
#include
using namespace std;
#pragma once
template
struct ListNode
{
	ListNode(const T& data = T())
	: _pPre(0)
	, _pNext(0)
	, _data(data)
	{}

	ListNode* _pPre;
	ListNode* _pNext;
	T _data;
};

template
class ListIterator
{
	typedef ListIterator Self;
public:
	ListIterator()
		: _pCur(0)
	{}

	ListIterator(ListNode* pCur)
		: _pCur(pCur)
	{}

	ListIterator(const Self& s)
		: _pCur(s._pCur)
	{}

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

	Ptr operator->()
	{
		return &(operator*());
		//return &(_pCur->_data); 
	}

	Self& operator++()
	{
		_pCur = _pCur->_pNext;
		return *this;
	}

	Self operator++(int)
	{
		Self temp(*this);
		_pCur = _pCur->_pNext;
		return temp;
	}

	Self& operator--()
	{
		_pCur = _pCur->_pPre;
		return*this;
	}

	Self operator--(int)
	{
		Self temp(*this);
		_pCur = _pCur->_pPre;
		return temp;
	}

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

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

	ListNode* _pCur;
};

template
class List
{
public:
	typedef ListIterator Iterator;
	typedef ListNode Node;
public:
	List()
		: _pHead(new Node)
	{
		_pHead->_pNext = _pHead;
		_pHead->_pPre = _pHead;
	}

	// 1 2 3 4 5 
	List(const T* array, size_t size)
		:_pHead(new ListNode)
	{
		_pHead->_pNext = _pHead;
		_pHead->_pPre = _pHead;
		for (size_t i = 0; i < size; i++)
		{
			PushBack(array[i]);
		}
	}
	List(const List& l)
	{
		size_t size = l.Size();
		_pHead = new ListNode;
		_pHead->_pNext = _pHead;
		_pHead->_pPre = _pHead;
		ListNode *p = (l._pHead)->_pNext;
		for (size_t i = 0; i < size; i++)
		{
			PushBack(p->_data);
			p = p->_pNext;
		}
	}
	List& operator=(const List& l)
	{
		size_t size = l.Size();
		if (this != &l)
		{
			ListNode *tmp = new ListNode;
			tmp._pNext = tmp;
			tmp._pPre = tmp;
			ListNode *p = l._pHead->_pNext;
			for (size_t i = 0; i < size; i++)
			{
				tmp.PushBack(p->_data);
				p = p->_pNext;
			}
			delete[] _pHead;
			_pHead = tmp;
		}
	    return *this;
	}
	~List()
	{
		Clear();
		delete[] _pHead;
		_pHead = NULL;
	}

		///////////////////////////////////////////////////// 
	Iterator Begin()
	{
			return Iterator(_pHead->_pNext);
	}

	Iterator End()
	{
		return Iterator(_pHead);
	}
	/////////////////////Modify////////////////////////// 
	void PushBack(const T& data)
	{
		ListNode *pNewNode = new ListNode(data);
		if (Empty())  //   
		{
			_pHead->_pNext = pNewNode;
			pNewNode->_pNext = _pHead;
			pNewNode->_pPre = _pHead;
			_pHead->_pPre = pNewNode;
		}
		else
		{
			ListNode *pTail = _pHead->_pPre;
			pTail->_pNext = pNewNode;
			pNewNode->_pNext = _pHead;
			pNewNode->_pPre = pTail;
			_pHead->_pPre = pNewNode;
		}
	}

	void PopBack()
	{
		if (Empty())
		{
			return;
		}
		else
		{
			ListNode *pTail = _pHead->_pPre->_pPre;
			delete pTail->_pNext;
			pTail->_pNext = _pHead;
			_pHead->_pPre = pTail;
		}
	}

	void PushFront(const T& data)
	{
		ListNode *pNewNode = new ListNode(data);
		pNewNode->_pNext = _pHead->_pNext;
		_pHead->_pNext->_pPre = pNewNode;
		_pHead->_pNext = pNewNode;
		pNewNode->_pPre = _pHead;
	}

	void PopFront()
	{
		if (Empty())
		{
			return;
		}
		else
		{
			ListNode *p = _pHead->_pNext->_pNext;
			delete p->_pPre;
			p->_pPre = _pHead;
			_pHead->_pNext = p;
		}
	}

	Iterator Insert(Iterator pos, const T& data)
	{
		ListNode *pNewNode = new ListNode(data);
		pNewNode->_pNext = pos._pCur;
		pos._pCur->_pPre->_pNext = pNewNode;
		pNewNode->_pPre = pos._pCur->_pPre;
		pos._pCur->_pPre = pNewNode;

		return Iterator(pNewNode);
	}

	Iterator Erase(Iterator pos)
	{
		ListNode *p = pos._pCur->_pNext;
		p->_pPre = pos._pCur->_pPre;
		pos._pCur->_pPre->_pNext = p;
		delete pos._pCur;
		return Iterator(p);
	}

	bool Empty()const
	{
		return _pHead == _pHead->_pNext;
	}

	size_t Size()const
	{
		size_t count = 0;
		ListNode *p = _pHead->_pNext;
		ListNode *q = _pHead;

		while (p != q)
		{
			count++;
			p = p->_pNext;
		}
		return count;

	/*	size_t count = 0;
		Iterator it = Begin();
		while (it != End())
		{
			count++;
			it++;
		}
		return count;*/
	}

	T& Front()
	{
		return _pHead->_pNext->_data;
	}
	const T& Front()const
	{
		return _pHead->_pNext->_data;
	}
	T& Back()
	{
		return _pHead->_pPre->_data;
	}
	const T& Back()const
	{
		return _pHead->_pPre->_data;
	}
	void Clear()
	{
		Iterator it = Begin();
		while (it != End())
		{
			it = Erase(it);
		}
		_pHead->_pNext = _pHead;
		_pHead->_pPre = _pHead;
	}
private:
	ListNode *_pHead;
};

void test()
{
	int array[] = { 1, 2, 3, 4, 5 };
	List l(array, sizeof(array)/sizeof(array[0]));
	//List l1(l);
	List l1 = l;
	/*l.PushBack(6);
	l.PushFront(0);*/

	/*l.PopBack();
	l.PopFront();*/
	//List::Iterator p = l.Begin();
	//l.Insert(p, 0);
	//l.Erase(p);
	////l.Clear();

	List::Iterator it = l1.Begin();
	while (it!=l1.End())
	{
		cout << *it << "->";
		it++;
	}
	cout << "NULL" << endl;
	cout << l.Size() << endl;


}
int main()
{
	test();
	system("pause");
	return 0;
}

読者は自分でテストすることができます.ご指摘を歓迎します.