• ＜vector模拟实现＞——《C++初阶》

    目录

    1.vector深度剖析及模拟实现：

    1.1 std::vector的核心框架接口的模拟实现bit::vector 

    1.2 使用memcpy拷贝问题

    1.3 对bit::vector核心接口的测试

    1.4动态二维数组理解

    2.vector模拟实现源码： 

    2.1：完整源码：

    2.2例题：使用vector实现杨辉三角：​

    后记：●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！                                                                  ——By 作者：新晓·故知

    1.vector深度剖析及模拟实现：

    vector的模拟实现主要对常用的函数接口：构造函数、拷贝构造函数、析构函数、赋值重载函数、vector迭代器、reserve、push_back、pop_back、insert、resize、erase等。

    对vector在Linux环境下g++编译器与Windows环境下VS系列编译器的vector迭代器失效问题进行对比、解决。

    磁盘调度算法的实现与对比
    rar 5星 超过95%的资源 56KB
    下载

     

    1.1 std::vector的核心框架接口的模拟实现bit::vector 

    1. #include 
    2. using namespace std;
    3. #include 
    4.  
    5. //自定义命名空间，防止与库冲突
    6. namespace bit
    7. {
    8. 	template<class T>
    9. 	class vector
    10. 	{
    11. 	public:
    12. 		// Vector的迭代器是一个原生指针
    13. 		typedef T* iterator;
    14. 		typedef const T* const_iterator;
    15. 		iterator begin() { return _start; }
    16. 		iterator end() { return _finish; }
    17. 		const_iterator cbegin() const { return _start; }
    18. 		const_iterator cend() const { return _finish; }
    19. 		// construct and destroy
    20. 		vector()
    21. 			: _start(nullptr)
    22. 			, _finish(nullptr)
    23. 			, _endOfStorage(nullptr)
    24. 		{}
    25. 		vector(int n, const T& value = T())
    26. 			: _start(nullptr)
    27. 			, _finish(nullptr)
    28. 			, _endOfStorage(nullptr)
    29. 		{
    30. 			reserve(n);
    31. 			while (n--)
    32. 			{
    33. 				push_back(value);
    34. 			}
    35. 		}
    36. 		// 若使用iterator做迭代器，会导致初始化的迭代器区间[first,last)只能是vector的迭代器
    37. 		// 重新声明迭代器，迭代器区间[first,last)可以是任意容器的迭代器
    38. 		template<class InputIterator>
    39. 		vector(InputIterator first, InputIterator last)
    40. 		{
    41. 			reserve(last - first);
    42. 			while (first != last)
    43. 			{
    44. 				push_back(*first);
    45. 				++first;
    46. 			}
    47. 		}
    48. 		vector(const vector& v)
    49. 			: _start(nullptr)
    50. 			, _finish(nullptr)
    51. 			, _endOfStorage(nullptr)
    52. 		{
    53. 			reserve(v.capacity());
    54. 			iterator it = begin();
    55. 			const_iterator vit = v.cbegin();
    56. 			while (vit != v.cend())
    57. 			{
    58. 				*it++ = *vit++;
    59. 			}
    60. 		}
    61. 		vector& operator=(vector v)
    62. 		{
    63. 			swap(v);
    64. 			return *this;
    65. 		}
    66. 		~vector()
    67. 		{
    68. 			delete[] _start;
    69. 			_start = _finish = _endOfStorage = nullptr;
    70. 		}
    71. 		// capacity
    72. 		size_t size() const { return _finish - _start; }
    73. 		size_t capacity() const { return _endOfStorage - _start; }
    74. 		bool empty() const { return _first == _finish; }
    75. 		void reserve(size_t n)
    76. 		{
    77. 			if (n > capacity())
    78. 			{
    79. 				size_t oldSize = size();
    80. 				T* tmp = new T[n];
    81. 				// 这里直接使用memcpy?
    82. 				//if (_start)
    83. 				// memcpy(tmp, _start, sizeof(T)*size);
    84. 				if (_start)
    85. 				{
    86. 					for (size_t i = 0; i < oldSize; ++i)
    87. 						tmp[i] = _start[i];
    88. 				}
    89. 				_start = tmp;
    90. 				_finish = _start + oldSize;
    91. 				_endOfStorage = _start + n;
    92. 			}
    93. 		}
    94. 		void resize(size_t n, const T& value = T())
    95. 		{
    96. 			// 1.如果n小于当前的size，则数据个数缩小到n
    97. 			if (n <= size())
    98. 			{
    99. 				_finish = _start + n;
    100. 				return;
    101. 			}
    102. 			// 2.空间不够则增容
    103. 			if (n > capacity())
    104. 				reserve(n);
    105. 			// 3.将size扩大到n
    106. 			iterator it = _finish;
    107. 			_finish = _start + n;
    108. 			while (it != _finish)
    109. 			{
    110. 				*it = value;
    111. 				++it;
    112. 			}
    113. 		}
    114. 		///access///
    115. 		T& operator[](size_t pos) { return _start[pos]; }
    116. 		const T& operator[](size_t pos)const { return _start[pos]; }
    117. 		///modify/
    118. 		void push_back(const T& x) { insert(end(), x); }
    119. 		void pop_back() { erase(--end()); }
    120. 		void swap(vector& v)
    121. 		{
    122. 			std::swap(_start, v._start);
    123. 			std::swap(_finish, v._finish);
    124. 			std::swap(_endOfStorage, v._endOfStorage);
    125. 		}
    126. 		iterator insert(iterator pos, const T& x)
    127. 		{
    128. 			assert(pos <= _finish);
    129. 			// 空间不够先进行增容
    130. 			if (_finish == _endOfStorage)
    131. 			{
    132. 				//size_t size = size();
    133. 				size_t newCapacity = (0 == capacity()) ? 1 : capacity() * 2;
    134. 				reserve(newCapacity);
    135. 				// 如果发生了增容，需要重置pos
    136. 				pos = _start + size();
    137. 			}
    138. 			iterator end = _finish - 1;
    139. 			while (end >= pos)
    140. 			{
    141. 				*(end + 1) = *end;
    142. 				--end;
    143. 			}
    144. 			*pos = x;
    145. 			++_finish;
    146. 			return pos;
    147. 		}
    148. 		// 返回删除数据的下一个数据
    149. 		// 方便解决:一边遍历一边删除的迭代器失效问题
    150. 		iterator erase(iterator pos)
    151. 		{
    152. 			// 挪动数据进行删除
    153. 			iterator begin = pos + 1;
    154. 			while (begin != _finish) {
    155. 				*(begin - 1) = *begin;
    156. 				++begin;
    157. 			}
    158. 			--_finish;
    159. 			return pos;
    160. 		}
    161.     private:
    162. 	      iterator _start; // 指向数据块的开始
    163. 	      iterator _finish; // 指向有效数据的尾
    164. 	      iterator _endOfStorage; // 指向存储容量的尾
    165.     };
    166. }

    1.2 使用memcpy拷贝问题

    假设模拟实现的vector中的reserve接口中，使用memcpy进行的拷贝，以下代码会发生什么问题？ 
    1. int main()
    2. {
    3.  bite::vector v;
    4.  v.push_back("1111");
    5.  v.push_back("2222");
    6.  v.push_back("3333");
    7.  return 0; 
    8. }

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

    结论：如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为memcpy是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃。

     1.3 对bit::vector核心接口的测试 

    1. // constructing vectors
    2. void TestVector1()
    3. {
    4. 	// constructors used in the same order as described above:
    5. 	bite::vector<int> first; // empty vector of
    6. 	ints
    7. 		bite::vector<int> second(4, 100); // four ints with value 
    8. 	100
    9. 		bite::vector<int> third(second.Begin(), second.End()); // iterating through 
    10. 	second
    11. 		bite::vector<int> fourth(third); // a copy of third
    12. 		// the iterator constructor can also be used to construct from arrays:
    13. 	int myints[] = { 16, 2, 77, 29 };
    14. 	bit::vector<int> fifth(myints, myints + sizeof(myints) / sizeof(int));
    15. 	std::cout << "The contents of fifth are:";
    16. 	for (bit::vector<int>::iterator it = fifth.begin(); it != fifth.end(); ++it)
    17. 		std::cout << *it << " ";
    18. 	std::cout << endl;
    19. 	// 测试T是string时，拷贝问题
    20. 	bit::vector strV;
    21. 	strV.PushBack("1111");
    22. 	strV.PushBack("2222");
    23. 	strV.PushBack("3333");
    24. 	strV.PushBack("4444");
    25. 	for (size_t i = 0; i < strV.size(); ++i)
    26. 	{
    27. 		cout << strV[i] << " ";
    28. 	}
    29. 	cout << endl;
    30. }
    31. //vector iterator的使用
    32. void PrintVector(const bite::vector<int>& v) {
    33. 	// 使用const迭代器进行遍历打印
    34. 	bit::vector<int>::const_iterator it = v.begin();
    35. 	while (it != v.end())
    36. 	{
    37. 		cout << *it << " ";
    38. 		++it;
    39. 	}
    40. 	cout << endl;
    41. }
    42. void TestVector2()
    43. {
    44. 	// 使用push_back插入4个数据
    45. 	bite::vector<int> v;
    46. 	v.push_back(1);
    47. 	v.push_back(2);
    48. 	v.push_back(3);
    49. 	v.push_back(4);
    50. 	PrintVector(v);
    51. 	// 使用迭代器进行修改
    52. 	auto it = v.begin();
    53. 	while (it != v.end())
    54. 	{
    55. 		*it *= 2;
    56. 		++it;
    57. 	}
    58. 	PrintVector(v);
    59.  
    60. 	// 这里可以看出C++11支持iterator及接口，就支持范围for
    61. 	for (auto e : v)
    62. 		cout << e << " ";
    63. }
    64. // find / insert / erase
    65. void TestVector3()
    66. {
    67. 	int a[] = { 1, 2, 3, 4 };
    68. 	bite::vector<int> v(a, a + sizeof(a) / sizeof(a[0]));
    69. 	// 使用find查找3所在位置的iterator
    70. 	auto pos = find(v.begin(), v.end(), 3);
    71. 	// 在pos位置之前插入30
    72. 	v.insert(pos, 30);
    73. 	PrintVector(v);
    74. 	// 删除pos位置的数据
    75. 	pos = find(v.begin(), v.end(), 3);
    76. 	v.Erase(pos);
    77. 	PrintVector(v);
    78. }
    79. // iterator失效问题
    80. void TestVector4()
    81. {
    82. 	int a[] = { 1, 2, 3, 4 };
    83. 	bite::vector<int> v(a, a + sizeof(a) / sizeof(a[0]));
    84. 	// 删除pos位置的数据，导致pos迭代器失效
    85. 	auto pos = find(v.begin(), v.end(), 3);
    86. 	v.erase(pos);
    87. 	cout << *pos << endl; // 此处会导致非法访问
    88. 	// 在pos位置插入数据，导致pos迭代器失效。
    89. 	// insert会导致迭代器失效，是因为insert可
    90. 	// 能会导致增容，增容后pos还指向原来的空间，而原来的空间已经释放了。
    91. 	pos = find(v.begin(), v.end(), 3);
    92. 	v.insert(pos, 30);
    93. 	cout << *pos << endl; // 此处会导致非法访问
    94. 	// 实现删除v中的所有偶数
    95. 	// 下面的程序会崩溃掉，如果是偶数，erase导致it失效
    96. 	// 对失效的迭代器进行++it，会导致程序崩溃
    97. 	auto it = v.begin();
    98. 	while (it != v.end())
    99. 	{
    100. 		if (*it % 2 == 0)
    101. 			v.erase(it);
    102. 		++it;
    103. 	}
    104. 	// 以上程序要改成下面这样，erase会返回删除位置的下一个位置
    105. 	it = v.begin();
    106. 	while (it != v.end())
    107. 	{
    108. 		if (*it % 2 == 0)
    109. 			it = v.erase(it);
    110. 		else
    111. 			++it;
    112. 	}
    113. }

    注：一般vector删除数据，都不考虑缩容的方案。

    缩容方案：size（）

    string迭代器也有失效问题，但string不常使用迭代器，而多使用下标+[ ],vector多使用迭代器，要注意失效问题。

    1.4动态二维数组理解

      
    1. // 以杨辉三角的前n行为例：假设n为5
    2. void test5(size_t n)
    3. {
    4. 	// 使用vector定义二维数组vv，vv中的每个元素都是vector
    5. 	bit::vectorint>> vv(n);
    6.  
    7. 	// 将二维数组每一行中的vecotr中的元素全部设置为1
    8. 	for (size_t i = 0; i < n; ++i)
    9. 		vv[i].resize(i + 1, 1);
    10. 	// 给杨辉三角出第一列和对角线的所有元素赋值
    11. 	for (int i = 2; i < n; ++i)
    12. 	{
    13. 		for (int j = 1; j < i; ++j)
    14. 		{
    15. 			vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
    16. 		}
    17. 	}
    18. }

    bit::vector> vv(n); 构造一个vv动态二维数组，vv中总共有n个元素，每个元素都是vector类型的，每行没有包含任何元素，如果n为5时如下所示：

     

    2.vector模拟实现源码： 

    2.1：完整源码：

    （1）vector.h：​​​​​​​

    1. #pragma once
    2. //模拟实现vector
    3. #include
    4. #include
    5. #include
    6. #include
    7. using namespace std;
    8.  
    9. //自定义命名空间，防止与库里的冲突
    10. namespace my
    11. {
    12. 	template<class T>
    13. 	class vector
    14. 	{
    15. 	public:
    16. 		typedef T* iterator;
    17. 		typedef const T* const_iterator;
    18. 		//构造函数
    19. 		vector()
    20. 			:_start(nullptr)
    21. 			,_finish(nullptr)
    22. 			,_endofstorage(nullptr)
    23. 		{}
    24. 		//使用n个val构造函数
    25. 		vector(size_t n, const T& val = T())
    26. 			:_start(nullptr)
    27. 			, _finish(nullptr)
    28. 			, _endofstorage(nullptr)
    29. 		{
    30. 			reserve(n);
    31. 			for (size_t i = 0; i < n; ++i)
    32. 			{
    33. 				push_back(val);
    34. 			}
    35. 		}
    36. 		vector(int n, const T& val = T())
    37. 			:_start(nullptr)
    38. 			, _finish(nullptr)
    39. 			, _endofstorage(nullptr)
    40. 		{
    41. 			reserve(n);
    42. 			for (size_t i = 0; i < n; ++i)
    43. 			{
    44. 				push_back(val);
    45. 			}
    46. 		}
    47. 		//类模板，类构造
    48. 		template<class InputIterator>
    49. 		vector(InputIterator first, InputIterator last)
    50. 			: _start(nullptr)
    51. 			, _finish(nullptr)
    52. 			, _endofstorage(nullptr)
    53. 		{
    54. 			while (first != last)
    55. 			{
    56. 				push_back(*first);
    57. 				++first;
    58. 			}
    59. 		}
    60. 		void swap(vector& v)
    61. 		{
    62. 			std::swap(_start, v._start);
    63. 			std::swap(_finish, v._finish);
    64. 			std::swap(_endofstorage, v._endofstorage);
    65.  
    66. 		}
    67. 		//拷贝构造函数（使用现代写法）
    68. 		vector(const vector& v)
    69. 			: _start(nullptr)
    70. 			, _finish(nullptr)
    71. 			, _endofstorage(nullptr)
    72. 		{
    73. 			vector tmp(v.begin(), v.end());
    74. 			swap(tmp); //this->swap(tmp);
    75. 		}
    76. 		//赋值重载函数(现代写法)
    77. 		vector& operator=(vector v)
    78. 		{
    79. 			swap(v);     //this->swap(v);
    80. 			return *this;
    81. 		}
    82. 		//析构函数（资源管理）
    83. 		~vector()
    84. 		{
    85. 			if (_start)
    86. 			{
    87. 				delete[] _start;
    88. 				_start = _finish = _endofstorage = nullptr;
    89. 			}
    90. 		}
    91. 		iterator begin()
    92. 		{
    93. 			return _start;
    94. 		}
    95. 		iterator end()
    96. 		{
    97. 			return _finish;
    98. 		}
    99. 		const_iterator begin() const
    100. 		{
    101. 			return _start;
    102. 		}
    103. 		const_iterator end() const
    104. 		{
    105. 			return _finish;
    106. 		}
    107. 		size_t size() const
    108. 		{
    109. 			return _finish - _start;
    110. 		}
    111. 		size_t capacity() const
    112. 		{
    113. 			return _endofstorage - _start;
    114. 		}
    115. 		void reserve(size_t n)
    116. 		{
    117. 			size_t sz = size();  
    118. 			if (n > capacity())
    119. 			{
    120. 				T* tmp = new T[n];
    121. 				if (_start)
    122. 				{
    123. 					//memcpy(tmp, _start, size() * sizeof(T));  //浅拷贝问题
    124. 					for (size_t i = 0;i < size(); ++i)
    125. 					{
    126. 						tmp[i] = _start[i];
    127. 					}
    128. 					delete[] _start;
    129. 				}
    130. 				_start = tmp;
    131. 			}
    132. 			_finish = _start + sz;
    133. 			_endofstorage = _start + n;
    134. 		}
    135. 		//总结：vector中，当T涉及深拷贝的类型时，如：string、vector等等，
    136. 		//扩容使用memcpy拷贝数据会存在浅拷贝问题，造成析构两次
    137. 		//解决：使用传值拷贝，如上
    138. 		void push_back(const T& x)
    139. 		{
    140. 			/*if (_finish == _endofstorage)
    141. 			{
    142. 				size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
    143. 				reserve(newCapacity);
    144. 			}
    145. 			*_finish = x;
    146. 			++_finish;*/
    147.  
    148. 			//附用insert
    149. 			insert(end(),x);
    150. 		}
    151. 		void pop_back()
    152. 		{
    153. 			/*if (_finish > _start)
    154. 			{
    155. 				--_finish;
    156. 			}*/
    157.  
    158. 			//附用erase
    159. 			erase(end()-1);
    160. 		}
    161. 		T& operator[](size_t pos)
    162. 		{
    163. 			assert(pos < size());
    164. 			return _start[pos];
    165. 		}
    166. 		const T& operator[](size_t pos) const
    167. 		{
    168. 			assert(pos < size());
    169. 			return _start[pos];
    170. 		}
    171. 		//写在类里的小函数，被当做内联函数处理，减少了多次调用建立栈帧
    172. 		//void resize(size_t n, const T& val = T())
    173. 		void resize(size_t n, T val = T()) //T()匿名对象，调用默认构造函数，若T()为int（内置类型），
    174. 		{                                  //C++对于内置类型也可以认为有构造函数、析构函数，才能支持模板，只是int为0，double为0.1
    175. 			/*int i = 0;
    176. 			int j = int();
    177. 			int k = int(1);*/
    178. 			 
    179. 			if (n > capacity())
    180. 			{
    181. 				reserve(n);
    182. 			}
    183. 			if (n > size())
    184. 			{
    185. 				while (_finish < _start + n)
    186. 				{
    187. 					*_finish = val;
    188. 					++_finish;
    189. 				}
    190. 			}
    191. 			else
    192. 			{
    193. 				_finish = _start + n;
    194. 			}
    195. 		}
    196. 		iterator insert(iterator pos, const T& x)  //返回值为iterator,解决迭代器失效问题
    197. 		{ 
    198. 			//如果pos传引用，但有些时候，传不过去
    199. 			//检查参数
    200. 			assert(pos >= _start && pos <= _finish);
    201. 			//扩容
    202. 			//扩容以后，pos就失效了，要更新
    203. 			//insert导致的迭代器失效，是因为pos没更新
    204. 			if (_finish == _endofstorage)
    205. 			{
    206. 				size_t n = pos - _start;
    207. 				size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
    208. 				reserve(newCapacity);
    209. 				pos = _start + n;
    210. 			}
    211. 			//挪动数据
    212. 			iterator end = _finish - 1;
    213. 			while (end >= pos)
    214. 			{
    215. 				*(end + 1) = *end;
    216. 				--end;
    217. 			}
    218. 			*pos = x;
    219. 			++_finish;
    220. 			return pos;
    221. 		}
    222. 		//总结：迭代器在insert里的两种失效：
    223. 		//1.pos失效   2.迭代器it失效
    224. 		
    225. 		iterator erase(iterator pos)
    226. 		{
    227. 			assert(pos >= _start && pos <= _finish);
    228. 			iterator it = pos + 1;
    229. 			while (it != _finish)
    230. 			{
    231. 				*(it - 1) = *it;
    232. 				++it;
    233. 			}
    234. 			--_finish;
    235. 			return pos;
    236. 		}
    237. 		//总结：
    238. 		//1.erase的失效都是意义变了，过着不在有效访问数据有效范围
    239. 		//2.一般不会使用缩容的方案，那么erase的失效也不存在野指针的失效
    240. 		//在VS和Linux不同环境下，处理不同
    241. 		//erase(pos)，使得pos失效,pos的意义改变，但是不同环境平台的处理不一样
    242. 		//在使用的时候，统一以失效的角度看待
    243.  
    244. 		//整体总结：
    245. 		//对于insert和erase造成的迭代器失效问题，Linux环境下g++检查不严格，基本依靠操作系统自身野指针越界检查机制
    246. 		//Windows环境下，VS系列检查严格，使用一些强制检查机制，意义改变造成的失效，也可能会检查出来
    247.  
    248. 		//vector迭代器的失效有两种：
    249. 		//1.扩容、缩容，导致形成野指针失效
    250. 		//2.迭代器指向的位置意义改变
    251. 		//这些通过操作系统的越界检查机制不一定能检查到
    252. 		//而通过编译器实现机制检查，相对靠谱
    253. 		void clear()
    254. 		{
    255. 			_finish = _start;
    256. 		}
    257.  
    258. 	private:
    259. 		iterator _start;
    260. 		iterator _finish;
    261. 		iterator _endofstorage;
    262.  
    263. 	};
    264. }

    （2）test.cpp:

    1. #include "vector.h"
    2.  
    3. void TestVector1()
    4. {
    5. 	my::vector<int> v; //注意类域，这里使用模拟的vector，要加上类名
    6. 	v.push_back(2);
    7. 	v.push_back(0);
    8. 	v.push_back(2);
    9. 	v.push_back(2);
    10. 	v.push_back(8);
    11. 	1.使用范围for遍历
    12. 	//for (auto e : v)
    13. 	//{
    14. 	//	cout << e << " ";
    15. 	//}
    16. 	//cout << endl;
    17. 	//2.使模拟迭代器遍历
    18. 	my::vector<int>::iterator it = v.begin();
    19. 	while (it != v.end())
    20. 	{
    21. 		cout << *it << " ";
    22. 		++it;
    23. 	}
    24. 	cout << endl;
    25. }
    26. void TestVector2()
    27. {
    28. 	my::vector<int> v;
    29. 	v.push_back(2);
    30. 	v.push_back(0);
    31. 	v.push_back(2);
    32. 	v.push_back(2);
    33. 	v.push_back(8);
    34. 	//模拟迭代器遍历
    35. 	my::vector<int>::iterator it = v.begin();
    36. 	while (it != v.end())
    37. 	{
    38. 		cout << *it << " ";
    39. 		++it;
    40. 	}
    41. 	cout << endl;
    42. 	v.pop_back();
    43. 	v.pop_back();
    44. 	v.pop_back();
    45. 	//1.下标+[] 进行遍历 有3种遍历方式
    46. 	for (size_t i = 0; i < v.size(); ++i)
    47. 	{
    48. 		cout << v[i] << " ";
    49. 	}
    50. 	cout << endl;
    51. }
    52. void TestVector3()
    53. {
    54. 	my::vector<int> v;
    55. 	v.resize(6, 6);
    56. 	for (auto e : v)
    57. 	{
    58. 		cout << e << " ";
    59. 	}
    60. 	cout << endl;
    61. }
    62. void TestVector4()
    63. {
    64. 	my::vector<int> v;
    65. 	v.push_back(1);
    66. 	v.push_back(2);
    67. 	v.push_back(3);
    68. 	v.push_back(4);
    69. 	//v.push_back(5);
    70. 	//模拟迭代器遍历
    71. 	my::vector<int>::iterator it = v.begin();
    72. 	while (it != v.end())
    73. 	{
    74. 		cout << *it << " ";
    75. 		++it;
    76. 	}
    77. 	cout << endl;
    78. 	v.insert(v.begin(), 0);
    79. 	//v.insert(v.begin()+2, 0);
    80.  
    81. 	for (auto e : v)
    82. 	{
    83. 		cout << e << " ";
    84. 	}
    85. 	cout << endl;
    86. }
    87. void TestVector5()
    88. {
    89. 	//在所有的偶数前面插入9
    90. 	my::vector<int> v;
    91. 	//v.reserve(10);
    92. 	v.push_back(1);
    93. 	v.push_back(2);
    94. 	v.push_back(3);
    95. 	v.push_back(4);
    96. 	v.push_back(5);
    97. 	for (auto e : v)
    98. 	{
    99. 		cout << e << " ";
    100. 	}
    101. 	cout << endl;
    102.  
    103. 	my::vector<int>::iterator it = v.begin();
    104. 	while (it != v.end())
    105. 	{
    106. 		if (*it % 2 == 0)
    107. 		{
    108. 			it=v.insert(it, 9); //insert扩容以后，it就失效了，it值传递给pos，pos改变不影响it
    109. 								//it指向的位置变了
    110. 			++it;
    111.  
    112. 		}
    113. 		++it;
    114. 	
    115. 	}
    116. 	for (auto e : v)
    117. 	{
    118. 		cout << e << " ";
    119. 	}
    120. 	cout << endl;
    121. }
    122. void TestVector6()
    123. {
    124. 	my::vector<int> v;
    125. 	v.push_back(1);
    126. 	v.push_back(2);
    127. 	v.push_back(3);
    128. 	v.push_back(4);
    129. 	for (auto e : v)
    130. 	{
    131. 		cout << e << " ";
    132. 	}
    133. 	cout << endl;
    134. 	cout << "v.size():" << v.size()<<"  " << "v.capacity:" << v.capacity() << endl;
    135. 	auto pos = find(v.begin(), v.end(), 2);
    136. 	if (pos != v.end())
    137. 	{
    138. 		v.erase(pos);
    139. 	}
    140. 	for (auto e : v)
    141. 	{
    142. 		cout << e << " ";
    143. 	}
    144. 	cout << endl;
    145. 	cout << "v.size():" << v.size() << "  " << "v.capacity:" << v.capacity() << endl;
    146. 	cout << *pos << endl;
    147. 	*pos = 10;
    148. 	for (auto e : v)
    149. 	{
    150. 		cout << e << " ";
    151. 	}
    152. }
    153. void TestVector7()
    154. {
    155. 	//删除所有的偶数
    156. 	my::vector<int> v;
    157. 	//std::vector v; //库里的vector
    158. 	v.push_back(2);
    159. 	v.push_back(1);
    160. 	v.push_back(2);
    161. 	v.push_back(2);
    162. 	v.push_back(2);
    163. 	v.push_back(3);
    164. 	v.push_back(4);
    165. 	v.push_back(5);
    166. 	v.push_back(6);
    167. 	v.push_back(6);
    168. 	v.push_back(6);
    169. 	v.push_back(6);
    170. 	v.push_back(5);
    171. 	for (auto e : v)
    172. 	{
    173. 		cout << e << " ";
    174. 	}
    175. 	cout << endl;
    176. 	auto it = v.begin();
    177. 	while (it != v.end())
    178. 	{
    179. 		if (*it % 2 == 0)
    180. 		{
    181. 			it=v.erase(it);  //处理迭代器失效问题的解决方式
    182. 		}
    183. 		else
    184. 		{
    185. 			++it;
    186. 		}
    187. 	}
    188. 	for (auto e : v)
    189. 	{
    190. 		cout << e << " ";
    191. 	}
    192. 	cout << endl;
    193.  
    194. }
    195. void TestVector8()
    196. {
    197. 	my::vector<int> v1;
    198. 	v1.push_back(1);
    199. 	v1.push_back(2);
    200. 	v1.push_back(3);
    201. 	v1.push_back(4);
    202. 	for (auto e : v1)
    203. 	{
    204. 		cout << e << " ";
    205. 	}
    206. 	cout << endl;
    207. 	my::vector<int> v2(v1.begin(), v1.end());
    208. 	std::string s("hello");
    209. 	my::vector<int> v3(s.begin(), s.end());
    210. 	for (auto e : v2)
    211. 	{
    212. 		cout << e << " ";
    213. 	}
    214. 	cout << endl;
    215. 	for (auto e : v3)
    216. 	{
    217. 		cout << e << " ";
    218. 	}
    219. 	cout << endl;
    220. }
    221. void TestVector9()
    222. {
    223. 	my::vector<int> v1;
    224. 	v1.push_back(1);
    225. 	v1.push_back(2);
    226. 	v1.push_back(3);
    227. 	v1.push_back(4);
    228. 	for (auto e : v1)
    229. 	{
    230. 		cout << e << " ";
    231. 	}
    232. 	cout << endl;
    233. 	my::vector<int> v2(v1); //拷贝构造
    234. 	for (auto e : v2)
    235. 	{
    236. 		cout << e << " ";
    237. 	}
    238. 	cout << endl;
    239. 	my::vector<int> v3;  
    240. 	v3 = v1;               //赋值
    241. 	for (auto e : v3)
    242. 	{
    243. 		cout << e << " ";
    244. 	}
    245. 	cout << endl;
    246. }
    247. void TestVector10()
    248. {
    249. 	//使用n个val构造函数
    250. 	my::vector<int> v1(10,2);
    251. 	for (auto e : v1)
    252. 	{
    253. 		cout << e << " ";
    254. 	}
    255. 	cout << endl;
    256. 	my::vector<char> v2(10, 'q');
    257. 	for (auto e : v2)
    258. 	{
    259. 		cout << e << " ";
    260. 	}
    261. 	cout << endl;
    262. }
    263. void TestVector11()
    264. {
    265. 	//杨辉三角
    266. 	class Solution
    267. 	{
    268. 	public:
    269. 		my::vectorint>> generate(int numRows)
    270. 		{
    271. 			my::vectorint>> vv;
    272. 			vv.resize(numRows);
    273. 			for (size_t i = 0; i < vv.size(); ++i)
    274. 			{
    275. 				//每次每行个数递增1
    276. 				vv[i].resize(i + 1, 0);
    277. 				vv[i][0] = 1;
    278. 				vv[i][vv[i].size() - 1] = 1;
    279. 			}
    280. 			for (int i = 0; i < vv.size(); ++i)
    281. 			{
    282.  
    283. 				for (int j = 0; j < vv[i].size(); ++j)
    284. 				{
    285. 					if (vv[i][j] == 0)
    286. 					{
    287. 						//中间位置等于上一行j-1列和j列相加
    288. 						vv[i][j] = vv[i - 1][j - 1] + vv[i - 1][j];
    289. 					}
    290. 					cout << vv[i][j] << " ";
    291. 				}
    292. 				cout << endl;
    293. 			}
    294. 			cout << endl;
    295. 			return vv;
    296. 		}
    297. 		
    298. 	};
    299. 	my::vectorint>> vv = Solution().generate(7);
    300. 	for (int i = 0; i < vv.size(); ++i)
    301. 	{
    302. 		for (int j = 0; j < vv[i].size(); ++j)
    303. 		{
    304. 			cout << vv[i][j] << " ";
    305. 		}
    306. 		cout << endl;
    307.  
    308. 	}
    309. }
    310.  
    311. int main()
    312. {
    313. 	//TestVector1();
    314. 	//TestVector2();
    315. 	//TestVector3();
    316. 	//TestVector4();
    317. 	//TestVector5();
    318. 	//TestVector6();
    319. 	//TestVector7();
    320. 	//TestVector8();
    321. 	//TestVector9();
    322. 	//TestVector10();
    323. 	TestVector11();
    324.  
    325. 	return 0;
    326. }

    2.2例题：使用vector实现杨辉三角：

     

    后记：
    ●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！
                                                                      ——By 作者：新晓·故知

     

  • 相关阅读:
    微信聊天功能测试用例
    @umijs/plugin-locale使用
    Pipenv
    100 余个网页设计优化案例（用户体验、交互优化等方面）
    AOP 编程
    【数据结构】图 常见题型汇总
    RabbitMQ的高级特性
    基于Swagger的接口自动化测试
    CSS 网页布局
    echarts折线图（其他图也是一样）设置tooltip自动滚动
  • 原文地址：https://blog.csdn.net/m0_57859086/article/details/126165377