学习笔记（4月18日）vector底层模拟实现（1）

对编程一片赤诚的小吴

发布于 2024-04-20 10:05:33

630

发布于 2024-04-20 10:05:33

文章被收录于专栏：热爱编程的证据热爱编程的证据

1.迭代器

vector实际上是由迭代器进行维护的，关于迭代器是什么，为什么要叫这个名字，后面的学习会逐渐了解，现在先将迭代器是作为指针即可。

vector底层有三个迭代器，用来起到容量、数组头、元素个数的作用。

同时为了实现方便存储各种类型的vector，vector要写成类模板。

template<class T>
class vector
{
public:
	typedef T* iterator;
	typedef const T* const_iterator;
iterator begin()
{
	return _start;
}
iterator end()
{
	return _finsh;
}
const_iterator begin() const
{
	return _start;
}

const_iterator end() const
{
	return _finsh;
}
private:
	iterator _start = nullptr;
	iterator _finsh = nullptr;
	iterator _endofstorage = nullptr;
};

2.push_back

尾插一个元素，和顺序表一样，也要考虑扩容问题，由此也可以直接写一个reserve来进行扩容。

reserve

和顺序表判断容量满了的条件不一样，要利用迭代器来进行判断，_endofstorage来表示数组最大容量的所在位置，而_finsh表示数组最后一个元素的下一个位置，当_finsh等于_endofstorage时就意味着容量满了，此时就要扩容。

而扩容也不是在原数组上面进行操作，C++没有提供扩容的函数，所以只能另开一块空间来进行拷贝，而这里就会涉及到一个关于迭代器失效的问题。

迭代器失效

什么是迭代器失效，用容易理解的话来解释就是迭代器所指向的位置没有用了，甚至越界起不到调用数据的效果了就叫迭代器失效。

在扩容后，我们会用一个新指针来指向新开辟的空间，之后再赋给_start，但此时_finsh和_endofstorage也要进行操作，因为它们原来指向的地方被回收了，如果不修改的话会造成对野指针的解引用，因此要进行相应的修改。

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

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

void reserve(size_t n)
{
	if (n > capacity())
	{
		T* tmp = new T[n];
		size_t oldsize = size();
		memcpy(tmp, _start, sizeof(T) * size());


		delete[] _start;
		_start = tmp;
		_finsh = tmp + oldsize;
		_endofstorage = tmp + n;
	}
}

完成扩容操作后我们就可以进行尾插了

void push_back(const T& val)
{

	if (_finsh == _endofstorage)
	{
		reserve(capacity() == 0 ? 4 : capacity() * 2);
	}
	*_finsh = val;
	_finsh++;
}

3.遍历

1.迭代器

vector提供了通过迭代器来访问每一个数组中的元素，而我们就可以利用范围for去遍历整个数组，因为范围for底层调用的也是迭代器。

2.下标方括号重载

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

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

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

vector

本文分享自作者个人站点/博客?前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与?腾讯云自媒体分享计划? ，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度