【C++】STL中list仿写

---

#ifndef LIST_H
#define LIST_H
namespace pzj
{
	template<class T>
	void swap(T v1, T v2)
	{
		T tmp = v1;
		v1 = v2;
		v2 = tmp;
	}
	//_Ty值类型
	template<class _Ty>
	class List
	{
	public:
		//设计节点类型
		struct _Node;
		typedef struct _Node* _Nodeptr;
		struct _Node
		{
			_Ty value;          //value
			_Nodeptr pref;      //前驱
			_Nodeptr next;      //后继
		};
	public:
		//设计获取结点数据类
		struct _Acc;
		typedef _Ty& _Valref;  //value的引用类型
		typedef _Node*& _Noderef; //指针的引用类型

		struct _Acc
		{
			//获取结点中的值的引用
			static _Valref Value(_Nodeptr node)
			{
				return node->value;
			}
			//获取结点中的pref的引用
			static _Noderef _Pref(_Nodeptr node)
			{
				return node->pref;
			}
			//获取节点中的next的引用
			static _Noderef _Next(_Nodeptr node)
			{
				return node->next;
			}
		};
	public:
		//_Ty的类型重命名:两种迭代器将使用
		typedef _Ty         value_type;
		typedef _Ty*		value_pointer;
		typedef _Ty&		value_reference;
		typedef const _Ty*	value_const_pointer;
		typedef const _Ty&	value_const_reference;

	public:
		//设计两种迭代器
		//能力：const_itreator（常性迭代器） < iterator迭代器
		//能力：const_reverse_iterator(常性反向迭代器) < reverse_iterator(反向迭代器)
		class iterator;
		class const_iterator;
		class reverse_iterator;
		class const_reverse_itertor;

		//常性迭代器
		class const_iterator
		{
		protected:
			_Nodeptr _Ptr; //节点指针类型（结点地址）
		public:
			const_iterator(_Nodeptr node = nullptr) : _Ptr(node) {}
			//获取_Ptr指向节点中的value
			value_const_reference operator*() const
			{
				return _Acc::Value(_Ptr);
			}
			//获取value地址
			value_const_pointer operator->() const
			{
				// return &_Acc::Value(_Ptr);
				return &**this;
			}

			//前置++ 后继结点的迭代器
			const_iterator& operator++()
			{
				_Ptr = _Acc::_Next(_Ptr);
				return *this;
			}
			const_iterator operator++(int)
			{
				iterator tmp = *this;
				++* this;
				return tmp;
			}

			const_iterator& operator--()
			{
				_Ptr = _Acc::_Pref(_Ptr);
				return *this;
			}
			const_iterator operator--(int)
			{
				iterator tmp = *this;
				--* this;
				return tmp;
			}
			// ==
			bool operator==(const const_iterator & it) const
			{
				return _Ptr == it._Ptr;
			}
			//!=
			bool operator!=(const const_iterator& it) const
			{
				return !(*this == it);
			}
			//返回_Ptr
			_Nodeptr MyNode()const
			{
				return _Ptr;
			}
		};

		//迭代器:同名方法隐藏
		class iterator : public const_iterator
		{
		public:
			//解决未识别const_iterator中的_Ptr
			typedef const_iterator Base;
			
			iterator(_Nodeptr node = nullptr) :const_iterator(node) {}
			//获取_Ptr指向节点中的value
			value_reference operator*()const
			{
				return _Acc::Value(Base::_Ptr);
			}
			//获取value地址
			value_pointer operator->()const
			{
				//return &_Acc::Value(_Ptr);
				return &**this;
			}

			//前置++ 后继结点的迭代器
			iterator& operator++()
			{
				Base::_Ptr = _Acc::_Next(Base::_Ptr);
				return *this;
			}
			iterator operator++(int)
			{
				iterator tmp = *this;
				++* this;
				return tmp;
			}

			iterator& operator--()
			{
				Base::_Ptr = _Acc::_Pref(Base::_Ptr);
				return *this;
			}
			iterator operator--(int)
			{
				iterator tmp = *this;
				--* this;
				return tmp;
			}
			// ==
			bool operator==(const iterator & it)const
			{
				return Base::_Ptr == it._Ptr;
			}
			//!=
			bool operator!=(const iterator& it)const
			{
				return !(*this == it);
			}
			_Nodeptr MyNode()const
			{
				return Base::_Ptr;
			}
		};

	
	private:
		//List成员属性
		_Nodeptr	_Head;		//头结点
		size_t		_Size;		//数据结点个数

		//申请结点
		_Nodeptr Alloc_Node(_Nodeptr pref = nullptr, _Nodeptr next = nullptr)
		{
			_Nodeptr node = (_Nodeptr)malloc(sizeof(_Node));
			assert(node != nullptr);
			_Acc::_Next(node) = next == nullptr ? node : next;
			_Acc::_Pref(node) = pref == nullptr ? node : pref;
			return node;
		}

		//释放结点
		void Delete_Node(_Nodeptr node)
		{
			if(nullptr != node)
				free(node);
			node = nullptr;
		}
	
	public:
		//List的成员方法
		List() :_Head(Alloc_Node()), _Size(0) {}
		~List() 
		{
			this->clear();
			Delete_Node(_Head);
		}
		List(const List& _S):_Head(Alloc_Node()), _Size(0) 
		{
			insert(begin(), _S.begin(), _S.end());
		}
		//list<_Ty> list = {, , ,};构建
		List(std::initializer_list<_Ty> list) :List()
		{
			for (auto& it : list)
			{
				push_back(it);
			}
		}
		//list<_Ty> list(iterator ...,{, , ,});构建
		List(iterator _P, std::initializer_list<_Ty> list) :List()
		{
			for (auto& x : list)
			{
				insert(_P, x);
			}
		}
		
		//_P迭代器之前 插入结点
		iterator insert(iterator _P, const _Ty& val)
		{
			_Nodeptr _S = _P.MyNode();
			
			_Acc::_Pref(_S) = Alloc_Node(_Acc::_Pref(_S), _S);
			_S = _Acc::_Pref(_S);
			_Acc::_Next(_Acc::_Pref(_S)) = _S;

			////在这个地址中调用_Ty的构造函数（例：string）
			new(&_Acc::Value(_S)) _Ty(val);
			++_Size;
			return iterator(_S);
		}

		//从_P迭代器之前 插入_F到_L之间的值
		void insert(iterator _P, const _Ty& _F, const _Ty& _L)
		{
			for (; _F != _L; ++_F)
			{
				insert(_P, *_F);
			}
		}
		//重命名常性迭代器
		typedef const_iterator _It;
		//从_P迭代器之前 插入_F迭代器到_L迭代器之间的值
		void insert(iterator _P, _It _F, _It _L)
		{
			for (; _F != _L; ++_F)
			{
				insert(_P, *_F);
			}
		}
		//从_P迭代器之前 插入count个val
		void insert(iterator _P, size_t count,const _Ty& val)
		{
			assert(count > 0);
			while (count--)
			{
				insert(_P, val);
			}
		}

		//push_front
		void push_front(const _Ty& val)
		{
			insert(begin(), val);
		}
		//push_back
		void push_back(const _Ty& val)
		{
			insert(end(), val);
		}

		//删除_P迭代器的结点
		iterator erase(iterator _P)
		{
			//先调用重载后置++,返回
			_Nodeptr _S = _P++.MyNode();
			_Acc::_Next(_Acc::_Pref(_S)) = _Acc::_Next(_S);
			_Acc::_Pref(_Acc::_Next(_S)) = _Acc::_Pref(_S);
			//调用_P指向的结点中数据的析构函数
			(&_Acc::Value(_S))->~_Ty();
			Delete_Node(_S);
			--_Size;
			return _P;
		}

		void pop_front()
		{
			erase(begin());
		}
		void pop_back()
		{
			erase(--end());
		}
		void erase(iterator _F, iterator _L)
		{
			for (; _F != _L; )
			{
				erase(_F++);
			}
		}
		void clear()
		{
			erase(begin(), end());
		}

		void remove(const _Ty& val)
		{
			for (iterator it = begin(); it != end(); ++it)
			{
				if (val == *it)
				{
					erase(it);
					break;
				}
			}
		}
		void remove_all(const _Ty& _X)
		{
			iterator _F = begin(), _L = end();
			for (; _F != _L; )
			{
				if (*_F == _X)
				{
					erase(_F++);
				}
				else
				{
					++_F;
				}
			}
		}
		//交换
		void Swap(List& _L)
		{
			pzj::swap(_Head, _L._Head);
			pzj::swap(_Size, _L._Size);
		}
		List& operator=(const List & _S)
		{
			if (this == &_S)
			{
				return *this;
			}
			iterator _F1 = begin();
			iterator _L1 = end();
			const_iterator _F2 = _S.begin();
			const_iterator _L2 = _S.end();
			while (_F1 != _L1 && _F2 != _L2)
			{
				*_F1 = *_F2;
				++_F1;
				++_F2;
			}
			erase(_F1, _L1);
			insert(_L1, _F2, _L2);
			return *this;
		}
	
	public:
		//List的迭代器方法
		iterator begin()
		{
			return iterator(_Acc::_Next(_Head));
		}
		iterator end()
		{
			return iterator(_Head);
		}

		const_iterator begin()const
		{
			return const_iterator(_Acc::_Next(_Head));
		}
		const_iterator end()const
		{
			return const_iterator(_Head);
		}
	};
}

#endif