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

vector底层实现及深层次拷贝问题_vector怎么拷贝

作者：很楠不爱3 | 2024-04-19 16:56:33

赞

踩

vector怎么拷贝

目录

大框架

接口实现

深层次拷贝问题（两次深拷贝）

大框架

为了与库里实现的更接近一些，先来看一下STL中是如何实现vector的（这里不是PJ版，PJ版稍微晦涩一点不容易理解，这里采用Linux下g++的版本）这里仅就大体框架做个简单介绍，其中复杂的概念不做过多解释。

 首先是vector定义的模板参数T和Alloc，这是空间配置器是一种底层实现机制，使用角度不用管。

可以看到源码做了很多typedef，主要是对格式的控制和方便理解编写。其中将T* typedef成了iterator，这个要注意，后面protected 成员变量会用到。

 这里成员变量就用到了刚刚typedef的iterator，实际上就是T* start ; T* finish;  T* end_of_storage;

T就是实例化模板参数。好像与我们设想的变量不太一样，我们设想的应该是有size和capacity的，但是这里全部统一使用指针，其实只是改变了使用方式，本质还是一样的。

 假设存在size（有效数据个数），capacity（容量），那么finish也可以表示成start+size，end_of_storage也可以表示成strat+capacity，本质是一样的。

后面是各个接口的实现，后面我们自己实现的时候具体说明，先把大框架搭建起来。

  1. namespace bc
  2. {
  3. 	template<class T>
  4. 	class vector
  5. 	{
  6. 	public:
  7. 		typedef T* iterator;
  8.  
  9. 	private:
  10. 		iterator _start;
  11. 		iterator _finish;
  12. 		iterator _end_of_storage;
  13. 	};
  14. }

为了避免和库里的冲突，将我们的实现代码封在命名空间内，库里的繁杂的typedef我们省略，只保留基本的T* 的重命名和成员变量表示。

接口实现

vector.h

  1. #pragma once
  2.  
  3. #include<iostream>
  4. #include<vector>
  5. #include<assert.h>
  6.  
  7. using namespace std;
  8.  
  9. namespace bc
  10. {
  11. 	template<class T>
  12. 	class vector
  13. 	{
  14. 	public:
  15. 		typedef T* iterator;
  16. 		vector()
  17. 			:_start(nullptr)
  18. 			, _finish(nullptr)
  19. 			, _end_of_storage(nullptr)
  20. 		{ }
  21.  
  22. 		//拷贝构造写法一
  23. 		//vector(const vector<T>& v)
  24. 		//	: _start(nullptr)
  25. 		//	, _finish(nullptr)
  26. 		//	, _end_of_storage(nullptr)
  27. 		//{
  28. 		//	reserve(size());
  29. 		//	for (auto& e : v) {
  30. 		//		push_back(e);
  31. 		//	}
  32. 		//}
  33.  
  34.  
  35. 		//拷贝构造现代写法
  36. 		template<class InputIterator>
  37. 		vector(InputIterator first, InputIterator last) 
  38. 			: _start(nullptr)
  39. 			, _finish(nullptr)
  40. 			, _end_of_storage(nullptr)
  41. 		{
  42. 			while (first != last) {
  43. 				push_back(*first);
  44. 				first++;
  45. 			}
  46. 		}
  47.  
  48. 		vector(vector<T>& v) 
  49. 			: _start(nullptr)
  50. 			, _finish(nullptr)
  51. 			, _end_of_storage(nullptr)
  52. 		{
  53. 			vector<T> tmp(v.begin(), v.end());
  54. 			swap(tmp);
  55. 		}
  56.  
  57. 		vector(size_t n, const T& val= T()) 
  58. 			: _start(nullptr)
  59. 			, _finish(nullptr)
  60. 			, _end_of_storage(nullptr)
  61. 		{
  62. 			reserve(n);
  63. 			for (size_t i = 0; i < n; ++i) {
  64. 				push_back(val);
  65. 			}
  66. 		}
  67. 		//函数重载
  68. 		vector(int n, const T& val= T())
  69. 			: _start(nullptr)
  70. 			, _finish(nullptr)
  71. 			, _end_of_storage(nullptr)
  72. 		{
  73. 			reserve(n);
  74. 			for (int i = 0; i < n; ++i) {
  75. 				push_back(val);
  76. 			}
  77. 		}
  78.  
  79. 		~vector() {
  80. 			delete[]_start;
  81. 			_start = _finish = _end_of_storage = nullptr;
  82. 		}
  83.  
  84. 		vector<T>& operator=(vector<T> v) {
  85. 			swap(v);
  86. 			return *this;
  87. 		}
  88.  
  89. 		size_t size()const {
  90. 			return _finish - _start;
  91. 		}
  92. 		size_t capacity()const {
  93. 			return _end_of_storage - _start;
  94. 		}
  95.  
  96. 		iterator begin() {
  97. 			return _start;
  98. 		}
  99. 		iterator end() {
  100. 			return _finish;
  101. 		}
  102. 		const iterator begin() const {
  103. 			return _start;
  104. 		}
  105. 		const iterator end() const {
  106. 			return _finish;
  107. 		}
  108.  
  109. 		bool empty()const {
  110. 			return _finish == _start;
  111. 		}
  112.  
  113. 		void clear() {
  114. 			_finish = _start;
  115. 		}
  116.  
  117. 		void swap(vector<T>& v) {
  118. 			std::swap(_start, v._start);
  119. 			std::swap(_finish, v._finish);
  120. 			std::swap(_end_of_storage, v._end_of_storage);
  121. 		}
  122. 		T& operator[](size_t pos) {
  123. 			assert(pos < size());
  124. 			return _start[pos];
  125. 		}
  126. 		const T& operator[](size_t pos) const {
  127. 			assert(pos < size());
  128. 			return _start[pos];
  129. 		}
  130.  
  131. 		void resize(size_t n, T val = T()) {
  132. 			if (n > capacity()) {
  133. 				reserve(n);
  134. 			}
  135. 			if (n > size() && n <= capacity()) {
  136. 				while (_finish < _start + n) {
  137. 					*_finish = val;
  138. 					++_finish;
  139. 				}
  140. 			}
  141. 			if (n <= size()) {
  142. 				_finish = _start + n;
  143. 			}
  144. 		}
  145.  
  146. 		void reserve(size_t n) {
  147. 			if (n > capacity()) {
  148. 				size_t oldsize = size();
  149. 				T* tmp = new T[n];
  150. 				if (_start != nullptr) {
  151. 					memcpy(tmp, _start, sizeof(T) * oldsize);
  152. 					/*for (size_t i = 0; i < oldsize; ++i) {
  153. 						tmp[i] = _start[i];
  154. 					}*/
  155. 					delete[]_start;
  156. 				}
  157. 				_start = tmp;
  158. 				_finish = tmp + oldsize;
  159. 				_end_of_storage = _start + n;
  160. 			}
  161. 		}
  162.  
  163.  
  164.  
  165. 		void push_back(const T& x) {
  166. 			if (_finish == _end_of_storage) {
  167. 				size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
  168. 				reserve(newcapacity);
  169. 			}
  170. 			*_finish = x;
  171. 			++_finish;
  172. 		}
  173.  
  174.  
  175. 		void pop_back() {
  176. 			assert(!empty());
  177. 			_finish--;
  178. 		}
  179.  
  180. 		//迭代器失效
  181. 		iterator insert(iterator pos, const T& x) {
  182. 			assert(pos >= _start);
  183. 			assert(pos < _finish);
  184. 			if (_finish == _end_of_storage) {
  185. 				size_t len = pos - _start;
  186. 				size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
  187. 				reserve(newcapacity);
  188. 				pos = _start + len;
  189. 			}
  190. 			iterator end = _finish - 1;
  191. 			while (end >= pos) {
  192. 				*(end + 1) = *(end);
  193. 				--end;
  194. 			}
  195. 			*pos = x;
  196. 			_finish++;
  197. 			return pos;	
  198. 		}
  199.  
  200. 		iterator erase(iterator pos) {
  201. 			assert(pos >= _start);
  202. 			assert(pos < _finish);
  203. 			iterator begin = pos + 1;
  204. 			while (begin < _finish) {
  205. 				*(begin-1) = *(begin);
  206. 				++begin;
  207. 			}
  208. 			_finish--;
  209. 			return pos;
  210. 		}
  211.  
  212. 	private:
  213. 		iterator _start;
  214. 		iterator _finish;
  215. 		iterator _end_of_storage;
  216. 	};

下面是我给出的测试用例：

vector.h

  1. 	void Test1() {
  2. 		vector<int>a;
  3. 		a.push_back(1);
  4. 		a.push_back(1);
  5. 		a.push_back(1);
  6. 		a.push_back(1);
  7. 		a.push_back(1);
  8. 		cout << a.capacity() << endl;
  9. 		for (size_t i = 0; i < a.size(); ++i)
  10. 		{
  11. 			cout << a[i] << " ";
  12. 		}
  13. 		cout << endl;
  14.  
  15. 		vector<int>::iterator it = a.begin();
  16. 		while (it != a.end()) {
  17. 			cout << (*it) << " ";
  18. 			it++;
  19. 		}
  20. 		cout << endl;
  21.  
  22. 		//a.resize(2);
  23. 		for (auto e : a) {
  24. 			cout << e << " ";
  25. 		}
  26. 		cout << endl;
  27.  
  28. 		cout << a.empty() << endl;
  29.  
  30. 		a.pop_back();
  31.  
  32. 		for (auto e : a) {
  33. 			cout << e << " ";
  34. 		}
  35. 		cout << endl;
  36. 	}
  37.  
  38. 	void Test2() {
  39. 		vector<int> a;
  40. 		a.push_back(1);
  41. 		a.push_back(1);
  42. 		a.push_back(1);
  43. 		a.push_back(1);
  44. 		for (auto e : a) {
  45. 			cout << e << " ";
  46. 		}
  47. 		cout << endl;
  48.  
  49. 		a.insert(a.begin(), 0);
  50.  
  51. 		for (auto e : a) {
  52. 			cout << e << " ";
  53. 		}
  54. 		cout << endl;
  55.  
  56. 		vector<int>::iterator it = find(a.begin(), a.end(), 1);
  57. 		if (it != a.end()) {
  58. 			a.insert(it, 2);
  59. 		}
  60. 		for (auto e : a) {
  61. 			cout << e << " ";
  62. 		}
  63. 		cout << endl;
  64.  
  65. 		(*it)++;
  66. 		for (auto e : a) {
  67. 			cout << e << " ";
  68. 		}
  69. 		cout << endl;
  70. 	}
  71.  
  72. 	void Test3() {
  73. 		vector<int> v;
  74. 		v.push_back(1);
  75. 		v.push_back(2);
  76. 		v.push_back(3);
  77. 		v.push_back(4);
  78. 		v.push_back(4);
  79. 		v.push_back(5);
  80. 		vector<int>::iterator it = v.begin();
  81. 		while (it != v.end()) {
  82. 			if ((*it) % 2 == 0) {
  83. 				it = v.erase(it);
  84. 			}
  85. 			else {
  86. 				++it;
  87. 			}
  88. 		}
  89. 		for (auto e : v) {
  90. 			cout << e << " ";
  91. 		}
  92. 		cout << endl; 
  93. 	}
  94.  
  95. 	void Test4() {
  96. 		vector<int> v;
  97. 		v.push_back(1);
  98. 		v.push_back(1);
  99. 		v.push_back(1);
  100. 		v.push_back(1);
  101. 		vector<int> a(v);
  102. 		for (auto e : a) {
  103. 			cout << e << " ";
  104. 		}
  105. 		cout << endl;
  106.  
  107. 		vector<int> b;
  108. 		b = a;
  109. 		for (auto e : b) {
  110. 			cout << e << " ";
  111. 		}
  112. 		cout << endl;
  113.  
  114. 		vector<int>c(10, 1);
  115. 		for (auto e : c) {
  116. 			cout << e << " ";
  117. 		}
  118. 		cout << endl;
  119. 	}
  120.  
  121. void Test5()
  122. 	{
  123. 		vector<vector<int>> vv;
  124. 		vector<int> v(4, 1);
  125. 		vv.push_back(v);
  126. 		vv.push_back(v);
  127. 		vv.push_back(v);
  128. 		vv.push_back(v);
  129. 		vv.push_back(v);
  130.  
  131. 		for (size_t i = 0; i < vv.size(); ++i)
  132. 		{
  133. 			for (size_t j = 0; j < vv[i].size(); ++j)
  134. 			{
  135. 				cout << vv[i][j] << " ";
  136. 			}
  137. 			cout << endl;
  138. 		}
  139. 		cout << endl;
  140. 	}	
  141. }

test.cpp

  1. #include"vector.h"
  2.  
  3. int main()
  4. {
  5. 	bc::Test1();
  6.     bc::Test2();
  7. 	bc::Test3();
  8. 	bc::Test4();
  9. 	bc::Test5();
  10.  
  11. 	/*vector<int> v;
  12. 	v.push_back(1);
  13. 	v.push_back(2);
  14. 	v.push_back(3);
  15. 	v.push_back(4);
  16. 	v.push_back(5);
  17. 	std::vector<int>::iterator it = v.begin();
  18. 	while (it != v.end()) {
  19. 		if ((*it) % 2 == 0) {
  20. 			v.erase(it);
  21. 		}
  22. 		++it;
  23. 	}
  24. 	for (auto e : v) {
  25. 		cout << e << " ";
  26. 	}
  27. 	cout << endl;*/
  28.  
  29. 	return 0;
  30. }

以上是常用接口的大致实现，基本功能包含在内，还有些不太常用的接口没有实现。

深层次拷贝问题（两次深拷贝）

在测试vector<vector<int>>二维数组的时候，发现一个奇怪的现象：

当创建好vector<vector<int>> vv模型，并创建出内置数组vector<int> v (4,1)后，此时想要设定行数，也就是通过push_back插入行实现时，如果插入4个以内，没有问题，超过4个就会报错。

 

 

由此我们可以判定问题出在扩容上，具体我画图来解释。

 对于vector<vector<int>>模型要有一定理解，外部的大类型是vector<>，< >里面的类型是vector<int>，所以先从内部开始创建，vector<int> v(4,1) 构造一个{1,1,1,1}的一维数组，里面构建好了，在外面通过push_back插入，相当于插入一个一个这样的一维数组，这样就构建了二维数组，push_back多少次就相当于有多少行，里面4相当于列。

vector<int> v 数组里面的元素是int类型的，外面通过_start 指针指向v数组，指针是int* 类型的，一个指针指向一个v数组，外面还有一个_start指针指向整个vector<vector<int>>，指针类型是vector<int>*

建好二维数组后来看扩容问题，当调用reserve时，需要开辟新空间tmp，用memcpy将数据传给tmp 。                   

 而memcpy是按内存将数据拷贝给tmp的，这里的拷贝是浅拷贝，这就会导致一个问题，tmp最后也会指向_start 空间，

然后memcpy结束就是delete[]_start，delete会调用析构函数将_start空间释放，这下tmp指向的空间get不到了，tmp就是野指针了。

所以要想解决这个问题，就要解决内层浅拷贝的问题，将其改为深拷贝，这样外层tmp对象深拷贝，里层tmp数据也进行深拷贝，就不会出问题了。

解决方案：1、不用memcpy，利用operator = 重载函数将数据一个一个拷贝给tmp

  1. 		void reserve(size_t n)
  2. 		{
  3. 			if (n > capacity())
  4. 			{
  5. 				size_t oldSize = size();
  6. 				T* tmp = new T[n];
  7.  
  8. 				if (_start)
  9. 				{
  10. 					//memcpy(tmp, _start, sizeof(T)*oldSize);
  11. 					for (size_t i = 0; i < oldSize; ++i)
  12. 					{
  13. 						tmp[i] = _start[i];
  14. 					}
  15.  
  16. 					delete[] _start;
  17. 				}
  18. 				_start = tmp;
  19. 				_finish = tmp + oldSize;
  20. 				_endofstorage = _start + n;
  21. 			}
  22. 		}

tmp[i] = _start[i] 将_start[i] 一个一个拷贝给tmp[i]，这里调用operator= 是深拷贝。

  1. 		vector<T>& operator=(vector<T> v)
  2. 		{
  3. 			swap(v);
  4. 			return *this;
  5. 		}

但是这种方法缺点是效率太低。在C++11 中会有更好的方式解决上述问题。

以上就是深层拷贝的内容，关于底层实现还有其他不同版本，但因为复杂度等原因我们是按Linux g++使用的库实现的，感谢浏览！

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

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

  

闽ICP备14008679号