【C++STL精讲】vector的模拟实现

举报
花想云 发表于 2023/05/30 22:58:31 2023/05/30
【摘要】 本章我们将参照STL源码来模拟实现vector，这要求我们具备数据结构的基础且了解vector的基本使用。模式实现vector，将锻炼我们的代码能力，加深对类和对象的认识，同时能使我们对vector的使用更加游刃有余。

image.png

💐文章导读

本章我们将参照STL源码来模拟实现vector，这要求我们具备数据结构的基础且了解vector的基本使用。模式实现vector，将锻炼我们的代码能力，加深对类和对象的认识，同时能使我们对vector的使用更加游刃有余。

🌷定义vector类

为了区别于标准库中的vector，我们可以使用自己的命名空间，在自己的命名空间中模拟实现vector。我们已经了解过库中vector的基本使用，知道vector是一个可以存储任何类型的容器，为了实现各种类型都可以匹配，我们可以利用模板来实现。

STL源码中，vector包含三个基本成员：

  • iterator _start：指向首元素的迭代器；
  • iterator _finish：指向尾元素下一位的迭代器；
  • iterator _end_of_storage：指向最大容量的下一位的迭代器；

我们可以把迭代器理解为像指针一样的东西。

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

	private:
		iterator _start;
		iterator _finish;
		iterator _end_of_storage;
	};
}

🌷各成员函数的实现

🌺构造函数

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

🌺迭代器

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

	const_iterator end() const
	{
		return _finish;
	}

🌺size与capacity——求大小与容量

	size_t size() const
	{
		return _finish - _start; //指针相减即为个数
	}

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

🌺reserve——扩容

	void reserve(size_t n)
	{
		if (n > capacity())
		{
			size_t sz = size();
			//使用中间变量，防止new失败
			iterator tmp = new T[n];
			if (_start)
			{
				//转移数据
				for (size_t i = 0; i < sz; i++)
				{
					tmp[i] = _start[i];
				}
				//释放旧空间
				delete[] _start;
			}
			//指向新空间
			_start = tmp;
			_finish = _start + sz;
			_end_of_storage = _start + n;
		}
	}

关于reserve中的深浅拷贝问题

在reserve的实现中，我们不能使用memcpy来拷贝数据，否则会发生浅拷贝的问题，导致在析构报错。对于简单的内置类型或自定义类型，memcpy是一个不错的选择，既高效又实用。但是一旦元素涉及到资源申请，memcpy只是简单的将一个元素的值拷贝给另一个元素，并不会将该元素指向的空间的内容全部拷贝给另一个元素。所以，我们必须手动实现深拷贝。

🍁错误示例

	void reserve(size_t n)
	{
		if (n > capacity())
		{
			size_t sz = size();
			//使用中间变量，防止new失败
			iterator tmp = new T[n];
			if (_start)
			{
				//浅拷贝
				memcpy(tmp, _start, sizeof(T)*size());
				delete[] _start;
			}
			//指向新空间
			_start = tmp;
			_finish = _start + sz;
			_end_of_storage = _start + n;
		}
	}

🌺resize——扩容并初始化

	void resize(size_t n, T val = T())
	{
		//n<size()，删除数据
		if (n < size())
		{
			_finish = _start + n;
		}
		else
		{
			if (n > capacity)
				reserve(n); //扩容
			while (_finish != _start + n)
			{
				//初始化
				*_finish = val;
				++_finish;
			}
		}
	}

🌺push_back——尾插

	void push_back(const T& val)
	{
		//扩容
		if (_finish == _end_of_storage)
		{
			reserve(capacity() == 0 ? 4 : capacity() * 2);
		}
		//插入元素
		*_finish = val;
		++_finish;
	}

🌺pop_back——尾删

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

🌺insert——插入

	iterator insert(iterator pos,T val=T()) //使用匿名构造
	{
		assert(pos >= _start);
		assert(pos <= _finish);
		//扩容
		if (_finish == _end_of_storage)
		{
			size_t len = pos - _start;
			reserve(capacity() == 0 ? 4 : capacity() * 2);
			//扩容后更新pos的位置，解决pos失效的问题
			pos =_start + len;
		}
		//挪动数据
		iterator end = _finish-1;
		while (end >= pos)
		{
			*(end + 1) = *end;
			--end;
		}
		//插入元素
		*pos = val;
		++_finish;
		
		return pos;
	}

🌺erase——删除

	iterator erase(iterator pos)
	{
		assert(pos >= _start);
		assert(pos < _finish);
		//挪动数据
		iterator end = pos + 1;
		while (end != _finish)
		{
			*(end - 1) = *end;
			++end;
		}
		--_finish;
		return pos;
	}

🌺empty——判空

	bool empty()
	{
		return size() == 0;
	}

🌺[]重载——访问元素

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

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

🌺传值构造

	vector<int> v1(10, 5); //用10个5来构造

	vector(size_t n, const T& val = T())
		:_start(nullptr),
		_finish(nullptr),
		_end_of_storage(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),
		_end_of_storage(nullptr)
	{
		reserve(n);

		for (size_t i = 0; i < n; i++)
		{
			push_back(val);
		}
	}

🌺迭代器区间构造

	vector<int> v1(10, 5); 
	vector<string> v2(v1.begin(), v1.end()); //迭代器区间构造

	template<class InputIterator>
	vector(InputIterator begin, InputIterator end)
	{
		//扩容
		reserve(end - begin);
		while (begin != end)
		{
			push_back(*begin);
			++begin;
		}
	}

🌺赋值重载

	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;
	}

🌺拷贝构造

	vector(const vector<T>& v)
	{
		//写法1
		//_start = new T[v.capacity()];
		//for (size_t i = 0; i < v.size(); i++)
		//{
		//	_start[i] = v._start[i];
		//}

		//_finish = _start + v.size();
		//_end_of_storage = _start + v.capacity();

		//写法2
		vector<T> tmp(v.begin(), v.end());
		swap(tmp);
	}

拷贝构造中的深浅拷贝问题

在写法1中，如果使用memcpy，同样会发生浅拷贝的问题。

🍁错误示例

		vector(const vector<T>& v)
		{
			_start = new T[v.capacity()];
			//浅拷贝
			memcpy(_start, v._start, sizeof(T)*v.size());
			
			_finish = _start + v.size();
			_end_of_storage = _start + v.capacity();
		}

🌺析构函数

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

完整源码

#include<iostream>
#include<assert.h>
using namespace std;
namespace hxy
{
	template<class T>
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;

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

		vector(size_t n, const T& val = T())
			:_start(nullptr),
			_finish(nullptr),
			_end_of_storage(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),
			_end_of_storage(nullptr)
		{
			reserve(n);

			for (size_t i = 0; i < n; i++)
			{
				push_back(val);
			}
		}

		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;
		}

		vector(const vector<T>& v)
		{
			//写法1
			_start = new T[v.capacity()];
			for (size_t i = 0; i < v.size(); i++)
			{
				_start[i] = v._start[i];
			}

			_finish = _start + v.size();
			_end_of_storage = _start + v.capacity();

			////写法2
			//vector<T> tmp(v.begin(), v.end());
			//swap(tmp);
		}


		template<class InputIterator>
		vector(InputIterator begin, InputIterator end)
		{
			reserve(end - begin);
			while (begin != end)
			{
				push_back(*begin);
				++begin;
			}
		}
		
		~vector()
		{
			delete[] _start;
			_start = _finish = _end_of_storage = nullptr;
		}

		iterator begin()
		{
			return _start;
		}

		iterator end()
		{
			return _finish;
		}

		const_iterator begin() const
		{
			return _start;
		}

		const_iterator end() const
		{
			return _finish;
		}

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

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

		void reserve(size_t n)
		{
			if (n > capacity())
			{
				size_t sz = size();
				//使用中间变量，防止new失败
				iterator tmp = new T[n];
				if (_start)
				{
					//memcpy(tmp, _start, sizeof(T) * size());
					//转移数据
					for (size_t i = 0; i < sz; i++)
					{
						tmp[i] = _start[i];
					}
					//释放旧空间
					delete[] _start;
				}
				//指向新空间
				_start = tmp;
				_finish = _start + sz;
				_end_of_storage = _start + n;
			}
		}

		void resize(size_t n, T val = T())
		{
			//n<size()，删除数据
			if (n < size())
			{
				_finish = _start + n;
			}
			else
			{
				if (n > capacity)
					reserve(n); //扩容
				while (_finish != _start + n)
				{
					//初始化
					*_finish = val;
					++_finish;
				}
			}
		}
		void push_back(const T& val)
		{
			//扩容
			if (_finish == _end_of_storage)
			{
				reserve(capacity() == 0 ? 4 : capacity() * 2);
			}
			//插入元素
			*_finish = val;
			++_finish;
		}

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

		iterator insert(iterator pos,T val=T()) //使用匿名构造
		{
			assert(pos >= _start);
			assert(pos <= _finish);
			//扩容
			if (_finish == _end_of_storage)
			{
				size_t len = pos - _start;
				reserve(capacity() == 0 ? 4 : capacity() * 2);
				//扩容后更新pos的位置，解决pos失效的问题
				pos =_start + len;
			}
			//挪动数据
			iterator end = _finish-1;
			while (end >= pos)
			{
				*(end + 1) = *end;
				--end;
			}
			//插入元素
			*pos = val;
			++_finish;

			return pos;
		}

		iterator erase(iterator pos)
		{
			assert(pos >= _start);
			assert(pos < _finish);
			//挪动数据
			iterator end = pos + 1;
			while (end != _finish)
			{
				*(end - 1) = *end;
				++end;
			}
			--_finish;

			return pos;
		}

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

		const T& operator[](size_t pos) const
		{
			assert(pos < size());
			return _start[pos];
		}
		bool empty()
		{
			return size() == 0;
		}

	private:
		iterator _start;
		iterator _finish;
		iterator _end_of_storage;
	};
}
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱： cloudbbs@huaweicloud.com
C++
  • 点赞
  • 收藏
  • 关注作者

评论（0）

0/1000
抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认 取消

加入云驻计划，成为创作者

  • 华为云周边好礼
  • 免费体验产品
  • 特殊身份标识
  • 线下官方门票
  • 内部专家零距离
  • 与10000+优质创作者共同成长
立即加入