目录

list的逻辑结构

构造函数

拷贝构造函数

赋值运算符重载

返回迭代器的初始位置

返回迭代器的最终位置

 元素的插入

头插

尾插 

删除元素

头删

尾删

清空整个链表

析构函数

正向迭代器 

反向迭代器

整体代码 

---

 上期我们学写了list的基本操作，本期我们将学习list的模拟实现。

list的逻辑结构

list是一个带头结点的双向循环链表。

构造函数

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

 这是一个无参的构造函数。

        template<class inputiterator>
		list(inputiterator begin, inputiterator end)
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
			while (begin != end)
			{
				push_back(*begin);
				++begin;
			}
		}

这是用迭代器区间进行初始化的构造函数。

		list(int n, const T& data = T())
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
			while (n != 0)
			{
				push_back(data);
				n--;
			}
		}

 初始化链表的n个节点，使它们的每个结点的数据为data的值。

拷贝构造函数

	    list(const list<T>& lt)
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;

			list<T> tmp(lt.begin(), lt.end());
			std::swap(_head, tmp._head);
		}

这是拷贝构造函数的现代写法，通过使用迭代器区间构造函数构造了一个list的临时对象，然后交换了临时对象和当前对象的头结点指针，前提是得保证当前结点的头指针不为空，不然到时候调用析构函数时会将同一空间释放两次，导致出错。

赋值运算符重载

	    list<T>& operator= (const list<T>lt)
		{
			std:swap(_head,lt._head);
			return *this;
		}

 先通过拷贝构造函数生成了一个临时对象，然后再交换了临时对象和当前对象的头结点指针。

返回迭代器的初始位置

	iterator begin()
		{
			return  iterator(_head->_next);
		}

迭代器的初始位置就是头结点的下一位置。

返回迭代器的最终位置

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

迭代器的最终位置为最后一个元素的下一位置，即头结点的位置。

 元素的插入

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

 表示在当前位置之前插入一个元素，但是当前位置必须为迭代器类型。

元素的插入会导致迭代器失效吗？
不会，因为插入元素之后会及时更改迭代器中节点指针的指向。 

头插

        void push_front(const T& x)
		{
			insert(begin(), x);
		}

	

在头节点之前插入元素，复用了插入函数。 

尾插 

	    void push_back(const T& x)
		{
			insert(end(), x);
		}

在最后一个元素的后面插入元素，复用了插入函数。

删除元素

		iterator erase(iterator pos)
		{
			//前提是不能删除掉头结点

			assert(pos != end());
			Node* prev =pos._node->_prev;
			Node* next = pos._node->_next;
			delete pos._node;
			pos._node = nullptr;
			prev->_next = next;
			next->_prev = prev;
			return iterator(next);
		}

删除某一位置之后，返回的是当前位置的下一位置的迭代器。 

元素的删除会导致迭代器失效吗？
会，因为删除掉当前位置之后，当前迭代器的节点指针会被释放。迭代器的节点都被释放了，所以迭代器自然会失效。

头删

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

尾删

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

清空整个链表

		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				erase(it);
				it++;
			}
		}

删除除头结点之外的所有节点。 

析构函数

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

		}

析构函数会清空整个链表的信息，所以头结点指针也会被释放。

正向迭代器 

正向迭代器，其实就是从前往后进行链表元素的遍历。

	template<class T,class Ref,class Ptr>
	struct list_iterator
	{
		typedef ListNode<T> Node;
		typedef list_iterator<T, Ref, Ptr> self;

		//构造函数
		list_iterator<T,Ref,Ptr>(Node* node)
			:_node(node)
		{
		}
		//解引用操作
		Ref operator*()    
		{
			return _node->_data;
		}

		//->操作，返回迭代器中的节点指针指向的数据的地址
		Ptr 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;
		}
		//赋值运算符重载，浅拷贝
		self& operator=(const self& iterator)
		{
			_node = iterator._node;
			return *this;
		}
		//判断是否相等
		bool operator ==(const self& iterator) const
		{
			return _node == iterator._node;
		}

		bool operator !=(const self& iterator) const

		{
			return _node != iterator._node;
		}
		Node* _node;

		
	};

list的迭代器和vector的迭代器是不同的，vector的迭代器类型是指针类型，即内置类型。而list的迭代器类型是自定义类型。

反向迭代器

反向迭代器即从后往前进行链表元素的遍历。

namespace yjd {
	template<class iterator,class Ref,class Ptr>
	class reverse_iterator
	{
	public:
		typedef reverse_iterator<iterator, Ref, Ptr> self;
		//构造函数
		reverse_iterator(iterator it)
			:_it(it)
		{
		}
		//解引用操作
		Ref operator*()
		{
			iterator prev = _it;
			return *(--prev);
		}

		//->
		Ptr operator->()
		{
			iterator prev = _it;
			return &(--prev);

		}

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

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

		//判断是否相等
		bool  operator!=(const self & rit) const
		{
			return  _it != rit._it;
		}
	private:
		iterator _it;
	};

}

正向迭代器和返现迭代器的开始和结束位置刚好是相对的。反向迭代器的本质仍然是正向迭代器。反向迭代器的++为正向迭代器的--。

虽然说返现迭代器的开始和结束如图如上图所示，但是我们真正在访问的时候并不是访问所示位置的元素，而是访问其前一个位置的元素，比如要访问rbgin位置的元素，则要让正向迭代器进行--访问最后一个位置的元素。 

整体代码 

list.h

#pragma once
#include<assert.h>
#include"reverse_iterator.h"
namespace yjd 
{
	//节点类型
	template<class T>
	struct ListNode {
		 ListNode* _next;
		 ListNode* _prev;
		T _data;
		ListNode(const T& data=T())
			:_next(nullptr)
			,_prev(nullptr)
			,_data(data)
		{
		}
	};

	//链表的迭代器类型
	template<class T,class Ref,class Ptr>
	struct list_iterator
	{
		typedef ListNode<T> Node;
		typedef list_iterator<T, Ref, Ptr> self;

		//构造函数
		list_iterator<T,Ref,Ptr>(Node* node)
			:_node(node)
		{
		}
		//解引用操作
		Ref operator*()    
		{
			return _node->_data;
		}

		//->操作，返回迭代器中的节点指针指向的数据的地址
		Ptr 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;
		}
		//赋值运算符重载，浅拷贝
		self& operator=(const self& iterator)
		{
			_node = iterator._node;
			return *this;
		}
		//判断是否相等
		bool operator ==(const self& iterator) const
		{
			return _node == iterator._node;
		}

		bool operator !=(const self& iterator) const

		{
			return _node != iterator._node;
		}
		Node* _node;

		
	};



	//链表类型
	template<class T>
	class list 
    {
		typedef ListNode<T> Node;
      public:
		typedef list_iterator<T, T&, T*> iterator;
		typedef list_iterator<T, const T&, const T*> const_iterator;
		typedef reverse_iterator<iterator, T&, T*> reverse_iterator;
		typedef reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;
		//构造函数
		list()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}

		//构造函数，迭代器区间进行构造
		template<class inputiterator>
		list(inputiterator begin, inputiterator end)
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
			while (begin != end)
			{
				push_back(*begin);
				++begin;
			}
		}

		//拷贝构造
		list(const list<T>& lt)
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;

			list<T> tmp(lt.begin(), lt.end());
			std::swap(_head, tmp._head);
		}

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

		//构造函数n个data
		list(int n, const T& data = T())
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
			while (n != 0)
			{
				push_back(data);
				n--;
			}
		}


		//尾插
		//void push_back(const T& data)
		//{
		//	Node* newnode = new Node(data);
		//	Node* tail = _head->_prev;
		//	tail->_next = newnode;
		//	newnode->_prev = tail;
		//	newnode->_next = _head;
		//	_head->_prev = newnode;
		//}
		// 
	


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

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

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

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

	

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

		//元素的插入,在pos位置之前插入元素
		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);
		}

		//list的头插和尾插，可以复用insert,插入元素之后我们更改的是节点的指针，所以不会涉及到迭代器失效
		void push_front(const T& x)
		{
			insert(begin(), x);
		}

		void push_back(const T& x)
		{
			insert(end(), x);
		}

		//链表删除某一位置元素，删除某一位置的元素，迭代器会失效吗？会失效，因为删除掉元素之后，会释放节点的指针，节点的指针都被释放了，迭代器自然也就没有意义了
		iterator erase(iterator pos)
		{
			//前提是不能删除掉头结点

			assert(pos != end());
			Node* prev =pos._node->_prev;
			Node* next = pos._node->_next;
			delete pos._node;
			pos._node = nullptr;
			prev->_next = next;
			next->_prev = prev;
			return iterator(next);
		}

		//list的尾删头删
		void pop_back()
		{
			erase(--end());
		}

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

		//list整个的删除，这个删除是删除所有的有效的节点
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				erase(it);
				it++;
			}
		}

		//析构函数
		~list()
		{
			clear();
			delete _head;
		    _head = nullptr;

		}

	private:
		Node* _head;

	};



	
}

reverse_iterator.h

#pragma once

 namespace yjd {
	template<class iterator,class Ref,class Ptr>
	class reverse_iterator
	{
	public:
		typedef reverse_iterator<iterator, Ref, Ptr> self;
		//构造函数
		reverse_iterator(iterator it)
			:_it(it)
		{
		}
		//解引用操作
		Ref operator*()
		{
			iterator prev = _it;
			return *(--prev);
		}

		//->
		Ptr operator->()
		{
			iterator prev = _it;
			return &(--prev);

		}

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

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

		//判断是否相等
		bool  operator!=(const self & rit) const
		{
			return  _it != rit._it;
		}
	private:
		iterator _it;
	};

}

以上便是list模拟实现的所有知识点。

本期内容到此结束^_^