//構(gòu)造空的list
list()
//拷貝構(gòu)造
list (const list& x);
//迭代器構(gòu)造，使用模板能適合不同的類型
template <class InputIterator>
list (InputIterator first, InputIterator last);
//構(gòu)造n個(gè)值為val的list
list (size_type n, const value_type& val = value_type())

//返回開(kāi)始位置的迭代器
iterator begin();
const_iterator begin() const;
//返回結(jié)束位置的迭代器
iterator end();
const_iterator end() const;

//判斷是否為空
bool empty() const;
//返回有效節(jié)點(diǎn)的個(gè)數(shù)
size_type size() const;

//返回首元素的引用
reference front();
const_reference front() const;
//返回末尾元素的引用
reference back();
const_reference back() const;

//頭插
void push_front (const value_type& val);
//尾插
void push_back (const value_type& val);
//頭刪
void pop_front();
//尾刪
void pop_back();
//在任意位置插入
iterator insert (iterator position, const value_type& val);
//在任意位置刪除
iterator erase (iterator position);
//交換兩個(gè)鏈表中的元素
void swap (list& x);
//清空鏈表中的元素
void clear();

template<class T>
	class list_node
	{
	public:
		list_node<T>* _next;
		list_node<T>* _prev;
		T _val;
		list_node(const T& val = T())//默認(rèn)匿名對(duì)象
			:_next(nullptr)
			,_prev(nullptr)
			,_val(val)
		{}
	};

template<class T,class Ref ,class Ptr>
	class _list_iterator
	{
	public:
        //這里事實(shí)上迭代器只是借用節(jié)點(diǎn)進(jìn)行訪問(wèn)，而不是管理這些節(jié)點(diǎn)，鏈表才管理節(jié)點(diǎn)    
		typedef list_node<T> Node;
		typedef _list_iterator<T, Ref,Ptr> self;
		Node* _node;
		_list_iterator(Node* node)
			:_node(node)
		{}
		Ref operator*()//這里控制解引用的返回類型
		{
			return _node->_val;
		}
		Ptr operator->()
		{
			return &_node->_val;
		}
		//前置++
		self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		//后置++
		self operator++(int)
		{
			self temp(*this);
			_node = _node->_next;
			return temp;
		}
		//前置--
		self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}
		//后置--
		self operator--(int)
		{
			self temp(*this);
			_node = _node->_prev;
			return temp;
		}
		bool operator!=(const self& it) const
		{
			return _node != it._node;
		}
		bool operator==(const self& it) const
		{
			return _node == it._node;
		}
	};

template<class T>
	class list
	{
		typedef list_node<T> Node;
	public:
		typedef _list_iterator<T,T&,T*> iterator;//內(nèi)嵌類
		typedef _list_iterator<T,const T&,const T*> const_iterator;
		//這里const迭代器的設(shè)計(jì)是錯(cuò)誤的，因?yàn)閏onst迭代器是希望指向內(nèi)容不被修改
		//這樣的設(shè)計(jì)是迭代器本身不能修改
		//typedef const _list_iterator<T> const_iterator;
		iterator begin() 
		{
			return _head->_next;//單參數(shù)的構(gòu)造函數(shù)支持隱式類型轉(zhuǎn)換
		}
		const_iterator begin() const
		{
			return _head->_next;
		}
		iterator end()
		{
			return _head;
		}
		const_iterator end() const
		{
			return _head;
		}
		void empty_init()
		{
			_head = new Node;
			_head->_prev = _head;
			_head->_next = _head;
		}
		list()
		{
			empty_init();
		}
		//lt2(lt1)
		list(const list<T>& lt)
		//list(const list& lt)//不推薦這樣使用
		{
			empty_init();
			//遍歷lt1，直接把lt2尾插到lt1
			//這里傳引用效率高
			for (const auto& e : lt)
			{
				push_back(e);
			}
		}
		void swap(list<T>& lt)
		{
			std::swap(_head, lt._head);
		}
		list<T>& operator=(list<T> lt)
		//list& operator=(list lt)//這里與上面的拷貝構(gòu)造同理
		{
			swap(lt);
			return *this;
		}
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}
		void push_back(const T& x)
		{
			insert(end(), x);
		}
		void pop_back()
		{
			erase(--end());//這里調(diào)用--，頭節(jié)點(diǎn)的prev就是尾
		}
		void push_front(const T& x)
		{
			insert(begin(), x);
		}
		void pop_front()
		{
			erase(begin());
		}
		iterator insert(iterator pos, const T& x)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* newnode = new Node(x);
			prev->_next = newnode;
			newnode->_next = cur;
			cur->_prev = newnode;
			newnode->_prev = prev;
			return newnode;
		}
		iterator erase(iterator pos)//這里會(huì)有迭代器失效，返回下一個(gè)位置的迭代器
		{
			assert(pos != end());
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;
			prev->_next = next;
			next->_prev = prev;
			delete cur;
			return next;
		}
		size_t size()
		{
			size_t sz = 0;
			iterator it = begin();
			while (it != end())
			{
				++sz;
				++it;
			}
			return sz;
		}
	private:
		Node* _head;
	};