STL中list类的模拟实现

#include <iostream>
using namespace std;

//结点的定义
template <class T>
struct Node {
public:
	Node(const T& data = T())
		:data_(data)
		,prev_(nullptr）		//指向前驱结点
		,next_(nullptr)		//指向后继结点
	{}


	T data_;
	Node<T>* prev_;
	Node<T>* next_;
};

//正向迭代器
template<class T,class TRef,class TPtr>
class ListIterator{
	typedef Node<T>* PNode;
	typedef ListIterator<T, TRef, TPtr> Self;
private:
	PNode _pNode;
public:
	ListIterator(PNode pNode = nullptr)
		:_pNode(pNode)
	{}

	ListIterator(const Self& l)
		:_pNode(l._pNode)
	{}

	T& operator*()
	{
		return _pNode->data_;
	}

	T* operator->()
	{
		return &(operator*());
	}

	Self& operator++()   //前置++,返回自己
	{
		_pNode = _pNode->next_;
		return *this;
	}

	Self& operator++(int)  //后置++，返回一个拷贝对象
	{
		Self tmp(*this);
		_pNode = _pNode->next_;
		return tmp;
	}

	Self& operator--()
	{
		_pNode = _pNode->prev_;
		return *this;
	}

	Self& operator--(int)
	{
		Self tmp(*this);
		_pNode = _pNode->prev_;
		return tmp;
	}

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

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

//反向迭代器
template<class T,class Ref,class Ptr,class Iterator>
class ReverseIterator{
	typedef ReverseIterator<T, Ref, Ptr, Iterator> Self;
private:
	Iterator _it;
public:
	ReverseIterator(const Iterator& it)
		:_it(it) 
	{}

	ReverseIterator(const Self& s)
		:_it(s._it)
	{}

	Ref operator*()
	{
		Itertor tmp = _it;
		return *(--tmp);
	}

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

	Self& operator++()
	{
		--_it;
		return *this;
	}

	Self& operator++(int)
	{
		Itertor tmp(_it);
		--_it;
		return tmp;
	}

	Self& operator--()
	{
		++_it;
		return *this;
	}

	Self& operator--(int)
	{
		Itertor tmp(_it);
		++_it;
		return tmp;
	}

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

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


//list类的模拟实现
template<class T>
class List {
	typedef Node<T> Node;
	typedef Node* PNode;
public:
	typedef ListIterator<T, T&, T*> Iterator;
	typedef ListIterator<T, const T&, const T*> ConstIterator;
	typedef ReverseIterator<T, T&, T*,Iterator> RIterator;
	typedef ReverseIterator<T, const T&, const T*, ConstIterator> ConstRIterator;

private:
	PNode _pHead;

	void Init()
	{
		_pHead = new Node;
		_pHead->prev_ = _pHead;
		_pHead->next_ = _pHead;
	}

public:
	List()
	{
		Init();
	}

	List(int n, const T& value = T())  //只有一个参数用来构造时，就会用T()来构造默认参数，即n个值为0的元素。
	{
		Init();
		for (int i = 0; i < n; ++i) {
			PushBack(value);
		}
	}
	template<class Iterator>
	List(Iterator first, Iterator last)
	{
		Init();
		while (first != last)
		{
			PushBack(*first);
			++first;
		}
	}

	List(const List<T>& l)
	{
		Init();
		List<T> tmp(l.Begin(),l.end());
		this->Swap(tmp);
	}

	List<T>& operator=(const List<T>& l)
	{
		if (this != &l)
		{
			List<T> temp(l);
			this->Swap(tmp);
		}
		return *this;
	}

	~List()
	{
		Clear();
		delete _pHead;
		_pHead = nullptr;
	}

	size_t Size()const
	{
		size_t count = 0;
		PNode pCur = _pHead->next_;
		while (pCur != _pHead)
		{
			++count;
			pCur = pCur->next_;
		}
		return count;
	}

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

	void Resize(size_t newSize, const T& val = T())
	{
		size_t oldSize = Size();
		if (oldSize <= newSize)
		{
			for (size_t i = oldSize; i < newSize; ++i)
				PushBack(val);
		}
		else
		{
			for (size_t i = newSize; i < oldSize; ++i)
				PopBack();
		}
	}

	T& Front()
	{
		return _pHead->next_->data_;
	}

	const T& Front()const
	{
		return _pHead->next_->data_;
	}

	T& Back()
	{
		return _pHead->prev_->data_;
	}

	const T& Back()const
	{
		return _pHead->prev_->data_;
	}

	void PushBack(const T& data)
	{
		PNode pNewNode = new Node(data);
		pNewNode->next_ = _pHead;
		pNewNode->prev_ = _pHead->prev_;
		_pHead->prev_ = pNewNode;
		pNewNode->prev_->next_ = pNewNode;
	}

	void PopBack()
	{
		PNode pDel = _pHead->prev_;
		if (pDel != _pHead)
		{
			_pHead->prev_ = pDel->prev_;
			pDel->prev_->next_ = _pHead;
			delete pDel;
		}
	}

	void PushFront(const T& data)
	{
		PNode pNewNode = new Node(data);
		pNewNode->next_ = _pHead->next_;
		pNewNode->prev_ = _pHead;
		_pHead->next_ = pNewNode;
		pNewNode->next_->prev_ = pNewNode;
	}

	void PopFront()
	{
		PNode Del = _pHead->next_;
		if (Del != _pHead)
		{
			_pHead->next_ = Del->next_;
			Del->next_->prev_ = _pHead;
			delete Del;
		}
	}

	Iterator Insert(Iterator pos, const T& data)
	{
		PNode pNewNode = new Node(data);
		PNode pCur = pos._pNode;

		pNewNode->prev_ = pCur->prev_;
		pNewNode->next_ = pCur;
		pNewNode->prev_->next_ = pNewNode;
		pCur->prev_ = pNewNode;
		return Iterator(pNewNode);
	}

	Iterator Erase(Iterator pos)
	{
		PNode pDel = pos._pNode;
		PNode pCur = pDel->next_;

		pDel->next_->prev_ = pDel->prev_;
		pDel->prev_->next_ = pDel->next_;
		delete pDel;
		return Iterator(pCur);
	}

	Iterator begin()
	{
		return Iterator(_pHead->next_);
	}

	Iterator end()
	{
		return Iterator(_pHead);
	}

	RIterator rbegin()
	{
		return ReverseIterator(end());
	}

	RIterator rend()
	{
		return ReverseIterator(begin());
	}

	ConstIterator cbegin()const
	{
		return ConstIterator(_pHead->next_);
	}

	ConstIterator cend()const
	{
		return ConstIterator(_pHead);
	}

	ConstRIterator crbegin()const
	{
		return ConstRIterator(cend());
	}

	ConstRIterator crend()const
	{
		return ConstRIterator(cbegin());
	}

	void Clear()
	{
		PNode pCur = _pHead->next_;
		while (pCur != _pHead)
		{
			_pHead->next_ = pCur->next_;
			delete pCur;
			pCur = _pHead->next_;
		}
		_pHead->next_ = _pHead;
		_pHead->prev_ = _pHead;
	}

	void Swap(List<T>& l)
	{
		swap(_pHead,l._pHead);
	}
};