Introduction and mock implementation of list:list

-----------"Don't ask if you can,Just say whether you want it or not"

---

(1)list是什么？

1.listcan be in the constant range,Insert anywhere、删除数据.

2.list底层是双向循环链表.

3.list相对于(vector\string)插入数据,简单高效

4.但list不支持随机访问.

        

---

(2)listfunction and its use:

①构造函数

构造函数	说明
list()	构造空的list
list (size_type n, const value_type& val = value_type())	构造的list中包含n个值为val的元素
list (const list& x)	拷贝构造函数
list (InputIterator fifirst, InputIterator last)	用[fifirst, last)区间中的元素构造list

---

② 迭代器

迭代器	说明
begin+end	返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin + rend	返回第一个元素的reverse_iterator,即end位置,返回最后一个元素下一个位置的reverse_iterator,即begin位置

---

 ③修改:

函数声明	说明
push_front	在list首元素前插入值为val的元素
pop_front	删除list中第一个元素
push_back	在list尾部插入值为val的元素
pop_back	删除list中最后一个元素
insert	在list position 位置中插入值为val的元素
erase	删除list position位置的元素
swap	交换两个list中的元素
clear	清空list中的有效元素

Most of the functions have already been introduced,Just stop here. 

---

 (3)list模拟实现:

list基本框架:

---

①<重>list迭代器: 

 

//迭代器
	template<class T>
	struct _list_iterator
	{
		//Let the node be here again Rename inside the struct
		typedef _list_node<T> node;
		//Some operations are involved
		typedef _list_iterator<T> self;  
		node* _pnode;   //list迭代器 本质就是个 节点指针


		_list_iterator(const node* pnode)
			:_pnode(pnode)
		{}

		//*
		T& operator* ()
		{
			return _pnode->_val;
		}

		//重载!=
		bool operator!=(const self& s)
		{ 
			//两个地址不一样
			return _pnode != s._pnode;
		}

	   //前置++
		self& operator++()
		{
			_pnode = _pnode->_next;
			return *this;
		}

		//后置++
		self operator++(int)
		{
			node* tmp = _pnode;
			_pnode = _pnode->_next;
			return tmp;
		}

		//前置--
		self& operator--()
		{
			_pnode = _pnode->_prev;
			return *this;
		}

		//后置
		self operator--()
		{
			node* tmp = _pnode;
			_pnode = _pnode->_prev;
			return tmp;
		}

	};

 对listThe iterator laying framework is perfect,Simply insert.

 

Let's start by inserting a few numbers at the end;

Iterators can also be used normally. 

迭代器模板！！！:

void PrintList(const list<int>& lt)
	{
		list<int> ::iterator it = lt.begin();
		while (it != lt.end())
		{
			*it += 1;
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}

At this point we encapsulate a printlist内容的函数,

此时出现报错,The current reason may be out of useconst迭代器. 

 

所以我们在list内 更新迭代器.

 At this point the code has changed,但问题是,Can actually be modifiedconst修饰的对象？！ This is definitely more than what we want.

 问题出在:

 所以,Just go and start again 单独创建一个const_iterator 才能实现.

然而,This would be too complicated,constIterator and notconstIterators are only in one place 不同.

 最后:

	template<class T,class Ref,class Ptr>
	struct _list_iterator
	{
		//Let the node be here again Rename inside the struct
		typedef _list_node<T> node;
		//Some operations are involved
		typedef _list_iterator<T, Ref,	Ptr>  self;  
		node* _pnode;   //list迭代器 本质就是个 节点指针


		_list_iterator(node* pnode)
			:_pnode(pnode)
		{}

		//*
		T& operator*()
		{
			return _pnode->_val;
		}

		//重载!=
		bool operator!=(const self& s)
		{ 
			//两个地址不一样
			return _pnode != s._pnode;
		}

	   //前置++
		self& operator++()
		{
			_pnode = _pnode->_next;
			return *this;
		}

		//后置++
		self operator++(int)
		{
			node* tmp = _pnode;
			_pnode = _pnode->_next;
			return tmp;
		}

		//前置--
		self& operator--()
		{
			_pnode = _pnode->_prev;
			return *this;
		}

		//后置
		self operator--(int)
		{
			node* tmp = _pnode;
			_pnode = _pnode->_prev;
			return tmp;
		}
	};

Each will find its own corresponding part. 

 listThe hard part is the iterators,搞定 这部分,Subsequent operations are as easy as the palm of your hand

---

②属性:

size:

链表的size有两种方法:

1.计数++

size_t size()
		{
			size_t count = 0;
			const_iterator it = begin();
			while (it != end())
			{
				count++;
				it++;
			}
			return count++;
		}

2.定义类成员变量,动态增加. 

empty:

	bool empty()
		{
		    //最初 头节点 pointers point to themselves
			return begin() == end();  
		}

---

③修改:

push_back:

void push_back(const T& x)
		{
			node* newnode = new node(x);  //创建节点
			//尾插链接
			node* tail = _head->_prev;

			tail->_next = newnode;
			newnode->_prev = tail;

			newnode->_next = _head;
			_head->_prev = newnode;
		}

push_front\pop_front\pop_backwill be reused(insert\erase),

Insert:

		void Insert(iterator pos, const T& x)
		{
			assert(pos._pnode);
			//pos是迭代器 不是node
			node* cur = pos._pnode;
			node* prev = cur->_prev;
			node* newnode = new node(x);
			//newnode 链接在prev cur 之间

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

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

		}

 

 erase:

iterator erase(iterator pos)
		{
			assert(pos._pnode);
			node* cur = pos._pnode;
			node* prev = cur->_prev;
			node* next = cur->_next;

			delete cur;
			prev->_next = next;
			next->_prev = prev;
	       //Returns an iterator for the next node
			return iterator(next);  //用next 去构造

		}

pop\push: 

	void push_back(const T& x)
		{
			//node* newnode = new node(x);  //创建节点
			尾插链接
			//node* tail = _head->_prev;

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

---

 ④Construct and delete:

destructor cleanup：

	void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				//erase(it++);
				it=erase(it);
			}
		}
		~list()
		{
			clear();
			delete _head; 
			_head = nullptr;
		}

 

拷贝构造与赋值重载:

	//拷贝构造
		//l2(l1);
		list(const list<T>& lt)
		{
			//构造头节点
			_head = new node();
			_head->_next = _head;
			_head->_prev = _head;

			//Tail in sequence
			for (const auto& c : lt)
			{
				//Not referencing is copy construction
				push_back(c);
			}
		}

	 

		list<T>& operator=(list<T> v)
		{
			swap(_head,v._head);
			return *this;
		}

		//s1=s2;
		//传统写法
		list<T>& operator=(list<T>& v)
		{
			if (this != &v)
			{
			//Clean yourself first
			clear();
			//Insert the value again
			for (const auto& c : v)
				{
					push_back(c);
				}
		}
		return *this;
		}

构造:

          
       //数值构造
		list(size_t n, const T& val)
		{
		 	_head = new node();  //首先创建头节点
			_head->_prev = _head;
	 		_head->_next = _head;   //指针指向自己 
 
			while (n--)
			{
				push_back(val);
			}
	  	  }
 

 //迭代区间
		list(iterator first, iterator last)
		{
			_head = new node();  //首先创建头节点
			_head->_prev = _head;
			_head->_next = _head;   //指针指向自己 

			while (first != last)
			{
				push_back(*first);
				first++;
			}
		}

---

这篇listThe short essay is over,希望对你有帮助

祝你好运~