【C++STL】以为 list 很简单？拆完它的 “骨架” 才发现，这货藏了这么多 “小心机”（附实现）

//定义结点
template<class T>
struct list_node
{
	T _data;//存放的数据
	list_node<T>* _next;//后继结点
	list_node<T>* _prev;//前驱结点


	//默认构造 对新结点初始化
	list_node(const T& x = T())
		:_data(x)
		,_prev(nullptr)
		,_next(nullptr)
	{
	}
};

	template<class T>
	struct __list_iterator
	{
		typedef list_node<T> Node;
		Node* _node;

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

		T& operator*()
		{
			return _node->_data;
		}

		//不能实现，因为const __list_iterator对象才能调用这个重载
		//但是const __list_iterator对象不能调用++
		/*const T& operator*() const
		{
			return _node->_data;
		}*/

		__list_iterator<T>& operator++()
		{
			_node = _node->_next;
			return *this;
		}

		__list_iterator<T> operator++(int)
		{
			__list_iterator<T> tmp(*this);
			_node = _node->_next;
			return tmp;
		}

		__list_iterator<T>& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

		__list_iterator<T> operator--(int)
		{
			__list_iterator<T> tmp(*this);
			_node = _node->_prev;
			return tmp;
		}

		bool operator!=(const __list_iterator<T>& it) const
		{
			return _node != it._node;
		}

		bool operator==(const __list_iterator<T>& it) const
		{
			return _node == it._node;
		}
	};

//要使用该模板实现const迭代器 就要给模板加上对应的参数 来控制
//封装*Node 因为结点的指针解引用不是数据而是结点 结点的指针++不是下一个数据
//所以要封装重载 * ++ -> != 这些操作
template<class T,class Ref,class Ptr>
struct _list_iterator
{
	typedef list_node<T> Node;
	//self就是iterator<>这样能更好的维护代码 如果要添加参数只需要在模板这里该就行 不需要一个个的去改
	typedef _list_iterator<T, Ref, Ptr> Self;

	Node* _node;

	//给迭代器初始化 这里的迭代器相当于就是一个结点 所以我们管理的是一个结点
	_list_iterator(Node* node)
		:_node(node)
	{}
	
	//重载operator* 要求解引用拿到的是结点的数据
	Ref operator*()//引用返回支持修改  改成了Ref就由上层决定是返回T* 还是const T*
	{
		return _node->_data;
	}

	//operator++ 要求走到下一个结点 前置++ 
	Self& operator++()
	{
		_node = _node->_next;
		return *this;
	}

	//后置加加 这里一定是浅拷贝传值返回
	Self operator++(int)
	{
		Self tmp(_node);
		_node = _node->_next;
		return tmp;
		
	}

	//重载operator-> 返回的是数据的地址 所以要再加一个模板参数Ptr 为T*或const T* 由上层决定
	Ptr operator->()
	{
		return &_node->_data;
	}

	//前置--
	Self& operator--()
	{
		_node = _node->_prev;
		return _node;
	}

	Self operator--(int)
	{
		Self tmp(*this);
		_node = _node->_prev;
		return tmp;
	}

	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;
	typedef _list_iterator<T, const T&,const T*> const_iterator;
		
//为什么在链表中返回begin()end()因为只有链表知道头和尾
	iterator begin()
	{
		//使用迭代器来构造_head的next指针
		return iterator(_head->_next);
	}

	iterator end()
	{
		return iterator(_head);
	}

	const_iterator begin() const 
	{
		return const_iterator(_head->_next);
	}

	const_iterator end() const 
	{
		return const_iterator(_head);
	}
private:
	Node* _head;
	size_t _size=0;
};

//空链表的处理
void empty_initial()
{
	_head = new Node;
	_head->_next = _head;
	_head->_prev = _head;
}


//list自己的默认构造
list()
{
	empty_initial();
}

//lit1(lit2) 拷贝构造
//在类内部还支持直接写list不带模板参数 但是最好带上 
list(list<T>& li)
{
	//给空链表初始化
	empty_initial();
	for (const auto& e : li)
	{
		push_back(e);
	}
}

//初始化列表初始化
list(initializer_list<T> il)
{
	empty_initial();
	for (const auto& e : il)
	{
		push_back(e);
	}
}


void swap(list<T>& lt)
{
	std::swap(_head, lt._head);
	std::swap(_size, lt._size);
}

//现代写法
// lt1 = lt3
//list& operator=(list lt)
list<T>& operator=(list<T> lt)
{
	swap(lt);

	return *this;
}


//赋值重载
//list& operator=(list lt)  lit1=lit3
list<T>& operator=(const list<T>& lt)
{
	if (this != &lt)
	{
		clear();
		for (const auto& e : lt)
		{
			push_back(e);
		}
	}
	return *this;
}

~list()
{
	clear();
	delete _head;
	_head = nullptr;
}

void clear()
{
	//使用迭代器 不再使用老传统遍历链表一个结点一个结点的删除
	iterator it = begin();
	while(it!=end())
	{
		//这里为了防止迭代器失效 要更新it
		it=erase(it);
	}
}

	iterator insert(iterator pos, const T& val)
	{
		//在pos前插入一个结点 知道prev  newnode cur结点最后连接就行
		Node* newnode = new Node(val);
		Node* cur = pos._node;
		Node* prev = cur->_prev;
			
		prev->_next = newnode;
		newnode->_next = cur;

		newnode->_prev = prev;
		cur->_prev = newnode;
		++_size;

		//返回迭代器
		return iterator(newnode);
		}

	iterator erase(iterator pos)
	{
		//删除pos前的结点 也是一样知道  prev  pos  next
		Node* cur = pos._node;
		Node* prev = cur->_prev;
		Node* next = cur->_next;

		prev->_next = next;
		next->_prev = prev;

		delete cur;
		--_size;

		//返回下一个迭代器 避免迭代器失效
		return next;//或者直接返回next 走隐式类型转化
	}

//下面的头插尾插、头删尾删，复用上面的代码
	void push_back(const T& x)
	{
		insert(end(),x);
	}
	void push_front(const T& x)
	{
		insert(begin(), x);
	}

	void pop_back()
	{
		erase(--end());
	}

	void pop_front()
	{
		erase(begin());
	}
	size_t size() const
	{
			/*size_t n = 0;
			for (auto& e : *this)
			{
				++n;
			}
			return n;*/
		//直接返回成员变量 该成员变量在插入删除时会自动更改
		return _size;
	}