C++——list类及其模拟实现

前言：这篇文章我们继续进行C++容器类的分享——list，也就是数据结构中的链表，而且是带头双向循环链表。

一.基本框架

namespace Mylist
{
	template<class T>
	//定义节点
	struct ListNode
	{
		ListNode<T>* _next;
		ListNode<T>* _prev;
		T _data;

		ListNode(const <T>& x = T())
			:_next(nullptr)	
			,_prev(nullptr)
			,_data(x)
		{}
	};
	template<class T>
	class list
	{
		typedef ListNode<T> Node;
	public:
		//构造函数
		list()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}
		//析构函数
		~list()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
			delete _head;
			_head = nullptr;
		}
		//数据个数
		size_t size()
		{
			iterator it = begin();
			size_t Size = 0;
			while (it != end())
			{
				Size++;
				it++;
			}
			return Size;
		}
	private:
		Node* _head;
	};
}

由于要满足存储任意类型的数据，所以我们必须要使用模版来进行定义。 

迭代器

关于list类中的最难之处，就是迭代器了。

因为迭代器的原理即为指针，对于string和vector这种创建的对象的物理空间是连续的类来说，我们可以直接对迭代器进行“++”、“–”等数学运算。

而对于本质为链表的list来说，由于每个节点的物理空间都是随机创建，各个节点的地址并不连续，所以我们没法直接进行迭代器的数学运算，而需要对迭代器的各种功能进行重新定义，所以我们创建一个专门为迭代器服务的类：

	//迭代器
	template<class T>
	struct ListIterator
	{
		typedef ListNode<T> Node;
		typedef ListIterator<T> Self;

		ListIterator(Node* node)
			:_node(node)
		{}
		//解引用
		T& operator*()
		{
			return _node->_data;
		}
		//前置++
		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;
		}
		//不相等
		bool operator!=(const Self& it)
		{
			return _node != it._node;
		}
		//相等
		bool operator==(const Self& it)
		{
			return _node == it._node;
		}
		Node* _node;
	};

随后在list类中将该类名重定义为iterator，便可正常使用迭代器了：

		typedef ListIterator<T> iterator;
		iterator begin()
		{
			return _head->_next;
		}
		iterator end()
		{
			return _head;
		}

 这里值得注意的是，因为是带头双向循环链表，所以链表的开始即哨兵位的下一个，而结尾就是哨兵位。

但是现在的迭代器是存在问题的，它并不能实现对const修饰的数据的操作，所以我们还需要一个const迭代器。因为我们的普通迭代器就是用模版来实现的，所以这里可以直接通过模版来实现const迭代器：

	//迭代器
	template<class T,class Ref>
	struct ListIterator
	{
		typedef ListNode<T> Node;
		typedef ListIterator<T,Ref> Self;
		//构造函数
		ListIterator(Node* node)
			:_node(node)
		{}
		//解引用
		Ref operator*()
		{
			return _node->_data;
		}
		//前置++
		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;
		}
		//不相等
		bool operator!=(const Self& it)
		{
			return _node != it._node;
		}
		//相等
		bool operator==(const Self& it)
		{
			return _node == it._node;
		}
		Node* _node;
	};

		typedef ListIterator<T，T&> iterator;
		typedef ListIterator<T,const T&> const_iterator;

这里有一个细节，因为T同时还要服务于Node类，所以不能直接对其进行修改，而是另用一个模版参数。 

 因为const对象与非const对象最大的不同之处在于对数据的访问，所以定义一个名为Ref（引用）的模版参数，来对解引用运算符重载函数进行改造。

二.常用操作

1.插入

先来看任意位置的插入，需要传入某个位置的指针pos：

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

			prev->_next = newnode;
			newnode->_next = cur;
			cur->_prev = newnode;
			newnode->_prev = prev;
		}

 现在对于我们来说就是非常简单，测试如下：

这里有一个小细节，如果我们插入的位置是第一个节点之前，由于it迭代器的指向并未改变，所以如果进行遍历，他就不会遍历出我们新插入的数据，所以需要更新一下it。

有了pos位置的插入之后，就可以用它来扩展头插和尾插：

		//尾插
		void push_back(const T& x)
		{
			insert(end(), x);
		}
		//头插
		void push_front(const T& x)
		{
			insert(begin, x);
		}

2.删除

我们同样先写出pos位置的删除：

		//pos删除
		iterator erase(iterator pos)
		{
			Node* cur = pos._node;
			Node* next = cur->_next;
			Node* prev = cur->_prev;

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

由于删除会导致迭代器成为野指针，所以我们要对其进行更新， 测试如下：

同样由其扩展出头删和尾删：

		//头删
		void pop_front()
		{
			erase(begin());
		}
		//尾删
		void pop_back()
		{
			erase(--end());
		}

3.拷贝

和string和vector一样，list的拷贝也需要使用深拷贝，那么它的拷贝构造函数该怎么写？

同样是要开辟新的空间，需要一个自己的头结点，随后按照被拷贝的链表的数据进行尾插即可：

		//拷贝构造
		list(const list<T>& lt)
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
			for (auto& e : lt)
			{
				push_back(e);
			}
		}

测试如下：

此外，还有“=”运算符重载的方法：

		//交换
		void swap(list<T>& it)
		{
			std::swap(_head, it._head);
		}
		//=运算符重载
		list<T>& operator=(list<T> lt)
		{
			swap(lt);
			return *this;
		}

这里仍然是巧妙的运用swap函数，因为lt是一个临时拷贝，有自己的空间和地址，所以直接让两者进行交换，lt在退出函数时即被销毁，而拷贝者则继承了它的地址空间，测试如下：

总结

关于list类的基本知识就分享到这里啦。

因为与string和vector都存在很多相似之处，所以建议将这三者放在一起学习。

喜欢本篇文章记得一键三连，下期再见！