• 【C++】学习C++STL中的数组——vector

    ❤️前言

            好久不见大家！今天的这篇博客是关于我对于STL(C++标准模板库)中的容器vector的学习和理解，希望大家能够喜欢。

    正文

             vector是STL中的一种序列容器，对应着数据结构中的顺序表，也可以说是数组。在我们正式学习了解vector之前，我们先看看C++官网对其的文档介绍。

    vector的文档介绍

            这是纯英文的官网链接：cplusplus.com/reference/vector/vector/icon-default.png?t=N7T8https://cplusplus.com/reference/vector/vector/        这是大概的中文翻译：

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

            看不懂也没什么问题，这本来就只是给我们一个大致的vector的印象，接下来我们继续更加细致的了解和学习这个容器。

    vector的简单使用

            首先我们知道STL是C++的标准模板库，而vector是其中的一种容器(数据结构)，它是一种类模板，通过模板的显式实例化可以产生各种各样不同的类，初始化时vector需要我们给出其中存储的数据类型。

            要使用vector，我们首先要知道如何初始化一个vector对象。这时候我们就需要关注vector对应的构造函数。

    vector的构造函数

            如下是C++98中给出的vector构造函数：

             第一个构造函数可以看作无参数的默认构造函数，那个唯一的参数叫做空间配置器，在使用vector时我们基本上可以无视，它的作用就是提高堆区内存资源的存取效率，而且它那里给了缺省参数，一般我们在使用的时候是不怎么需要考虑的。

    1. // 使用这个构造函数初始化vector对象的大致方式：
    2. vector<数据类型> v();
    3. // 存储int类型的数据：
    4. vector<int> v();
    5. // 存储vector类型的数据模拟二维数组：
    6. vectorint>> vv();

            第二个构造函数的效果是初始化出n个值，初始化的值默认调用vector中数据的默认构造函数。

    1. // 使用这个构造函数初始化vector对象的大致方式：
    2. vector<数据类型> v(初始化数据的个数,数据初始值);
    3. // 存储int类型的数据10个10：
    4. vector<int> v(10, 10);
    5. // 存储vector类型的数据模拟n*n的二维数组：
    6. vectorint>> vv(n, vector<int>(n));

            第三个构造函数通过迭代器区间进行构造，我们只需要给出起止的范围即可(迭代器我们在使用string类时就已经接触过了，它是对应着指针的一类对象)。

    1. // 使用这个构造函数初始化vector对象的大致方式：
    2. vector<数据类型> v(起始迭代器，终止迭代器);
    3.  
    4. // 存储int类型的数据：
    5. int arr[] = { 0,1,2,3,4 };
    6. int* p1 = arr; int* p2 = arr + 5;
    7. vector<int> v(p1,p2);

            第四个构造函数就是拷贝构造函数，使用方式想必不需要过多探讨。

    vector的迭代器使用

            下面是关于迭代器(iterator)的简单介绍：

            在STL中，我们要访问顺序容器和关联容器中的元素，需要通过“迭代器（iterator）”进行。迭代器是一个变量，相当于容器和操纵容器的算法之间的中介。迭代器可以指向容器中的某个元素，通过迭代器就可以读写它指向的元素。从这一点上看，迭代器和指针类似。

            简单认识了迭代器之后，让我们看看迭代器在vector中的使用。在vector中，我们一般使用迭代器来对应指针在数组中的操作。通过迭代器，我们可以访问vector中的任意元素。那我们该如何使用迭代器呢？下面举例vector迭代器的使用方式：

    1. vector<int> v(10, 10);
    2.  
    3. // 创建vector迭代器对象指向v的开头
    4. vector<int>::iterator it = v.begin();
    5. while (it != v.end())
    6. {
    7. 	cout << *it << ' ';
    8. 	++it;
    9. }

            在上述代码中，我调用v的成员函数begin()为it赋初值，我们大概能看出这里的begin()和end()会返回迭代器的值。顾名思义，begin()给出了v的初始位置对应迭代器的值，end()给出末尾元素后的一个位置的值，也就是对应着一个左闭右开的区间。

            除此之外，还有一种迭代器被称为反向迭代器(reverse_iterator)，这种迭代器从最后一个元素为起始点，第一个元素的前一个位置为终止点，是与普通迭代器相反的迭代器，可以对容器里的元素进行反向遍历，对应在成员函数中就是rbegin()和rend()。使用方式：

    1. vector<int> v(10, 10);
    2.  
    3. // 创建vector反向迭代器对象指向v的末尾
    4. vector<int>::reverse_iterator rit = v.rbegin();
    5. while (rit != v.rend())
    6. {
    7. 	cout << *rit << ' ';
    8. 	++rit;
    9. }

            我们可以看到，当我们声明一个迭代器时，它的类型名经常会有些复杂，这时候我们就可以想到之前学习过的一种关键字：auto ，它可以自行推导对象的类型(当然，这需要我们对变量赋初值)，这使我们在使用长类型名对象时更加的方便。例如上面的反向迭代器声明就可以变为：

    auto rit = v.rbegin();

    vector的空间使用

            在使用vector时，我们也需要控制内存和数据，类似于我们在学习数据结构时控制顺序表的内存和数据。

            相应的函数有size() capacity() empty() reserve() resize()等。

            其中reserve() 可以改变vector的capacity resize()可以改变vector的size也就是有效数据个数。

    这些接口的使用大家可以参考C++的文档：

    vector - C++ Reference (cplusplus.com)icon-default.png?t=N7T8https://legacy.cplusplus.com/reference/vector/vector/

    vector的增删查改

            对于vector的增删查改，我们比较常用的接口有末端插入push_back()、末端删除pop_back()、重载方括号operator[ ]。

            这些函数也可以参考文档进行学习。

    迭代器失效问题

            迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装，比如：vector的迭代器就是原生指针T* 。因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，程序可能会崩溃)。由此可见，迭代器失效也就类似于我们曾经在C指针阶段非常苦恼的野指针问题。

            可能会引起迭代器失效的操作有：

            1.可能会引起底层空间发生改变的各种操作，都可能会引发迭代器失效。例如：resize、reserve、insert、assign、push_back等。示例代码如下：

    1. vector<int> v{ 1,2,3,4,5,6 };
    2. auto it = v.begin();
    3.  
    4. // 将有效元素个数增加到100个，多出的位置使用8填充，操作期间底层会扩容
    5. // v.resize(100, 8);
    6.  
    7. // reserve的作用就是改变扩容大小但不改变有效元素个数，操作期间可能会引起底层容量改变
    8. // v.reserve(100);
    9.  
    10. // 插入元素期间，可能会引起扩容，而导致原空间被释放
    11. // v.insert(v.begin(), 0);
    12. // v.push_back(8);
    13.  
    14. // 给vector重新赋值，可能会引起底层容量改变
    15. v.assign(100, 8);
    16.  
    17. /*
    18. 出错原因：以上操作，都有可能会导致vector扩容，也就是说vector底层原理旧空间被释放掉，
    19. 而在打印时，it还使用的是释放之间的旧空间，在对it迭代器操作时，实际操作的是一块已经被释放的
    20. 空间，而引起代码运行时崩溃。
    21. 解决方式：在以上操作完成之后，如果想要继续通过迭代器操作vector中的元素，只需给it重新
    22. 赋值即可。
    23. */
    24.  
    25. it = v.begin();
    26.  
    27. while (it != v.end())
    28. {
    29. 	cout << *it << " ";
    30. 	++it;
    31. }
    32. cout << endl;

            2.指定位置元素的删除操作--erase，当我们通过erase删除了一个元素之后，那么指向这个元素的迭代器就会失效，因为目前这个迭代器的指向是未知的(它会指向原来的下一个位置)。示例代码如下：

    1. vector<int> v{ 1,2,3,4,5,6 };
    2.  
    3. auto it = v.begin();
    4. while (it != v.end())
    5. {
    6. 	if (*it % 2 == 0)
    7. 		it = v.erase(it);
    8. 	else
    9. 		++it;
    10. }
    11.  
    12. it = v.begin();
    13. while (it != v.end())
    14. {
    15. 	std::cout << *it << " ";
    16. 	++it;
    17. }
    18. std::cout << endl;

            总的来说，迭代器失效就类似于野指针问题，我们解决迭代器失效的方式就是为迭代器重新赋值。

    vector的模拟实现

            大致了解了vector的使用之后，让我们一起学着模拟实现vector，以此加深我们对与vector的理解，让我们更好的使用它。

    1. namespace MO_lion
    2. {
    3. 	template<typename T>
    4. 	class vector
    5. 	{
    6. 	public:
    7. 		// 迭代器
    8. 		typedef T* iterator;
    9. 		typedef const T* const_iterator;
    10.  
    11. 		iterator begin()
    12. 		{
    13. 			return _start;
    14. 		}
    15.  
    16. 		iterator end()
    17. 		{
    18. 			return _finish;
    19. 		}
    20.  
    21. 		const_iterator begin() const
    22. 		{
    23. 			return _start;
    24. 		}
    25.  
    26. 		const_iterator end() const
    27. 		{
    28. 			return _finish;
    29. 		}
    30.  
    31. 		// 构造函数
    32. 		vector()
    33. 			: _start(nullptr)
    34. 			, _finish(nullptr)
    35. 			, _end_of_storage(nullptr)
    36. 		{}
    37.  
    38. 		// 拷贝构造
    39. 		vector(const vector& v)
    40. 			: _start(nullptr)
    41. 			, _finish(nullptr)
    42. 			, _end_of_storage(nullptr)
    43. 		{
    44. 			reserve(v.capacity());
    45. 			for (int i = 0; i < v.size(); ++i)
    46. 			{
    47. 				_start[i] = v[i];
    48. 			}
    49. 			_finish += v.size();
    50. 		}
    51.  
    52. 		vector(int n, const T& x = T())
    53. 		{
    54. 			resize(n, x);
    55. 		}
    56.  
    57. 		// 扩容
    58. 		void reserve(size_t n)
    59. 		{
    60. 			if (n <= capacity()) return;
    61. 			size_t oldsize = size();
    62. 			iterator tmp = new T[n];
    63. 			if (_start)
    64. 			{
    65. 				for (int i = 0; i < size(); ++i)
    66. 				{
    67. 					tmp[i] = _start[i];
    68. 				}
    69. 				delete[] _start;
    70. 			}
    71. 			_start = tmp;
    72. 			_finish = _start + oldsize;
    73. 			_end_of_storage = _start + n;
    74. 		}
    75.  
    76. 		void resize(size_t n, const T& x = T())
    77. 		{
    78. 			if (n > capacity()) reserve(n);
    79. 			for (int i = size(); i < n; ++i)
    80. 			{
    81. 				_start[i] = x;
    82. 			}
    83. 			_finish = _start + n;
    84. 		}
    85.  
    86. 		// 尾插
    87. 		void push_back(const T& x)
    88. 		{
    89. 			//if (_finish == _end_of_storage)
    90. 			//{
    91. 			//	reserve(capacity() == 0 ? 5 : capacity() * 2);
    92. 			//}
    93. 			//*_finish = x;
    94. 			//_finish++;
    95.  
    96. 			insert(end(), x);
    97. 		}
    98.  
    99. 		// 随机位置插入
    100. 		iterator insert(iterator pos, const T& x)
    101. 		{
    102. 			assert(pos <= _finish && pos >= _start);
    103. 			if (_finish == _end_of_storage)
    104. 			{
    105. 				size_t len = pos - _start;
    106. 				reserve(capacity() == 0 ? 5 : capacity() * 2);
    107. 				pos = _start + len;
    108. 			}
    109.  
    110. 			for (int i = size(); i > pos - _start; --i)
    111. 			{
    112. 				_start[i] = _start[i - 1];
    113. 			}
    114.  
    115. 			*pos = x;
    116. 			_finish++;
    117.  
    118. 			return pos;
    119. 		}
    120.  
    121. 		// 指定位置删除
    122. 		iterator erase(iterator pos)
    123. 		{
    124. 			assert(pos < _finish && pos >= _start);
    125. 			for (int i = pos - _start; i < size() - 1; ++i)
    126. 			{
    127. 				_start[i] = _start[i + 1];
    128. 			}
    129. 			_finish--;
    130.  
    131. 			return pos;
    132. 		}
    133.  
    134. 		// 重载方括号
    135. 		T& operator[](size_t n)
    136. 		{
    137. 			return _start[n];
    138. 		}
    139.  
    140. 		const T& operator[](size_t n) const
    141. 		{
    142. 			return _start[n];
    143. 		}
    144.  
    145. 		// 交换两个vector
    146. 		void swap(vector& v)
    147. 		{
    148. 			std::swap(_start, v._start);
    149. 			std::swap(_finish, v._finish);
    150. 			std::swap(_end_of_storage, v._end_of_storage);
    151. 		}
    152.  
    153. 		// 重载等号
    154. 		vector& operator=(vector v)
    155. 		{
    156. 			swap(v);
    157. 			return *this;
    158. 		}
    159.  
    160. 		// 返回有效数据个数
    161. 		size_t size() const
    162. 		{
    163. 			return _finish - _start;
    164. 		}
    165.  
    166. 		// 返回可用空间大小
    167. 		size_t capacity() const
    168. 		{
    169. 			return _end_of_storage - _start;
    170. 		}
    171.         
    172.         // 析构函数
    173. 		~vector()
    174. 		{
    175. 			if (_start == nullptr) return;
    176. 			delete[] _start;
    177. 			_start = nullptr;
    178. 			_finish = nullptr;
    179. 			_end_of_storage = nullptr;
    180. 		}
    181.  
    182. 	private:
    183.         // 将三个指向不同位置的迭代器作为私有成员；
    184.         // 起始位置
    185. 		iterator _start;
    186.         // 终止位置
    187. 		iterator _finish;
    188.         // 容量的极限位置
    189. 		iterator _end_of_storage;
    190. 	};
    191.  
    192. }

            在vector的模拟实现中，有以下问题比较值得注意：

    深浅拷贝问题

            由于vector可以存储各种各样不同的数据类型，我们在模拟实现reverse()和拷贝构造函数复制有效数据的过程中使用赋值运算符 "=" 进行操作。

            如果我们像实现string时一样使用memcpy()进行数据拷贝，那么当这样的vector用于存储需要进行资源管理的对象的时候(例如vector>)，就会发生错误，因为memcpy()是浅拷贝。而使用 "=" 这里就比较妙了，它可以适配所有的对象，因为大家都有赋值运算符，正常情况下，赋值运算符会适配对应对象的资源管理方式。

    重载等号的现代写法

            上面我们可以看到重载等号的写法十分的简洁，实际上是创建了一个临时的vector对象，然后将成员交换给当前对象，相当于复用了拷贝构造的代码，这里有一个比较妙的点就是传参得来的参数是原对象的临时拷贝。

    1. // 交换两个vector
    2. void swap(vector& v)
    3. {
    4. 	std::swap(_start, v._start);
    5. 	std::swap(_finish, v._finish);
    6. 	std::swap(_end_of_storage, v._end_of_storage);
    7. }
    8.  
    9. // 重载等号
    10. vector& operator=(vector v)
    11. {
    12. 	swap(v);
    13. 	return *this;
    14. }

    🍀结语

            以上内容就是今天的所有vector相关知识啦，接下来我们使用C++经常会使用到vector，希望这篇博客能够对大家有用。

  • 相关阅读:
    基于Spring Boot 框架的试卷自动生成系统的设计与实现
    threejs
    物业服务神秘顾客监测的难点及对策
    实在是解决不了来提问一下。UE5，打开项目地变成黑色怎么解决？
    vue element-table分页回显选中与再次更改保留状态，前端手动过滤多条件查询
    API cop
    【Servlet】Servlet学习之基础篇(HTTP)
    【C++】解引用 (及指针) 和 引用 的概念区别
    模块、服务、接口命名示例
    赞不绝口！仅靠阿里P9分享的 Redis 工作手册，拿到60W年薪Offer
  • 原文地址：https://blog.csdn.net/MO_lion/article/details/132567675