用C++写线性容器List

MyList.h内容如下:

#pragma once

#include <iostream>

using namespace std;

template<class T>
struct MyListNode
{
	T m_Data;
	MyListNode * m_pPrev;
	MyListNode * m_pNext;
public:
	MyListNode()
	{
		m_pPrev = NULL;
		m_pNext = NULL;
	}
	MyListNode(const T & x)
	{
		m_Data = x;
		m_pPrev = NULL;
		m_pNext = NULL;
	}
};

template<class T>
struct MyListNodeIterator
{
	typedef T & reference;
	typedef T * ptr;
	typedef MyListNodeIterator<T> self;
public:
	MyListNodeIterator()
	{
		m_pCurNode = NULL;
	}
	MyListNodeIterator(MyListNode<T> * x)
	{
		m_pCurNode = x;
	}
	MyListNodeIterator(const MyListNodeIterator& x)
	{
		m_pCurNode = x.m_pCurNode;
	}
	//判断两个迭代器是否相等
	bool operator == (const MyListNodeIterator & x)
	{
		return m_pCurNode == x.m_pCurNode;
	}
	//判断两个迭代器是否不等
	bool operator != (const MyListNodeIterator & x)
	{
		return m_pCurNode != x.m_pCurNode;
	}

	//提取数据
	reference operator * () const { return m_pCurNode->m_Data; }

	//提取数据成员
	MyListNode<T> * operator ->() const { return m_pCurNode; }

	//前置++
	self & operator ++ ()
	{
		m_pCurNode = m_pCurNode->m_pNext;
		return *this;
	}
	//后置++
	self operator ++ (int)
	{
		self tmp = *this;
		m_pCurNode = m_pCurNode->m_pNext;
		return tmp;
	}
	//前置--
	self& operator --()
	{
		m_pCurNode = m_pCurNode->m_pPrev;
		return *this;
	}
	//后置--
	self operator --(int)
	{
		self tmp = *this;
		m_pCurNode = m_pCurNode->m_pPrev;
		return tmp;
	}

	MyListNode<T> * m_pCurNode;
};

template<class T>
class MyList
{
public:
	typedef MyListNodeIterator<T> iterator;
	typedef T & reference;
	//创建一个空的list
	MyList()
	{
		m_pList = new MyListNode<T>;
		m_pList->m_pNext = m_pList;
		m_pList->m_pPrev = m_pList;
	}
	//复制另一个同类型元素的MyList
	MyList(MyList<T> & listOther)
	{
		m_pList = new MyListNode<T>;
		m_pList->m_pNext = m_pList;
		m_pList->m_pPrev = m_pList;
		iterator it = listOther.Begin();
		for (; it != listOther.End(); it++)
			PushBack(*it);
	}
	//析构
	~MyList()
	{
		MyListNode<T> * pCur = NULL;
		MyListNode<T> * pTmp = m_pList->m_pNext;
		while (pTmp != m_pList)
		{
			pCur = pTmp;
			pTmp = pTmp->m_pNext;
			delete pCur;
		}
		delete m_pList;
	}

	//返回容器元素的个数
	int Size()
	{
		MyListNode<T> * pTmp = m_pList;
		int nNum = 0;
		while (pTmp->m_pNext != m_pList)
		{
			nNum++;
			pTmp = pTmp->m_pNext;
		}
		return nNum;
	}
	//判断容器是否为空，空则返回true，否则返回fase
	bool Empty() const
	{
		return m_pList->m_pNext == m_pList;
	}

	//在MyList容器尾部增加一个元素x
	void PushBack(T x)
	{
		MyListNode<T> * pTmp = new MyListNode<T>(x);
		if (!pTmp)
		{
			return;
		}
		pTmp->m_pPrev = m_pList->m_pPrev;
		pTmp->m_pNext = m_pList;
		m_pList->m_pPrev->m_pNext = pTmp;
		m_pList->m_pPrev = pTmp;
		return;
	}
	//在MyList容器首元素前增加一个元素x
	void PushFront(const T & x)
	{
		MyListNode<T> * pTmp = new MyListNode<T>(x);
		if (!pTmp)
		{
			return;
		}
		pTmp->m_pPrev = m_pList;
		pTmp->m_pNext = m_pList->m_pNext;
		m_pList->m_pNext->m_pPrev = pTmp;
		m_pList->m_pNext = pTmp;
		return;
	}

	//在Pos前插入x
	iterator Insert(iterator Pos, const T & x)
	{		
		MyListNode<T> * pTmp = new MyListNode<T>(x);
		if (!pTmp)
		{
			return NULL;
		}
		pTmp->m_pPrev = Pos->m_pPrev;
		pTmp->m_pNext = Pos.m_pCurNode;
		Pos->m_pPrev->m_pNext = pTmp;
		Pos->m_pPrev = pTmp;
		return pTmp;
	}
	
	//返回首元素的迭代器
	iterator Begin()
	{
		return m_pList->m_pNext;
	}

	//删除迭代器指针对应的元素
	iterator Erase(iterator it)
	{
		MyListNode<T> * pNext = it->m_pNext;
		MyListNode<T> * pPrev = it->m_pPrev;
		it->m_pPrev->m_pNext = pNext;
		it->m_pNext->m_pPrev = pPrev;
		MyListNode<T> * pCur = it.m_pCurNode;
		if (pCur)
		{
			delete pCur;
		}
		return pNext;
	}
	
	//删除容器中所有元素值为x的元素
	void Remove(const T& x)
	{
		iterator it;
		it = Begin();
		while (it != End())
		{
			iterator Next = it;
			Next++;
			if (it->m_Data == x)
			{
				Erase(it);
			}
			it = Next;
		}
	}

	//删除容器中所有元素
	void Clear()
	{
		iterator it;
		it = Begin(); 
		while (it != End())
		{
			iterator Next = it;
			Next++;
			Erase(it);
			it = Next;
		}			
	}

	//返回结束标志迭代器
	iterator End()
	{
		return m_pList;
	}

	//返回首元素的引用
	reference Front()
	{
		return m_pList->m_pNext->m_Data;
	}

	//返回尾元素的引用
	reference Back()
	{
		return m_pList->m_pPrev->m_Data;
	}

	//归并排序
	void Sort()
	{
		MyList<T> Carry;
		MyList<T> Counter[64];
		int nFill = 0;
		int i = 0;
		while (!Empty())
		{
			Carry.Splice(Carry.Begin(), *this, Begin());
			i = 0;
			for (; i < nFill && !Counter[i].Empty();)
			{
				Counter[i].Merge(Carry);
				Carry.Swap(Counter[i++]);
			}
			Carry.Swap(Counter[i]);
			if (i == nFill)
				nFill++;
		}

		for ( i = 1; i < nFill; i++)
		{
			Counter[i].Merge(Counter[i - 1]);
		}

		Swap(Counter[nFill - 1]);
	}

	//将链表l中的i所指向的元素放到当前链表Pos之前，并且从l中移除i所指向的元素
	void Splice(iterator Pos, MyList<T> & l, iterator i)
	{
		iterator j = i;
		++j;
		if (Pos == i || Pos == j) return;
		Transfer(Pos, i, j);
	}

	//交换链表l和当前链表的内容
	void Swap(MyList<T> & l)
	{
		MyListNode<T> * pTmp = l.m_pList;
		l.m_pList = m_pList;
		m_pList = pTmp;
	}

	//合并两个链表，前提是这两个链表都有序递增
	void Merge(MyList<T> & l)
	{
		iterator First1 = Begin();
		iterator End1 = End();
		iterator First2 = l.Begin();
		iterator End2 = l.End();

		while (First1 != End1 && First2 != End2)
		{
			if (*First1 < *First2)
			{
				First1++;
			}
			else
			{
				iterator Next = First2;
				Next++;
				Transfer(First1, First2, Next);
				First2 = Next;
			}
		}
		if (First2 != End2)
		{
			Transfer(End1, First2, End2);
		}
	}


	//将[First,Last)之间的元素插入到pos之前，如果Pos和[First,Last)在同一个链表，那么Pos不能在[First,End)之间。
	void Transfer(iterator Pos, iterator First, iterator Last)
	{
		if (Pos != Last)
		{
			Last.m_pCurNode->m_pPrev->m_pNext = Pos.m_pCurNode;
			First.m_pCurNode->m_pPrev->m_pNext = Last.m_pCurNode;
			Pos.m_pCurNode->m_pPrev->m_pNext = First.m_pCurNode;
			MyListNode<T> * pTmp = Pos.m_pCurNode->m_pPrev;
			Pos.m_pCurNode->m_pPrev = Last.m_pCurNode->m_pPrev;
			Last.m_pCurNode->m_pPrev = First.m_pCurNode->m_pPrev;
			First.m_pCurNode->m_pPrev = pTmp;
		}
	}
protected:
	MyListNode<T> * m_pList;
};
#pragma once

#include <iost