• [c++基础]-vector类

    前言

    作者：小蜗牛向前冲

    名言：我可以接受失败，但我不能接受放弃

     如果觉的博主的文章还不错的话，还请点赞，收藏，关注👀支持博主。如果发现有问题的地方欢迎❀大家在评论区指正。

    目录

    一、 vector类的基本用法

    1、什么是vector

    2、vector的基本使用 

    3、reserve 和resize使用细节

    ​二、刨析迭代器失效

    1、引起其底层空间改变导致失效

     2、指定位置元素的删除操作--erase导致失效

     三、模拟实现vector

    1、模拟实现

    2、模拟实现中深浅拷贝问题

    本期学习目标: 了解vector类的基本用法，刨析迭代器失效问题，刨析深浅拷贝问题，模拟实现vector。

    一、 vector类的基本用法

    1、什么是vector

    简单点来是其实就是一个数组，那这和我们在C语言学习的数组又有什么区别。

    下面我们来看到vector的文档介绍：

    1.  vector是表示可变大小数组的序列容器。
    2.  就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素 进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
    3.  本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是 一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。
    4. vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存 储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是 对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
    5. 因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。
    6.  与其它动态序列容器相比（deque, list and forward_list）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起list和forward_list 统一的迭代器和引用更好。 

    2、vector的基本使用 

    对于vector的来是他是一个类，他有自己的成员函数和成员变量，但是这次我们不在一一去为大家分析，大家有不理解的地方可以多多查询文档。(博主一般用cplusplus查询)

    我对数据进行操作无法就是对数据进行增删查改，而数组也是要对数据进行处理的，下面我们就一起去见一见vector的增删查改。

    vector增删查改

    接口说明

    push_back（重点）

    尾插

    pop_back （重点）

    尾删

    find

    查找。（注意这个是算法模块实现，不是vector的成员接口）

    insert

    在position之前插入val

    erase

    删除position位置的数据

    swap

    交换两个vector的数据空间

    operator[] （重点）

    像数组一样访问

    简单举例：

    1. int main()
    2. {
    3. 	vector<int> v;
    4. 	v.push_back(1);
    5. 	v.push_back(2);
    6. 	v.push_back(3);
    7. 	v.push_back(4);
    8. 	v.push_back(5);
    9. 	//迭代器遍历
    10. 	vector<int>::iterator it = v.begin();
    11. 	while (it != v.end())
    12. 	{
    13. 		cout << *it << " ";
    14. 		++it;
    15. 	}
    16. 	cout << endl;
    17. 	return 0;
    18. }

      上面那些增删查改的接口大家多用用就会使用了，但是大家都知道C++的语法是细节特别多的，

     下面我们了解一下在使用的时候要注意哪些细节：

    3、reserve 和resize使用细节

    大家可能会说reserve不就是提前开好空间吗？resize不就是开空间并初始化吗？这哪里有什么细节。下面大家看看一段代码：

    1. void test()
    2. {
    3. 	vector<int> v;
    4. 	//开好100个元素的空间
    5. 	v.reserve(100);
    6. 	//用[]插入10个元素
    7. 	for (size_t i = 0;i < 10;++i)
    8. 	{
    9. 		v[i] = i;
    10. 	}
    11. }

    大家觉的上面代码可行吗？不少小伙伴可能会说没问题，我开好了100个元素的空间，存放10个元素肯定没问题，但事实真的是如此吗？

     但是实际上代码崩溃了，还是断错误，这是怎么回事呢?难道我们不能使用我开辟的空间吗？

     其实不然，我是可以使用，但是由于在重载[]的时候加了检测是否越界的断言，因为我们用reserve仅仅只是开辟了100个空间，但是size==0，而[]的检测正好是检测size在遍历的时候有没有超过，而刚刚开始数组中的元素为0，而我们却要输入到第10个元素这肯定是不被允许的。

    那么当我们要为数组赋值元素怎么办了，就可以用resize初始化好元素个数在进行赋值。

    1. void test3()
    2. {
    3. 	vector<int> v;
    4. 	//开好10个元素的空间
    5. 	v.resize(10);
    6. 	//用[]插入10个元素
    7. 	for (size_t i = 0;i < 10;++i)
    8. 	{
    9. 		v[i] = i;
    10. 	}
    11. 	for (auto ret : v)
    12. 	{
    13. 		cout << ret << " ";
    14. 	}
    15. 	cout << endl;
    16. }

    二、刨析迭代器失效

    在很多种情况下vector的迭代器会失效，为什么会失效呢？

            迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了 封装，比如：vector的迭代器就是原生态指针T* 。因此迭代器失效，实际就是迭代器底层对应指针所指向的 空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器， 程序可能会崩溃)。

    1、引起其底层空间改变导致失效

          当我们对数组进行增删查改时，会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、 push_back等。

    1. void test4()
    2. {
    3. 	vector<int> v;
    4. 	v.push_back(1);
    5. 	v.push_back(2);
    6. 	v.push_back(3);
    7. 	v.push_back(4);
    8. 	auto it = v.begin();
    9. 	v.resize(100, 2);//扩间
    10. }

    扩容前 

    扩容后

          这里我们可看到当v进行扩容后，他的空间不在是原来的空间进行扩容的而是，进行异地扩容的。但是这时候it他任何指向原来的空间，而原来的空间已经释放，所以他会失效。也就是说当用vector开辟出来的数组在扩容后，有可能会导致迭代器失效。

     2、指定位置元素的删除操作--erase导致失效

         erase删除pos位置元素后，pos位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代 器不应该会失效，但是：如果pos刚好是最后一个元素，删完之后pos刚好是end的位置，而end位置是 没有元素的，那么pos就失效了。因此删除vector中任意位置上元素时，vs就认为该位置迭代器失效了。

    下面继续举个例子：

    1. #include 
    2. #include 
    3. using namespace std;
    4.  
    5. int main()
    6. {
    7. 	int a[] = { 1, 2, 3, 4 };
    8. 	vector<int> v(a, a + sizeof(a) / sizeof(int));
    9. 	// 使用find查找3所在位置的iterator
    10. 	vector<int>::iterator pos = find(v.begin(), v.end(), 3);
    11. 	// 删除pos位置的数据，导致pos迭代器失效。
    12. 	v.erase(pos);
    13. 	cout << *pos << endl; // 此处会导致非法访问
    14. 	return 0;
    15. }

     当我们进行调试的时候发现程序会崩溃，大家可能会想我这不删除的是3吗?这时pos的应该指向4啊？没问题，但是由于C++的检测机制的原因，这里我们仍然认为pos是失效的。

    所以是：只要我们进行了erase操作次迭代器就会失效。

    那我们在后面又要用到迭代器怎么办？

    其实很简单，我们只要在迭代器失效后在更新一下迭代器就可以了。

     三、模拟实现vector

    1、模拟实现

    为了更好的理解vector的底层实现，下面要模拟实现vector:

    这里我们写二个文件，test.cpp用来测试，而vector.h用来实现cector各种功能

    1. #define  _CRT_SECURE_NO_WARNINGS
    2.  
    3. #include
    4. #include
    5. #include
    6. #include
    7. using namespace std;
    8. #include"vector.h"
    9.  
    10. int main()
    11. {
    12. 	pjb::test2();
    13. 	return 0;
    14. }

    test.cpp 

    1. #pragma once
    2.  
    3.  
    4. namespace pjb
    5. {
    6. 	template<class T>
    7. 	class vector
    8. 	{
    9. 	public:
    10. 		//二种版本的迭代器
    11. 		typedef T* iterator;
    12. 		typedef const T* const_iterator;
    13.  
    14. 		iterator begin()
    15. 		{
    16. 			return _start;
    17. 		}
    18.  
    19. 		iterator end()
    20. 		{
    21. 			return _finish ;
    22. 		}
    23. 		const_iterator begin()const
    24. 		{
    25. 			return _start;
    26. 		}
    27.  
    28. 		const_iterator end()const
    29. 		{
    30. 			return _finish;
    31. 		}
    32. 		
    33. 		bool empty()const
    34. 		{
    35. 			return _start == _finish;
    36. 		}
    37.  
    38. 		size_t size()const
    39. 		{
    40. 			return _finish - _start;
    41. 		}
    42.  
    43. 		size_t capacity()const
    44. 		{
    45. 			return _endofstorage - _start;
    46. 		}
    47.  
    48. 		T& operator[](size_t pos)
    49. 		{
    50. 			assert(pos < size());
    51. 			return _start[pos];//这里可理解_strart是一个指针
    52. 		}
    53.  
    54. 		T& operator[](size_t pos)const
    55. 		{
    56. 			assert(pos < size());
    57. 			return _start[pos];//这里可理解_strart是一个指针
    58. 		}
    59.  
    60. 		//析构函数
    61. 		vector()
    62. 			:_start(nullptr)
    63. 			,_finish(nullptr)
    64. 			,_endofstorage(nullptr)
    65. 		{}
    66. 		//拷贝构造v2(v1)
    67. 		vector(size_t n,const T& val =T())
    68. 			:_start(nullptr)
    69. 			, _finish(nullptr)
    70. 			, _endofstorage(nullptr)
    71. 		{
    72. 			reserve(n);
    73. 			for (size_t i = 0; i < n;++i)
    74. 			{
    75. 				push_back(val);
    76. 			}
    77. 		}
    78. 		//这里是为了解决类型不匹配的问题
    79. 		//vector v(10,1);
    80. 		//vectorv(10,'A');
    81. 		vector(int n, const T& val = T())
    82. 			:_start(nullptr)
    83. 			, _finish(nullptr)
    84. 			, _endofstorage(nullptr)
    85. 		{
    86. 			reserve(n);
    87. 			for (int i = 0; i < n;++i)
    88. 			{
    89. 				push_back(val);
    90. 			}
    91. 		}
    92. 		//迭代器版本拷贝构造
    93. 		template<class InputIterator>
    94. 		vector(InputIterator first, InputIterator last)
    95. 			:_start(nullptr)
    96. 			, _finish(nullptr)
    97. 			, _endofstorage(nullptr)
    98. 		{
    99. 			while (first != last)
    100. 			{
    101. 				push_back(*first);
    102. 				++first;
    103. 			}
    104. 		}
    105.  
    106. 		vector(const vector& v)
    107. 			:_start(nullptr)
    108. 			, _finish(nullptr)
    109. 			, _endofstorage(nullptr)
    110. 		{
    111. 			vector tmp(v.begin(), v.end());
    112. 			swap(tmp);
    113. 		}
    114.  
    115. 		//析构函数
    116. 		~vector()
    117. 		{
    118. 			delete[] _start;
    119. 			_start = _finish = _endofstorage = nullptr;
    120. 		}
    121.  
    122. 		//开内存
    123. 		void reserve(size_t n)
    124. 		{
    125. 			if (n > capacity())
    126. 			{
    127. 				size_t oldSize = size();
    128. 				T* tmp = new T[n];
    129. 				if (_start)
    130. 				{
    131. 					//memcpy(tmp, _start, sizeof(T) * oldSize);//用memcop会出现浅拷贝的问题
    132. 					for (size_t i = 0;i < oldSize;++i)
    133. 					{
    134. 						tmp[i] = _start[i];
    135. 					}
    136. 					delete[]_start;//释放原来的空间
    137. 				}
    138. 				_start = tmp;
    139. 				_finish = tmp + oldSize;
    140. 				_endofstorage = _start + n;
    141. 			}
    142. 		}
    143. 		//开内存并初始化
    144. 		void resize(size_t n,T val = T ())
    145. 		{
    146. 			if (n > capacity())
    147. 			{
    148. 				reserve(n);
    149. 			}
    150. 			if (n > size())
    151. 			{
    152. 				//进行初始化，size后面的空间
    153. 				while (_finish < _start + n)
    154. 				{
    155. 					*_finish = val;
    156. 					++_finish;
    157. 				}
    158. 			}
    159. 			//删除数据
    160. 			else
    161. 			{
    162. 				_finish = _start + n;
    163. 			}
    164. 		}
    165. 		//重载=
    166. 		//v1==v2
    167. 		vector& operator=(vector v)
    168. 		{
    169. 			swap(v);
    170. 			return *this;
    171. 		}
    172.  
    173. 		//尾插
    174. 		void push_back(const T& x)
    175. 		{
    176. 			if (_finish == _endofstorage)
    177. 			{
    178. 				size_t  newCapacity = capacity() == 0 ? 4 : capacity() * 2;
    179. 				reserve(newCapacity);
    180. 			}
    181. 			*_finish = x;
    182. 			++_finish;
    183. 		}
    184. 		
    185. 		//尾删除
    186. 		void pop_back()
    187. 		{
    188. 			assert(empty());
    189. 			--_finish;
    190. 		}
    191. 		//插入
    192. 		//迭代器失效
    193. 		void insert(iterator pos, const T& val)
    194. 		{
    195. 			assert(pos < _finish);
    196. 			assert(pos >= _start);
    197. 			if (_finish == _endofstorage)
    198. 			{
    199. 				//提前算好pos距离_start的距离，好进行更新
    200. 				size_t  len = pos - _start;
    201. 				size_t  newCapacity = capacity() == 0 ? 4 : capacity() * 2;
    202. 				reserve(newCapacity);
    203. 				//这里由于扩容回导致迭代器失效，需要跟更新pos
    204. 				pos = _start + len;
    205. 			}
    206. 			//挪动数据,从后向前挪动
    207. 			iterator end = _finish - 1;
    208. 			while (end >= pos)
    209. 			{
    210. 				*(end + 1) = *end;
    211. 				--end;
    212. 			}
    213. 			*pos = val;
    214. 			++_finish;
    215. 		}
    216. 		//交换
    217. 		void swap(vector& v)
    218. 		{
    219. 			std::swap(_start, v._start);
    220. 			std::swap(_finish, v._finish);
    221. 			std::swap(_endofstorage, v._endofstorage);
    222. 		}
    223. 		//清理
    224. 		void clear()
    225. 		{
    226. 			_finish = _start;
    227. 		}
    228. 	private:
    229. 		iterator _start;//指向数组的第1个数据
    230. 		iterator _finish;//指向数组最后1个元素的下个位置
    231. 		iterator _endofstorage;//指向容量的位置
    232. 	};

    vector.h

    2、模拟实现中深浅拷贝问题

    其实我们在模拟实现中要考虑很多问题，其中最为重要的是迭代器失效和深浅拷贝问题，迭代器失效的问题前面已经说过了这里就不在多说了，下面我们一起来研究一下深浅拷贝问题。

    这里我们来看上面我们模拟实现reserve:

    1. 		void reserve(size_t n)
    2. 		{
    3. 			if (n > capacity())
    4. 			{
    5. 				size_t oldSize = size();
    6. 				T* tmp = new T[n];
    7. 				if (_start)
    8. 				{
    9. 					memcpy(tmp, _start, sizeof(T) * oldSize);
    10. 					delete[]_start;//释放原来的空间
    11. 				}
    12. 				_start = tmp;
    13. 				_finish = tmp + oldSize;
    14. 				_endofstorage = _start + n;
    15. 			}
    16. 		}

    分析: 

    1. memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中。
    2. 如果拷贝的是自定义类型的元素，memcpy既高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝。

    测试代码：

    1. 	void test3()
    2. 	{
    3. 		vectorint>> vv;
    4. 		vector<int> v(5, 1);
    5. 		vv.push_back(v);
    6. 		vv.push_back(v);
    7. 		vv.push_back(v);
    8. 		vv.push_back(v);
    9. 		vv.push_back(v);//这里多了这里插入就要扩容
    10.  
    11. 		for (size_t i = 0; i < vv.size(); ++i)
    12. 		{
    13. 			for (size_t j = 0; j < vv[i].size(); ++j)
    14. 			{
    15. 				cout << vv[i][j] << " ";
    16. 			}
    17. 			cout << endl;
    18. 		}
    19. 		cout << endl;
    20. 	}

     

    不需要扩容 

    要扩容 

     这里我们用的是一个二维数组，也就是vector的类型又是一个vector，这里为什么会崩溃，其原来是这里进行了扩容，就要进行空间的拷贝，但这里进行的是浅拷贝，所以就崩溃了。

     没扩容前的空间指向

     

     扩容后

    这里结合上图我们一起了分析一下为什么一扩容就会崩溃呢？

    在扩容前vector*的数组他指向一个空间，这个空间存放了多个vector。

    但是当扩容后，vtmp就扩容8空间存放多个vector这是没问题的；但是这里每个vector由于用的是memcpy拷贝的，就会出现浅拷贝现象，也就是tmp中的vector的仍然指向原来的空间，但是当拷贝完后vector的原空间是要被释放的。使用这里程序自然就崩溃了。

    那我们怎么解决呢？

    其实也很简单，我们只要保证进行二次深拷贝就可以了。

    1. 		//开内存
    2. 		void reserve(size_t n)
    3. 		{
    4. 			if (n > capacity())
    5. 			{
    6. 				size_t oldSize = size();
    7. 				T* tmp = new T[n];
    8. 				if (_start)
    9. 				{
    10. /*					memcpy(tmp, _start, sizeof(T) * oldSize);*///用memcop会出现浅拷贝的问题
    11. 					for (size_t i = 0;i < oldSize;++i)
    12. 					{
    13. 						tmp[i] = _start[i];
    14. 					}
    15. 					delete[]_start;//释放原来的空间
    16. 				}
    17. 				_start = tmp;
    18. 				_finish = tmp + oldSize;
    19. 				_endofstorage = _start + n;
    20. 			}
    21. 		}

    这里我们调用对象的赋值就可以解决了。

  • 相关阅读:
    LaTeX的section章节标题怎么设置为1,2,3？现在显示不了
    基于springboot的高校失物招领系统毕业设计源码111731
    SQL 改写系列七：谓词移动
    最新出炉！2022金九银十Java面试复盘，22w字
    Java18新特性
    Mac版本破解Typora，解决Mac安装软件的“已损坏，无法打开。 您应该将它移到废纸篓”问题
    WZOI-227我家的门牌号
    机器学习实验三：决策树-隐形眼镜分类（判断视力程度）
    javascript的AMD模式
    了解 IPv4 和 IPv6 之间的区别？
  • 原文地址：https://blog.csdn.net/qq_61552595/article/details/128110583