• C++ vector类模拟实现

    目录

    一、成员变量

    二、构造函数

    1.默认构造 

     2.拷贝构造

    3.迭代器构造

    4.使用n个值构造

    5.赋值拷贝

    三、析构函数 

    四、vector重要成员函数

    1.size和capacity函数

     2.reserve函数

     3.resize函数

     4.push_back函数

    5.insert函数

    6.erase函数 

    7.重载operator[]

    一、成员变量

    STL库里面，vector的成员变量和string有一些不一样，他的成员变量是用了迭代器

    _start是数组起始位置

    _finish是数据内容结束位置的下一个

    _endofstorage是开辟的空间结束位置的下一个。

     

    那么vector的迭代器是又是什么呢？

    vector使用了模版，他可以适配各种类型，他的迭代器就是这个模板类型的指针。

     因为vector和string一样，本质上就是数组，开辟的空间在内存上是连续的，因此使用指针当迭代器是在合理不过了。

    二、构造函数

    我们模仿一下STL里面的vector，没有使用适配器。

    1.默认构造 

    vector的默认构造很简单，直接写上就好，内容都可以不需要，因为我们在成员变量哪里给到了初始值，他会在初始化列表中自动调用，因此这里可以不需要写初始化列表。

    那么我们可以不可以不要下面这局代码呢？   

    答案是不可以的，因为我们后续还会写上其他的构造函数，那么编译器就不会提供默认生成的构造函数了。那这样我们普通的一个代码  vector v  就会报错

    1. vector()
    2. {}

     2.拷贝构造

    拷贝构造调用了push_back函数，先开辟好空间，防止后续再扩容，后续尾插即可。

    1. vector(const vector& v)
    2. {
    3. 	reserve(v.capacity());
    4. 	for (auto& e : v)
    5. 	{
    6. 		push_back(e);
    7. 	}
    8. }

    3.迭代器构造

    这里使用了模板来处理，因为我们不仅仅想使用vector迭代器去构造类对象，我们还想使用其他类对象的迭代器去构造。也是利用尾插即可。

    1. template <class InputIterator>
    2. vector(InputIterator first, InputIterator last)
    3. {
    4. 	while (first != last)
    5. 	{
    6. 		push_back(*first);
    7. 		first++;
    8. 	}
    9. }

    4.使用n个值构造

    开辟n个空间，并全部赋值为给到的val参数。

    1. vector(int n, const T& val = T())
    2. {
    3. 	resize(n, val);
    4. }
    5.  
    6. vector(size_t n, const T& val = T())
    7. {
    8. 	resize(n,val);
    9. }

     这里为什么我们要重载呢，一个写出int类型，一个写成size_t类型？

    我们先不写上面的int重载，下面这句代码，使用n个val进行拷贝，竟然报错了，为啥会这样？

    48行有问题，我们发现，明明我想调用的是58行的拷贝构造，为啥会到模板那里去？

    是因为此时所传的 10 和 1 都是int类型，而下面那个是 size_t和 int 两个类型，编译器认为你要用这个模板来初始化，因此会调用生成 InputIterator为int的函数，int类型去解引用，那可不就报错了嘛，为了让编译器认识两个整形，我们就重载了vector，使他能够知道我们的意思。

    5.赋值拷贝

    利用了很现代的写法，参数我们不传&，就会拷贝构造一个临时对象，这个临时对象刚好是我this需要的内容，我直接和你swap一下，你身上就有了我不要的内容了，同时出了作用域你会析构，我会引用返回，就完成了赋值拷贝。

    1. vector& operator=(vector v)
    2. {
    3. 	swap(_start,v._start);
    4. 	swap(_finish, v._finish);
    5. 	swap(_endofstorage, v._endofstorage);
    6. 	return *this;
    7. }

    三、析构函数 

    easy，直接delete[]  ，顺便置空即可。

    1. ~vector()
    2. {
    3. 	delete[] _start;
    4. 	_start = _finish = _endofstorage = nullptr;
    5. }

    四、vector重要成员函数

    1.size和capacity函数

    由于我们成员变量都是迭代器(实现方式为指针)，因此size()的大小和capacity()都可以用迭代器相减的方式得到。

    1. size_t size() const
    2. {
    3. 	return _finish - _start;
    4. }
    5. size_t capacity() const
    6. {
    7. 	return _endofstorage - _start;
    8. }

     2.reserve函数

    reserve可以开辟空间，n比现在的空间大才开辟，比现在的空间小则不管，不会删除数据。

    如果需要开辟空间，则会先new出新的空间，把原有的数据数据拷贝到这个空间里，再删除原有的数据，同时对成员变量进行修改。

    注意我们在拷贝的时候不能使用memcpy，因为用memcpy拷贝，如果类型为自定义类型，就仅仅是浅拷贝，浅拷贝会在开辟新空间的时候进行delete，一旦delete，新空间也被delete了。

    这里我们选择了使用循环赋值，因为自定义类型会调用他的赋值拷贝，而他的赋值拷贝一般是深拷贝(只要写了的话)，因此我们再扩容的时候就不会因为delete而发生错误了。

    1. void reserve(size_t n)
    2. {
    3. 	if (n > capacity())
    4. 	{
    5. 		size_t sz = size();
    6. 		T* tmp = new T[n];
    7. 		if (_start)
    8. 		{
    9. 			//memcpy对自定义类型是浅拷贝
    10. 			//memcpy(tmp, _start, sz * sizeof(T));
    11. 			//循环赋值，会调用自定义类型的赋值拷贝，就是深拷贝
    12. 			for (size_t i = 0; i < sz; i++)
    13. 			{
    14. 				tmp[i] = _start[i];
    15. 			}
    16. 			delete[] _start;
    17. 		}
    18. 		_start = tmp;
    19. 		_finish = _start + sz;
    20. 		_endofstorage = _start + n;
    21. 	}
    22. }

     3.resize函数

    resize会改变vector的size()。

    如果传的n要比size()小，那么就变成这个长度。

    如果n比size()大，就要先看扩不扩容，但是无论扩不扩容，我们都可以直接调用reserve函数，需要扩你就扩，不需要也没啥影响，后面在将你传过来的值，赋值给还未初始化的空间。

    注意在C++中一切类型都算对象，包括内置类型，因此我们传参给到的默认参数为T()  就像一个类的默认构造一样。 

    1. void resize(size_t n,const T& val = T())
    2. {
    3. 	if (n <= size())
    4. 	{
    5. 		_finish = _start + n;
    6. 	}
    7. 	else
    8. 	{
    9. 		reserve(n);
    10. 		for (size_t i = size(); i < n; i++)
    11. 		{
    12. 			_start[i] = val;
    13. 		}
    14. 		_finish = _start + n;
    15. 	}
    16. }

     4.push_back函数

    push_back函数先判断空间满了没有，满了就去扩容，空间capacity()为0就给4，不为0就给2倍。

    然后再*_finish这里赋值，_finish++即可。

    1. void push_back(const T& x)
    2. {
    3. 	if (size() == capacity())
    4. 	{
    5. 		size_t cp = capacity() == 0 ? 4 : capacity() * 2;
    6. 		reserve(cp);
    7. 	}
    8. 	*_finish = x;
    9. 	_finish++;
    10. }

    5.insert函数

    insert函数传的参数不是索引，而是迭代器！！！

    只要有插入，我们都得判断是否扩容，由于这里传递的是迭代器(vector中是指针)，扩容有可能是异地扩容，因此地址会发生改变，我们扩容前先记录一下pos相对于_start的位置，扩容后再加上这个位置赋值给pos才对。

    后续就是挪动数据，挪动完赋值，_finish++，最后要返回pos（可以防止迭代器失效）。

    1. iterator insert(iterator pos,const T& x)
    2. {
    3. 	assert(pos >= _start);
    4. 	assert(pos <= _finish);
    5. 	if (size() == capacity())
    6. 	{
    7. 		size_t len = pos - _start; 
    8. 		//扩容后_start位置可能会发生改变了，因此要记录pos的相对位置，改变pos的值
    9. 		size_t cp = capacity() == 0 ? 4 : capacity() * 2;
    10. 		reserve(cp);
    11. 		pos = _start+len;
    12. 	}
    13. 	iterator end = _finish - 1;
    14. 	while (end >= pos)
    15. 	{
    16. 		*(end + 1)  = *end;
    17. 		end--;
    18. 	}
    19. 	*pos = x;
    20. 	_finish++;
    21. 	return pos;
    22. }

    6.erase函数 

    erase比insert还要简单一点，也是挪动数据，方向不一样，insert是从后往前数据往后挪动，erase是从当前位置往后向前挪动数据。再_finish--，最后返回pos（这也是为了防止迭代器失效）。

    1. iterator erase(iterator pos)
    2. {
    3. 	assert(pos >= _start);
    4. 	assert(pos < _finish);
    5. 	iterator it = pos;
    6. 	while (it < _finish - 1)
    7. 	{
    8. 		*it = *(it +1);
    9. 		++it;
    10. 	}
    11. 	_finish--;
    12. 	return pos;
    13. }

    7.重载operator[]

     分为普通版本和const版本，普通可读可写，const只能读。

    1. T& operator[](size_t pos)
    2. {
    3. 	assert(pos < size());
    4. 	return _start[pos];
    5. }
    6. //不可修改
    7. const T& operator[](size_t pos) const
    8. {
    9. 	assert(pos < size());
    10. 	return _start[pos];  
    11. }

    最后附上总代码 

    vector.h

    1. #pragma once
    2. namespace kky
    3. {
    4. 	template<class T>
    5. 	class vector
    6. 	{
    7. 	public:
    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. 		vector()
    32. 		{}
    33.  
    34. 		vector(const vector& v)
    35. 		{
    36. 			reserve(v.capacity());
    37. 			for (auto& e : v)
    38. 			{
    39. 				push_back(e);
    40. 			}
    41. 		}
    42.  
    43. 		template <class InputIterator>
    44. 		vector(InputIterator first, InputIterator last)
    45. 		{
    46. 			while (first != last)
    47. 			{
    48. 				push_back(*first);
    49. 				first++;
    50. 			}
    51. 		}
    52.  
    53. 		vector(int n, const T& val = T())
    54. 		{
    55. 			resize(n, val);
    56. 		}
    57.  
    58. 		//vector(size_t n, const T& val = T())
    59. 		//{
    60. 		//	resize(n,val);
    61. 		//}
    62.  
    63. 		vector& operator=(vector v)
    64. 		{
    65. 			swap(_start,v._start);
    66. 			swap(_finish, v._finish);
    67. 			swap(_endofstorage, v._endofstorage);
    68. 			return *this;
    69. 		}
    70.  
    71.  
    72. 		~vector()
    73. 		{
    74. 			delete[] _start;
    75. 			_start = _finish = _endofstorage = nullptr;
    76. 		}
    77.  
    78. 		size_t size() const
    79. 		{
    80. 			return _finish - _start;
    81. 		}
    82. 		size_t capacity() const
    83. 		{
    84. 			return _endofstorage - _start;
    85. 		}
    86.  
    87. 		void reserve(size_t n)
    88. 		{
    89. 			if (n > capacity())
    90. 			{
    91. 				size_t sz = size();
    92. 				T* tmp = new T[n];
    93. 				if (_start)
    94. 				{
    95. 					//memcpy对自定义类型是浅拷贝
    96. 					//memcpy(tmp, _start, sz * sizeof(T));
    97. 					//循环赋值，会调用自定义类型的赋值拷贝，就是深拷贝
    98. 					for (size_t i = 0; i < sz; i++)
    99. 					{
    100. 						tmp[i] = _start[i];
    101. 					}
    102. 					delete[] _start;
    103. 				}
    104. 				_start = tmp;
    105. 				_finish = _start + sz;
    106. 				_endofstorage = _start + n;
    107. 			}
    108. 		}
    109.  
    110. 		void resize(size_t n,const T& val = T())
    111. 		{
    112. 			if (n <= size())
    113. 			{
    114. 				_finish = _start + n;
    115. 			}
    116. 			else
    117. 			{
    118. 				reserve(n);
    119. 				for (size_t i = size(); i < n; i++)
    120. 				{
    121. 					_start[i] = val;
    122. 				}
    123. 				_finish = _start + n;
    124. 			}
    125. 		}
    126.  
    127. 		void push_back(const T& x)
    128. 		{
    129. 			if (size() == capacity())
    130. 			{
    131. 				size_t cp = capacity() == 0 ? 4 : capacity() * 2;
    132. 				reserve(cp);
    133. 			}
    134. 			*_finish = x;
    135. 			_finish++;
    136. 		}
    137.  
    138. 		iterator insert(iterator pos,const T& x)
    139. 		{
    140. 			assert(pos >= _start);
    141. 			assert(pos <= _finish);
    142. 			if (size() == capacity())
    143. 			{
    144. 				size_t len = pos - _start; 
    145. 				//扩容后_start位置可能会发生改变了，因此要记录pos的相对位置，改变pos的值
    146. 				size_t cp = capacity() == 0 ? 4 : capacity() * 2;
    147. 				reserve(cp);
    148. 				pos = _start+len;
    149. 			}
    150. 			iterator end = _finish - 1;
    151. 			while (end >= pos)
    152. 			{
    153. 				*(end + 1)  = *end;
    154. 				end--;
    155. 			}
    156. 			*pos = x;
    157. 			_finish++;
    158. 			return pos;
    159. 		}
    160.  
    161. 		iterator erase(iterator pos)
    162. 		{
    163. 			assert(pos >= _start);
    164. 			assert(pos < _finish);
    165. 			iterator it = pos;
    166. 			while (it < _finish - 1)
    167. 			{
    168. 				*it = *(it +1);
    169. 				++it;
    170. 			}
    171. 			_finish--;
    172. 			return pos;
    173. 		}
    174.  
    175. 		
    176. 		T& operator[](size_t pos)
    177. 		{
    178. 			assert(pos < size());
    179. 			return _start[pos];
    180. 		}
    181. 		//不可修改
    182. 		const T& operator[](size_t pos) const
    183. 		{
    184. 			assert(pos < size());
    185. 			return _start[pos];  
    186. 		}
    187. 	private:
    188. 		iterator _start = nullptr;
    189. 		iterator _finish = nullptr;
    190. 		iterator _endofstorage = nullptr;
    191. 	};
    192. 	void test01()
    193. 	{
    194. 		vector<int> v;
    195. 		v.push_back(1);
    196. 		v.push_back(2);
    197. 		v.push_back(3);
    198. 		v.push_back(4);
    199. 		v.push_back(5);
    200. 		for (size_t i = 0; i < v.size(); i++)
    201. 		{
    202. 			cout << v[i] << " ";
    203. 		}
    204. 		cout << endl;
    205. 		for (auto e : v)
    206. 		{
    207. 			cout << e << " ";
    208. 		}
    209. 	}
    210. 	void test02()
    211. 	{
    212. 		vector<int> v;
    213. 		v.push_back(1);
    214. 		v.push_back(2);
    215. 		v.push_back(3);
    216. 		v.push_back(4);
    217. 		v.push_back(5);
    218. 		v.resize(10, 6);
    219. 		for (auto e : v)
    220. 		{
    221. 			cout << e << " ";
    222. 		}
    223. 		cout << endl;
    224. 		v.insert(v.begin(), 30);
    225. 		for (auto e : v)
    226. 		{
    227. 			cout << e << " ";
    228. 		}
    229. 		cout << endl;
    230. 	}
    231. 	void test03()
    232. 	{
    233. 		vector<int> v;
    234. 		v.push_back(1);
    235. 		v.push_back(2);
    236. 		v.push_back(3);
    237. 		v.push_back(4);
    238. 		v.push_back(5);
    239. 		for (auto e : v)
    240. 		{
    241. 			cout << e << " ";
    242. 		}
    243. 		cout << endl;
    244. 		v.erase(v.begin());
    245. 		for (auto e : v)
    246. 		{
    247. 			cout << e << " ";
    248. 		}
    249. 		cout << endl;
    250. 		v.erase(v.begin()+2);
    251. 		for (auto e : v)
    252. 		{
    253. 			cout << e << " ";
    254. 		}
    255. 	}
    256. 	void test04()
    257. 	{
    258. 		vector<int> v;
    259. 		v.push_back(1);
    260. 		v.push_back(2);
    261. 		v.push_back(3);
    262. 		v.push_back(4);
    263. 		v.push_back(5);
    264. 		v.push_back(6);
    265. 		vector<int>::iterator it = v.begin();
    266. 		while (it != v.end())
    267. 		{
    268. 			if (*it % 2 == 0)
    269. 			{
    270. 				it = v.erase(it);
    271. 			}
    272. 			else
    273. 			{
    274. 				it++;
    275. 			}
    276. 		}
    277. 		for (auto e : v)
    278. 		{
    279. 			cout << e << " ";
    280. 		}
    281. 	}
    282. 	void test05()
    283. 	{
    284. 		vector<int> v;
    285. 		v.push_back(1);
    286. 		v.push_back(2);
    287. 		v.push_back(3);
    288. 		v.push_back(4);
    289. 		v.push_back(5);
    290. 		v.push_back(6);
    291. 		vector<int> v2(v);
    292. 		for (auto e : v)
    293. 		{
    294. 			cout << e << " ";
    295. 		}
    296. 		cout << endl;
    297. 		for (auto e : v2)
    298. 		{
    299. 			cout << e << " ";
    300. 		}
    301. 		cout << endl;
    302. 		vector<int> v3;
    303. 		v3.push_back(1);
    304. 		v3 = v;
    305. 		for (auto e : v3)
    306. 		{
    307. 			cout << e << " ";
    308. 		}
    309. 	}
    310. 	void test06()
    311. 	{
    312. 		vector<int> v(10, 1);
    313. 		for (auto e : v)
    314. 		{
    315. 			cout << e << " ";
    316. 		}
    317. 		cout << endl;
    318.  
    319. 		std::string s("123456");
    320. 		vector<int> v1(s.begin(), s.end());
    321. 		for (auto e : v1)
    322. 		{
    323. 			cout << e << " ";
    324. 		}
    325. 		cout << endl;
    326. 	}
    327. 	void test07()
    328. 	{
    329. 		vector<int>v1(10, 1);
    330. 		vector<int>v2(10, 2);
    331. 		v1 = v2;
    332. 		for (auto e : v1)
    333. 		{
    334. 			cout << e << " ";
    335. 		}
    336. 		cout << endl;
    337. 	}
    338. }
    339.  
    340.

    test.cpp

    1. #include 
    2. using namespace std;
    3. #include
    4. #include"vector.h"
    5. int main()
    6. {
    7. 	kky::test07();
    8.  
    9. }

  • 相关阅读:
    Unity笔记（10）：SHOOT GAME EXAMPLE【2D】
    Spring Boot 自定义注解
    7-29 删除字符串中的子串
    C# OpenCvSharp 环形文字处理 直角坐标与极坐标转换
    c语言入门---操作符
    error while loading shared libraries: libgo.so.19 错误的解决
    如何学好次世代3D建模，学些什么，达到什么标准才能入行？
    【jmeter的使用】【性能测试1】
    动环监控系统的主要功能，动环监控系统的监控对象有哪些
    Python面向对象，实现图片处理案例，支持：高斯模糊、Canny边缘检测、反转边缘图像、生成手绘效果、调亮度......等等
  • 原文地址：https://blog.csdn.net/kkbca/article/details/133925279