C++初阶 Vector模拟实现

作者：@小萌新
专栏：@C++初阶
作者简介：大二学生 希望能和大家一起进步
本篇博客介绍：本篇博客会模拟Vector实现

学习目标

1. 模拟默认函数实现
2. 模拟迭代器实现
3. 模拟容器大小相关函数
4. 模拟修改内容相关函数
5. 模拟访问容器相关函数

我们先来看看整体的模板是什么样子的

vector是一个经典的类模板 所以我们这里使用泛型编程

namespace shy
{
	template<class T> // 使用模板
	class vector
	{
	public:
		typedef T* itreator; // 使用迭代器
		typedef const T* const_iterator; // const 迭代器

	private:
		iterator _start; // 指向容器的头
		iterator _finish; // 指向有效数据的尾
		iterator _endofstorage; // 指向容器的尾
	};
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

模拟默认函数的实现

构造函数

无参构造

顾名思义就是不传参数构造 那我们这里就给几个默认值就好

		vector<T>()                      // 无参 默认初始化 
			:_start(nullptr),
			_finish(nullptr),
			_endofstorage(nullptr)
		{}
1
2
3
4
5

我们来看看运行效果

可以运行 不会报错

迭代器构造

除了无参构造之外 vector类还支持迭代器构造

（这两个要实现后面的函数之后复用才比较简便 所以我们后面再回来实现这个函数）

		template<class InputIterator> //模板函数
		vector(InputIterator first, InputIterator last)
			:_start(nullptr)
			, _finish(nullptr)
			, _endofstorage(nullptr)
		{
			//将迭代器区间在[first,last)的数据一个个尾插到容器当中
			while (first != last)
			{
				push_back(*first);
				first++;
			}
		}
1
2
3
4
5
6
7
8
9
10
11
12
13

指定构造

此外vetor构造函数还支持指定大小构造相同的值 也是一样 我们后面先实现其他函数之后再来实现它们

所以说我们这里要输入两个参数 一个是大小 一个是值

那么思路就很清晰了 插入n个这个值就好啦

//构造函数3
vector(size_t n, const T& val)
	:_start(nullptr)
	, _finish(nullptr)
	, _endofstorage(nullptr)
{
	reserve(n); //调用reserve函数将容器容量设置为n
	for (size_t i = 0; i < n; i++) //尾插n个值为val的数据到容器当中
	{
		push_back(val);
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13

析构函数

释放空间 全部指针（迭代器）置空即可 代码表示如下

		~vector()
		{
			delete[] _start;
			_start = nullptr; //_start置空
			_finish = nullptr; //_finish置空
			_endofstorage = nullptr; //_endofstorage置空
		}
1
2
3
4
5
6
7
8

拷贝构造

思路如下

我们首先将空间扩大至要拷贝的空间

然后一个个的插入数据即可

代码表示如下

//现代写法
vector(const vector<T>& v)
	:_start(nullptr)
	, _finish(nullptr)
	, _endofstorage(nullptr)
{
	reserve(v.capacity()); //调用reserve函数将容器容量设置为与v相同
	for (auto e : v) //将容器v当中的数据一个个尾插过来
	{
		push_back(e);
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13

赋值运算符重载

这里也很简单

我们使用传值拷贝 然后交换它们的三个指针就可以

//现代写法
vector<T>& operator=(vector<T> v) //编译器接收右值的时候自动调用其拷贝构造函数
{
	swap(v); //交换这两个对象
	return *this; //支持连续赋值
}

1
2
3
4
5
6
7

容量大小相关函数

capacity

这个函数的意思很明显 就是返回容量有多少就可以

代码也很简单

		int capacity()
		{
			return _endofstorage - _start; // 计算容量大小
		}
1
2
3
4
5

size

返回有效元素的个数 代码也是一样的

		int size()
		{
			return _finish - _start; // 计算有效元素个数
		}
1
2
3
4
5

empty

判断是否为空 这里只要判断下首和尾是否相同就可以了

		bool empty()
		{
			return _finish == _start;
		}
1
2
3
4

reserve

reserve的使用规则如下

1. 如果reserve的大小小于本来容器的容量 那就什么都不做
2. 如果reserve的大小大于本来容器的容量 那就扩容至给予的大小

代码表示和效果图如下

	void reserve(int n)
		{
			if (n > this->capacity()) // 这里写this指向也可以
			{
				size_t sz = size(); //记录一下原本的大小是多少
				T* tmp = new T[n]; // 开辟出来这么大的空间
				// 这里开始将原本空间的所有数据拷贝进去
				if (_start)
				{
					int i = 0;
					while (i<sz)
					{
						tmp[i] = *(_start + i);
						i++;
					}
					// 走到这里全部赋值完毕
				}
				delete[] _start; // 将原本的容器删除

				_start = tmp;
				_finish = _start + sz;
				_endofstorage = _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

这里我们有两个注意点

一 我们必须提前保存size的值

这是为什么呢？ 还记不记我们要在什么时候使用sz

是在start被赋值tmp的时候吧 那么这个时候start的位置是不是改变了

size的值是不是就失真了啊 （size = finish - start （原本的））

所以说我们要提前保存size的值

二 我们这里必须使用传值赋值不能使用memcpy

为什么呢？

如果是自定义类型的话 是不是传值还是memcpy没有任何区别

但是如果是自定义类型呢？

假如我们使用memcpy进行复制的话 是不是就是连指针指向的位置都复制过来了啊

那么当我们delete原来空间的时候是不是全部会自动调用析构函数然后不就直接g了

开新空间开了个寂寞

所以说这个时候用传值拷贝就可以了

resize

resize的使用规则是这样子的

首先它有两个参数 一个是我们要resize的大小 一个是默认初始化的值

1. 假设我们要resize的大小小于目前的有效元素 我们将n赋值给_finish
2. 假设我们要resize的大小大于目前的有效元素并且小于有效容量时 我们将_finish到n这一段赋值给我们给的值
3. 假设我们要resize的大小大于目前的有效元素并且大于有效容量时 扩容有效容量大小到n 之后重复2的操作

		void resize(int n ,const T& val = T())
		{
			assert(n >= 0);
			// 首先处理最简单的情况 也就是resize小于当前有效元素 
			if (n < size())
			{
				_finish = n;
			}

			if (n > size())
			{
				reserve(n); // 这里不用管其他的直接用就行 因为容量小于caoacity是什么都不会发生的

				while (_finish < _start + n)// 注意不是finish大于n 而是要大于start+n 
				{
					*_finish = val;
					_finish++;
				}
			}
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

修改内容相关函数

push_back

见名知义 往后插入一个元素 和前面一样 我们需要判断是否需要扩容

这个时候我们的引用传参的左右就来了 万一我们要传递的参数是一个非常大大的数组呢？

如果传值传递是不是效率就特别低了

代码表示如下

	void push_back(const T& val)
		{
			if (_finish == _endofstorage)
			{
				reserve(capacity() == 0 ? 4 : 2 * capacity()); // 扩容
			}

			_finish = val; // 赋值
			_finish++; // 指针++
		}

1
2
3
4
5
6
7
8
9
10
11
12

pop_bakc

尾删 这个操作就更简单了 只不过有一个小注意点要判断下是否为空

	void pop_back()
		{
			assert(!empty());
			_finish--;
		}
1
2
3
4
5

insert

insert函数可以在指定的pos位置插入一个数据

我们需要给两个参数 一个是我们要插入位置的迭代器 一个是要插入的数据

代码表示如下

		void insert(iterator pos, const T& val)
		{


	    	// 首先要判断是否需要扩容
			if (_endofstorage == _finish)
			{
				int len = pos - _start;
				reserve(capacity() == 0 ? 4 : 2 * capacity());
				pos = _start + len; // 为什么这么操作呢？ 因为扩容之后start的位置有可能改变
			}

			iterator end = _finish; 
			// 将前面一个位置移动到后面一个位置 pos位置不移动
			while (pos < end)
			{
				*(end) = *(end - 1);
				end--;
			}
			*pos = val;
			_finish++;
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

earse

这里可以指定位置函数 还是一样记得要判断是否为空

还有一点特殊点就是它会返回被它删除之后的下一位迭代器！

代码表示如下

		iterator earse(iterator pos)
		{
			assert(!empty());
			iterator it = pos;
			while (pos != _finish)
			{
				*pos = *(pos +1)
			}
			
			_finish--;
			return pos;
		}

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

迭代器相关函数

这里返回的都很简单 我们直接写就好了

		iterator begin()
		{
			return _start;
		}

		iterator end()
		{
			return _finish;
		}

		const_iterator begin()
		{
			return _start;
		}


		const_iterator end()
		{
			return _finish;
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

访问下标有关

Vector还支持下标访问

所以说我们这里要重载下下标访问运算符

代码表示如下

		T& operator[](size_t i)
		{
			assert(i < size()); //检测下标的合法性

			return _start[i]; //返回对应数据
		}
		const T& operator[](size_t i)const
		{
			assert(i < size()); //检测下标的合法性

			return _start[i]; //返回对应数据
		}
1
2
3
4
5
6
7
8
9
10
11
12

总结

本篇博客主要介绍了vector的模拟实现
由于作者水平有限 错误在所难免 希望大佬看到之后可以及时指正
如果这篇文章帮助到了你 别忘记一键三连啊
阿尼亚 哇酷哇酷！