list的模拟实现

一.list的简单介绍

list是一个带头双向循环的链表，通过头结点分隔开首末尾。它和vector的使用方法类似，可以进行头插尾插，++/--等操作，区别在于list的结点在内存上不是连续的。list属于双向迭代器即可以++/--，不能想vector一样可以进行随机访问。

二.list模拟实现的三个类

1.结点类

根据list的特点带头双向循环，我们可以得知，他需要一个前置结点prev，以及后置结点next，保证能向前向后找到结点。 每个结点存有数据data，我们可以用模板T来进行复用。

  1. template <class T>
  2. 	struct list_node
  3. 	{
  4. 		list_node(const T& x = T())//模板有x时情况
  5. 		:_next(nullptr)
  6. 		,_prev(nullptr)
  7. 		,_data(x)
  8. 		{}
  9.  
  10. 		list_node* _next;
  11. 		list_node* _prev;
  12. 		T _data;
  13. 	};

 2.迭代器类

我们知道迭代器分为普通迭代器和const迭代器，在实现string类和vector类时我们并没有单独对迭代器这一类进行实现，这是因为vector和string类在底层空间上是连续的，可以直接进行++/--，解引用操作。但list在底层中是由指针来连接的，所以直接++/--解引用无法实现我们想要的效果。所以我们要单独提出迭代器对++/--解引用进行重载运算符操作。

  1. template<class T, class Ref, class Ptr>
  2. struct list_iterator
  3. {
  4. 	typedef list_node Node;
  5. 	typedef list_iterator Self;
  6. 	Node* _node;
  7.  
  8. 	list_iterator(Node* node)
  9. 		:_node(node)
  10. 	{}
  11.  
  12. 	T& operator*()
  13. 	{
  14. 		return _node->_data;
  15. 	}
  16.  
  17. 	T& operator++()//前置
  18. 	{
  19. 		_node = _node->_next;
  20. 		return *this;
  21. 	}
  22.  
  23. 	T& operator++(int)//后置,后置++区分前置要加入括号
  24. 	{
  25. 		Self tmp(*this);
  26. 		_node = _node->_next;
  27. 		return tmp;
  28. 	}
  29.  
  30. 	T& operator--()//前置
  31. 	{
  32. 		_node = _node->_prev;
  33. 		return *this;
  34. 	}
  35.  
  36. 	T& operator--(int)//前置
  37. 	{
  38. 		Self tmp(*this);
  39. 		_node = _node->_prev;
  40. 		return tmp;
  41. 	}
  42.  
  43. 	T* operator->()
  44. 	{
  45. 		return &_node->_data;
  46. 	}
  47.  
  48. 	bool operator!=(const T& it)
  49. 	{
  50. 		return _node != it._node;
  51. 	}
  52.  
  53. 	bool operator==(const T& it)
  54. 	{
  55. 		return _node == _it._node;
  56. 	}
  57. };

如上我们对迭代器进行了初步的实现，里面的实现内容较为简单就不一一展开叙述。这时候又有了另一个问题，如果迭代器是const类型的该怎么办呢？还是像上面这样，重新封装一个const_iterator类吗？

这样操作固然是没有问题的，但是还不够简略。

我们可以仔细想想，普通迭代器与const迭代器的区别不就是多了一个const吗？所以我们可以考虑用模板来套用实现。

  1. 	template<class T,class Ref,class Ptr>//提供模板参数，为const类型提供模板参数,ref代替引用，ptr代替*，复用
  2. 	struct list_iterator
  3. 	{
  4. 		typedef list_node Node;
  5. 		typedef list_iterator Self;
  6. 		Node* _node;
  7.  
  8. 		list_iterator(Node* node)
  9. 		:_node(node)
  10. 		{}
  11.  
  12. 		Ref operator*()
  13. 		{
  14. 			return _node->_data;
  15. 		}
  16.  
  17. 		Self& operator++()//前置
  18. 		{
  19. 			_node = _node->_next;
  20. 			return *this;
  21. 		}
  22.  
  23. 		Self operator++(int)//后置,后置++区分前置要加入括号
  24. 		{
  25. 			Self tmp(*this);
  26. 			_node = _node->_next;
  27. 			return tmp;
  28. 		}
  29.  
  30. 		Self& operator--()//前置
  31. 		{
  32. 			_node = _node->_prev;
  33. 			return *this;
  34. 		}
  35.  
  36. 		Self operator--(int)//前置
  37. 		{
  38. 			Self tmp(*this);
  39. 			_node = _node->_prev;
  40. 			return tmp;
  41. 		}
  42.  
  43. 		Ptr operator->()
  44. 		{ 
  45. 			return &_node->_data;
  46. 		}
  47.  
  48. 		bool operator!=(const Self& it)
  49. 		{
  50. 			return _node != it._node;
  51. 		}
  52.  
  53. 		bool operator==(const Self& it)
  54. 		{
  55. 			return _node == _it._node;
  56. 		}
  57. 	};

我们将原先的T&  用模板Ref来替代，T*  用模板Ptr来代替。这样就对代码进行了缩减。所以用ref和ptr模板我们就不需要关心是不是const类型迭代器，只要传就是什么，我们就无需关心。 

3.链表类

  1. template <class T>
  2. 	class list
  3. 	{
  4. 		typedef list_node Node;
  5. 	public:
  6. 		typedef list_iterator iterator;
  7. 		typedef list_iteratorconst T&, const T*> const_iterator;
  8.  
  9. 		iterator begin()
  10. 		{
  11. 			return list_iterator(_head->_next);
  12. 		}
  13.  
  14. 		iterator end()
  15. 		{
  16. 			return list_iterator(_head);
  17. 		}
  18.  
  19. 		void empty_init()
  20. 		{
  21. 			_head = new Node;
  22. 			_head->_prev = _head;
  23. 			_head->_next = _head;
  24. 		}
  25.  
  26. 		list()
  27. 		{
  28. 			empty_init();
  29. 		}
  30.  
  31. 		list(initializer_list it)
  32. 		{
  33. 			for (auto& e : it)
  34. 			{
  35. 				push_back(e);
  36. 			}
  37. 		}
  38.  
  39. 		list(const list& it)
  40. 		{
  41. 			empty_init();
  42. 			for (auto& e : it)
  43. 			{
  44. 				push_back(e);
  45. 			}
  46. 		}
  47.  
  48. 		~list()
  49. 		{
  50. 			clear();
  51. 		}
  52.  
  53. 		void swap(list& it)
  54. 		{
  55. 			std::swap(_head, it._head);
  56. 		}
  57.  
  58. 		list& operator=(list it)
  59. 		{
  60. 			swap(it);
  61. 			return *this;
  62. 		}
  63.  
  64. 		void clear()
  65. 		{
  66. 			iterator it = begin();
  67. 			while (it != end())
  68. 			{
  69. 				it = erase(it);
  70. 			}
  71. 		}
  72.  
  73. 		void push_back(const T& x)
  74. 		{
  75. 			Node* newnode = new Node(x);
  76.  
  77. 			Node* tail = _head->_prev;
  78. 			newnode->_prev = tail;
  79. 			tail->_next = newnode;
  80. 			newnode->_next = _head;
  81. 			_head->_prev = newnode;
  82. 		}
  83.  
  84. 		void push_front(const T& x)
  85. 		{
  86. 			insert(begin(), x);
  87. 		}
  88.  
  89. 		void push_back(const T& x)
  90. 		{
  91. 			insert(end(), x);
  92. 		}
  93.  
  94. 		void pop_front()
  95. 		{
  96. 			erase(begin());
  97. 		}
  98.  
  99. 		void pop_back()
  100. 		{
  101. 			erase(--end());
  102. 		}
  103.  
  104. 		void insert(iterator pos, const T& x)
  105. 		{
  106. 			Node* cur = pos._node;
  107. 			Node* prev = cur->_prev;
  108. 			Node* newnode = new Node(x);
  109. 			prev->_next = newnode;
  110. 			newnode->_prev = prev;
  111. 			cur->_prev = newnode;
  112. 			newnode->_next = cur;
  113. 		}
  114.  
  115. 		iterator erase(iterator pos)
  116. 		{
  117. 			assert(pos != end());
  118. 			Node* cur = pos._node;
  119. 			Node* nextNode = cur->_next;
  120. 			Node* prevNode = cur->_prev;
  121.  
  122. 			prevNode->_next = nextNode;
  123. 			nextNode->_prev = prevNode;
  124.  
  125. 			delete cur;
  126. 			return iterator(nextNode);
  127. 		}
  128.  
  129. 	private:
  130. 		Node* _head;
  131. 	};
  132. }

上述只需要注意一点，就是erase的用法。erase在官方库中是有返回值的，在使用时，例如析构时需要用变量来接收erase的返回值，否则容易导致迭代器失效。

链表部分的实现不难，基本都是先前vector类实现的功能相差无几，构造函数，拷贝函数，析构函数，迭代器的运用，以及增删等操作。

 三.总结

本篇文章最关键的内容就是对于模板的复用，在面对代码相似度较高，实现功能类似的情况下，我们需要优先考虑模板的复用。

下面放上完整代码：

  1. #pragma once
  2. #include 
  3. using namespace std;
  4.  
  5. namespace wu
  6. {
  7. 	template <class T>
  8. 	struct list_node
  9. 	{
  10. 		list_node(const T& x = T())//模板有x时情况
  11. 		:_next(nullptr)
  12. 		,_prev(nullptr)
  13. 		,_data(x)
  14. 		{}
  15.  
  16. 		list_node* _next;
  17. 		list_node* _prev;
  18. 		T _data;
  19. 	};
  20.  
  21. 	template<class T,class Ref,class Ptr>//提供模板参数，为const类型提供模板参数,ref代替引用，ptr代替*，复用
  22. 	struct list_iterator
  23. 	{
  24. 		typedef list_node Node;
  25. 		typedef list_iterator Self;
  26. 		Node* _node;
  27.  
  28. 		list_iterator(Node* node)
  29. 		:_node(node)
  30. 		{}
  31.  
  32. 		Ref operator*()
  33. 		{
  34. 			return _node->_data;
  35. 		}
  36.  
  37. 		Self& operator++()//前置
  38. 		{
  39. 			_node = _node->_next;
  40. 			return *this;
  41. 		}
  42.  
  43. 		Self operator++(int)//后置,后置++区分前置要加入括号
  44. 		{
  45. 			Self tmp(*this);
  46. 			_node = _node->_next;
  47. 			return tmp;
  48. 		}
  49.  
  50. 		Self& operator--()//前置
  51. 		{
  52. 			_node = _node->_prev;
  53. 			return *this;
  54. 		}
  55.  
  56. 		Self operator--(int)//前置
  57. 		{
  58. 			Self tmp(*this);
  59. 			_node = _node->_prev;
  60. 			return tmp;
  61. 		}
  62.  
  63. 		Ptr operator->()
  64. 		{ 
  65. 			return &_node->_data;
  66. 		}
  67.  
  68. 		bool operator!=(const Self& it)
  69. 		{
  70. 			return _node != it._node;
  71. 		}
  72.  
  73. 		bool operator==(const Self& it)
  74. 		{
  75. 			return _node == _it._node;
  76. 		}
  77. 	};
  78.  
  79. 	template <class T>
  80. 	class list
  81. 	{
  82. 		typedef list_node Node;
  83. 	public:
  84. 		typedef list_iterator iterator;
  85. 		typedef list_iteratorconst T&, const T*> const_iterator;
  86.  
  87. 		iterator begin()
  88. 		{
  89. 			return list_iterator(_head->_next);
  90. 		}
  91.  
  92. 		iterator end()
  93. 		{
  94. 			return list_iterator(_head);
  95. 		}
  96.  
  97. 		void empty_init()
  98. 		{
  99. 			_head = new Node;
  100. 			_head->_prev = _head;
  101. 			_head->_next = _head;
  102. 		}
  103.  
  104. 		list()
  105. 		{
  106. 			empty_init();
  107. 		}
  108.  
  109. 		list(initializer_list it)
  110. 		{
  111. 			for (auto& e : it)
  112. 			{
  113. 				push_back(e);
  114. 			}
  115. 		}
  116.  
  117. 		list(const list& it)
  118. 		{
  119. 			empty_init();
  120. 			for (auto& e : it)
  121. 			{
  122. 				push_back(e);
  123. 			}
  124. 		}
  125.  
  126. 		~list()
  127. 		{
  128. 			clear();
  129. 		}
  130.  
  131. 		void swap(list& it)
  132. 		{
  133. 			std::swap(_head, it._head);
  134. 		}
  135.  
  136. 		list& operator=(list it)
  137. 		{
  138. 			swap(it);
  139. 			return *this;
  140. 		}
  141.  
  142. 		void clear()
  143. 		{
  144. 			iterator it = begin();
  145. 			while (it != end())
  146. 			{
  147. 				it = erase(it);
  148. 			}
  149. 		}
  150.  
  151. 		void push_back(const T& x)
  152. 		{
  153. 			Node* newnode = new Node(x);
  154.  
  155. 			Node* tail = _head->_prev;
  156. 			newnode->_prev = tail;
  157. 			tail->_next = newnode;
  158. 			newnode->_next = _head;
  159. 			_head->_prev = newnode;
  160. 		}
  161.  
  162. 		void push_front(const T& x)
  163. 		{
  164. 			insert(begin(), x);
  165. 		}
  166.  
  167. 		void push_back(const T& x)
  168. 		{
  169. 			insert(end(), x);
  170. 		}
  171.  
  172. 		void pop_front()
  173. 		{
  174. 			erase(begin());
  175. 		}
  176.  
  177. 		void pop_back()
  178. 		{
  179. 			erase(--end());
  180. 		}
  181.  
  182. 		void insert(iterator pos, const T& x)
  183. 		{
  184. 			Node* cur = pos._node;
  185. 			Node* prev = cur->_prev;
  186. 			Node* newnode = new Node(x);
  187. 			prev->_next = newnode;
  188. 			newnode->_prev = prev;
  189. 			cur->_prev = newnode;
  190. 			newnode->_next = cur;
  191. 		}
  192.  
  193. 		iterator erase(iterator pos)
  194. 		{
  195. 			assert(pos != end());
  196. 			Node* cur = pos._node;
  197. 			Node* nextNode = cur->_next;
  198. 			Node* prevNode = cur->_prev;
  199.  
  200. 			prevNode->_next = nextNode;
  201. 			nextNode->_prev = prevNode;
  202.  
  203. 			delete cur;
  204. 			return iterator(nextNode);
  205. 		}
  206.  
  207. 	private:
  208. 		Node* _head;
  209. 	};
  210. }

注：本文转载自blog.csdn.net的打不了嗝的文章"https://blog.csdn.net/2401_86449430/article/details/145784183"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！