vector的模拟实现

ahao

发布于 2024-03-19 19:13:45

1890

文章被收录于专栏：学习学习

上一篇我们对vector一些常用的函数进行了讲解，本篇博客我们就对vector进行模拟实现，以便于我们更好地了解vector的使用以及对一些常见bug的认识

有了string类的模拟实现，vector的模拟实现我们上手起来就简单一点了：首先为了和库里面的vector混淆视听，放入自己命名的空间里，并且根据vector的源码分析我们得出了三个成员变量：

分别是：其实他们实质上都是指针，位置大概是这样的，遵循左闭右开的规则

_start
_finish
_endofstorage

这样一个简单的框架就构造出来了： template是模板初阶我们学习过的，里面的T可以是char，int等任意类型

namespace jh 
{
	template <class T>
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;

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

capacity和size

capacity就是endofstorage到start之间的可存储元素个数 size就是finish到start之间的有效元素个数

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

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

pushback尾插函数

尾插函数在很多地方可以复用，所以我们首先解决了尾插，为后面的函数进行模拟实现提供了基础：插入首先就是要判断是否已满，所以我们先检查是否需要扩容，然后将当前finish位置的值置为x，finish的位置要往后移动一位

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

insert插入函数

同样的insert插入函数也需要复用，我们来解决它：我们首先做的就是断言，pos一定是要在start和finish的区间之内的当finish和endofstorage相等时就需要扩容，但是这里考虑到迭代器失效的问题我们就要记录pos和start原本之间的元素个数，然后再给start赋值最后用while循环移动元素，移动完成后将pos位置的值置为x，同时finish位置往后移动一位即可

void insert(iterator pos, const T& x)
{
	assert(pos <= _finish);
	assert(pos >= _start);
	if (_finish == _endofstorage)
	{
		size_t len = pos - _start;
		reserve(capacity() == 0 ? 4 : capacity() * 2);
		_start = pos + len;//考虑到扩容之后迭代器失效的问题，所以记录位置
	}
	iterator end = _finish - 1;
	while (end >= pos)
	{
		*(end + 1) = *(end);
		end--;
	}
	*pos = x;
	_finish++;
}

迭代器

迭代器是很常用的一个知识点，相信我们之前的学习中早已经熟悉了他的用法，很简单，但是我们需要对权限的放大有一个照顾，所以加上const

iterator begin()
{
	return _start;
}
iterator end()
{
	return _finish;
}
const_iterator begin()const
{
	return _start;
}
const_iterator end()const
{
	return _finish;
}

构造函数

构造函数主要用于初始化，他的作用很大也很常见，但是这里vector的构造函数可以用一个特殊的迭代器初始化

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

还可以以这种方式，T（）默认就是0，和上面一样，直接用pushback尾插进去，当然这里的T（）其实是C++的一个匿名函数，通常我们所说匿名对象的生命周期只有一行，但是用const修饰后的匿名对象的生命周期会延长！

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

拷贝构造函数

拷贝构造我们直接用for循环解决，然后调用pushback ，很简单的

vector(const vector<T>& v)
{
	reserve(v.capacity());
	for (auto e : v)
	{
		push_back(e);
	}
}

析构函数

析构函数直接重拳出击了属于是（狗头）用delete清空_start的空间，然后将其全部置为空

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

swap函数

swap函数其实我们的用处不大，我们直接复用std标准库里的swap：

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

赋值操作符函数重载

也很简单，我们偷点懒用直接复用swap函数：交换后返回*this即可

vector<T>& operator=(vector<T> tmp)
{
	swap(tmp);
	return *this;
}

下标访问符重载

直接返回start下标指定下标的值即可，当然前提是这里的pos是要小于size的

T& operator[](size_t pos)
		{
			assert(pos < size());

			return _start[pos];
		}

		const T& operator[](size_t pos) const
		{
			assert(pos < size());

			return _start[pos];
		}

resize函数和reserve函数

其实我们可以将reserve先实现后直接将reserve复用再resize上，直接扩容 reserve扩容时只有n是大于原本的capacity时才会扩容，向前几篇博客所说的，不会进行缩容，然后我们记录有效元素个数sz=size（提前记录好是因为后面会进行delete释放原本start空间的操作），如果start不为空，就将start中的元素按照深拷贝的方式用for循环放入提前开辟好的tmp空间里，然后将tmp给予start，finish依旧时start+size，但是endofstorage变成了start+n

void reserve(size_t n)
{
	if (n > capacity())
	{
		T* tmp = new T[n];
		size_t sz = size();
		if (_start)
		{
			for (size_t i = 0; i < sz; i++)
			{
				tmp[i] = _start[i];
			}
			delete[] _start;
		}
		_start = tmp;
		_finish = _start + sz;
		_endofstorage = _start + n;
	}
}

resize函数的扩容我们就用reserve来实现，但是resize可以会初始化：

void resize(size_t n, const T& val = T())
{
	if (n <= size())
	{
		_finish = _start + n;
	}
	else
	{
		reserve(n);
		while (_finish < _start+n)
		{
			*finish = val;
			finish++;
		}
	}
}

erase函数

这里有一个需要注意的点： erase会返回被删除元素的下一个元素的迭代器！ 断言我相信大家都是信手拈来了我们将pos位置后的元素往前移动一位即可！

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

好了，今天的分享到这里就结束了，感谢大家的支持！

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-01-22，如有侵权请联系 cloudcommunity@tencent.com 删除

函数