C++list实现

长话短说，我们直接实现。

#pragma once
#include <assert.h>
namespace cx
{
	template <class T>
	struct ListNode
	{
		//构造函数
		ListNode(const T& x=T())
			:_next(nullptr),_prev(nullptr),_val(x)
		{}
		//成员变量：
		ListNode<T>* _next;
		ListNode<T>* _prev;
		T _val;
	};
	template <class T,class Ref,class Ptr>
	//template <class T, class Ref>
	struct _list_iterator
	{
		typedef ListNode<T> Node;
		typedef _list_iterator<T,Ref, Ptr> self;
		//typedef _list_iterator<T, Ref> self;

		//构造函数：
		//_list_iterator()
		/*iterator(Node* x)
			:_node(x)
		{}*/
		_list_iterator(Node* x)
			:_node(x)
		{}
		//不用写析构：原因在于我们的目标不是在这里析构
		//常见操作：		
		self& operator++()//前置++
		{
			_node = _node->_next;
			return (*this);
		}
		self operator++(int)//后置++
		{
			self tmp(*this);
			_node = _node->_next;
			return tmp;
		}
		self& operator--()//前置--
		{
			_node = _node->_prev;
			return *this;
		}
		self& operator--(int)//后置--
		{
			self tmp(*this);
			_node = _node->_prev;
			return tmp;
		}
		Ref operator*()
		{
			return _node->_val;
		}
		bool operator!=(const self& s)
		{
			return !(_node == s._node);
		}
		bool operator==(const self& s)
		{
			return !(*this != s);
		}
		Ptr operator->()
		{
			return &_node->_val;
		}
		//类成员函数：
		Node* _node;
	};
	//template <class T>
	//struct _list_const_iterator
	//{
	//	typedef ListNode<T> Node;
	//	typedef _list_const_iterator<T> const_iterator;
	//	//构造函数：
	//	//_list_iterator()
	//	/*iterator(Node* x)
	//		:_node(x)
	//	{}*/
	//	_list_const_iterator(Node* x)
	//		:_node(x)
	//	{}
	//	//不用写析构：原因在于我们的目标不是在这里析构
	//	//常见操作：		
	//	const_iterator& operator++()//前置++
	//	{
	//		_node = _node->_next;
	//		return (*this);
	//	}
	//	const_iterator operator++(int)//后置++
	//	{
	//		const_iterator tmp(*this);
	//		_node = _node->_next;
	//		return tmp;
	//	}
	//	const_iterator& operator--()//前置--
	//	{
	//		_node = _node->_prev;
	//		return *this;
	//	}
	//	const_iterator& operator--(int)//后置--
	//	{
	//		const_iterator tmp(*this);
	//		_node = _node->_prev;
	//		return tmp;
	//	}
	//	const T& operator*()
	//	{
	//		return _node->_val;
	//	}
	//	bool operator!=(const const_iterator& s)
	//	{
	//		return !(_node == s._node);
	//	}
	//	bool operator==(const const_iterator& s)
	//	{
	//		return !(*this != s);
	//	}
	//	//类成员函数：
	//	Node* _node;
	//};
	template <class T>
	class list
	{
	public:
		typedef ListNode<T> Node;
		//typedef _list_iterator<T,T&> iterator;
		typedef _list_iterator<T, T&, T*> iterator;
		//typedef _list_iterator<T, const T&> const_iterator;
		typedef _list_iterator<T,const T&,const T*> const_iterator;
		//构造函数
		void empty_list()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}
		list()
		{
			empty_list();
		}
		//list ( list& x);
		list(const list<T>& s)
		{
			empty_list();
			for (auto e : s)//该类型为：T
			{
				push_back(e);
			}
		}
		//list& operator= (const list& lt);
		//传统写法：
		//list<T>& operator= (list<T>& lt)
		//{
		//	if(this != &lt)
		//	{
		//		//清除*this中内容
		//		clear();
		//		for (T e : lt)
		//		{
		//			push_back(e);
		//		}
		//	}
		//	return *this;
		//}
		//现代写法：
		list<T>& operator= (list<T> lt)
		{
			swap(lt);
			return *this;
		}
		//析构函数：
		void clear()
		{
			//区别析构函数，clear只会删除有效数据，保留虚拟头结点
			iterator it = begin();
			while (it != end())
			{
				it=erase(it);
			}
		}
		~list()
		{
			clear();
			//删除_head;
			delete _head;
			_head = nullptr;
		}
		//迭代器：
		iterator begin()//有效第一个节点
		{
			//assert(_head->_next != _head);
			//如果写上面这句，会出现开始为空链表报错情况
			return _head->_next;
		}
		const_iterator begin() const
		{
			return _head->_next;
		}
		iterator end()
		{
			return _head;
		}
		const_iterator end() const
		{
			return _head;
		}
		//常见操作：
		iterator erase(iterator pos)
		{
			//检查pos位置非_head位置
			assert(pos !=end());
			//删除的是pos位置
			Node* current = pos._node;
			Node* prev = current->_prev;
			Node* next = current->_next;
			//删除操作
			prev->_next = next;
			next->_prev = prev;
			delete current;
			return next;//返回的是pos下一个位置
		}
		iterator erase(iterator first, iterator last)//区间左闭右开
		{
			assert(first != end());
			assert(last != end());
			while (first != last)
			{
				if (first == end())
					break;
				first = erase(first);
			}
			return first;
		}
		void push_back(const T& val)
		{
			Node* tmp = new Node(val);
			Node* tail = _head->_prev;
			tail->_next = tmp;
			tmp->_prev = tail;
			tmp->_next = _head;
			_head->_prev = tmp;
		}
		void swap(list<T>& tmp)
		{
			std::swap(_head, tmp._head);
		}
		iterator insert(iterator pos, const T& x)
		{
			//insert是指在pos位置前插入
			Node* current = pos._node;
			Node* prev = current->_prev;
			//开空间
			Node* tmp = new Node(x);
			tmp->_prev = prev;
			prev->_next = tmp;
			tmp->_next = current;
			current->_prev = tmp;
			//return iterator(tmp);
			return tmp;//注意点：单参数的类可以隐式类型转换
		}
		//容量相关：
		bool empty() const
		{
			return _head->_next == _head;
		}
		size_t size() const
		{
			size_t n = 0;
			Node* tmp = _head->_next;
			while (tmp!=_head)
			{
				tmp = tmp->_next;
				n++;
			}
			return n;
		}
		void push_front(const T& x)
		{
			this->insert(begin(), x);
		}
		void pop_back()
		{
			this->erase(--end());
		}
		void pop_front()
		{
			erase(begin());
		}
		//Element access:
		T& front()
		{
			return _head->_next->_val;
		}
		const T& front() const
		{
			return _head->_next->_val;
		}
		T& back()
		{
			return _head->_prev->_val;
		}
		const T& back() const
		{
			return _head->_prev->_val;
		}
	private:
		//虚拟头结点：
		Node* _head;
	};
}

大家可以自行添加更多内容~