• C++ —— 模拟实现list

    目录

    1.链表节点的构建

    2.迭代器的初步实现

    3.成员变量以及默认构造

    4.普通迭代器接口

    5.插入接口

    6.删除与find接口

    7.const迭代器实现与接口

    8.范围拷贝与拷贝构造

    9.如果实例化参数是自定义类型

    10.析构函数

    11.完整代码

    1.链表节点的构建

    链表的节点有指针与和数据域，所以无法用任何一个内置类型来表示它，我们需要自定义好节点的类型。list容器使用的是带头双向循环链表。

    1. 	template <class T>
    2. 	struct list_node		//节点类型
    3. 	{
    4. 		list_node* _next;
    5. 		list_node* _prev;
    6. 		T _val;
    7. 		list_node(const T& val = T()) 
    8. 			:_val(val)
    9. 			,_next(nullptr)
    10. 			,_prev(nullptr)
    11. 		{}
    12. 	};

    2.迭代器的初步实现

    链表的节点所占用的内存空间是不连续的，所以不能使用原生指针来代替迭代器。我们需要自定义迭代器的行为(例如++是从前一个节点移动到后一个节点)。

    1. template <class T>
    2. 	struct list_iterator
    3. 	{
    4. 		typedef list_node node;
    5. 		node* pnode;
    6. 		
    7. 		list_iterator(node* p)
    8. 			:pnode(p)
    9. 		{}
    10.  
    11. 		list_iterator& operator++()
    12. 		{
    13. 			pnode = pnode->_next;
    14. 			return *this;
    15. 		}
    16.  
    17. 		bool operator!=(list_iterator& lt)
    18. 		{
    19. 			return pnode != lt.pnode;
    20. 		}
    21. 	};

    3.成员变量以及默认构造

    定义空容器时，容器是存在头节点(哨兵卫)的。

    1. 	template <class T>
    2. 	class list
    3. 	{
    4. 	public:
    5. 		typedef list_node node;
    6. 		typedef list_iterator iterator;
    7.  
    8. 		void empty_init()
    9. 		{
    10. 			_head = new node(T());		//哨兵卫
    11. 			_head->_next = _head;
    12. 			_head->_prev = _head;
    13. 			_size = 0;
    14. 		}
    15. 		list()
    16. 		{
    17. 			empty_init();		//复用
    18. 		}
    19.  
    20. 	private:
    21. 		node* _head;
    22. 		size_t size;		//记录有节点个数(除哨兵卫)
    23. 	};

    4.普通迭代器接口

    1. iterator begin()
    2. {
    3. 	return iterator(_head->_next);
    4. }
    5. iterator end()
    6. {
    7. 	return iterator(_head);		//尾后迭代器
    8. }

    5.插入接口

    插入有头插、尾插、随机插。我们重点实现随机插，头插和尾插复用随机插。

    1. void push_back(const T& val)
    2. {
    3. 	insert(end(), val);		//在哨兵卫头插就是尾插
    4. }
    5.  
    6. void push_front(const T& val)
    7. {
    8. 	insert(begin(), val);
    9. }
    10.  
    11. iterator insert(iterator pos, const T& val)
    12. {
    13. 	node* newnode = new node(val);
    14. 	node* prev = pos.pnode->_prev;
    15.  
    16. 	prev->_next = newnode;
    17. 	newnode->_prev = prev;
    18. 	newnode->_next = pos.pnode;
    19. 	pos.pnode->_prev = newnode;
    20. 			
    21. 	++_size;
    22. 	return iterator(newnode);		//返回插入节点的位置(防止迭代器失效)
    23. }

    6.删除与find接口

    删除有头删、尾删、随机删。我们重点实现随机删，头删和尾删复用随机删。

    1. void pop_back()
    2. {
    3. 	erase(end().pnode->_prev);
    4. }
    5. 		
    6. void pop_front()
    7. {
    8. 	erase(begin());
    9. }
    10.  
    11. iterator erase(iterator pos)
    12. {
    13. 	assert(end() != pos);		//不能删除哨兵卫
    14. 			
    15. 	node* prev = pos.pnode->_prev;
    16. 	node* next = pos.pnode->_next;
    17.  
    18. 	prev->_next = next;
    19. 	next->_prev = prev;
    20.  
    21. 	delete pos.pnode;
    22. 	--_size;
    23. 	return iterator(next);		//返回删除节点的下一个节点位置(防止迭代器失效)
    24. 			
    25. }
    26.  
    27. iterator find(iterator first, iterator last, const T& val)
    28. {
    29. 	assert(first != last);
    30. 	while (first != last)
    31. 	{
    32. 		if (*first == val) return first;
    33. 		++first;
    34. 	}
    35. 	return end();
    36. }

    7.const迭代器实现与接口

    不能使用const成员函数重载，因为我们要的效果是底层const而非顶层const(即指向的内容不可变，迭代器本身可变)。所以我们有两套方案，一是再构建一个迭代器类模板；二是在原来的迭代器模板基础上添加一个模板参数。再构建一个迭代器的方案与原模板的唯一区别就是返回值不同。所以否决第一套设计方案。

    现在先统一一下迭代器接口：

    1. typedef list_iterator iterator;
    2. typedef list_iteratorconst T&> const_iterator;
    3.  
    4. const_iterator begin() const
    5. {
    6. 	return const_iterator(_head->_next);
    7. }
    8. const_iterator end() const
    9. {
    10. 	return const_iterator(_head);
    11. }

    迭代器设计：

    1. template <class T,class ref>		//多使用一个模板参数
    2. struct list_iterator
    3. {
    4. 	typedef list_node node;
    5. 	typedef list_iterator self;		//为了方便
    6. 	node* pnode;
    7. 		
    8. 	list_iterator(node* p)
    9. 		:pnode(p)
    10. 	{}
    11.  
    12. 	ref operator*()
    13. 	{
    14. 		return pnode->_val;
    15. 	}
    16.  
    17. 	self& operator++()
    18. 	{
    19. 		pnode = pnode->_next;
    20. 		return *this;
    21. 	}
    22.  
    23. 	bool operator!=(self& lt)
    24. 	{
    25. 		return pnode != lt.pnode;
    26. 	}
    27. };

    8.范围拷贝与拷贝构造

    我们实现更加全面的构造接口。

    1. template <class InputIterator>
    2. list(InputIterator first, InputIterator last)		//范围拷贝
    3. {
    4. 	empty_init();
    5. 	while (first != last)
    6. 	{
    7. 		push_back(*first);
    8. 		++first;
    9. 	}
    10. }
    11. 		
    12. void swap(list& lt)
    13. {
    14. 	std::swap(_head, lt._head);
    15. 	std::swap(_size, lt._size);
    16. }
    17. list(const list& lt)		//拷贝构造现代写法
    18. {
    19. 	empty_init();
    20. 	list tmp(lt.begin(), lt.end());
    21. 	swap(tmp);
    22. }
    23.  
    24. list& operator=(list lt)		//赋值运算符重载现代写法
    25. {
    26. 	swap(lt);
    27. 	return *this;
    28. }

    9.如果实例化参数是自定义类型

    如果链表的节点是一个自定义类型，那么使用 * 将无法读取自定义类型的数据。所以我们需要完善访问自定义类型成员的功能，即 -> 运算符重载。此重载函数的返回值是实例化参数类型的指针，这个指针也有const与非const之分，并且调用此重载的对象可能是const或非const对象，也就是说迭代器可能是const迭代器与非const迭代器。那么我们依然为迭代器模板添加一个参数，并且完善迭代器的功能。

    别忘了对迭代器的重命名需要更新一下：

    1. typedef list_iterator iterator;
    2. typedef list_iteratorconst T&,const T*> const_iterator;
    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* pnode;
    7. 		
    8. 	list_iterator(node* p)
    9. 		:pnode(p)
    10. 	{}
    11.  
    12. 	ref operator*()
    13. 	{
    14. 		return pnode->_val;
    15. 	}
    16.  
    17. 	ptr operator->()
    18. 	{
    19. 		return &pnode->_val;
    20. 	}
    21.  
    22. 	self& operator++()
    23. 	{
    24. 		pnode = pnode->_next;
    25. 		return *this;
    26. 	}
    27.  
    28. 	self operator++(int)		//后置++
    29. 	{
    30. 		node* tmp(pnode);
    31. 		pnode = pnode->_next;
    32. 		return tmp;
    33. 	}
    34.  
    35. 	self& operator--()
    36. 	{
    37. 		pnode = pnode->_prev;
    38. 		return *this;
    39. 	}
    40.  
    41. 	self operator--(int)		//后置--
    42. 	{
    43. 		node* tmp(pnode);
    44. 		pnode = pnode->_prev;
    45. 		return tmp;
    46. 	}
    47.  
    48. 	bool operator!=(const self& lt)
    49. 	{
    50. 		return pnode != lt.pnode;
    51. 	}
    52.  
    53. 	bool operator==(const self& lt)
    54. 	{
    55. 		return pnode == lt.pnode;
    56. 	}
    57. };

    10.析构函数

    释放分为两个部分，一是不释放哨兵卫，将有效节点释放；而是全部释放。我们实现一个clear接口，让析构复用此接口。

    1. ~list()
    2. {
    3. 	clear();
    4. 	delete _head;
    5. 	_head = nullptr;
    6. }
    7.  
    8. void clear()
    9. {
    10. 	auto it = begin();
    11. 	while (it != end())
    12. 	{
    13. 		it = erase(it);
    14. 	}
    15. }

    11.完整代码

    这里只实现了list容器常用的接口，并没有完全依照标准库1：1模拟实现。代码会有很多细节没有处理好，并不是会报错，而是有些地方显得不够严谨。

    1. #include 
    2. #include 
    3. namespace ly
    4. {
    5. 	template <class T>
    6. 	struct list_node		//节点类型
    7. 	{
    8. 		list_node* _next;
    9. 		list_node* _prev;
    10. 		T _val;
    11. 		list_node(const T& val = T()) 
    12. 			:_val(val)
    13. 			,_next(nullptr)
    14. 			,_prev(nullptr)
    15. 		{}
    16. 	};
    17.  
    18. template <class T,class ref,class ptr>		//多使用一个模板参数
    19. struct list_iterator
    20. {
    21. 	typedef list_node node;
    22. 	typedef list_iterator self;		
    23. 	node* pnode;
    24. 		
    25. 	list_iterator(node* p)
    26. 		:pnode(p)
    27. 	{}
    28.  
    29. 	ref operator*()
    30. 	{
    31. 		return pnode->_val;
    32. 	}
    33.  
    34. 	ptr operator->()
    35. 	{
    36. 		return &pnode->_val;
    37. 	}
    38.  
    39. 	self& operator++()
    40. 	{
    41. 		pnode = pnode->_next;
    42. 		return *this;
    43. 	}
    44.  
    45. 	self operator++(int)		//后置++
    46. 	{
    47. 		node* tmp(pnode);
    48. 		pnode = pnode->_next;
    49. 		return tmp;
    50. 	}
    51.  
    52. 	self& operator--()
    53. 	{
    54. 		pnode = pnode->_prev;
    55. 		return *this;
    56. 	}
    57.  
    58. 	self operator--(int)		//后置--
    59. 	{
    60. 		node* tmp(pnode);
    61. 		pnode = pnode->_prev;
    62. 		return tmp;
    63. 	}
    64.  
    65. 	bool operator!=(const self& lt)
    66. 	{
    67. 		return pnode != lt.pnode;
    68. 	}
    69.  
    70. 	bool operator==(const self& lt)
    71. 	{
    72. 		return pnode == lt.pnode;
    73. 	}
    74. };
    75.  
    76. 	template <class T>
    77. 	class list
    78. 	{
    79. 	public:
    80. 		typedef list_node node;
    81. 		typedef list_iterator iterator;
    82. 		typedef list_iteratorconst T&,const T*> const_iterator;
    83.  
    84. 		iterator begin()
    85. 		{
    86. 			return iterator(_head->_next);
    87. 		}
    88. 		iterator end()
    89. 		{
    90. 			return iterator(_head);		//尾后迭代器
    91. 		}
    92. 		const_iterator begin() const
    93. 		{
    94. 			return const_iterator(_head->_next);
    95. 		}
    96. 		const_iterator end() const
    97. 		{
    98. 			return const_iterator(_head);
    99. 		}
    100.  
    101. 		void empty_init()
    102. 		{
    103. 			_head = new node(T());		//哨兵卫
    104. 			_head->_next = _head;
    105. 			_head->_prev = _head;
    106. 			_size = 0;
    107. 		}
    108. 		list()
    109. 		{
    110. 			empty_init();		//复用
    111. 		}
    112.  
    113. 		template <class InputIterator>
    114. 		list(InputIterator first, InputIterator last)		//范围拷贝
    115. 		{
    116. 			empty_init();
    117. 			while (first != last)
    118. 			{
    119. 				push_back(*first);
    120. 				++first;
    121. 			}
    122. 		}
    123. 		
    124. 		void swap(list& lt)
    125. 		{
    126. 			std::swap(_head, lt._head);
    127. 			std::swap(_size, lt._size);
    128. 		}
    129. 		list(const list& lt)		//拷贝构造现代写法
    130. 		{
    131. 			empty_init();
    132. 			list tmp(lt.begin(), lt.end());
    133. 			swap(tmp);
    134. 		}
    135.  
    136. 		list& operator=(list lt)		//赋值运算符重载现代写法
    137. 		{
    138. 			swap(lt);
    139. 			return *this;
    140. 		}
    141.  
    142.  
    143. 		void pop_back()
    144. 		{
    145. 			erase(end().pnode->_prev);
    146. 		}
    147. 		
    148. 		void pop_front()
    149. 		{
    150. 			erase(begin());
    151. 		}
    152.  
    153. 		iterator erase(iterator pos)
    154. 		{
    155. 			assert(end() != pos);		//不能删除哨兵卫
    156. 			
    157. 			node* prev = pos.pnode->_prev;
    158. 			node* next = pos.pnode->_next;
    159.  
    160. 			prev->_next = next;
    161. 			next->_prev = prev;
    162.  
    163.             delete pos.pnode;
    164. 			--_size;
    165. 			return iterator(next);		//返回删除节点的下一个节点位置(防止迭代器失效)
    166. 			
    167. 		}
    168.  
    169. 		iterator find(iterator first, iterator last, const T& val)
    170. 		{
    171. 			assert(first != last);
    172. 			while (first != last)
    173. 			{
    174. 				if (*first == val) return first;
    175. 				++first;
    176. 			}
    177. 			return end();
    178. 		}
    179.  
    180.  
    181. 		void push_back(const T& val)
    182. 		{
    183. 			insert(end(), val);		//在哨兵卫头插就是尾插
    184. 		}
    185.  
    186. 		void push_front(const T& val)
    187. 		{
    188. 			insert(begin(), val);
    189. 		}
    190.  
    191. 		iterator insert(iterator pos, const T& val)
    192. 		{
    193. 			node* newnode = new node(val);
    194. 			node* prev = pos.pnode->_prev;
    195.  
    196. 			prev->_next = newnode;
    197. 			newnode->_prev = prev;
    198. 			newnode->_next = pos.pnode;
    199. 			pos.pnode->_prev = newnode;
    200. 			
    201. 			++_size;
    202. 			return iterator(newnode);		//返回插入节点的位置(防止迭代器失效)
    203. 		}
    204.  
    205.  
    206.  
    207. 	private:
    208. 		node* _head;
    209. 		size_t _size;		//记录有节点个数(除哨兵卫)
    210. 	};
    211. }

  • 相关阅读:
    总结算法题中一些常用的Java方法
    组件以及组件间的通讯
    两条命令解决移动硬盘无法弹出的问题
    Spring Boot 中使用 tkMapper
    （汇总）系统设计 - 我们如何通俗的理解那些技术的运行原理 - 汇总篇
    java基础之适配器模式[30]
    太强了吧，架构师联手总结17w字的计算机基础知识与操作系统PDF
    python经典案例（2）
    在Spring Boot中使用MyBatis访问数据库
    幂等设计详解
  • 原文地址：https://blog.csdn.net/weixin_59913110/article/details/128159117