devbox
小丑西瓜9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【C++】-- STL之list模拟实现_仿照stl模板库中的list容器,制作一个属于自己的基本链表容器,实现以下功能

作者：小丑西瓜9 | 2024-04-10 09:26:14

赞

踩

仿照stl模板库中的list容器,制作一个属于自己的基本链表容器,实现以下功能

目录

一、list模拟实现思路 

二、节点类的实现

三、list迭代器的实现

1._list_iterator类

2.构造函数

3.operator* 运算符重载

4.operator-> 运算符重载

5.operator!= 运算符重载

6.operator==运算符重载

7.前置++

8.后置++

9.前置--

10.后置--

四、list类的实现

1.list类 

2.构造函数

3.拷贝构造

4.赋值运算符重载

（1）传统的赋值运算符重载

（2）现代的赋值运算符重载

5.析构

6.迭代器

7.insert( ) 

8.erase( )

9.clear( )

10.push_front( )

11.push_back( )

12.pop_front( )

13.pop_back( )

14.empty( )

15 size( )

五、完整代码段

一、list模拟实现思路 

list链表的模拟实现，与前面的string和vector相比，略复杂一点：

（1）由于链表节点本身就是一个结构体，包含数据域、指针域。 将节点的相关操作放入节点类进行处理，逻辑更清晰

（2）string和vector的元素在空间上是连续分布的，迭代器++就能指向下一个元素，但list的迭代器不行，它的每个元素在空间上都不连续，要访问下一个节点必须找到当前节点的next，因此list的迭代器必须重写

链表主要模拟实现以下功能：

 

为了和库里面的list区分开，使用命名空间delia将 list类和库里list隔离开

  1. namespace delia
  2. {
  3. }

二、节点类的实现

节点类的成员变量有3个：

（1）节点值_val

（2）指向前一个节点的指针_prev

（3）指向后一个节点的指针_next 

节点无需拷贝构造、赋值运算符重载，由于没有额外申请空间，因此也不需要析构

  1. 	template<class T>
  2. 	struct _list_node
  3. 	{
  4.         //3个成员变量
  5. 		T _val;
  6. 		_list_node<T>* _next;
  7. 		_list_node<T>* _prev;
  8.  
  9.         //构造函数
  10. 		_list_node(const T& val = T())
  11. 			:_val(val) 
  12. 			, _prev(nullptr)
  13. 			, _next(nullptr)
  14. 		{};	
  15. 	};

三、list迭代器的实现

由于节点的指针原生行为不满足迭代器定义，在这里，迭代器通过类来封装节点的指针重载运算符，如operator*、operator->、operator++等。用迭代器封装节点指针的思路不关心容器底层结构是数组、链表还是树等数据结构，都封装隐藏了底层细节，可以用一种统一的方式去访问、修改容器。

迭代器分为普通迭代器和const迭代器，对于_list_iterator类要实现两个版本，一个是普通的_list_iterator，另一个是const版本的_list_const_iterator，区别在于：对于两个类中的部分函数有普通函数和const函数之分（如begin( )和end( )），其他并无区别。因为这两个类的大部分代码相似，会造成代码冗余，如何解决呢？

对于T&，类模板实例化出两个类，一个是T&类，一个是const T&类，同理，T*也一样。使用 

template<class T,class Ref,class Ptr>

类模板就会实例化出来两个类，一个是普通的不带const的T，T&， T*，另一个是带const的T，const T&， const T*，其中Ref是引用，Ptr是指针，该类模板实例化了以下这两个类模板：

  1. template _list_iterator<T, T&, T*> _iterator;
  2. template _list_iterator<T, const T&, const T*> const_iterator;

这就解决了需要写两个类的问题。 

1._list_iterator类

迭代链表的节点，只需要一个成员变量即节点 

  1.     template<class T,class Ref,class Ptr>
  2. 	struct _list_iterator//使用_list_iterator类来封装node*
  3. 	{
  4. 		typedef _list_node<T> node;
  5. 		typedef _list_iterator<T,Ref,Ptr> self;
  6.  
  7. 		node* _pnode;//成员变量
  8.     }

2.构造函数

只需要初始化节点即可 

  1. 		//构造函数
  2. 		_list_iterator(node* pnode)
  3. 			:_pnode(pnode)
  4. 		{}

拷贝构造、赋值运算符重载、析构函数，编译器默认生成即可

3.operator* 运算符重载

  1. 		//解引用，返回左值，是拷贝，因此要用传引用返回
  2. 		Ref operator*()
  3. 		{
  4. 			return _pnode->_val;
  5. 		}

4.operator-> 运算符重载

  1. 		//结构体指针解引用，返回节点值的指针
  2. 		Ptr operator->()
  3. 		{
  4. 			return &_pnode->_val;
  5. 		}

5.operator!= 运算符重载

  1. 		//!=重载
  2. 		bool operator!=(const self& s) const
  3. 		{
  4. 			return _pnode != s._pnode;
  5. 		}

6.operator==运算符重载

  1. 		//==重载
  2. 		bool operator==(const self& s) const
  3. 		{
  4. 			return _pnode == s._pnode;
  5. 		}

7.前置++

让迭代器走到下一个节点 

  1. 		//前置++  it.operator(&it)
  2. 		self& operator++()
  3. 		{
  4. 			_pnode = _pnode->next;
  5. 			return *this;
  6. 		}

8.后置++

  1. 		//后置++ 返回++之前的值  it.operator(&it,0)
  2. 		self operator++(int)//需构造临时对象，临时对象不能用引用返回，所以self没有加&
  3. 		{
  4. 			self tmp(*this);
  5. 			_pnode = _pnode->_next;
  6. 			return tmp;
  7. 		}

9.前置--

让迭代器走到前一个节点 

  1. 		//前置--  it.operator(&it)
  2. 		self& operator--()
  3. 		{
  4. 			_pnode = _pnode->prev;
  5. 			return *this;
  6. 		}

10.后置--

  1. 		//后置-- 返回--之前的值  it.operator(&it,0)
  2. 		self operator--(int)//需构造临时对象，临时对象不能用引用返回，所以self没有加&
  3. 		{
  4. 			self tmp(*this);
  5. 			_pnode = _pnode->_prev;
  6. 			return tmp;
  7. 		}

四、list类的实现

1.list类 

list的成员只需要一个头节点，通过迭代器访问其他节点元素

  1. 	template<class T>
  2. 	class list
  3. 	{
  4. 		typedef _list_node<T> node;
  5. 	public:
  6. 		typedef _list_iterator<T,T&,T*> iterator;//重命名迭代器
  7. 		typedef _list_iterator<T, const T&, const T*> const_iterator;//重命名const迭代器
  8. 	private:
  9. 		node* _head;
  10. 	};

2.构造函数

  1. 		list()
  2. 		{
  3. 			_head = new node;//会调_list_node的构造函数
  4. 			_head->_next = _head;//整个链表只有头节点，先构造一个没有实际节点的链表
  5. 			_head->_prev = _head;//整个链表只有头节点，先构造一个没有实际节点的链表
  6. 		}

3.拷贝构造

创建一个空链表，再把参数链表节点的值一个一个尾插进去

  1. 		//拷贝构造 lt1(lt)
  2. 		list(const list<T>& lt)
  3. 		{
  4. 			//1.先构造一个只有头节点的空list：创建头节点，头节点的前一个是自己，头节点的后一个是自己
  5. 			_head = new node;
  6. 			_head->_next = _head;
  7. 			_head->_prev = _head;
  8.  
  9. 			//2.将lt的元素全部尾插到新链表
  10. 			for (const auto& e : lt)
  11. 			{
  12. 				push_back(e);
  13. 			}
  14. 		}

4.赋值运算符重载

（1）传统的赋值运算符重载

  1.         //赋值运算符重载  lt1 = lt  传统写法
  2. 		list<T> operator=(const list<T>& lt)
  3. 		{
  4.             //链表已存在，只需将节点尾插进去即可
  5. 			if(this != lt)
  6. 			{
  7. 				for (auto& e : lt)
  8. 				{
  9. 					push_back(e);
  10. 				}
  11. 			}
  12. 		}

（2）现代的赋值运算符重载

  1. 		list<T>& operator=(list<T>& lt)
  2. 		{
  3. 			swap(_head, lt->_head);
  4. 			return *this;
  5. 		}

其中，swap( )函数的执行过程如下：  

  1. template <class T> void swap ( T& a, T& b )
  2. {
  3.   T c(a); a=b; b=c;
  4. }

在执行赋值运算符重载时，会调用拷贝构造函数执行深拷贝，然后再交换两个链表头节点的指针，把this要释放的资源交给临时对象，临时对象出了swap的函数作用域就被this要释放的资源也会被同时释放。

5.析构

（1）清除所有节点内容

（2）删除头节点，链表就销毁了 

  1. 		//析构
  2. 		~list()
  3. 		{
  4. 			clear();//先清除所有节点内容
  5. 			delete _head;//再删除头节点
  6. 			_head = nullptr;
  7. 		}

6.迭代器

（1）普通迭代器

  1. 		iterator begin()
  2. 		{
  3. 			return iterator(_head->_next);//头节点不存数据
  4. 		}
  5.  
  6. 		iterator end()
  7. 		{
  8. 			return iterator(_head);//尾节点的下一个节点位置即头节点
  9. 		}

 （2）const迭代器

  1. 		const_iterator begin() const
  2. 		{
  3. 			return const_iterator(_head->_next);//头节点不存数据
  4. 		}
  5.  
  6. 		const_iterator end() const
  7. 		{
  8. 			return const_iterator(_head);//尾节点的下一个节点位置即头节点
  9. 		}

7.insert( ) 

（1）构造节点

（2）双向带头循环链表插入节点

  1.         //插入节点		
  2.         void insert(iterator pos, const T& x)
  3. 		{
  4. 			assert(pos._pnode);
  5. 			node* newnode = new node(x);//构造节点
  6.  
  7. 			node* prev = pos._pnode->_prev;//为方便后续操作，给插入位置的前一个节点起了个名字，pos是迭代器对象
  8.             
  9.             //插入节点
  10. 			newnode->_next = pos._pnode;
  11. 			pos._pnode->_prev = newnode;
  12. 			prev->_next = newnode;
  13. 			newnode->_prev = prev;
  14.  
  15. 		}

8.erase( )

（1）删除节点

（2）更新指针指向 

  1. 		//删除节点
  2.         iterator erase(iterator pos)
  3. 		{
  4. 			assert(pos._pnode);//判断该位置节点是否存在
  5. 			assert(pos != end());//end()是最后一个节点的下一个节点位置，也就是头节点，头节点不能删，需要断言
  6.  
  7. 			node* prev = pos._pnode->_prev;//pos位置节点的前一个节点
  8. 			node* next = pos._pnode->_next;//pos位置节点的后一个节点
  9.             
  10.             //删除节点
  11. 			delete pos._pnode;
  12. 			prev->_next = next;
  13. 			next->_prev = prev;
  14.  
  15. 			return iterator(next);//删除之后pos失效，把下一个位置的迭代器给它
  16. 		}

9.clear( )

只清除所有节点内容，不能删除头节点，如果删除头节点那么链表就不存在了，是链表的析构函数需要完成的操作

  1. 		void clear()
  2. 		{
  3. 			iterator it = begin();
  4. 			while (it != end())
  5. 			{
  6. 				erase(it++);//erase需要传参迭代器，即位置
  7. 			}
  8. 		}

10.push_front( )

 头插

  1.         //头插		
  2.         void push_front(const T& x)
  3. 		{
  4. 			insert(begin(), x);
  5. 		}

11.push_back( )

尾插

  1. 		//尾插
  2. 		void push_back(const T& x)
  3. 		{
  4. 			insert(end()--, x);	
  5. 		}

12.pop_front( )

头删

  1. 		//头删
  2. 		void pop_front()
  3. 		{
  4. 			erase(begin());
  5. 		}

13.pop_back( )

尾删

  1. 		//尾删
  2. 		void pop_back()
  3. 		{
  4. 			erase(--end());
  5. 		}

14.empty( )

判空 

  1. 		//判空
  2.         bool empty()
  3. 		{
  4. 			return end() == begin();
  5. 		}

15 size( )

求节点个数

  1. 		//求节点个数
  2.         size_t size()
  3. 		{
  4. 			iterator it = begin();
  5. 			size_t sz = 0;
  6. 			while (it != end())//时间复杂度O(N)
  7. 			{
  8. 				it++;
  9. 				sz++;
  10. 			}
  11.  
  12. 			return sz;
  13. 		}

五、完整代码段

016-list.h 

  1. #pragma once
  2. #include<iostream>
  3. #include<assert.h>
  4. using namespace std;
  5.  
  6. namespace delia
  7. {
  8. 	template<class T>
  9. 	struct _list_node
  10. 	{
  11. 		T _val;
  12. 		_list_node<T>* _prev;
  13. 		_list_node<T>* _next;
  14.  
  15. 		_list_node(const T& val = T())
  16. 			:_val(val) 
  17. 			, _prev(nullptr)
  18. 			, _next(nullptr)
  19. 		{};	
  20. 	};
  21.  
  22.  
  23. 	//节点的指针原生行为不满足迭代器定义，在这里，迭代器通过类来封装节点的指针重载运算符来控制
  24.  
  25. 	//对于T&，类模板实例化出两个类，一个是T&类，一个是const T&类，同理，T*也一样。
  26. 	//使用template<class T,class Ref,class Ptr>类模板就会实例化出来两个类，一个是T,T&, T*的，一个是T,const T&, const T*的	 
  27. 	//template _list_iterator<T, T&, T*> _iterator;
  28. 	//template _list_iterator<T, const T&, const T*> const_iterator;
  29. 	
  30. 	//这样就不需要再去定义一个如下const的迭代器类：
  31. 	//template<class T>
  32. 	//struct _list_const_iterartor
  33. 	//{
  34. 	//	typedef _list_node<T> node;
  35. 	//	typedef _list_const_iterartor<T> self;
  36.  
  37. 	//	node* _pnode;
  38. 	//}
  39. 	// 
  40. 	
  41. 	template<class T,class Ref,class Ptr>
  42. 	struct _list_iterator//使用_list_iterator类来封装node*
  43. 	{
  44. 		typedef _list_node<T> node;
  45. 		typedef _list_iterator<T,Ref,Ptr> self;
  46.  
  47. 		node* _pnode;
  48.  
  49. 		//构造函数
  50. 		_list_iterator(node* pnode)
  51. 			:_pnode(pnode)
  52. 		{}
  53.  
  54. 		//拷贝构造、赋值运算符重载、析构函数，编译器默认生成即可
  55.  
  56. 		//解引用，返回左值，是拷贝，因此要用引用返回
  57. 		Ref operator*()
  58. 		{
  59. 			return _pnode->_val;
  60. 		}
  61.  
  62. 		//结构体指针解引用，返回节点值的引用
  63. 		Ptr operator->()
  64. 		{
  65. 			return &_pnode->_val;
  66. 		}
  67.  
  68. 		//!=重载
  69. 		bool operator!=(const self& s) const
  70. 		{
  71. 			return _pnode != s._pnode;
  72. 		}
  73.  
  74. 		//==重载
  75. 		bool operator==(const self& s) const
  76. 		{
  77. 			return _pnode == s._pnode;
  78. 		}
  79.  
  80. 		//前置++  it.operator(&it)
  81. 		self& operator++()
  82. 		{
  83. 			_pnode = _pnode->_next;
  84. 			return *this;
  85. 		}
  86.  
  87. 		//后置++ 返回++之前的值  it.operator(&it,0)
  88. 		self operator++(int)
  89. 		{
  90. 			self tmp(*this);
  91. 			_pnode = _pnode->_next;
  92. 			return tmp;
  93. 		}
  94.  
  95. 		//前置--  it.operator(&it)
  96. 		self& operator--()
  97. 		{
  98. 			_pnode = _pnode->prev;
  99. 			return *this;
  100. 		}
  101.  
  102. 		//后置++ 返回++之前的值  it.operator(&it,0)
  103. 		self operator--(int)//临时对象不能用引用返回，所以self没有加&
  104. 		{
  105. 			self tmp(*this);
  106. 			_pnode = _pnode->_prev;
  107. 			return tmp;
  108. 		}
  109. 	};
  110.  
  111. 	template<class T>
  112. 	class list
  113. 	{
  114. 		typedef _list_node<T> node;
  115. 	public:
  116. 		typedef _list_iterator<T,T&,T*> iterator;//重命名迭代器
  117. 		typedef _list_iterator<T, const T&, const T*> const_iterator;//重命名const迭代器
  118.  
  119. 		//构造函数
  120. 		list()
  121. 		{
  122. 			_head = new node;//会调_list_node的构造函数
  123. 			_head->_next = _head;//整个链表只有头节点，先构造一个没有实际节点的链表
  124. 			_head->_prev = _head;//整个链表只有头节点，先构造一个没有实际节点的链表
  125. 		}
  126.  
  127. 		//拷贝构造 lt1(lt)
  128. 		list(const list<T>& lt)
  129. 		{
  130. 			//1.先构造一个只有头节点的空list：创建头节点，头节点的前一个是自己，头节点的后一个是自己
  131. 			_head = new node;
  132. 			_head->_next = _head;
  133. 			_head->_prev = _head;
  134.  
  135. 			//2.将lt的元素全部尾插到新链表
  136. 			for (const auto& e : lt)
  137. 			{
  138. 				push_back(e);
  139. 			}
  140. 		}
  141.  
  142. 		赋值运算符重载  lt1 = lt  传统写法
  143. 		//list<T>& operator=(list<T>& lt)
  144. 		//{
  145. 		//	if(this != lt)
  146. 		//	{
  147. 		//		for (auto& e : lt)
  148. 		//		{
  149. 		//			push_back(e);
  150. 		//		}
  151. 		//	}
  152. 		//}
  153. 		
  154. 		//赋值运算符重载  lt1 = lt  现代写法
  155. 		list<T>& operator=(list<T>& lt)
  156. 		{
  157. 			swap(_head, lt._head);
  158. 			return *this;
  159. 		}
  160.  
  161. 		//析构
  162. 		~list()
  163. 		{
  164. 			clear();
  165. 			delete _head;
  166. 			_head = nullptr;
  167. 		}
  168.  
  169. 		iterator begin()
  170. 		{
  171. 			return iterator(_head->_next);
  172. 		}
  173.  
  174. 		iterator end()
  175. 		{
  176. 			return iterator(_head);//尾节点的下一个节点位置即头节点
  177. 		}
  178.  
  179. 		const_iterator begin() const
  180. 		{
  181. 			return const_iterator(_head->_next);
  182. 		}
  183.  
  184. 		const_iterator end() const
  185. 		{
  186. 			return const_iterator(_head);//尾节点的下一个节点位置即头节点
  187. 		}
  188.  
  189. 		//插入节点
  190. 		void insert(iterator pos, const T& x)
  191. 		{
  192. 			assert(pos._pnode);
  193. 			node* newnode = new node(x);//构造节点
  194.  
  195. 			node* prev = pos._pnode->_prev;//为方便后续操作，给插入位置的前一个节点起了个名字，pos是迭代器对象
  196.  
  197. 			//插入节点
  198. 			newnode->_next = pos._pnode;
  199. 			pos._pnode->_prev = newnode;
  200. 			prev->_next = newnode;
  201. 			newnode->_prev = prev;
  202.  
  203. 		}
  204.  
  205. 		//删除节点
  206. 		iterator erase(iterator pos)
  207. 		{
  208. 			assert(pos._pnode);//判断该位置节点是否存在
  209. 			assert(pos != end());//end()是最后一个节点的下一个节点位置，也就是头节点，头节点不能删，需要断言
  210.  
  211. 			node* prev = pos._pnode->_prev;//pos位置节点的前一个节点
  212. 			node* next = pos._pnode->_next;//pos位置节点的后一个节点
  213.  
  214. 			//删除节点
  215. 			delete pos._pnode;
  216. 			prev->_next = next;
  217. 			next->_prev = prev;
  218.  
  219. 			return iterator(next);//删除之后pos失效，把下一个位置的迭代器给它
  220. 		}
  221.  
  222. 		void clear()
  223. 		{
  224. 			iterator it = begin();
  225. 			while (it != end())
  226. 			{
  227. 				erase(it++);
  228. 			}
  229. 		}
  230.  
  231. 		//头插
  232. 		void push_front(const T& x)
  233. 		{
  234. 			insert(begin(), x);
  235. 		}
  236.  
  237. 		//尾插
  238. 		void push_back(const T& x)
  239. 		{
  240. 			insert(end()--, x);	
  241. 		}
  242.  
  243. 		//头删
  244. 		void pop_front()
  245. 		{
  246. 			erase(begin());
  247. 		}
  248.  
  249. 		//尾删
  250. 		void pop_back()
  251. 		{
  252. 			erase(--end());
  253. 		}
  254. 		
  255. 		//判空
  256. 		bool empty()
  257. 		{
  258. 			return _head->_next == _head;
  259. 		}
  260. 		
  261. 		//求节点个数
  262. 		size_t size()
  263. 		{
  264. 			iterator it = begin();
  265. 			size_t sz = 0;
  266. 			while (it != end())//时间复杂度O(N)
  267. 			{
  268. 				it++;
  269. 				sz++;
  270. 			}
  271.  
  272. 			return sz;
  273. 		}
  274. 	private:
  275. 		node* _head;
  276. 	};
  277.  
  278. 	void PrintList(const list<int>& lt)
  279. 	{
  280. 		list<int>::const_iterator it = lt.begin();
  281. 		while (it != lt.end())
  282. 		{
  283. 			cout << it._pnode->_val << " ";
  284. 			it++;
  285. 		}
  286. 		cout << endl;
  287. 	}
  288.  
  289. 	void test_list1()
  290. 	{
  291. 		list<int> l1;
  292. 		l1.push_back(5);
  293. 		l1.push_back(8);
  294. 		l1.push_back(20);
  295. 		l1.push_back(9);
  296.  
  297. 		PrintList(l1);
  298.  
  299. 		list<int> l2;
  300. 		l2 = l1;
  301. 		PrintList(l2);
  302.  
  303. 		cout << endl;
  304. 	}
  305. }

016-test.cpp

  1. #include "016-list.h"
  2. #include<list>
  3. using namespace std;
  4.  
  5. int main()
  6. {
  7. 	delia::test_list1();
  8. 	return 0;
  9. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小丑西瓜9/article/detail/397854
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号