模拟实现list

list模拟实现

• 框架
• 构造/析构
• • 构造函数
  • 使用迭代器初始化构造函数
  • 拷贝构造
  • 运算符重载
  • 析构函数
• 正向迭代器
• 增删查改
• • 重命名
  • begin/end
  • insert/erase
  • 头插/头删/尾插/尾删
  • clear
• 反向迭代器

上一篇博客介绍了list的各种函数接口以及使用，这篇博客在这里自己实现一个简单的list，进一步加深对list的了解。

框架

list和之前的vector不同，他是使用一个双向带头链接来进行数据存储的，因此需要先定义一个结构体来存放节点。

	template
	struct ListNode
	{
		ListNode* _next;
		ListNode* _prev;
		T _data;
		ListNode(const T& data = T())
			:_next(nullptr)
			,_prev(nullptr)
			,_data(data)
		{

		}
	};

list中的成员很简单，就是一个节点指针。

	template
	class list
	{
		typedef ListNode Node;
	private:
		Node* _head;
	};

构造/析构 构造函数

普通的构造函数很简单，就是创建一个头节点即可，需要注意一下的是，头节点为链表为空的时候前后指针都指向自己。

		list()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}

使用迭代器初始化构造函数

		template
		list(InputIterator first, InputIterator last)
		{
			_head = new Node();
			_head->_next = _head;
			_head->_prev = _head;
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

拷贝构造

这种方法是用上面的迭代器构造出一个tmp的list，然后将我们需要的list中的内容和tmp进行交换，tmp会在出作用域的时候自动销毁。

		list(const list& lt)
		{
			_head = new Node();
			_head->_next = _head;
			_head->_prev = _head;
			list tmp(lt.begin(), lt.end());
			std::swap(_head, tmp._head);
		}

或者
这种方法是在定义头节点后，将被拷贝的值一个个尾插入list当中。

		list(const list& lt)
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
			for (auto e : lt)
			{
				push_back(e);
			}
		}

运算符重载

这两种方法和上面拷贝构造的做法类似，但是需要注意一下的是这里的第二种方法，在尾插之前需要调用clear清空原有的数据，因此operator=是作用于已经构造出的对象，因此要清空原有内容。

		list& operator=(list lt)
		{
		 	_head = new Node();
			_head->_next = _head;
			_head->_prev = _head;
			
			std::swap(_head, lt._head);
			
			return *this;
		}

或者

		list& operator=(const list& lt)
		{
			if (this != <)
			{
				clear();
				for (auto e : lt)
				{
					push_back(e);
				}
			}
			return *this;
		}

析构函数

析构函数直接调用clear函数先清空对象中的内容，然后再释放头节点即可。

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

正向迭代器

这里的迭代器和vector不太一样，由于list是双向链表，因此迭代器可以很方便的实现正向和反向迭代器。
这里的模板参数里面的T,Ref和Ptr分别代表T，T&以及T*
这里的迭代器和vector的迭代器还有的区别在于list的空间不是连续的，因此++、–等操作需要进行运算符重载才能正常使用

	template
	struct __list_iterator
	{	
		typedef ListNode Node;
		typedef __list_iterator self;
		Node* _node;
		__list_iterator(Node* x)
			:_node(x)
		{

		}
		//迭代器的拷贝构造和赋值重载以及析构都不需要自己实现，默认生成的即可
		//节点属于链表，不属于迭代器，所以不管释放
		Ref operator*()
		{
			return _node->_data;
		}

		Ptr operator->()
		{
			return &_node->_data;
		}
		//++it
		self& operator++()
		{
			_node = _node->_next;
			return *this;
		}

		//it++
		self operator++(int)
		{
			self tmp(*this);
			_node = _node->_next;
			return tmp;
		}

		//--it
		self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

		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;
		}
	};

增删查改

在实现了迭代器之后我们可以比较方便的进行list的各种插入删除操作

重命名

为了让代码看起来更加简洁一下，我们将迭代器类进行重命名
分别有普通版本和const版本

	typedef __list_iterator iterator;
	typedef __list_iterator const_iterator;

begin/end

实现了迭代器后，访问list的头和尾的迭代器函数就很容易实现了
这里需要注意一下，end指向的是尾指针的下一个节点，双向循环链表尾指针的下一个节点就是头指针。

		iterator begin()
		{
			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);
		}

insert/erase

链表的中间位置的插入删除，在知道具体节点位置之后，插入删除操作很容易实现，这里唯一需要注意的是注意迭代器失效的问题即可。

		iterator insert(iterator pos, const T& x)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* newnode = new Node(x);
			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;
			return iterator(newnode);
		}
		//erase以后pos失效
		iterator erase(iterator pos)
		{
			assert(pos != end());
			Node* prev = pos._node->_prev;
			Node* next = pos._node->_next;
			delete pos._node;
			prev->_next = next;
			next->_prev = prev;
			return iterator(next);
		}

头插/头删/尾插/尾删

这里在实现了上面的中间位置的插入删除后，直接使用begin/end位置的复用插入/删除即可。

		void push_back(const T& x)
		{
			//Node* tail = _head->_prev;
			//Node* newnode = new Node(x);
			//tail->_next = newnode;
			//newnode->_prev = tail;
			//newnode->_next = _head;
			//_head->_prev = newnode;
			insert(end(), x);
		}

		void push_front(const T& x)
		{
			insert(begin(), x);
		}
		void pop_back()
		{
			erase(--end());
		}

		void pop_front()
		{
			erase(begin());
		}

clear

清空数据内容，仅剩头节点

		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				iterator del = it++;
				delete del._node;
			}
			_head->_next = _head;
			_head->_prev = _head;
		}

反向迭代器

之前我们就了解过，迭代器除了正向迭代器以外还有反向迭代器，实现的功能和正向迭代器相反，这里我们模拟实现一个list的反向迭代器
这里传入的模板参数分别为迭代器、T&和T*也就是说反向迭代器是在正向迭代器的基础上进行相反的操作实现的。

template
	class reverse_iterator
	{
		typedef reverse_iterator self;
	public:
		reverse_iterator(Iterator it)
			:_it(it)
		{

		}

		Ref operator*()
		{
			Iterator prev = _it;
			return *--prev;
		}

		Ptr operator->()
		{
			return &operator*();
		}

		self& operator++()
		{
			--_it;
			return *this;
		}

		self& operator--()
		{
			++_it;
			return *this;
		}
		
		bool operator==(const self& rit) const 
		{
			return _it == rit._it;
		}

		bool operator!=(const self& rit) const
		{
			return _it != rit._it;
		}

	private:
		Iterator _it;
	};

这里反向迭代器的需要实现的功能和正向的类似，需要注意++、–的操作和正向迭代器的相反即可。
在list类中的声明以及函数实现

typedef reverse_iterator const_reverse_iterator;

typedef reverse_iterator reverse_iterator;
		reverse_iterator rbegin()
		{
			return reverse_iterator(end());
		}

		reverse_iterator rend()
		{
			return reverse_iterator(begin());
		}

		const_reverse_iterator rbegin() const
		{
			return const_reverse_iterator(end());
		}

		const_reverse_iterator rend() const
		{
			return const_reverse_iterator(begin());
		}