• vector模拟实现【c++】

    文章目录：

    🛰️vector模拟实现底层结构

    在这里插入图片描述

    🛰️vector基础框架

    namespace hy
{
	template
	class vector
	{
	public:
	    //vector的迭代器是一个原生指针
		typedef T* iterator;
		typedef const T* const_iterator;

		vector()
			:_start(nullptr)
			,_finish(nullptr)
			,_endofstorage(nullptr)
		{}

		~vector()
		{
			if (_start)
			{
				delete[] _start;
			}
			_start = _finish = _endofstorage = nullptr;
		}

	private:
		iterator _start;      
		iterator _finish;
		iterator _endofstorage;
	};
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31

    🛰️vector中reserve 、resize

    void reserve(size_t n)
{
	if (n > capacity())
	{
		size_t sz = size();
		T* tmp = new T[n];
		if (_start)
		{
			//这里直接使用memcpy拷贝会出现一些深层次问题，文章末尾分析
			//memcpy(tmp, _start, size() * sizeof(T));

			for (size_t i = 0;i < sz;++i)
			{
				tmp[i] = _start[i];
			}
			delete[] _start;
		}
		_start = tmp;
		_finish = _start + sz;
		_endofstorage = _start + n;
	}
}

//void resize(size_t n,T val = T())
void resize(size_t n, const T& val = T())
{
	//空间不够，增容
	if (n > capacity())
		reserve(n);

	//如果n大于当前的size,则多出空间用val填充
	if (n > size())
	{
		while (_finish < _start + n)
		{
			*_finish = val;
			++_finish;
		}
	}
	//如果n小于当前的size,则数据个数缩小到n
	else
	{
		_finish = _start + n;
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45

    🛰️vector的构造函数

    在这里插入图片描述
    ❗理论上来说，提供了vector(size_t n,const T& val = T())后，就不需要提供vector(int n, const T& val = T())，但是对于vector的构造函数（vector v(10,5);），编译器编译代码时，认为T被实例化为int，10和5编译器默认为是int类型，就不会匹配vector(size_t n,const T& val = T())，编译器识别10和5两个数据类型一致，因此编译器匹配了 vector(InputIterator first, InputIterator last)，导致编译器将模板参数InputIterator实例化为int，导致后序匹配失败，编译器报错。所以需要重载size_t和int两个版本的构造函数。

    template
vector(InputIterator first, InputIterator last)
	: _start(nullptr)
	, _finish(nullptr)
	, _endofstorage(nullptr)
{
	while (first != last)
	{
		push_back(*first);
		++first;
	}
}

vector(size_t n, const T& val = T())
	:_start(nullptr)
	, _finish(nullptr)
	, _endofstorage(nullptr)
{
	reserve(n);
	for (size_t i = 0;i < n;++i)
	{
		push_back(val);
	}
}

vector(int n, const T& val = T())
	:_start(nullptr)
	, _finish(nullptr)
	, _endofstorage(nullptr)
{
	reserve(n);
	for (size_t i = 0;i < n;++i)
	{
		push_back(val);
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36

    🛰️vector的push_back、pop_back

    void push_back(const T& val)
{
	if (_finish == _endofstorage)
	{
		size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
		reserve(newCapacity);
	}
	*finish = val;
	++finish;
}

void pop_back()
{
	assert(!empty());
	--_finish;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    🛰️vector的insert、erase

    在这里插入图片描述
    🎯注意：insert插入数据时，若vector空间满了，则需要扩容，扩容后之前传入的pos还是指向旧空间，这时我们需要更新pos的位置，使它指向新空间对应的位置。否则程序就会崩溃。

    iterator insert(iterator pos , const T& val)
{
	assert(pos >= _start && pos <= _finish);

	//扩容以后pos就失效了，需要更新pos的位置
	if (_finish == _endofstorage)
	{
		//计算出pos位置相对于起始位置的相对位置
		size_t n = pos - _start;

		size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
		reserve(newCapacity);

		//更新pos,解决增容后pos失效的问题
		pos = _start + n;
	}

	iterator end = _finish - 1;
	while (end >= pos)
	{
		*(end + 1) = *end;
		--end;
	}
	*pos = val;
	++_finish;

	return pos;
}

iterator erase(iterator pos)
{
	assert(pos >= _start && pos < _finish);
	iterator it = pos + 1;
	while (it !=_finish)
	{
		*(it - 1) = *it;
		++it;
	}
	--_finish;

	return pos;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42

    🛰️vector的拷贝构造和赋值运算符重载

    写法一：

    iterator erase(iterator pos)
{
	assert(pos >= _start && pos < _finish);
	iterator it = pos + 1;
	while (it !=_finish)
	{
		*(it - 1) = *it;
		++it;
	}
	--_finish;

	return pos;
}

//vector(const vector& v)
vector(const vector& v)
	:_start(nullptr)
	, _finish(nullptr)
	, _endofstorage(nullptr)
{
	reserve(v.capacity());
	/*for (auto e : v)
		push_back(e);*/

	_start = new T[v.capacity()];
	memcpy(_start, v._start, sizeof(T) * v.size());
	_finish = _start + v.size();
	_endofstorage = _start + v.capacity();
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29

    写法二：
    拷贝构造：用v构造一个tmp对象，再将tmp交换到需要拷贝构造的对象。
    赋值运算符重载：使用传值传参，v是由传参时拷贝的临时对象，将拷贝的对象直接交换给最终被赋值的对象。

    void swap(vector& v)
{
	::swap(_start, v._start);
	::swap(_finish, v._finish);
	::swap(_endofstorage, v._endofstorage);
}

vector(const vector& v)
	:_start(nullptr)
	, _finish(nullptr)
	, _endofstorage(nullptr)
{
	vector tmp(v.begin(), v.end());
	swap(tmp);
}

vector& operator=(vector v)//v是由传参时拷贝构造的
{
    swap(v);
	return *this;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    🛰️memcpy的深层次拷贝问题

    ❓若vector接口中的增容接口reserve中使用memcpy进行拷贝数据，那么会有什么问题吗?
    在这里插入图片描述

    🎯以杨辉三角的打印为例，我们来看看vector中memcpy的深拷贝问题：

    class Solution {
public:
	vector> generate(int numRows) {
		vector> vv;
		//构建结构空间
		vv.resize(numRows);
		for (size_t i = 0;i < vv.size();++i)
		{
			vv[i].resize(i + 1);
		}
		for (size_t i = 0;i < vv.size();++i)
		{
			vv[i][0] = vv[i][vv[i].size() - 1] = 1;
		}

		for (int i = 0;i < vv.size();++i)
		{
			for (int j = 0;j < vv[i].size();++j)
			{
				if (vv[i][j] != 1)
				{
					vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
				}
			}
		}
		for (size_t i = 0; i < vv.size(); ++i)
		{
			for (size_t j = 0; j < vv[i].size(); ++j)
			{
				cout << vv[i][j] << " ";
			}
			cout << endl;
		}

		return vv;
	}
};

void test_vector1()
{
	vector> ret = Solution().generate(5);

	for (size_t i = 0; i < ret.size(); ++i)
	{
		for (size_t j = 0; j < ret[i].size(); ++j)
		{
			cout << ret[i][j] << " ";
		}
		cout << endl;
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51

    当杨辉三角的行数为5时，vector>中结构如下：
    在这里插入图片描述
    运行结果如下：
    1、memcpy是内存中的二进制格式拷贝，它会将一段内存空间中的内容原封不动的拷贝到另外一段内存空间里面。
    2、若memcpy拷贝的是自定义类型的数据，memcpy高效且不会出错。但是如果拷贝的是自定义类型的元素，并且自定义类型中元素涉及资源管理时，使用memcpy就会出错，因为memcpy是浅拷贝。
    在这里插入图片描述
    🎯对于这个问题的解决方案：
    在这里插入图片描述

    🪩总结一下：若拷贝的对象中涉及资源管理时，不能使用memcpy进行对象之间的拷贝，memcpy只能进行浅拷贝，继续使用可能导致内存泄漏和程序崩溃等问题，所以我们使用memcpy的时候一定要谨慎。

    🛰️vector模拟实现代码

    vector.h

    #pragma once
#include
#include
#include
using namespace std;

namespace hy
{
	template
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;

		vector()
			:_start(nullptr)
			,_finish(nullptr)
			,_endofstorage(nullptr)
		{}

		iterator begin()
		{
			return _start;
		}

		iterator end()
		{
			return _finish;
		}

		const_iterator begin() const
		{
			return _start;
		}

		const_iterator end() const
		{
			return _finish;
		}

		template
		vector(InputIterator first, InputIterator last)
			: _start(nullptr)
			, _finish(nullptr)
			, _endofstorage(nullptr)
		{
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

		vector(size_t n, const T& val = T())
			:_start(nullptr)
			, _finish(nullptr)
			, _endofstorage(nullptr)
		{
			reserve(n);
			for (size_t i = 0;i < n;++i)
			{
				push_back(val);
			}
		}

		vector(int n, const T& val = T())
			:_start(nullptr)
			, _finish(nullptr)
			, _endofstorage(nullptr)
		{
			reserve(n);
			for (size_t i = 0;i < n;++i)
			{
				push_back(val);
			}
		}

		size_t size()const
		{
			return _finish - _start;
		}

		size_t capacity()const
		{
			return _endofstorage - _start;
		}

		bool empty()const
		{
			return _start == _finish;
		}

		T& operator[](size_t i)
		{
			assert(i < size());
			return _start[i];
		}

		const T& operator[](size_t i) const
		{
			assert(i < size());
			return _start[i];
		}

		void reserve(size_t n)
		{
			if (n > capacity())
			{
				size_t sz = size();
				T* tmp = new T[n];
				if (_start)
				{
					//这里直接使用memcpy拷贝会出现一些深层次问题，文章末尾分析
					//memcpy(tmp, _start, size() * sizeof(T));

					for (size_t i = 0;i < sz;++i)
					{
						tmp[i] = _start[i];
					}
					delete[] _start;
				}
				_start = tmp;
				_finish = _start + sz;
				_endofstorage = _start + n;
			}
		}

		//void resize(size_t n,T val = T())
		void resize(size_t n, const T& val = T())
		{
			//空间不够，增容
			if (n > capacity())
				reserve(n);

			//如果n大于当前的size,则多出空间用val填充
			if (n > size())
			{
				while (_finish < _start + n)
				{
					*_finish = val;
					++_finish;
				}
			}
			//如果n小于当前的size,则数据个数缩小到n
			else
			{
				_finish = _start + n;
			}
		}

		void push_back(const T& val)
		{
			if (_finish == _endofstorage)
			{
				size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newCapacity);
			}
			*_finish = val;
			++_finish;
		}

		void pop_back()
		{
			assert(!empty());
			--_finish;
		}

		iterator insert(iterator pos , const T& val)
		{
			assert(pos >= _start && pos <= _finish);

			//扩容以后pos就失效了，需要更新pos的位置
			if (_finish == _endofstorage)
			{
				//计算出pos位置相对于起始位置的相对位置
				size_t n = pos - _start;

				size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newCapacity);

				//更新pos,解决增容后pos失效的问题
				pos = _start + n;
			}

			iterator end = _finish - 1;
			while (end >= pos)
			{
				*(end + 1) = *end;
				--end;
			}
			*pos = val;
			++_finish;

			return pos;
		}

		iterator erase(iterator pos)
		{
			assert(pos >= _start && pos < _finish);
			iterator it = pos + 1;
			while (it !=_finish)
			{
				*(it - 1) = *it;
				++it;
			}
			--_finish;

			return pos;
		}

		void swap(vector& v)
		{
			::swap(_start, v._start);
			::swap(_finish, v._finish);
			::swap(_endofstorage, v._endofstorage);
		}

		vector(const vector& v)
			:_start(nullptr)
			, _finish(nullptr)
			, _endofstorage(nullptr)
		{
			vector tmp(v.begin(), v.end());
			swap(tmp);
		}

		vector& operator=(vector v)//v是由传参时拷贝构造的
		{
			swap(v);
			return *this;
		}

		vector(const vector& v)
		//vector(const vector& v)
		//	:_start(nullptr)
		//	, _finish(nullptr)
		//	, _endofstorage(nullptr)
		//{
		//	reserve(v.capacity());
		//	/*for (auto e : v)
		//		push_back(e);*/

		//	_start = new T[v.capacity()];
		//	memcpy(_start, v._start, sizeof(T) * v.size());
		//	_finish = _start + v.size();
		//	_endofstorage = _start + v.capacity();
		//}

		//vector& operator=(const vector& v)
		//{
		//	if (this != &v)
		//	{
		//		delete[] _start;
		//		_start = new T[v.capacity()];
		//		memcpy(_start, v._start, sizeof(T) * v.size());
		//		_finish = _start + v.size();
		//		_endofstorage = _start + v.capacity();
		//	}
		//	return *this;
		//}

		~vector()
		{
			if (_start)
			{
				delete[] _start;
			}
			_start = _finish = _endofstorage = nullptr;
		}

	private:
		iterator _start;      
		iterator _finish;
		iterator _endofstorage;
	};
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235
    • 236
    • 237
    • 238
    • 239
    • 240
    • 241
    • 242
    • 243
    • 244
    • 245
    • 246
    • 247
    • 248
    • 249
    • 250
    • 251
    • 252
    • 253
    • 254
    • 255
    • 256
    • 257
    • 258
    • 259
    • 260
    • 261
    • 262
    • 263
    • 264
    • 265
    • 266
    • 267
    • 268
    • 269
    • 270
    • 271
    • 272
    • 273
    • 274
    • 275
    • 276
    • 277
  • 相关阅读:
    小程序备案小程序认证双系统
    奢侈品鉴定机构小程序开发制作功能介绍
    SQL Developer 小贴士：备份和恢复连接信息
    Ansible最佳实践之委派任务和事实
    muduo源码剖析之TcpServer服务端
    el-form动态表单动态验证(先验证不为空，再验证长度在20以内，最后向后台发送请求验证账号是否重复)
    基于NoneBot2的qq机器人配置记录
    美芯片禁令再次扩大，波及英伟达、AMD以及intel等科技公司 | 百能云芯
    AI实战营第二期 第五节 《目标检测与MMDetection》——笔记6
    工作学习记录
  • 原文地址：https://blog.csdn.net/qq_61939403/article/details/126770602