list 的实现

上图的下述代码实现：

void push_back(const T& x)
{
	Node* newnode = new Node(x);
	Node* tail = _head->_prev;

	tail->_next = newnode;
	newnode->_prev = tail;
	newnode->_next = _head;
	_head->_prev = newnode;
}

顺序表可以用原生指针代替迭代器的指针，但链表不可以，链表的指针++并不能够保证找到下一个节点的位置。因此需要把当前节点封装起来作为迭代器，在迭代器类中重载++函数，使其++也可以找到下一个结点的位置。

下述代码为list的迭代器代码，对于拷贝构造使用浅拷贝就可以，因为只需要让另一个指针指向当前节点的资源，而链表不可以浅拷贝。对于析构函数，迭代器不能去析构资源。因为资源是在链表中的，迭代器只是访问。

对于迭代器而言，需要完成 *it，重载 ++ 和 – 函数，还有迭代器的比较节点是否相等函数。

const迭代器为什么是const_iterator而不是const iterator？
const迭代器是迭代器指向的内容不能修改而不是迭代器本身不能修改，而const iterator是iterator不能修改，因此不满足需求。
const迭代器相当于要模拟的不是 T* const 而是 const T*
在list中写了一个模板类，编译器底层生成了两个类。

const类型的迭代器只有operator*和operator->的返回值和普通迭代器的返回值不同，返回值不同就可以用模板。
对于下述代码自定义类型A而言，如果想用迭代器->读取A的内容，就需要在迭代器中重载->，也就是定义的模板 Ptr 函数。

template <class T , class Ref, class Ptr>
struct ListIterator
{
	typedef ListNode<T> Node; 
	typedef ListIterator<T, Ref, Ptr> Self;

	Node* _node; //内置类型浅拷贝就可以了

	ListIterator(Node* node)
		:_node(node)
	{}

	//*it 可读可写，得引用返回。
	//T& operator*()
	Ref operator*()
	{
		return _node->_data;
	}
	// it->
	//T* operator->()
	Ptr operator->()
	{
		//node里的data进行取地址，返回一个T类型的指针指向data的地址，
		//如果存放的是A类型数据，data就是一个A类型指针就可以访问a1和a2
		return &_node->_data; 
	}

	Self& operator++() //前置++ 返回++以后的值
	{
		_node = _node->_next;
		return *this;
	}
	Self operator++(int)
	{
		//让tmp指针指向NOde*的资源就行了 浅拷贝够用。
		Self tmp(*this); 
		_node = _node->_next;

		return tmp;
	}
	Self& operator--() //前置-- 返回--以后的值
	{
		_node = _node->_prev;
		return *this;
	}
	Self operator--(int)
	{
		//让tmp指针指向NOde*的资源就行了 浅拷贝够用。
		Self tmp(*this);
		_node = _node->_prev;

		return tmp;
	}

	bool operator!=(const Self& it)
	{
		return _node != it._node;
	}
	bool operator==(const Self& it)
	{
		return _node == it._node;
	}
};

只有list才知道链表的开始和结束，因此得用list把封装的iterator连接起来。
完整的list代码：

namespace ggg
{
	// 节点类型定义
	template<class T>
	struct ListNode //节点的数据需要公开 用struct
	{
		ListNode<T>* _next;
		ListNode<T>* _prev;
		T _data;

		ListNode(const T& x = T())
			:_next(nullptr)
			, _prev(nullptr)
			, _data(x)
		{}
	};
	
	// 封装节点迭代器完成的工作 普通迭代器和const迭代器使用模板复用
	template <class T , class Ref, class Ptr>
	struct ListIterator
	{
		typedef ListNode<T> Node; 
		typedef ListIterator<T, Ref, Ptr> Self;

		Node* _node; //内置类型浅拷贝就可以了

		ListIterator(Node* node)
			:_node(node)
		{}

		//*it 可读可写，得引用返回。
		//T& operator*()
		Ref operator*()
		{
			return _node->_data;
		}
		// it->
		//T* operator->()
		Ptr operator->()
		{
			//node里的data进行取地址，返回一个T类型的指针指向data的地址，
			//如果存放的是A类型数据，data就是一个A类型指针就可以访问a1和a2
			return &_node->_data; 
		}

		Self& operator++() //前置++ 返回++以后的值
		{
			_node = _node->_next;
			return *this;
		}
		Self operator++(int)
		{
			//让tmp指针指向NOde*的资源就行了 浅拷贝够用。
			Self tmp(*this); 
			_node = _node->_next;

			return tmp;
		}
		Self& operator--() //前置-- 返回--以后的值
		{
			_node = _node->_prev;
			return *this;
		}
		Self operator--(int)
		{
			//让tmp指针指向NOde*的资源就行了 浅拷贝够用。
			Self tmp(*this);
			_node = _node->_prev;

			return tmp;
		}

		bool operator!=(const Self& it)
		{
			return _node != it._node;
		}
		bool operator==(const Self& it)
		{
			return _node == it._node;
		}
	};
	/
	// 链表的类
	template<class T>
	class list
	{
		typedef ListNode<T> Node;
	public:
		//typedef ListIterator<T> iterator;
		//typedef ListConstIterator<T> const_iterator;
		typedef ListIterator<T, T&, T*> iterator;
		typedef ListIterator<T, const T&, const T*> const_iterator;

		iterator begin()
		{
			//return iterator(_head->_next); 匿名对象
			iterator it(_head->_next);
			return it;
		}
		//链表的结尾是最后一个节点的下一个位置，也就是哨兵位
		iterator end() 
		{
			return iterator(_head);
		}

		//类比：相当于要模拟的不是 T* const 而是 const T*
		const_iterator begin() const
		{
			const_iterator it(_head->_next);
			return it;
		}
		const_iterator end() const
		{
			return const_iterator(_head);
		}
	///
		void empty_init()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
			_size = 0;
		}
		void clear()
		{
			iterator it = begin();
			while (it != end()) // !=end() 就不会清除掉head节点
			{
				it = erase(it);
			}
		}

		list() //构造
		{
			empty_init();
		}
		//lt1(lt)
		list(const list<T>& lt) //拷贝构造
		{
			empty_init();
			for (auto& e : lt)
			{
				push_back(e);
			}
		}
		list<T>& operator=(list<T> lt) //赋值
		{
			std::swap(_head, lt._head);
			std::swap(_size, lt._size);
			return *this;
		}
		~list() //析构
		{
			clear();
			delete _head;
			_head = nullptr;
		}

		void push_back(const T& x) //插入
		{
			//Node* newnode = new Node(x);
			//Node* tail = _head->_prev;

			//tail->_next = newnode;
			//newnode->_prev = tail;
			//newnode->_next = _head;
			//_head->_prev = newnode;

			insert(end(), x); //在end前面插入就是尾插
		}
		void push_front(const T& x)
		{
			insert(begin(), x);
		}

		//尾删，删掉end()（哨兵位head）的下一个，也就是最后一个有数据的位置，--就是求上一个位置prev
		void pop_back() 
		{
			erase(--end());
		}
		void pop_front() //头删，begin()就是头
		{
			erase(begin());
		}

		void insert(iterator pos, const T& val)
		{
			Node* cur = pos._node;
			Node* newnode = new Node(val);
			Node* prev = cur->_prev;

			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;
			_size++;
		}
		iterator erase(iterator pos)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;

			prev->_next = next;
			next->_prev = prev;
			delete cur;
			_size--;
			return iterator(next);
		}

		
		size_t size() const
		{
			return _size;
		}
		bool empty()
		{
			return _size == 0;
		}

	private:
		Node* _head;
		size_t _size;
	};

	/
	struct A
	{
		int _a1;
		int _a2;
		A(int a1 = 0, int a2 = 0)
			:_a1(a1)
			,_a2(a2)
		{}
	};

}