• C++ —— 模拟实现vector和迭代器失效

    目录

    1.成员变量的设计

     2.迭代器以及接口设计

    3.容量接口

    4.reserve的设计

    5.resize的设计

    6.尾插尾删的设计

    7.构造、析构函数

    8.运算符重载

    9.insert接口设计与迭代器失效

    10.erase的设计和迭代器失效

    11.双层深拷贝问题

    12.完整代码

    1.成员变量的设计

    成员变量设计为三个迭代器，分别是：_start、_finish、_endofstorage。此设计原理参考STL源码。_start与_finish之间是存储有效元素的；_start与_endofstorage之间表容器的容量。

    1. iterator _start;
    2. iterator _finish;
    3. iterator _endofstorage;

     2.迭代器以及接口设计

    使用指针的方式实现迭代器，同时需要兼顾 const 对象和 const 迭代器。

    1. typedef T* iterator;
    2. typedef const T* const_iterator;		//使用指针实现迭代器
    3. iterator begin()
    4. {
    5. 	return _start;
    6. }
    7. iterator end()
    8. {
    9. 	return _finish;
    10. }
    11. const_iterator begin() const
    12. {
    13. 	return _start;
    14. }
    15. const_iterator end() const
    16. {
    17. 	return _finish;
    18. }

    3.容量接口

    1. size_t size()
    2. {
    3. 	return _finish - _start;
    4. }
    5. size_t capacity()
    6. {
    7. 	return _endofstorage - _start;
    8. }
    9. void clear()
    10. {
    11. 	_finish = _start;
    12. }
    13. bool empty()
    14. {
    15. 	return _finish == _start;
    16. }

    4.reserve的设计

    reserve如果涉及到扩容，统一采用异地扩容的方式。当参数小于当前容量时不作处理。

    1. void reserve(const size_t& n)
    2. {
    3. 	if (n > capacity())
    4. 	{
    5. 		T* tmp = new T[n];
    6. 		assert(tmp);		//检查是否成功开辟
    7. 		int oldsize = _finish - _start;
    8.  
    9. 		if (_start)		//如果_start不为空需要拷贝数据
    10. 		{
    11. 			memcpy(tmp, _start, sizeof(T) * oldsize);        
    12. 			delete[] _start;		//释放旧空间
    13. 		}
    14.  
    15. 		//异地扩容，更新迭代器
    16. 		_start = tmp;
    17. 		_finish = _start + oldsize;
    18. 		_endofstorage = _start + n;
    19. 	}
    20. }

    5.resize的设计

    resize需要分情况讨论，如果接收的参数小于当前容量时，空间不进行变动；如果小于当前有效元素个数时，需要更新_finish迭代器达到删除的效果。同时需要注意resize有第二个参数(官方手册)。

    1. void resize(const size_t n, T val = T())
    2. {
    3. 	if (n > capacity) reserve(n);		//大于当前容量,扩容
    4. 	if (n > size())
    5. 	{
    6. 		while (_finish < _start + n)
    7. 		{
    8. 			*_finish = val;
    9. 			++_finish;
    10. 		}
    11. 	}
    12. 	else _finish = _start + n;
    13. }

    6.尾插尾删的设计

    1. void push_back(const T& val)
    2. {
    3. 	if (_finish == _endofstorage)		//是否需要扩容
    4. 	{
    5. 		size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
    6. 		reserve(newcapacity);
    7. 	}
    8. 	*_finish = val;
    9. 	++_finish;
    10. }
    11. void pop_back()
    12. {
    13. 	assert(!empty());		//尾删容器不能为空
    14. 	--_finish;
    15. }

    7.构造、析构函数

    这里模拟实现：默认构造函数、范围拷贝、指定容器大小、拷贝构造函数(现代写法)、析构函数。

    1. vector()		//默认构造函数
    2. 	:_start(nullptr)
    3. 	,_finish(nullptr)
    4. 	,_endofstorage(nullptr)
    5. {}
    6.  
    7. template <class it>
    8. vector(it first, it last)		//范围拷贝构造
    9. 	: _start(nullptr)
    10. 	, _finish(nullptr)
    11. 	, _endofstorage(nullptr)
    12. {
    13. 	while (first != last)
    14. 	{
    15. 		push_back(*first);
    16. 		++first;
    17. 	}
    18. }
    19.  
    20. //拷贝构造现代写法
    21. void swap(vector& v)
    22. {
    23. 	std::swap(_start, v._start);
    24. 	std::swap(_finish, v._finish);
    25. 	std::swap(_endofstorage, v._endofstorage);
    26.  
    27. }
    28. vector(const vector& v)
    29. 	:_start(nullptr)
    30. 	, _finish(nullptr)
    31. 	, _endofstorage(nullptr)
    32. {
    33. 	vector tmp(v.begin(), v.end());
    34. 	swap(tmp);
    35. }
    36.  
    37. vector(size_t n, const T& val = T())		//指定容器大小构造
    38. 	:_start(nullptr)
    39. 	, _finish(nullptr)
    40. 	, _endofstorage(nullptr)
    41. {
    42. 	reserve(n);
    43. 	for (size_t i = 0; i < n; ++i)
    44. 	{
    45. 		push_back(val);
    46. 	}
    47.  
    48. }
    49.  
    50. ~vector()		//析构函数
    51. {
    52. 	delete[] _start;
    53. 	_start = _finish = _endofstorage = nullptr;
    54. }

    上面的代码会出一个错误：

    其原因在于：10 在编译器的视角中默认是一个 int 类型的数，而我们的接口设计是一个 size_t 类型的数，所以会存在一些类型提升。而我们又设计了一个模板，在编译器的视角看来，调用模板函数是开销更小的选择。

    解决方案是添加一个重载：

    1. vector(int n, const T& val = T())		//指定容器大小构造
    2. 	:_start(nullptr)
    3. 	, _finish(nullptr)
    4. 	, _endofstorage(nullptr)
    5. {
    6. 	reserve(n);
    7. 	for (int i = 0; i < n; ++i)
    8. 	{
    9. 		push_back(val);
    10. 	}
    11. }

    8.运算符重载

    需不需要使用 const 函数是看我们需求来的，这里给出设计原则：

    • 只读接口函数，设计为const函数
    • 只写接口函数，设计为非const函数
    • 读、写接口函数，const函数、非const函数都要设计

    上面的代码可能考虑的不够周全，读者可自行改进。下标运算符对于我们来说是可读可写的。

    1. T& operator[](const size_t n)
    2. {
    3. 	assert(n >= 0 && n < size());		//防止越界
    4. 	return _start[n];
    5. }
    6.  
    7. const T& operator[](const size_t n) const
    8. {
    9. 	assert(n >= 0 && n < size());		//防止越界
    10. 	return _start[n];
    11. }
    12.  
    13. vector& operator=(vector v)		//赋值运算符重载
    14. {
    15. 	swap(v);
    16. 	return *this;
    17. }

    9.insert接口设计与迭代器失效

    1. void insert(iterator pos,const T& val)
    2. {
    3. 	assert(pos >= _start && pos < _finish);
    4. 	if (_finish == _endofstorage)		//检查是否需要扩容
    5. 	{
    6. 		size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
    7. 		reserve(newcapacity);
    8. 	}
    9. 	auto end = _finish - 1;
    10. 	while (end >= pos)
    11. 	{
    12. 		*(end + 1) = *end;
    13. 		--end;
    14. 	}
    15. 	*pos = val;
    16. 	++_finish;
    17. }

    这样设计的接口发生扩容时会产生迭代器失效，因为扩容是异地扩容，就会导致pos指向的空间已经被释放了，需要更新pos。因为是传值调用，我们还必须保证外部的迭代器能够及时更新。

    1. iterator insert(iterator pos,const T& val)
    2. {
    3. 	assert(pos >= _start && pos < _finish);
    4. 	if (_finish == _endofstorage)		//检查是否需要扩容
    5. 	{
    6. 		size_t oldsize = _finish - _start;
    7. 		size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
    8. 		reserve(newcapacity);
    9. 		pos = _start + oldsize;		//扩容后，_start的指向已经更改，需要更新pos
    10. 	}
    11. 	auto end = _finish - 1;
    12. 	while (end >= pos)
    13. 	{
    14. 		*(end + 1) = *end;
    15. 		--end;
    16. 	}
    17. 	*pos = val;
    18. 	++_finish;
    19. 	return pos;		//添加一个返回值供外部迭代器更新
    20. }

    外部需要继续使用迭代器的正确方法为：

    在VS环境中使用标准库的insert接口，不按上面的方式使用迭代器，就会发生迭代器失效问题。

    10.erase的设计和迭代器失效

    1. void erase(iterator pos)
    2. {
    3. 	assert(pos >= _start);
    4. 	assert(pos < _finish);
    5. 			
    6. 	auto del = pos + 1;
    7. 	while (del < _finish)
    8. 	{
    9. 		*(del - 1) = *del;
    10. 		++del;
    11. 	}
    12. 	--_finish;
    13. }

    这样做会导致迭代器失效。其原因在于：删除最后一个元素，del的位置会指向一个不合法的位置，如果后续要对这个指针指向的内容进行读、写是非常危险的。所以与insert一样，VS的编译环境是使用insert和erase后迭代器失效。解决方案是返回指向删除元素位置的迭代器。

    1. iterator erase(iterator pos)
    2. {
    3. 	assert(pos >= _start);
    4. 	assert(pos < _finish);
    5. 			
    6. 	auto del = pos + 1;
    7. 	while (del < _finish)
    8. 	{
    9. 		*(del - 1) = *del;
    10. 		++del;
    11. 	}
    12. 	--_finish;
    13. 	return pos;
    14. }

    外部调用时正确的使用方法：

    使用标准库中的vector容器，不按上述方法使用会发生错误：

    11.双层深拷贝问题

    留意刚才的reserve接口：

    1. void reserve(const size_t& n)
    2. {
    3. 	if (n > capacity())
    4. 	{
    5. 		T* tmp = new T[n];
    6. 		assert(tmp);		//检查是否成功开辟
    7. 		int oldsize = _finish - _start;
    8.  
    9. 		if (_start)		//如果_start不为空需要拷贝数据
    10. 		{
    11. 			memcpy(tmp, _start, sizeof(T) * oldsize);
    12. 			delete[] _start;		//释放旧空间
    13. 		}
    14.  
    15. 		//异地扩容，更新迭代器
    16. 		_start = tmp;
    17. 		_finish = _start + oldsize;
    18. 		_endofstorage = _start + n;
    19. 	}
    20. }

    这么做会导致一个非常严重的野指针问题：

    其原因在于：异地扩容之后，使用memcpy进行拷贝，而这个拷贝是一次浅拷贝，新空间和旧空间的对象都指向原来的_start指向的空间，当_start指向的空间释放后，新空间的对象_start就是野指针了，所以打印的就是乱码。当函数栈帧退出时又析构一次，就会造成一次严重的野指针问题。 

    所以我们的解决方案是不使用memcpy进行浅拷贝，而是使用赋值运算符重载进行深拷贝。

    1. void reserve(const size_t n)
    2. {
    3. 	if (n > capacity())
    4. 	{
    5. 		int oldsize = _finish - _start;
    6. 		T* tmp = new T[n];
    7. 		assert(tmp);		//检查是否成功开辟
    8.  
    9. 		if (_start)		//如果_start不为空需要拷贝数据
    10. 		{
    11. 			//memcpy(tmp, _start, sizeof(T) * oldsize);
    12. 			for (size_t i = 0; i < size(); i++)
    13. 			{
    14. 				tmp[i] = _start[i];		//使用赋值运算符重载
    15. 			}
    16. 			delete[] _start;		//释放旧空间
    17. 		}
    18.  
    19. 		//异地扩容，更新迭代器
    20. 		_start = tmp;
    21. 		_finish = _start + oldsize;
    22. 		_endofstorage = _start + n;
    23. 	}
    24. }

    12.完整代码

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. namespace ly
    6. {
    7. 	template <class T>
    8. 	class vector
    9. 	{
    10. 	public:
    11. 		typedef T* iterator;
    12. 		typedef const T* const_iterator;		//使用指针实现迭代器
    13. 		iterator begin()
    14. 		{
    15. 			return _start;
    16. 		}
    17. 		iterator end()
    18. 		{
    19. 			return _finish;
    20. 		}
    21. 		const_iterator begin() const
    22. 		{
    23. 			return _start;
    24. 		}
    25. 		const_iterator end() const
    26. 		{
    27. 			return _finish;
    28. 		}
    29.  
    30. 		vector()		//默认构造函数
    31. 			:_start(nullptr)
    32. 			,_finish(nullptr)
    33. 			,_endofstorage(nullptr)
    34. 		{}
    35.  
    36. 		~vector()		//析构函数
    37. 		{
    38. 			delete[] _start;
    39. 			_start = _finish = _endofstorage = nullptr;
    40. 		}
    41.  
    42.  
    43. 		template <class it>
    44. 		vector(it first, it last)		//范围拷贝构造
    45. 			: _start(nullptr)
    46. 			, _finish(nullptr)
    47. 			, _endofstorage(nullptr)
    48. 		{
    49. 			while (first != last)
    50. 			{
    51. 				push_back(*first);
    52. 				++first;
    53. 			}
    54. 		}
    55.  
    56. 		//拷贝构造现代写法
    57. 		void swap(vector& v)
    58. 		{
    59. 			std::swap(_start, v._start);
    60. 			std::swap(_finish, v._finish);
    61. 			std::swap(_endofstorage, v._endofstorage);
    62.  
    63. 		}
    64. 		vector(const vector& v)
    65. 			:_start(nullptr)
    66. 			, _finish(nullptr)
    67. 			, _endofstorage(nullptr)
    68. 		{
    69. 			vector tmp(v.begin(), v.end());
    70. 			swap(tmp);
    71. 		}
    72.  
    73. 		vector(size_t n, const T& val = T())		//指定容器大小构造
    74. 			:_start(nullptr)
    75. 			, _finish(nullptr)
    76. 			, _endofstorage(nullptr)
    77. 		{
    78. 			reserve(n);
    79. 			for (size_t i = 0; i < n; ++i)
    80. 			{
    81. 				push_back(val);
    82. 			}
    83.  
    84. 		}
    85. 		vector(int n, const T& val = T())		//指定容器大小构造
    86. 			:_start(nullptr)
    87. 			, _finish(nullptr)
    88. 			, _endofstorage(nullptr)
    89. 		{
    90. 			reserve(n);
    91. 			for (int i = 0; i < n; ++i)
    92. 			{
    93. 				push_back(val);
    94. 			}
    95.  
    96. 		}
    97. 		
    98. 		T& operator[](const size_t n)
    99. 		{
    100. 			assert(n < size());		//防止越界
    101. 			return _start[n];
    102. 		}
    103. 		const T& operator[](const size_t n) const
    104. 		{
    105. 			assert( n < size());		//防止越界
    106. 			return _start[n];
    107. 		}
    108. 		vector& operator=(vector v)
    109. 		{
    110. 			swap(v);
    111. 			return *this;
    112. 		}
    113.  
    114. void reserve(const size_t n)
    115. {
    116. 	if (n > capacity())
    117. 	{
    118. 		int oldsize = _finish - _start;
    119. 		T* tmp = new T[n];
    120. 		assert(tmp);		//检查是否成功开辟
    121.  
    122. 		if (_start)		//如果_start不为空需要拷贝数据
    123. 		{
    124. 			//memcpy(tmp, _start, sizeof(T) * oldsize);
    125. 			for (size_t i = 0; i < size(); i++)
    126. 			{
    127. 				tmp[i] = _start[i];		//使用运算符重载
    128. 			}
    129. 			delete[] _start;		//释放旧空间
    130. 		}
    131.  
    132. 		//异地扩容，更新迭代器
    133. 		_start = tmp;
    134. 		_finish = _start + oldsize;
    135. 		_endofstorage = _start + n;
    136. 	}
    137. }
    138.  
    139.  
    140. 		void resize(const size_t n, T val = T())
    141. 		{
    142. 			if (n > capacity) reserve(n);		//大于当前容量,扩容
    143. 			if (n > size())
    144. 			{
    145. 				while (_finish < _start + n)
    146. 				{
    147. 					*_finish = val;
    148. 					++_finish;
    149. 				}
    150. 			}
    151. 			else _finish = _start + n;
    152. 		}
    153.  
    154. 		size_t size()
    155. 		{
    156. 			return _finish - _start;
    157. 		}
    158. 		size_t capacity()
    159. 		{
    160. 			return _endofstorage - _start;
    161. 		}
    162. 		void clear()
    163. 		{
    164. 			_finish = _start;
    165. 		}
    166. 		bool empty()
    167. 		{
    168. 			return _finish == _start;
    169. 		}
    170.  
    171. 		void push_back(const T& val)
    172. 		{
    173. 			if (_finish == _endofstorage)		//是否需要扩容
    174. 			{
    175. 				size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
    176. 				reserve(newcapacity);
    177. 			}
    178. 			*_finish = val;
    179. 			++_finish;
    180. 		}
    181. 		void pop_back()
    182. 		{
    183. 			assert(!empty());		//尾删容器不能为空
    184. 			--_finish;
    185. 		}
    186.  
    187. 		iterator insert(iterator pos,const T& val)
    188. 		{
    189. 			assert(pos >= _start && pos < _finish);
    190. 			if (_finish == _endofstorage)		//检查是否需要扩容
    191. 			{
    192. 				size_t oldsize = _finish - _start;
    193. 				size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
    194. 				reserve(newcapacity);
    195. 				pos = _start + oldsize;		//扩容后，_start的指向已经更改，需要更新pos
    196. 			}
    197. 			auto end = _finish - 1;
    198. 			while (end >= pos)
    199. 			{
    200. 				*(end + 1) = *end;
    201. 				--end;
    202. 			}
    203. 			*pos = val;
    204. 			++_finish;
    205. 			return pos;		//添加一个返回值供外部迭代器更新
    206. 		}
    207.  
    208. 		iterator erase(iterator pos)
    209. 		{
    210. 			assert(pos >= _start);
    211. 			assert(pos < _finish);
    212. 			
    213. 			auto del = pos + 1;
    214. 			while (del < _finish)
    215. 			{
    216. 				*(del - 1) = *del;
    217. 				++del;
    218. 			}
    219. 			--_finish;
    220. 			return pos;
    221. 		}
    222. 	private:
    223. 		iterator _start;
    224. 		iterator _finish;
    225. 		iterator _endofstorage;
    226.  
    227. 	};
    228. }

  • 相关阅读:
    c++ stl（标准模板库）
    Strtok函数切割字符串（附代码演示）
    绿联搭建rustdesk服务器
    javascript：Array.prototype.reduce()的使用场景
    软件设计模式系列之二十二——状态模式
    从双非硕士到大厂工作，优秀
    [网站部署03]宝塔+worldPress部署Ripro主题网站
    时间序列中的6大类10种异常值处理方法(从根源上提高预测精度)
    [前端基础] 浏览器篇
    C++静态代码检查工具 - cppcheck
  • 原文地址：https://blog.csdn.net/weixin_59913110/article/details/128025392