【C++从青铜到王者】第十三篇:STL之list类的模拟实现

柔情只为你懂 2022-08-30 00:53 108阅读 0赞

![在这里插入图片描述][20210717235742797.gif_pic_center]

# 系列文章目录 #

--------------------

### 文章目录 ###

*  系列文章目录
 *  前言
 *  一、list的模拟实现
 *  二、list与vector之间的对比
 *  总结

--------------------

# 前言 #

--------------------

# 一、list的模拟实现 #

#include<iostream>
    #include<assert.h>
    #pragma once
    namespace yyw
    { 
    	template<class T>
    	struct _list_node
    	{ 
    		_list_node<T>* _next;
    		_list_node<T>* _prev;
    		T _data;
    
    		_list_node(const T& val = T())
    			:_next(nullptr)
    			, _prev(nullptr)
    			, _data(val)
    		{ }
    	};
    
    	template<class T,class Ref,class Ptr>
    	struct _list_iterator
    	{ 
    		typedef _list_node<T> Node;
    		typedef _list_iterator<T, Ref, Ptr> Self;
    
    		Node* _node;
    
    		_list_iterator(Node* node)
    			:_node(node)
    		{ }
    
    		//*it,返回_data
    		Ref operator*()
    		{ 
    			return _node->_data;
    		}
    		//it->date
    		Ptr operator->()
    		{ 
    			return &_node->_data;
    		}
    		//it++,返回还是一个迭代器,前置加加
    		Self& operator++()
    		{ 
    			_node = _node->_next;
    			return *this;
    		}
    		//前置--
    		Self& operator--()
    		{ 
    			_node = _node->_prev;
    			return *this;
    		}
    		//后置加加
    		Self operator++(int)
    		{ 
    			Self tmp(*this);  //创建临时变量返回，后置加加，加加之前不变
    			//_list_iterator<T>tmp = *this;
    			_node = _node->_next;
    			//++（*this)
    			return tmp;
    		}
    		//后置减减
    		Self operator--(int)
    		{ 
    			Self tmp(*this);
    			_node = _node->_prev;
    			return tmp;
    		}
    
    		//==
    		bool operator ==(const Self& it)
    		{ 
    			return _node = it._node;
    		}
    		//it!=end()
    		bool operator!=(const Self& it)
    		{ 
    			return _node != it._node;
    		}
    	};
    
    	template<class T>
    	class list
    	{ 
    	public:
    		typedef _list_node<T> Node;
    	public:
    		typedef _list_iterator<T,T&,T*> iterator;
    		typedef _list_iterator<T,const T&,const T*> const_iterator;
    		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);
    		}
    
    
    		//带头双向循环链表
    		list()                      //list的构造
    		{ 
    			_head = new Node;
    			_head->_next = _head;
    			_head->_prev = _head;
    		} 
    
    		//l2(l1)
    		list(const list<T>& l1)            //拷贝构造
    		{ 
    			//链表的最初状态
    			_head = new Node;
    			_head->_next = _head;
    			_head->_prev = _head;
    
    			//const_iterator it = l1.begin(); //构造一个const迭代器尾插到新的迭代器中
    			//while (it != l1.end())
    			//{ 
    			// this->push_back(*it);
    			// it++;
    			//}
    
    			for (auto e : l1)
    			{ 
    				push_back(e);
    			}
    		}
    
    		list<T>& operator=(const list<T>& l1)
    		{ 
    			if (this != &l1)
    			{ 
    				clear();
    				for (auto e : l1)
    				{ 
    					push_back(e);
    				}
    			}
    			return *this;
    		}
    		
    		//现代版的拷贝构造
    		//list<T>& operator=(list<T> l1)
    		//{ 
    		// swap(_head, l1._head);
    		// return *this;
    		//}
    		void clear()
    		{ 
    			iterator it = begin();
    			while (it != end())
    			{ 
    				erase(it++);         //erase要自己单独实现出来
    			}
    		}
    		~list()                      //析构函数
    		{ 
    			clear();                 //clear没有删除头结点
    			delete _head;
    			_head = nullptr;
    		}
    
    		size_t size()  const
    		{ 
    
    		}
    		bool empty() const
    		{ 
    			return _head->_next == _head->_prev;
    		}
    		//T x 如果T类型是vector或者是string就造成了深拷贝,那么就得传引用，传引用不改变x就加const
    		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 insert(iterator pos, const T& x)    //在pos这个迭代器的前面插入一个节点
    		{ 
    			Node* newnode = new Node(x);
    			//pos 是个迭代器,而迭代器又是节点的指针，所以可以通过迭代器找到这个节点
    			Node* cur = pos._node;
    			Node* prev = cur->_prev;
    			
    			prev->_next = newnode;
    			newnode->_prev = prev;
    			newnode->_next = cur;
    			cur->_prev = newnode;
    			//return iterator(newnode);
    		}
    
    		void pop_back()
    		{ 
    			erase(--end());
    		}
    		void pop_front()
    		{ 
    			erase(begin());//end是最后一个有效数据的下一个位置，所以end先减减，删除end减减的位置
    		}
    		void erase(iterator pos)
    		{ 
    			//pos是一个迭代器，节点的指针，可以找到这个节点
    			//找到要删除的节点del
    			assert(pos != end());//头结点不能删除
    			Node* del = pos._node;
    			Node* next = del->_next;
    			//假设有1 2 3节点，要删除pos位置2节点，
    			//先2节点的前一个节点1节点的下一个节点指向2指向的3节点
    			//然后要把3和1链接起来，把3的前一个节点指向1，
    			//2的下一个节点3节点的前一个节点指向2的前一个节点
    			//删除2
    			del->_prev->_next = del->_next; 
    			del->_next->_prev = del->_prev;
    			delete del;
    			//return iterator(next);//返回节点的下一个位置
    		}
    	private:
    		Node* _head;
    	};
    	void testlist1()
    	{ 
    		list<int> lt1;
    		lt1.push_back(1);
    		lt1.push_back(2);
    		lt1.push_back(10);
    		lt1.push_back(20);
    		lt1.pop_back();
    		list<int>::iterator it = lt1.begin();
    		while (it != lt1.end())
    		{ 
    			std::cout << *it << " ";
    			++it;
    		}
    		std::cout << std::endl;
    	}
    	struct Date
    	{ 
    		int _year = 0;
    		int _month = 1;
    		int _day = 1;
    	};
    
    	void print_list(const list<int>& lt1)
    	{ 
    		list<int>::const_iterator it = lt1.begin();
    		while (it != lt1.end())
    		{ 
    			std::cout << *it << " ";
    			it++;
    		}
    		std::cout << std::endl;
    	}
    	void testlist2()
    	{ 
    		list<Date> lt1;
    		lt1.push_back(Date());
    		lt1.push_back(Date());
    		list<Date>::iterator it = lt1.begin();
    		while (it != lt1.end())
    		{ 
    			/*std::cout << *it << " ";*/
    			//it->Date->_year 
    			std::cout << it->_year << ":" << it->_month << ":" << it->_day << std::endl;
    			std::cout << (*it)._year << ":" << (*it)._month << ":" << (*it)._day << std::endl;
    			++it;
    		}
    		//print_list(lt1);
    	}
    	void testlist3()
    	{ 
    		list<int> l1;
    		l1.push_back(1);
    		l1.push_back(2);
    		l1.push_back(3);
    		l1.push_back(4);
    		
    		list<int>l2(l1); //拷贝构造，用l1拷贝构造l2
    		for (auto e : l1)
    		{ 
    			std::cout << e << " ";
    		}
    		std::cout << std::endl;
    		for (auto e : l2)
    		{ 
    			std::cout << e << " ";
    		}
    		std::cout << std::endl;
    	}
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 5]

# 二、list与vector之间的对比 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 7]

--------------------

# 总结 #

**以上就是今天要讲的内容，本文介绍了list类模拟实现和vector类的对比，而list类提供了大量能使我们快速便捷地处理数据的函数和方法，非常的便捷，所以我们务必掌握。另外如果上述有任何问题，请懂哥指教，不过没关系，主要是自己能坚持，更希望有一起学习的同学可以帮我指正，但是如果可以请温柔一点跟我讲，爱与和平是永远的主题，爱各位了。**  
![在这里插入图片描述][2021071723573432.gif_pic_center]

[20210717235742797.gif_pic_center]: /images/20220829/065467b3b7034362bf0f348dd451bf4d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70]: /images/20220829/517f2579a6e04205beaae2f785a320ae.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 1]: /images/20220829/530d5b0449db44eda901ac81f64d5134.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 2]: /images/20220829/5bc417499d2b4da28f2952fe154cce66.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 3]: /images/20220829/57d52bf3b8324d75b8379ccb802fa11d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 4]: /images/20220829/7691cd78b40f4b059fbb053a50b829b8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 5]: /images/20220829/bad42b05be7c47ecbbc0aab8b1405d30.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 6]: /images/20220829/c6242e6552fd479d9ca62fb9cb0a80e3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 7]: /images/20220829/b9aabdcdc9394d65848606638b13ad86.png
[2021071723573432.gif_pic_center]: /images/20220829/0b6c277f297b4ffa9242029b589498e9.png