list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向代。 list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。

---

1.list的使用

1.1list的构造

1.2 迭代器

list是一个带头的双向循环链表

 1.3 list capacity

1.4 list element access

1.5 list modifiers

1.6 迭代器失效

迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

2.模拟实现

list模拟实现的重点就是它的迭代器，list与string、vector不一样，它的底层不是一片连续的空间，所以它不能向string、和vector一样直接取指针，而需要构建一个结构体

	template <class T,class Ref,class Ptr>
	struct _list_iterator
	{
		typedef list_node Node;
		typedef _list_iterator self;
		Node* _node;
		_list_iterator (Node* node = Node())
			:_node(nullptr)
		{
			_node = node;
		}
		//*it
		Ref operator*()
		{
			return _node->_data;
		}
 
		Ptr operator->()
		{
			//return &(operator*());
			return &_node->_data;
		}
		//it1!=it2
		bool operator!=(const self& it)
		{
			return _node != it._node;
		}
		bool operator==(const self& it)
		{
			return _node == it._node;
		}
		//++it
		self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		//it++
		self& operator++(int)
		{
			self tempIterator = *this;
			_node = _node->_next;
			return tempIterator;
		}
		//--it
		self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}
		//it--
		self& operator--(int)
		{
			self tempIterator = *this;
			_node = _node->_prev;
			return tempIterator;
		}
 
	};

3.list模拟实现总览

#pragma once
#include 
using namespace std;
namespace ldx
{
	template <class T>
	struct list_node
	{
		list_node(const T& val = T())
			:_next(nullptr)
			, _prev(nullptr)
			, _data(val)
		{}
 
		list_node* _next;
		list_node* _prev;
		T _data;
 
	};
	template <class T,class Ref,class Ptr>
	struct _list_iterator
	{
		typedef list_node Node;
		typedef _list_iterator self;
		Node* _node;
		_list_iterator (Node* node = Node())
			:_node(nullptr)
		{
			_node = node;
		}
		//*it
		Ref operator*()
		{
			return _node->_data;
		}
		//自定义类型通过迭代器访问成员
		Ptr operator->()
		{
			//return &(operator*());
			return &_node->_data;
		}
		//it1!=it2
		bool operator!=(const self& it)
		{
			return _node != it._node;
		}
		bool operator==(const self& it)
		{
			return _node == it._node;
		}
		//++it
		self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		//it++
		self& operator++(int)
		{
			self tempIterator = *this;
			_node = _node->_next;
			return tempIterator;
		}
		//--it
		self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}
		//it--
		self& operator--(int)
		{
			self tempIterator = *this;
			_node = _node->_prev;
			return tempIterator;
		}
 
	};
	template <class T>
	class list
	{
		typedef _list_iterator iterator;
		typedef _list_iteratorconst T&, const T*> const_iterator;
		typedef list_node Node;
	public:
		list()
		{
			empty_init();
		}
		iterator begin()
		{
			return iterator(_head->_next);
		}
		const_iterator begin()const
		{
			return const_iterator(_head->_next);
		}
		const_iterator end()const
		{
			return const_iterator(_head);
		}
		iterator end()
		{
			return iterator(_head);
		}
		void empty_init()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}
		传统写法
		//list(const list& lt)
		//{
		//	_head = new Node;
		//	_head->_next = _head;
		//	_head->_prev = _head;
		//	auto it = lt.begin();
		//	while (it != lt.end())
		//	{
		//		push_back(*it);
		//		it++;
		//	}
		//}
		//现在写法
		template <typename InputIterator>
		list(InputIterator first, InputIterator last)
		{
			empty_init();
			while (first != last)
			{
				push_back(*first);
				first++;
			}
		}
		void swap(list& lt)
		{
			std::swap(_head, lt._head);
		}
		list(const list& lt)
		{
			empty_init();
			list temp(lt.begin(),lt.end());
			swap(temp);
		}
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}
		list& operator=(list lt)
		{
			swap(lt);
			return *this;
		}
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				erase(it);
			}
		}
		//在pos前插入节点
		void insert(iterator pos, const T& val)
		{
			Node* cur = pos._node;
			Node* new_node = new Node(val);
			new_node->_next = cur;
			new_node->_prev = cur->_prev;
			cur->_prev->_next = new_node;
			cur->_prev = new_node;
		}
		void push_back(const T& val)
		{
			insert(end(), val);
		}
		iterator erase(iterator pos)
		{
			Node* posNext = pos._node->_next;
			Node* posPrev = pos._node->_prev;
			posPrev->_next = posNext;
			posNext->_prev = posPrev;
			delete pos._node;
			return iterator(posNext);
 
		}
		iterator pop_back()
		{
			return erase(--end());
		}
	private:
		Node* _head;
 
	};
 
}