• ＜stl系列＞，vector深度剖析，掌握stl容器从这篇文章开始

    目录

    前言

    一、vector的介绍

    二、vector的使用

    1.基本函数接口

    2、迭代器失效

    2.1案例一

    2.2案例二

    三、vector的模拟实现

    1、核心框架图例

    2、核心框架接口模拟实现 

    3、使用memcpy拷贝问题

    总结

    前言

    哈喽，小伙伴们大家好。上一篇文章我们介绍了string类，和string一样，vector同样是stl容器的重要组成部分，那么今天就让我们一起来学习一下吧。

    一、vector的介绍

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

    二、vector的使用

    1.基本函数接口

    vector学习时一定要学会查看文档：vector的文档介绍，vector在实际中非常的重要，在实际中我们熟悉常见的接口就可以，下面列出了哪些接口是要重点掌握的。

     vector的函数和string极为相似，具体使用方法我在string的文章中详细介绍，相信大家结合上篇文章还有文档，使用一些基本的函数应该不是问题。

    2、迭代器失效

    2.1案例一

    先介绍一个函数，find函数，包含在头文件中，只要传迭代器给它，他就会从迭代器范围内搜索特定内容，并返回相应位置的迭代器。如果找不到，则返回末尾的（末尾的迭代器一般不在范围内）

     我们看一个代码：

    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. 	// 3的前面插入一个30
    11. 	vector<int>::iterator pos = find(v.begin(), v.end(), 3);
    12. 	if (pos != v.end())
    13. 	{
    14. 		v.insert(pos, 30);
    15. 	}
    16.  
    17. 	for (auto e : v)
    18. 	{
    19. 		cout << e << " ";
    20. 	}
    21. 	cout << endl;
    22.  
    23. 	// 删除3
    24. 	// pos在insert以后就失效了，所以我们不要用他
    25. 	v.erase(pos);
    26. 	for (auto e : v)
    27. 	{
    28. 		cout << e << " ";
    29. 	}
    30. 	cout << endl;
    31. }

    这里肯能有两种情况：

    情况1：不发生增容，pos的意义变了

     pos的意义改变，插入数据后，pos不再指向3，而是指向30，导致删除时没有按照我们的预期删掉3。

    情况2：发生增容，程序崩溃

    如果插入数据后，恰好赶上vector增容，则会崩溃。因为在增容时，编译器会把原来的空间销毁，去开辟一个新的空间，那么pos就成了野指针，再使用时导致程序崩溃。

    想要解决这个问题很简单，只需要在删除之前再调用一次find函数。

    1. 	// 删除3
    2. 	// pos在insert以后就失效了，所以我们不要用他
    3. 	pos = find(v.begin(), v.end(), 3);
    4. 	if (pos != v.end())
    5. 	{
    6. 		v.erase(pos);
    7. 	}

    2.2案例二

    代码如下：

    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. 	v.push_back(6);
    10. 	v.push_back(7);
    11.  
    12. 	vector<int>::iterator it = v.begin();
    13. 	while (it != v.end())
    14. 	{
    15. 		if (*it % 2 == 0)
    16. 		{
    17. 			// erase(it)以后 it失效，不能++，
    18. 			 v.erase(it);
    19. 			 it++;
    20. 		}
    21. 		else
    22. 		{
    23. 			++it;
    24. 		}
    25. 	}
    26.  
    27. 	for (auto e : v)
    28. 	{
    29. 		cout << e << " ";
    30. 	}
    31. 	cout << endl;
    32. }

    该代码运行过程如下，当it指向2时，删除2后，it开始指向3，意义改变，迭代器失效。然后再执行++命令，会直接指向4，等于越过了3的判断。更严重的是，it既然会越过3，在后面就有可能越过v.end(),变成野指针。 

    解决方法：  

    1. while (it != v.end())
    2. 	{
    3. 		if (*it % 2 == 0)
    4. 		{
    5. 			// erase(it)以后 it失效，不能++，
    6. 			// erase 会返回删除位置it的下一个位置
    7. 			it = v.erase(it);
    8. 		}
    9. 		else
    10. 		{
    11. 			++it;
    12. 		}
    13. 	}

     结论：无论是插入或删除都有可能导致迭代器失效，迭代器失效有两种情况，一是意义改变，二是变成野指针。 

    三、vector的模拟实现

    1、核心框架图例

    2、核心框架接口模拟实现 

    1. namespace zxy
    2. {
    3. 	template <class T>
    4. 	class vector
    5. 	{
    6. 	public:
    7. 		typedef T* iterator;
    8. 		typedef const T* const_iterator;
    9. 		
    10. 		//构造函数
    11. 		vector()
    12. 			:_start(nullptr)
    13. 			,_finish(nullptr)
    14. 			,_endofstorage(nullptr)
    15. 		{}
    16.  
    17. 		//拷贝构造
    18. 		vector(const vector& v)
    19. 			:_start(nullptr)
    20. 			,_finish(nullptr)
    21. 			,_endofstorage(nullptr)
    22. 		{
    23. 			_start=new T[v.capacity()];
    24. 			/*memcpy(_start,v._start,v.size()*sizeof(T))  拷贝构造string等自定义类型时，会出问题*/
    25. 			for (size_t i = 0; i < v.size(); i++)
    26. 			{
    27. 				_start[i] = v._start[i];
    28. 			}
    29. 			_finish = _start + v.size();
    30. 			_endofstorage = _start + v.capacity();
    31. 		}
    32.  
    33. 		//析构函数
    34. 		~vector()
    35. 		{
    36. 			delete[] _start;
    37. 			_start = _finish = _endofstorage=NULL;
    38. 		}
    39.  
    40. 		void swap(vector& v)
    41. 		{
    42. 			std::swap(_start, v._start);
    43. 			std::swap(_finish, v._finish);
    44. 			std::swap(_endofstorage, v._endofstorage);
    45. 		}
    46.  
    47. 		//赋值运算符重载
    48. 		vector& operator=(vector v)
    49. 		{
    50. 			swap(v);
    51. 			return *this;
    52. 		}
    53.  
    54. 		//判空
    55. 		bool empty()
    56. 		{
    57. 			return _start == _finish;
    58. 		}
    59.  
    60. 		//取开头的迭代器
    61. 		iterator begin()
    62. 		{
    63. 			return _start;
    64. 		}
    65.  
    66. 		//取末尾的迭代器
    67. 		iterator end()
    68. 		{
    69. 			return _finish;
    70. 		}
    71.  
    72. 		//计算存储个数
    73. 		size_t size() const
    74. 		{
    75. 			return _finish - _start;
    76. 		}
    77.  
    78. 		//计算容量
    79. 		size_t capacity() const
    80. 		{
    81. 			return _endofstorage - _start;
    82. 		}
    83.  
    84. 		//[]运算符重载
    85. 		T& operator[](size_t i)
    86. 		{
    87. 			assert(i < size());
    88. 			return _start[i];
    89. 		}
    90.  
    91. 		const T& operator[](size_t i) const
    92. 		{
    93. 			assert(i < size());
    94. 			return _start[i];
    95. 		}
    96.  
    97. 		//开辟特定空间
    98. 		void reserve(size_t n)
    99. 		{
    100. 			T* temp = new T[n];
    101. 			size_t sz = size();//提前计算好队列有多长，一会_start指针和_finish指针不在一个队列上了，就算不出来了
    102. 			if (n > capacity())
    103. 			{
    104. 				if (_start)
    105. 				{
    106. 					/*memcpy(temp, _start, size() * sizeof(T));拷贝自定义类型时会出错*/
    107. 					for (int i = 0; i < sz; i++)
    108. 					{
    109. 						temp[i] = _start[i];
    110. 					}
    111. 					
    112. 					delete[] _start;
    113. 					_start = temp;
    114. 				}
    115.  
    116. 				else
    117. 				{
    118. 					_start = temp;
    119. 				}
    120. 			}
    121.  
    122. 			_finish = _start + sz;
    123. 			_endofstorage = _start + n;
    124. 		}
    125.  
    126. 		//开辟特定空间并赋初值
    127. 		void resize(size_t n, T val=T())
    128. 		{
    129. 			if (n < size())
    130. 			{
    131. 				_finish = _start + n;
    132. 			}
    133.  
    134. 			else
    135. 			{
    136. 				if(n>capacity())
    137. 				{
    138. 					reserve(n);
    139. 				}
    140.  
    141. 				while (size() <  n)
    142. 				{
    143. 					*_finish= val;
    144. 					_finish++;
    145. 				}
    146. 			}
    147. 		}
    148.  
    149. 		void push_back(const T& x)
    150. 		{
    151. 			if (_finish == _endofstorage)
    152. 			{
    153. 				size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
    154. 				reserve(newcapacity);
    155. 			}
    156.  
    157. 			*_finish = x;
    158. 			_finish++;
    159. 		}
    160.  
    161. 		void pob_back()
    162. 		{
    163. 			assert(!empty());
    164. 			_finish--;
    165. 		}
    166.         
    167.         //插入
    168. 		void insert(iterator pos,const T& x)
    169. 		{
    170. 			if (_finish == _endofstorage)
    171. 			{
    172. 				size_t len = pos - _start;//保存一下pos的位置
    173. 				size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
    174. 				reserve(newcapacity);
    175. 				iterator pos = _start + len;//重置pos，避免迭代器失效
    176. 			}
    177. 			iterator end = _finish-1;
    178. 			while (end >= pos)
    179. 			{
    180. 				*(end + 1) = *end;
    181. 				end--;
    182. 			}
    183.  
    184. 			*pos = x;
    185. 			_finish++;
    186. 		}
    187. 	
    188.         //删除
    189.         iterator erase(iterator pos)
    190. 		{
    191. 			iterator temp = pos;
    192. 			while (temp < _finish-1)
    193. 			{
    194. 				*temp = *(temp + 1);
    195. 				temp++;
    196. 			}
    197. 			_finish--;
    198. 			return pos;
    199. 		}
    200.  
    201.  
    202. 	private:
    203. 		iterator _start;
    204. 		iterator _finish;
    205. 		iterator _endofstorage;
    206. 	};

    3、使用memcpy拷贝问题

    考虑一下，如果拷贝构造拷贝数据时使用memcpy会引起什么问题？

    1. //拷贝构造
    2. 		vector(const vector& v)
    3. 			:_start(nullptr)
    4. 			,_finish(nullptr)
    5. 			,_endofstorage(nullptr)
    6. 		{
    7. 			_start=new T[v.capacity()];
    8. 			/*memcpy(_start,v._start,v.size()*sizeof(T))  拷贝构造string等自定义类型时，会出问题*/
    9. 			for (size_t i = 0; i < v.size(); i++)
    10. 			{
    11. 				_start[i] = v._start[i];
    12. 			}
    13. 			_finish = _start + v.size();
    14. 			_endofstorage = _start + v.capacity();
    15. 		}

    答：memcpy完成的是浅拷贝，当vector中存放的是内置类型时，是不会出问题的。但是如果vector中存放string类型，则会出现问题，因为是浅拷贝，会拷贝出一个相同的指针和原指针指向同一块空间，调用析构函数时会导致同一块空间被析构两次，发生报错。所以要采用for循环依次赋值，这样赋值时相当于调用string的深拷贝。

    总结

    本章主要简单介绍了vector容器的使用和简单模拟实现，如果感觉有帮助的话不妨点个赞支持一下博主哦~你们的支持就是我创作的最大动力，感谢大家的阅读。

  • 相关阅读:
    ant design ant design Pro 中的table横向与纵向合并问题
    网站防钓鱼是否可以用SSL证书？
    开源AI Agent框架的选择
    一文总结现代 C++ 中的初始化
    51单片机实现换能器超声波测水深
    2019年Java面试题汇总
    手写vue路由
    计算机毕业设计php_thinphp_vue的约课管理系统-课程预约(源码+系统+mysql数据库+Lw文档）
    【k8s】pod调度——亲和，反亲和，污点，容忍
    Java中[Ljava.lang.Object；是什么?
  • 原文地址：https://blog.csdn.net/weixin_59371851/article/details/125269395