STL中List的模拟实现

本次所需实现的三个类及其成员函数接口总览

//链表的节点
struct list_node
{
	list_node* _next;
	list_node* _prev;
	T _val;
};
//链表的迭代器类
template<class T,class Ref,class ptr>
struct list_iterator
{
	typedef list_iterator<T,Ref,ptr> self;
	typedef list_node<T> Node;
	Node* _node;
}
//链表
template<class T>
class list
{
	typedef list_node<T> Node;
public:
	//显示实例化
	typedef list_iterator<T, T&, T*> iterator;
	typedef const list_iterator<T, const T&, const T*> const_iterator;
private：
Node*_head;

结点类的模拟实现
我们经常说list在底层实现时就是一个链表，更准确来说，list实际上是一个带头双向循环链表。

因此，我们若要实现list，则首先需要实现一个结点类。而一个结点需要存储的信息有：数据、前一个结点的地址、后一个结点的地址，于是该结点类的成员变量也就出来了（数据、前驱指针、后继指针）。

节点类的实现：

template <class T>
struct list_node
{
	list_node* _next;
	list_node* _prev;
	T _val;
	list_node(const T& val=T())
		:_next(nullptr)
		,_prev(nullptr)
		,_val(val)
	{}
};

迭代器类的实现

之前我们在实现string,vector的时候我们迭代器都没有都是他们的原生指针，在这边为什么要封装成一个类呢？首先string,vector他们本质上是一个数组，在空间上是连续的，我们指针++一个以后就到了下一个元素的位置。因此我们可以使用原生指针来实现。

链表的迭代器实现，首先我们得知道我们遍历链表的时候通常是cur->next;cur++是不能实现的，因为链表在空间上不是连续的。我们需要使用运算符重载来给它封装起来，使他在上层看起来使用是一样的

struct list_iterator
{
	typedef list_iterator<T,Ref,ptr> self;
	typedef list_node<T> Node;
	Node* _node;
	list_iterator(Node*node)
		:_node(node)
	{}
	bool operator!=(self it)
	{
		return _node != it._node;
	}
	bool operator==(self it)
	{
		return _node == it._node;
	}
	Ref operator*()
	{
		return _node->_val;
	}
	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;
	}
	ptr operator->()
	{
		return &_node->_val;
	}


};

list的模拟实现

默认成员函数
构造函数
list是一个带头双向循环链表，在构造一个list对象时，直接申请一个头结点，并让其前驱指针和后继指针都指向自己即可。

class list
{
	typedef list_node<T> Node;
public:
	//显示实例化
	typedef list_iterator<T, T&, T*> iterator;
	typedef const list_iterator<T, const T&, const T*> const_iterator;
	list()
	{
		_head = new Node;
		_head->_next = _head;
		_head->_prev = _head;
	}
	list(const list<T>& lt)
	{
		_head = new Node;
		_head->_next = _head;
		_head->_prev = _head;
		for (auto& e : lt)
		{
			push_back(e);
		}
	}
	~list()
	{
		clear();
		delete _head;
		_head = nullptr;
	}
	void clear()
	{
		list<T>::iterator it = begin();
		while (it != end())
		{
			it = erase(it);
		}
	}
	
	size_t size()
	{
		list<T>::iterator it = begin();
		size_t count = 0;
		while (it != end())
		{
			count++;
			++it;
		}
		return count;
	}
	//现代写法
	list<T>&operator=(list<T>lt)
	{
		swap(lt);
		return *this;
	}
	void push_back(const T& val)
	{
		Node* newnode = new Node(val);
		Node* tail = _head->_prev;
		tail->_next = newnode;
		newnode->_prev = tail;
		newnode->_next = _head;
		_head->_prev = newnode;
	}
	iterator insert( iterator pos,const T& val)
	{
		Node* cur = pos._node;
		Node* prev = cur->_prev;
		Node* newnode = new Node(val);
		prev->_next = newnode;
		newnode->_prev = prev;
		newnode->_next = cur;
		cur->_prev = newnode;
		return newnode;
	}
	void push_front(const T val)
	{
		insert(begin(), val);
	}
	void swap(list<T>& lt)
	{
		std::swap(_head, lt._head);
	}
	iterator erase( iterator pos)
	{
		assert(pos != end());
		Node* cur = pos._node;
		Node* prev = cur->_prev;
		Node* next = cur->_next;
		prev->_next = next;
		next->_prev = prev;
		delete cur;
		cur = nullptr;
		return next;
	}
	void pop_front()
	{
		erase(begin());
	}
	void pop_back()
	{
		erase(--end());
	}
	iterator begin()
	{
		return _head->_next;
	}
	iterator end()
	{
		return _head;
	}
	const_iterator begin()const
	{
		return _head->_next;
	}
	const_iterator end()const
	{
		return _head;
	}
	private:
	Node* _head;
};