(C++)vector模拟实现

2023-12-13 08:58:11

个人主页:Lei宝啊?

愿所有美好如期而遇


前言

我们模拟实现vector是为了更好的使用vector,大致了解他的成员函数是如何实现的,对我们的使用很有帮助。


我们先看private成员变量:

	private:
		T* _start = nullptr;
		T* _finish = nullptr;
		T* _end_of_storage = nullptr;

我们将来会开辟一段空间,然后用_start指向,而有效数据个数就是_finish - _start,空间大小就是_end_of_storage - _start。

同时我们public里typedef了迭代器

	public:
		typedef T* iterator;
		typedef const T* const_iterator;

		//无参构造函数
		vector(){};
		//拷贝构造函数
		vector(const vector<T>& v);
		//构造指定数量为n,值为v
		vector(int n, const T& v = T());
		//构造迭代器范围的值
		template<class InputIterator>
		vector(InputIterator first, InputIterator last);

挨个介绍思路:

拷贝构造函数:?开辟新空间,拷贝旧数据。

构造指定数量n,值为v:复用push_back,挨个尾插数据,因为刚开始尾插可能会频繁扩容,所以我们使用reserve提前扩容。

构造迭代器范围的值:仍然复用push_back,我们传的参全都是迭代器,目前string和vector迭代器都是使用原生指针,所以我们可以这样实现。

template<class T>
szl::vector<T>::vector(const vector<T>& v)
{
	_start = new T[v.capacity()];
	_finish = _start + v.size();
	_end_of_storage = _start + v.capacity();

	memcpy(_start, v._start, sizeof(T) * v.size());
}

template<class T>
szl::vector<T>::vector(int n, const T& v)
{
	reserve(n);
	for (int i = 0; i < n; i++)
	{
		push_back(v);
	}
}

template<class T>
template<class InputIterator>
szl::vector<T>::vector(InputIterator first, InputIterator last)
{
	while (first != last)
	{
		push_back(*first);
		first++;
	}
}

		//扩容
		void reserve(size_t n);

我们要实现的reserve不缩容,思路就是如果扩容的大小大于当前capacity,那么就开辟新空间,拷贝旧数据,释放旧空间。

我们下面使用old_size去接受size()返回的有效元素数量,多余吗?

不多余,size()函数我们定义在了类里,所以他是内联函数,展开后我们计算的finish可就成nullptr了,最后一用一个不吱声。

template<class T>
void szl::vector<T>::reserve(size_t n)
{
	if (n > capacity())
	{
		T* temp = _start;
		size_t old_size = size();

		_start = new T[n];
		_finish = _start + old_size;
		_end_of_storage = _start + n;

		if (temp)
		{
			memcpy(_start, temp, old_size * sizeof(T));
			delete[] temp;
		}		
	}
}

		//改变有效数据范围
		void resize(size_t n, const T& val = T());

思路,当n>capacity时,我们扩容,扩容操作已经更新了_finish和_end_of_storage,但是n可能会大于或者小于size(),所以我们下面仍然要更新_finish的位置,我们这个函数还要支持初始化,当改变有效元素数量超过原来的size(),那么超过部分我们需要初始化,初始化值默认为0。

template<class T>
void szl::vector<T>::resize(size_t n, const T& val)
{
	if (n > capacity())
	{
		reserve(n);		
	}		

	int old_size = size();
	_finish = _start + n;

	for (int i = old_size; i < size(); i++)
	{
		_start[i] = val;
	}
}

		//尾插
		void push_back(const T& v);

思路:

先判断空间是否已满,如果满了,就扩容,拷贝旧数据,删掉旧空间,然后在尾部插入数据,_finish++。

template<class T>
void szl::vector<T>::push_back(const T & v)
{
	if (_finish == _end_of_storage)
	{
		T* temp = _start;
		size_t n = size();

		size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
		_start = new T[newcapacity];

		memcpy(_start, temp, sizeof(T) * n);
		delete[] temp;

		_finish = _start + n;
		_end_of_storage = _start + newcapacity;
	}

	*_finish = v;
	_finish++;
}

	//尾删
	void pop_back()
	{
		assert(size() > 0);
		_finish--;
	}

?四个迭代器,一个size函数,一个capacity函数,不解释。?

		iterator begin()
		{
			return _start;
		}

		const_iterator begin() const 
		{
			return _start;
		}

		iterator end()
		{
			return _finish;
		}

		const_iterator end() const
		{
			return _finish;
		}

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

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

赋值运算符重载,我们的思路是传值,这样就会拷贝出一个vector<T>,我们交换两者的指针,然后临时的vector<T>析构,我们赋值完成。

		//vector内置交换函数
		void swap(vector<T>& v)
		{
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_end_of_storage, v._end_of_storage);
		}

		//赋值运算符重载
		vector<T>& operator=(vector<T> v)
		{
			swap(v);
			return *this;
		}

		//[]运算符重载
		T& operator[](size_t pos)
		{
			return _start[pos];
		}

		const T& operator[](size_t pos)const
		{
			return _start[pos];
		}

实现析构函数?

		//析构函数
		~vector()
		{
			if (_start)
			{
				delete[] _start;
				_start = _finish = _end_of_storage = nullptr;
			}		
		}

这里我们只模拟实现了第一个,在pos位置前插入一个值。

插入操作,首先判断插入位置是否合理,接着就是空间是否足够,不够则扩容,之后将pos位置及其后的值全部后移一位,在pos位置赋值val,_finish++。

template<class T>
void szl::vector<T>::insert(iterator pos, const T& val)
{
	assert(pos >= begin());
	assert(pos <= end());

	if (_finish == _end_of_storage)
	{
		reserve(capacity() == 0 ? 4 : capacity() * 2);
	}

	memmove(pos + 1, pos, sizeof(T) * (_finish - pos));
	*pos = val;
	_finish++;
}

这里我们仍然只模拟实现第一个。

template<class T>
void szl::vector<T>::erase(iterator pos)
{
	assert(pos >= begin());
	assert(pos < end());

	memmove(pos, pos + 1, sizeof(T) * (_finish - pos - 1));
	_finish--;
}

文章来源:https://blog.csdn.net/m0_74824254/article/details/134918008
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。