STL list的主要接口模拟实现

STL-list是什么

STL里面的list本质上就是一个双向带头循环链表,如果不知道什么是双链表的话可以去看看这篇文章双链表
就像下面这种C语言双链表结构

只不过在这个原有的基础之上添加了增删查改的功能，让他变得更高级更实用
相当于把这个list封装了一遍，让我们可以调用他的接口，更加方便快捷，下面我们来看看具体怎么实现

list的模拟实现

在list里面有点麻烦的就是他的迭代器，这个和string还有vector的迭代器有点不一样，他的内存空间不是连续的，我们不能随机访问
所以我们把list分为3个部分写成两个struct和一个class，（struct的默认是公有的，这样我们在调用迭代器，还有创建节点的时候会方便一**些不像class默认是私有的）第一个是节点，这里定义了节点的数据域，还有指向前驱和后继指针的指针域，第二个是迭代器，这里我们可以简单的把迭代器理解成一个指针，用来对list进行操作，**最后一个用来定义list本身。
下面我们看看代码

	template<class type>
	struct list_node
	{
		type data;
		list_node<type>* _next;
		list_node<type>* _prev;

		list_node(const type& val = type())
			:data(val)
			, _next(nullptr)
			, _prev(nullptr)
		{}
	};

这里就是节点本身有数据域和指针域，这里我们用了一个模板，让编译器自动推导，这样的好处是可以存放任何数据，使用性更加广泛，
这里我们用了初始化列表，来作为默认构造函数

list_node(const type& val = type())
			:data(val)
			, _next(nullptr)
			, _prev(nullptr)
		{}

**const type& val = type()**这里我们用了一个匿名对象来进行我们链表节点的构造，这样的好处就是，我们在构造节点的时候不用去手动去拿一个类去构造对象，这里的匿名对象自动去调用属于他自己的默认构造，列如int会去调用int的默认构造，匿名对象只在当前行起作用，出了当前行就自动销毁。

list的迭代器

	template<class type, class ref, class ptr>
	struct list_iterator
	{
		list_node<type>* _node;
		list_iterator(list_node<type>* node)
			:_node(node)
		{}
		list_iterator<type, ref, ptr>& operator++()
		{
			this->_node = _node->_next;
			return *this;
		}
		list_iterator<type, ref, ptr>& operator--()
		{

			this->_node = _node->_prev;
			return *this;
		}
		list_iterator<type, ref, ptr> operator++(int)
		{
			list_iterator<type, ref, ptr> temp = *this;
			this->_node = _node->_next;
			return temp;
		}
		list_iterator<type, ref, ptr> operator--(int)
		{
			list_iterator<type, ref, ptr> temp = *this;
			this->_node = _node->_prev;
			return temp;
		}
		// l1 != l2
		bool operator !=(list_iterator<type, ref, ptr> l2)
		{
			if (this->_node != l2._node)
			{
				return true;
			}
			else
			{
				return false;
			}
		}
		bool operator == (list_iterator<type, ref, ptr> l2)
		{
			return this->_node == l2._node;
		}
		ref operator*()
		{
			return this->_node->data;
		}
		ptr operator->()
		{
			&_node->data;
		}
	};

这里我们实现了主要的常用的迭代器的功能

template<class type, class ref, class ptr>

这里的定义的模板参数需要讲一下，这里，实现了类模板给编译器，给了编译器不同的参数，编译器实例化了两个不同的类第一个是type就是数据类型，下面这个ref就是引用,ptr就是指针，这样是为了方便const调用,ref,ptr具体是什么不用管，编译器会根据传的数据类型来推导创建相对应的类，传const引用就是const ref ,const ptr，不传就是普通指针，普通引用，如果不用模板，就要写两个非常相似的类，这样就太冗余了，非常麻烦

list_node<type>* _node;
		list_iterator(list_node<type>* node)
			:_node(node)
		{}

这里就是迭代器的默认构造，也是走的初始化列表，这里传了一个list_node类型的数据，也就是创建的节点来当构造参数，这里的迭代器我们可以把他理解成一个为我们list服务的专有指针，所以是list_node* _node类型，这个_node就是指针

list_iterator<type, ref, ptr>& operator++()
		{
			this->_node = _node->_next;
			return *this;
		}

这里就是实现迭代器++我们需要返回引用，因为要改变当前的迭代器的位置，这里的++不像vector还有string那样可以用原生指针，list的内存空间不连续，但他有指向前一个和下一个的指针

所以我们++就要返回当前迭代器指向的下一个地址就行了

list_iterator<type, ref, ptr>& operator--()
		{
			this->_node = _node->_prev;
			return *this;
		}

迭代器–也同理
下面是后置++迭代器，后置++，这里他会改变当前迭代器指向的位置，但会返回原来迭代器的位置，所以我们要创建一个temp变量来存放当前迭代器的值

	list_iterator<type, ref, ptr> operator++(int)
	{
		list_iterator<type, ref, ptr> temp = *this;
		this->_node = _node->_next;
		return temp;
	}

迭代器–也同理

	bool operator !=(list_iterator<type, ref, ptr> l2)
	{
		if (this->_node != l2._node)
		{
			return true;
		}
		else
		{
			return false;
		}
	}

这里是判断两个迭代器的是不是不相等的，用当前迭代器指向的位置来判断，
判断相等也同理

	bool operator == (list_iterator<type, ref, ptr> l2)
	{
		return this->_node == l2._node;
	}

这里是对*的运算符重载，返回当前迭代器下面的数据域，这里就体现模板的作用了，这里的ref是没有被定义的可以返回普通的，也可以是const的

ref operator*()
{
	return this->_node->data;
}

我们可以来试一下

这里迭代器就讲解完了，我们来说说list

list

下面是代码

template<class type, class ref, class ptr>
class list
{
public:
	void init_empty()
	{
		_head = new list_node<type>;
		_head->_next = _head;
		_head->_prev = _head;
		_size = 0;
	}
	list()
	{
		init_empty();
	}
	//l2(l1)
	list(const list<type, ref, ptr>& l1)
	{
		init_empty();
		list_iterator<type, const ref, const ptr> it = l1.const_begin();
		while (it.operator!=(l1.const_end()))
		{
			this->push_back(*it);
			it++;
		}
	}
	void swap(list<type, ref, ptr>& li)
	{
		std::swap(this->_head, li._head);
		std::swap(this->_size, li._size);
	}
	// l1                             l2
	list<type, ref, ptr>& operator=(list<type, ref, ptr>& li)
	{
		swap(li);
		return *this;
	}
	void clear()
	{
		auto it = this->begin();
		while (it != this->end())
		{
			it = this->erase(it);
		}
	}
	~list()
	{
		clear();
		delete this->_head;
		this->_head = nullptr;

	}
	list_iterator<type, ref, ptr> begin()
	{
		return _head->_next;
	}
	list_iterator<type, ref, ptr> end()
	{
		return _head;
	}
	list_iterator<type, const ref, const ptr> const_begin() const
	{
		return _head->_next;
	}
	list_iterator<type, const ref, const ptr> const_end() const
	{
		return _head;
	}
	//tail newnode head
	void push_back(const type& input)
	{
		list_node<type>* newnode = new list_node<type>(input);
		list_node<type>* tail = this->_head->_prev;

		newnode->_next = this->_head;
		newnode->_prev = tail;
		tail->_next = newnode;
		this->_head->_prev = newnode;
		_size++;
	}

	//pos newnode next
	void insert(list_iterator<type, ref, ptr> pos, const type& input)
	{
		list_node<type>* newnode = new list_node<type>(input);
		list_node<type>* next = pos._node->_next;
		list_node<type>* poser = pos._node;
		newnode->_next = next;
		newnode->_prev = poser;
		pos._node->_next = newnode;
		next->_prev = newnode;
		_size++;
	}
	// prev pos next
	list_iterator<type, ref, ptr> erase(list_iterator<type, ref, ptr> pos)
	{
		list_node<type>* poser = pos._node;
		list_node<type>* next = poser->_next;
		list_node<type>* prev = poser->_prev;
		delete poser;
		prev->_next = next;
		next->_prev = prev;

		return next;
	}

	void pop_fornt()
	{
		erase(this->begin());
	}
	void pop_back()
	{
		erase(this->end()--);
	}
	size_t size()
	{
		return this->_size;
	}
	size_t size() const
	{
		return this->_size;
	}
	bool is_empty()
	{
		return this->_size == 0;
	}
private:
	size_t _size;
	list_node<type>* _head;
};

这里，因为我们是双向循环带头链表，在初始化的时候就需要创建一个头节点，这个头节点不存放任何东西

void init_empty()
	{
		_head = new list_node<type>;
		_head->_next = _head;
		_head->_prev = _head;
		_size = 0;
	}

所以我们的默认构造函数，就要调用init_empty()来满足这个双向链表的结构特点

list()
{
	init_empty();
}

在有头节点之后，我们在进行对数据的插入，修改等
下面是拷贝构造函数

	//l2(l1)
	list(const list<type, ref, ptr>& l1)
	{
		init_empty();
		list_iterator<type, const ref, const ptr> it = l1.const_begin();
		while (it.operator!=(l1.const_end()))
		{
			this->push_back(*it);
			it++;
		}
	}

这个拷贝构造函数很巧妙，用了一个尾插来解决，把原始list里面的值复制一份拿下来，这里的必须是 const ref, const ptr，因为拷贝构造传的参数必须是const对类类型的对象的引用，这段代码用了迭代器来完成拷贝构造，it获取最先开始的位置，依次++直到最后一个迭代器位置

接下来就是赋值运算符重载

	// l1                             l2
	list<type, ref, ptr>& operator=(list<type, ref, ptr>& li)
	{
		swap(li);
		return *this;
	}
	void swap(list<type, ref, ptr>& li)
	{
		std::swap(this->_head, li._head);
		std::swap(this->_size, li._size);
	}

这里很巧妙，直接交换两个对象指向的指针，还有大小，就行了，假设把l2复制给l1，this指针是指向l1，交换完之后this就是指向l2了，当swap函数结束之后，l1会自动销毁，带走l1所指向的链表，直接返回*this就可以了,就完成了赋值，
下面是析构函数

		void clear()
		{
			auto it = this->begin();
			while (it != this->end())
			{
				it = this->erase(it);
			}
		}
		~list()
		{
			clear();
			delete this->_head;
			this->_head = nullptr;

		}

这里我们通过erase(it)这个函数来实现析构，这个函数就是删除当前节点函数，也是通过两个迭代器来控制区间，最后就是删除头节点
下面这些就是非常简单的小函数了，返回开始和结束的迭代器，还有const版本

list_iterator<type, ref, ptr> begin()
{
	return _head->_next;
}
list_iterator<type, ref, ptr> end()
{
	return _head;
}
list_iterator<type, const ref, const ptr> const_begin() const
{
	return _head->_next;
}
list_iterator<type, const ref, const ptr> const_end() const
{
	return _head;
}

下面我们来说说erase

list_iterator<type, ref, ptr> erase(list_iterator<type, ref, ptr> pos)
{
	list_node<type>* poser = pos._node;
	list_node<type>* next = poser->_next;
	list_node<type>* prev = poser->_prev;
	delete poser;
	prev->_next = next;
	next->_prev = prev;

	return next;
}

这里我们可以画图来理解一下

像push_back和insert可以看看开头给的文章链接，里面有更详细的讲解

	void pop_fornt()
	{
		erase(this->begin());
		_size--;
	}
	void pop_back()
	{
		erase(this->end()--);
		_size--;
	}
	size_t size()
	{
		return this->_size;
	}
	size_t size() const
	{
		return this->_size;
	}
	bool is_empty()
	{
		return this->_size == 0;
	}

这些小函数就不需要过多的讲解了删除头部，和删除尾部都可以调用erase来解决，判空可以判断_size是不是为0，size，我们在对链表中push_back ，insert, 等，里面都有对size进行统计，这样统计size更加方便，不用在去新写一个函数进行对size进行统计
print打印函数

template<class print_type>
void print(print_type& p1)
{
	list_iterator<int, int&, int*> it = p1.begin();
	while (it != p1.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
}

这里，我们创建了一个模板类，这里和上面一样可以传不同的数据类型进来进行打印，不同的数据类型实例化不同的类型，提高了函数的利用性
以上就是对list的主要接口的实现，如果有什么问题欢迎指正！
完