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

【c++vector】vector的实现和深层次的深浅拷贝_c++ vector 深拷贝

作者：不正经 | 2024-04-19 16:44:50

赞

踩

c++ vector 深拷贝

目录

 

1.深层次的深浅拷贝

2.vector的实现

                2.迭代器和打印函数

                3.reserve和resize

                4.拷贝构造函数和赋值运算符重载

                5.插入和删除 

                全部代码

1.深层次的深浅拷贝

步骤：

  1. 自己的实现容量初始为4个，增容2倍，当尾插的4个数，再插入第5个数时会发生增容;
  2. 使用memcpy增容或者拷贝构造，都会是深层次的浅拷贝；

总结：

  1. T是内置类型（int）或者是浅拷贝自定义类型（date），他们增容和拷贝构造中，使用memcpy是没有问题的；
  2. 但是T是深拷贝自定义类型（string），他们增容和拷贝构造中，使用memcpy浅拷贝，指向1块相同的空间，是有问题的；
  3. STL库里面是类型萃取区分类型（了解）：memcpy效率更高（内置类型，浅拷贝自定义类型），遍历+深拷贝自定义类型（string）的赋值运算符重载会，开空间+拷贝构造效率更低（深拷贝自定义类型）

解决：把memcpy替换为遍历+深拷贝自定义类型（string）的赋值运算符重载；

  1. for (size_t i = 0; i < v.size(); i++)//解决深层次的深浅拷贝
  2. 			{
  3. 				
  4. 				_start[i] = v._start[i];
  5. 			}

逻辑如图：

代码： 

  1. #include<iostream>
  2. #include<algorithm>
  3. #include<assert.h>
  4. #include<string>
  5. using namespace std;
  6.  
  7. namespace lj
  8. {
  9. 	template<class T>
  10. 	class vector
  11. 	{
  12. 	public:
  13. 		typedef T* iterator;
  14. 		typedef const T* const_iterator;
  15.  
  16. 		vector(const vector<T>& v)//拷贝构造
  17. 			:_start(nullptr)
  18. 			,_finish(nullptr)
  19. 			,_endofstorage(nullptr)
  20. 		{
  21. 			_start = new T[v.capacity()];
  22. 		    memcpy(_start, v._start, sizeof(T) * v.capacity());
  23. 			//for (size_t i = 0; i < v.size(); i++)//解决深层次的深浅拷贝
  24. 		    //{
  25. 			//	_start[i] = v._start[i];
  26. 			//}
  27. 			_endofstorage = _start + v.capacity();
  28. 			_finish = _start + v.size();
  29. 		}
  30.  
  31. 		void reserve(size_t n)
  32. 		{
  33. 			if (n > capacity())
  34. 			{
  35. 				size_t sz = size();
  36. 				iterator tmp = new T[n];
  37. 				if (_start)//start不为为空
  38. 				{
  39. 					memcpy(tmp, _start, sz*sizeof(T));
  40. 					//for (size_t i = 0; i << sz; i++)
  41. 					//{
  42. 						//tmp[i] = _start[i];
  43. 					//}
  44. 					delete[] _start;
  45. 				}
  46. 				_start = tmp;
  47. 				_finish = _start+sz;
  48. 				_endofstorage=_start+n;
  49. 			}
  50. 		}
  51. 		void push_back(const T& x)
  52. 		{
  53. 			if (_finish == _endofstorage)
  54. 			{
  55. 				size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
  56. 				reserve(newCapacity);
  57. 			}
  58. 			*_finish = x;
  59. 			_finish++;
  60. 		}
  61. 	private:
  62. 		iterator _start;
  63. 		iterator _finish;
  64. 		iterator _endofstorage;
  65. 	};
  66. 	void test_vector6()
  67. 	{
  68. 		vector<string> v;
  69. 		v.push_back("1111");
  70. 		v.push_back("2222");
  71. 		v.push_back("3333");
  72. 		v.push_back("4444");
  73. 		v.push_back("5555");
  74. 		vector<string> v1(v);
  75. 		v.PrintVector();
  76. 		v1.PrintVector();
  77. 	}
  78. }
  79. int main()
  80. {
  81.  
  82. 	lj::test_vector6();
  83. 	return 0;
  84. }

2.vector的实现

                1.构造函数和析构函数

  • 使用迭代器构造函数时，可以是任意类型（int,sting,double）所以把迭代器构造函数写成一个模板函数；类模板的成员函数，还可以再是函数模板；
  1. 		vector()
  2. 			:_start(nullptr)
  3. 			,_finish(nullptr)
  4. 			,_endofstorage(nullptr)
  5. 		{}
  6.         // 类模板的成员函数，还可以再是函数模板
  7. 		template<class InputIterator>
  8. 		vector(InputIterator first, InputIterator 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. 		~vector()
  20. 		{
  21. 			if (_start)
  22. 			{
  23. 				delete[] _start;
  24. 				_start = _finish = _endofstorage = nullptr;
  25. 			}
  26. 		}

                2.迭代器和打印函数

  • 一个接口需要可读和可读可写的时候，那么写成两份
  1. const_iterator begin()const
  2. 		{
  3. 			return _start;
  4. 		}
  5. const_iterator end()const
  6. 		{
  7. 			return _finish;
  8. 		}
  9. 	iterator begin()
  10. 		{
  11. 			return _start;
  12. 		}
  13. 	iterator end()
  14. 		{
  15. 			return _finish;
  16. 		}
  17. void PrintVector()const
  18. 		{
  19. 			vector<T>::const_iterator it = this->begin();
  20. 			while (it != this->end())
  21. 			{
  22. 				//*it += 1;//只能读，不能写
  23. 				cout << *it << " ";
  24. 				++it;
  25. 			}
  26. 			cout << endl;
  27. 		}

                3.reserve和resize

  • reserve最后_finish = _start+sz;和_endofstorage=_start+n;不能写成_start+size（）和_start+capacity（），因为计算是_finish和_endofstorage还是nullptr，求size（）和capacity（）会是一个很大的负值
  • resize3中情况：减少size；增加size，但是不用增容；增加size也需要增容；
  1. void reserve(size_t n)
  2. 		{
  3. 			if (n > capacity())
  4. 			{
  5. 				size_t sz = size();
  6. 				iterator tmp = new T[n];
  7. 				if (_start)//start不为为空
  8. 				{
  9. 					//memcpy(tmp, _start, sz*sizeof(T));
  10. 					for (size_t i = 0; i << sz; i++)
  11. 					{
  12. 						tmp[i] = _start[i];
  13. 					}
  14. 					delete[] _start;
  15. 				}
  16. 				_start = tmp;
  17. 				_finish = _start+sz;//finish还为0，start新空间，size()会返回很大的负值
  18. 				_endofstorage=_start+n;//endofstorage还为0，start新空间，capacity()会返回很大的负值
  19. 			}
  20. 		}
  21. 		void resize(size_t n, T val = T())
  22. 		{
  23. 			if (n < size())
  24. 			{
  25. 				_finish = _start + n;
  26. 			}
  27. 			else
  28. 			{
  29. 				if (n > capacity())
  30. 				{
  31. 					reserve(n);
  32.  
  33. 				}
  34. 				for (size_t i = size(); i < n; i++)
  35. 				{
  36. 					*_finish = val;
  37. 					_finish++;
  38. 				}
  39. 			}
  40. 		}

                4.拷贝构造函数和赋值运算符重载

  • 拷贝构造注意深层次的深浅拷贝；
  • 赋值运算符重载现代写法思想：传值传参，交换之后，因为v是临时对象，出函数生命周期结束，那么会释放交换后的数组；   
  1. vector(const vector<T>& v)//拷贝构造
  2. 			:_start(nullptr)
  3. 			,_finish(nullptr)
  4. 			,_endofstorage(nullptr)
  5. 		{
  6. 			_start = new T[v.capacity()];
  7. 			/*memcpy(_start, v._start, sizeof(T) * v.capacity());*/
  8. 			for (size_t i = 0; i < v.size(); i++)//解决深层次的深浅拷贝
  9. 			{
  10. 				
  11. 				_start[i] = v._start[i];
  12. 			}
  13. 			_endofstorage = _start + v.capacity();
  14. 			_finish = _start + v.size();
  15. 		}
  16. 		vector<T>& operator=(vector<T> v)
  17. 		{
  18. 			swap(_start, v._start);
  19. 			swap(_finish, v._finish);
  20. 			swap(_endofstorage, v._endofstorage);
  21. 			return *this;
  22. 		}

                5.插入和删除 

  • insert增容后注意更新一下pos，防止迭代器失效；
  1. 		void push_back(const T& x)
  2. 		{
  3. 			if (_finish == _endofstorage)
  4. 			{
  5. 				size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
  6. 				reserve(newCapacity);
  7. 			}
  8. 			*_finish = x;
  9. 			_finish++;
  10. 		}
  11. 		void pop_back()
  12. 		{
  13. 			assert(!empty());
  14. 			--_finish;
  15. 		}
  16. 		void insert(iterator pos, const T& x)
  17. 		{
  18. 			size_t sz = pos - _start;
  19. 			if (_finish == _endofstorage)//判断增容
  20. 			{
  21. 				size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
  22. 				reserve(newCapacity);
  23. 				//更新pos，防止迭代器失效
  24. 				pos = _start + sz;
  25. 			}
  26. 			iterator end = _finish - 1;
  27. 			while (end >= pos)
  28. 			{
  29. 				*(end + 1) = *end;
  30. 				--end;
  31. 			}
  32. 			*end = x;
  33. 			++_finish;
  34. 		}
  35. 		iterator erase(iterator pos)
  36. 		{
  37. 			iterator it = pos + 1;
  38. 			while (it != end())
  39. 			{
  40. 				*(it - 1) = *it;
  41. 				++it;
  42. 			}
  43. 			_finish--; 
  44. 			return pos;
  45. 		}

                全部代码

  1. #include<iostream>
  2. #include<algorithm>
  3. #include<assert.h>
  4. #include<string>
  5. using namespace std;
  6.  
  7. namespace lj
  8. {
  9. 	template<class T>
  10. 	class vector
  11. 	{
  12. 	public:
  13. 		typedef T* iterator;
  14. 		typedef const T* const_iterator;
  15. 		const_iterator begin()const
  16. 		{
  17. 			return _start;
  18. 		}
  19. 		const_iterator end()const
  20. 		{
  21. 			return _finish;
  22. 		}
  23. 		iterator begin()
  24. 		{
  25. 			return _start;
  26. 		}
  27. 		iterator end()
  28. 		{
  29. 			return _finish;
  30. 		}
  31. 		vector()
  32. 			:_start(nullptr)
  33. 			,_finish(nullptr)
  34. 			,_endofstorage(nullptr)
  35. 		{}
  36. 		// 类模板的成员函数，还可以再是函数模板
  37. 		template<class InputIterator>
  38. 		vector(InputIterator first, InputIterator last)
  39. 			: _start(nullptr)
  40. 			, _finish(nullptr)
  41. 			, _endofstorage(nullptr)
  42. 		{
  43. 			while (first != last)
  44. 			{
  45. 				push_back(*first);
  46. 				++first;
  47. 			}
  48. 		}
  49. 		~vector()
  50. 		{
  51. 			if (_start)
  52. 			{
  53. 				delete[] _start;
  54. 				_start = _finish = _endofstorage = nullptr;
  55. 			}
  56. 		}
  57. 		vector(const vector<T>& v)//拷贝构造
  58. 			:_start(nullptr)
  59. 			,_finish(nullptr)
  60. 			,_endofstorage(nullptr)
  61. 		{
  62. 			_start = new T[v.capacity()];
  63. 			/*memcpy(_start, v._start, sizeof(T) * v.capacity());*/
  64. 			for (size_t i = 0; i < v.size(); i++)//解决深层次的深浅拷贝
  65. 			{
  66. 				
  67. 				_start[i] = v._start[i];
  68. 			}
  69. 			_endofstorage = _start + v.capacity();
  70. 			_finish = _start + v.size();
  71. 		}
  72. 		vector<T>& operator=(vector<T> v)
  73. 		{
  74. 			swap(_start, v._start);
  75. 			swap(_finish, v._finish);
  76. 			swap(_endofstorage, v._endofstorage);
  77. 			return *this;
  78. 		}
  79. 		/*vector<T>& operator=(const vector<T>& v)
  80. 		{
  81. 			if(_start!=v._start)
  82. 			{
  83. 				delete[] _start;
  84. 				_start = new T[v.capacity()];
  85. 				memcpy(_start, v._start, sizeof(T) * v.capacity());
  86. 				_endofstorage = _start + v.capacity();
  87. 				_finish = _start + v.size();
  88. 			}
  89. 			return *this;
  90. 		}*/
  91. 		size_t size()const
  92. 		{
  93. 			return _finish - _start;
  94. 		}
  95. 		size_t capacity()const
  96. 		{
  97. 			return _endofstorage - _start;
  98. 		}
  99. 		void reserve(size_t n)
  100. 		{
  101. 			if (n > capacity())
  102. 			{
  103. 				size_t sz = size();
  104. 				iterator tmp = new T[n];
  105. 				if (_start)//start不为为空
  106. 				{
  107. 					//memcpy(tmp, _start, sz*sizeof(T));
  108. 					for (size_t i = 0; i << sz; i++)
  109. 					{
  110. 						tmp[i] = _start[i];
  111. 					}
  112. 					delete[] _start;
  113. 				}
  114. 				_start = tmp;
  115. 				_finish = _start+sz;//finish还为0，start新空间，size()会返回很大的负值
  116. 				_endofstorage=_start+n;//endofstorage还为0，start新空间，capacity()会返回很大的负值
  117. 			}
  118. 		}
  119. 		void resize(size_t n, T val = T())
  120. 		{
  121. 			if (n < size())
  122. 			{
  123. 				_finish = _start + n;
  124. 			}
  125. 			else
  126. 			{
  127. 				if (n > capacity())
  128. 				{
  129. 					reserve(n);
  130.  
  131. 				}
  132. 				for (size_t i = size(); i < n; i++)
  133. 				{
  134. 					*_finish = val;
  135. 					_finish++;
  136. 				}
  137. 			}
  138. 		}
  139. 		bool empty()
  140. 		{
  141. 			return _start == _finish;
  142. 		}
  143. 		void push_back(const T& x)
  144. 		{
  145. 			if (_finish == _endofstorage)
  146. 			{
  147. 				size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
  148. 				reserve(newCapacity);
  149. 			}
  150. 			*_finish = x;
  151. 			_finish++;
  152. 		}
  153. 		void pop_back()
  154. 		{
  155. 			assert(!empty());
  156. 			--_finish;
  157. 		}
  158. 		void insert(iterator pos, const T& x)
  159. 		{
  160. 			size_t sz = pos - _start;
  161. 			if (_finish == _endofstorage)//判断增容
  162. 			{
  163. 				size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
  164. 				reserve(newCapacity);
  165. 				//更新pos，防止迭代器失效
  166. 				pos = _start + sz;
  167. 			}
  168. 			iterator end = _finish - 1;
  169. 			while (end >= pos)
  170. 			{
  171. 				*(end + 1) = *end;
  172. 				--end;
  173. 			}
  174. 			*end = x;
  175. 			++_finish;
  176. 		}
  177. 		iterator erase(iterator pos)
  178. 		{
  179. 			iterator it = pos + 1;
  180. 			while (it != end())
  181. 			{
  182. 				*(it - 1) = *it;
  183. 				++it;
  184. 			}
  185. 			_finish--; 
  186. 			return pos;
  187. 		}
  188. 		void PrintVector()const
  189. 		{
  190. 			vector<T>::const_iterator it = this->begin();
  191. 			while (it != this->end())
  192. 			{
  193. 				//*it += 1;//只能读，不能写
  194. 				cout << *it << " ";
  195. 				++it;
  196. 			}
  197. 			cout << endl;
  198. 		}
  199. 	private:
  200. 		iterator _start;
  201. 		iterator _finish;
  202. 		iterator _endofstorage;
  203. 	};
  204. 	void test_vector1()
  205. 	{
  206. 		vector<int> v;
  207. 		v.push_back(1);
  208. 		v.push_back(2);
  209. 		v.push_back(3);
  210. 		v.push_back(4);
  211. 		v.push_back(5);
  212. 		v.push_back(6);
  213. 		vector<int>::iterator it = v.begin();
  214. 		while (it != v.end())
  215. 		{
  216. 			cout << *it << " ";
  217. 			++it;
  218. 		}
  219. 		cout << endl;
  220. 		v.PrintVector();
  221. 	}
  222. 	void test_vector2()
  223. 	{
  224. 		vector<int> v;
  225. 		v.push_back(1);
  226. 		v.push_back(2);
  227. 		v.push_back(3);
  228. 		v.push_back(4);
  229. 		v.push_back(5);
  230. 		v.push_back(6);
  231. 		//v.pop_back();
  232. 		v.resize(3);
  233. 		v.resize(6,1);
  234. 		v.resize(12,2);
  235. 		vector<int>::iterator it = v.begin();
  236. 		while (it != v.end())
  237. 		{
  238. 			cout << *it << " ";
  239. 			++it;
  240. 		}
  241. 		cout << endl;
  242. 	}
  243. 	void test_vector3()
  244. 	{
  245. 		vector<int> v;
  246. 		v.push_back(1);
  247. 		v.push_back(2);
  248. 		v.push_back(3);
  249. 		v.push_back(4);
  250. 		v.push_back(5);
  251. 		v.push_back(6);
  252. 		vector<int>::iterator pos = find(v.begin(), v.end(), 3);
  253. 		v.insert(pos, 30);
  254. 		v.PrintVector();
  255. 	}
  256. 	void test_vector4()
  257. 	{
  258. 		vector<int> v;
  259. 		v.push_back(1);
  260. 		v.push_back(2);
  261. 		v.push_back(3);
  262. 		v.push_back(4);
  263. 		v.push_back(5);
  264. 		v.push_back(6);
  265. 		vector<int>::iterator pos = find(v.begin(), v.end(), 3);
  266. 		v.erase(pos);
  267. 		v.PrintVector();
  268. 	}
  269. 	void test_vector5()
  270. 	{
  271. 		vector<int> v;
  272. 		v.push_back(1);
  273. 		v.push_back(2);
  274. 		v.push_back(3);
  275. 		vector<int> v1(v);
  276. 		vector<int> v2;
  277. 		v1=v2=v;
  278.  
  279. 		v.PrintVector();
  280. 		v1.PrintVector();
  281. 		v2.PrintVector();
  282. 	}
  283. 	void test_vector6()
  284. 	{
  285. 		vector<string> v;
  286. 		v.push_back("111111111111111111");
  287. 		v.push_back("2222");
  288. 		v.push_back("3333");
  289. 		v.push_back("4444");
  290. 		v.push_back("5555");
  291. 		vector<string> v1(v);
  292.  
  293.  
  294. 		v.PrintVector();
  295. 		v1.PrintVector();
  296. 	}
  297. }
  298. int main()
  299. {
  300. 	//lj::test_vector1();
  301. 	//lj::test_vector2();
  302. 	//lj::test_vector3();
  303. 	lj::test_vector6();
  304. 	return 0;
  305. }

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

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

  

闽ICP备14008679号