前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >C++:Vector的模拟实现

C++:Vector的模拟实现

作者头像
小陈在拼命
发布2024-03-08 09:30:47
730
发布2024-03-08 09:30:47
举报

一,前言 

       在学习string类的时候,我们可能会发现遍历的话下标访问特别香,比迭代器用的舒服,但是下标其实只能是支持连续的空间,他的使用是非常具有局限性的,随着STL学习的深入我们会发现其实迭代器才是大佬!!Vector虽然也支持下标访问,但是很多成员函数都是用的迭代器,所以我们要模拟实现的话迭代器十分重要,vs使用的是PJ版的STL版本,比较难懂,所以我们模拟实现统一用SGI版本去实现,所以在模拟实现之前,我们要去看看他的源码到底有哪些成员变量

       SGI下的vector有三个成员变量,通过观察其他源码可以大致推断  _start是指向起始位置,_finish是指向有效数据的下一个位置(迭代器都遵循左闭右开),end_of_storage是指向有效容量的最后一个位置。

     通过这个我们可以观察到SGI版本下的迭代器其实就是一个原生指针,value_type*类型相当于是模板T对应的指针类型,有了这些大致了解,我们就可以去模拟实现啦!!

二,vector的模拟实现

大致框架需要有模板(类外定义)/迭代器以及迭代器的获取(public定义,要有可读可写的也要有可读不可写的)/成员变量(private定义)  并且为了不和库的vector冲突,我们需要自己搞一个命名空间

代码语言:javascript
复制
namespace cyx
{
//模板
template<class T>
//迭代器(可读可写)
class vector
{
public:
typedef T* iterator;

iterator begin()
{
	return _start;
}

iterator end()
{
	return _finish;
}
//迭代器(可读不可写)
typedef const T* const_iterator;

const_iterator begin() const
{
	return _start;
}

const_iterator end() const
{
	return _finish;
}
private:
//成员变量
iterator _start;
iterator _finish;
iterator _end_of_storage;
}
}

然后我们开始实现!! 

2.1 构造函数和析构函数

2.1.1 无参构造函数
代码语言:javascript
复制
	//无参构造函数
	vector()
		:_start(nullptr)
		,_finish(nullptr)
		,_end_of_storage(nullptr)
	{}
2.1.2 迭代器区间构造
代码语言:javascript
复制
//传别人的迭代器进行构造
template<class InputIterator>
vector(InputIterator first, InputIterator last)
	:_start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{
     //这里传的是别人的迭代器,不知道会传多少数据,不能提前扩容,只能让pushback的时候去判断
	while (first != last)
	{
		push_back(*first);
		++first;
	}
}

 push_back是尾插数据,具体实现后面会写。

思考:为什么迭代器也要搞个类模板呢?

        答:本质上是为了让这个函数更加灵活,可以传不同类型的迭代器来帮助我们初始化!!

比如这个地方我们传string类的迭代器

 传vector类的迭代器

 2.1.3 有参构造函数(对n个存储的类型去调用他们的构造)
代码语言:javascript
复制
//有参构造函数(对n个存储的类型去调用他们的构造)
vector(size_t n,const T&val=T() )
	:_start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{
	reserve(n);//因为我们知道会进多少数据,所以可以提前开空间
	for (int i = 0; i < n; ++i)
		push_back(val);
}

reserve是扩容到n,具体实现后面会写。

思考:

1.缺省值T( )是什么意思

      答:这个地方的缺省值不能给0!!因为vector可能会存储内置类型,也可能会存储自定义类型,比如vector<string>,所以如果我们没给值,缺省值就要给他的默认无参构造函数,这个默认构造函数可以使用匿名对象。

2.const T&val=T()  T()不是用一次就析构吗,为什么可以用引用

答:T()是一个用一次就析构的匿名对象,其实本质上是因为他没有名字,用T引用val可以充当他的名字,此时用val就相当于用这个匿名对象,所以匿名对象的生命周期被延长到和val一样,但是由于匿名对象是一个临时变量,所以具有常性,所以必须用const修饰的val才可以当他的别名,否则会出现权限放大!!

3.非法的间接寻址是为什么?

如下图我传(10,5),会出非法间接寻址

 但是我传(10u,5)就可以正常使用了,为什么会这样??

答:

根据上图写出一个重载的有参构造

代码语言:javascript
复制
//重载一个防止间接寻址
vector(int n, const T val = T())
	:_start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{
	reserve(n);//因为我们知道会进多少数据,所以可以提前开空间
	for (int i = 0; i < n; ++i)
		push_back(val);
}
 2.1.4 拷贝构造+memcpy拷贝问题+赋值重载

 但是真的有这么顺利吗??

思考:

为什么存string类就会崩了??    这就涉及到memcpy的拷贝问题

 我们以上述问题来画图解释一下

总结:

1. memcpy是内存的二进制格式拷贝,将一段内存空间中内容原封不动的拷贝到另外一段内存空间中 2. 如果拷贝的是自定义类型的元素,memcpy既高效又不会出错,但如果拷贝的是自定义类型元素,并且自定义类型元素中涉及到资源管理时,就会出错,因为memcpy的拷贝实际是浅拷贝。  如果对象中涉及到资源管理时,千万不能使用memcpy进行对象之间的拷贝,因为memcpy是 浅拷贝,否则可能会引起内存泄漏甚至程序崩溃。

所以在这个地方我们的拷贝构造不能用memcpy

代码语言:javascript
复制
//拷贝构造(传统)
vector(const vector<T>& v)
	:_start(nullptr)
	,_finish(nullptr)
	,_end_of_storage(nullptr)
{
	_start = new T[v.capacity()];
	//memcpy(_start, v._start, sizeof(T)*v.size());  不能用memcpy 是浅拷贝
	for (int i = 0; i < v.size(); ++i)
		_start[i] = v._start[i];//实现重载运算符
	_finish = _start + v.size();
	_end_of_storage = _start + v.capacity();
}

 但是真的没有问题了吗??看看这个

 但道理来说得打印出9个1  结果呢??

 原因是什么呢,我们先看看resize函数

代码语言:javascript
复制
//重载赋值=(传统)
vector<T>& operator=(const vector<T> &v)
{
	T* temp = new T [v.capacity()];
	for(int i=0;i<v.size();++i)
		temp[i] = v[i];
	delete[]_start;
	_start = temp;
	_finish = _start +v.size();
	_end_of_storage = _start +v.capacity();
	return *this;
}
 2.1.5 拷贝构造和赋值重载的现代写法

先写个swap函数

代码语言:javascript
复制
//交换
void swap(vector<T>& v)
{
	std::swap(_start, v._start);
	std::swap(_finish, v._finish);
	std::swap(_end_of_storage, v._end_of_storage);
}

        拷贝构造的现代写法思路:创建一个临时对象利用被拷贝对象的迭代器区间构造,然后再swap一下就可以了!

代码语言:javascript
复制
	vector(const vector<T>& v)
		:_start(nullptr)
		, _finish(nullptr)
		, _end_of_storage(nullptr)
	{
		vector<T> temp(v.begin(), v.end());//让临时对象借助迭代器区间构造出来
		swap(temp);//窃取革命成果
	}

       赋值重载的现代写法的思路:反正我自己的空间也不要了,被赋值对象传值过来(这样被赋值对象不会被修改),然后直接和临时对象swap就可以了!!

代码语言:javascript
复制
vector<T>& operator=(vector<T> v)
{
	swap(v);//反正我原来的空间也要销毁,我跟你传值过来的v直接交换,而且不会改变你
	return *this;
}
2.1.6 析构函数 
代码语言:javascript
复制
~vector()
{
	/*if (_start)*///delete 会自动检查空指针  没必要
	delete[] _start;
	_start = _finish = _end_of_storage = nullptr;
}

注意:delete空指针是没关系的,delete会自己判断     delete出问题一般都是野指针

2.1.7 构造函数相关的全部代码

 我们发现大部分都设计要到初始化为nullptr,c11后是支持直接在成员变量那边给缺省值的,所以们可以美化一下

全部代码

代码语言:javascript
复制
		//无参构造函数
		vector()
		{}
		//有参构造函数(对n个存储的类型去调用他们的构造)
		vector(size_t n, const T& val = T())
		{
			reserve(n);//因为我们知道会进多少数据,所以可以提前开空间
			for (int i = 0; i < n; ++i)
				push_back(val);
		}
		//重载一个防止间接寻址
		vector(int n, const T val = T())
		{
			reserve(n);//因为我们知道会进多少数据,所以可以提前开空间
			for (int i = 0; i < n; ++i)
				push_back(val);
		}
		//传别人的迭代器区间进行构造
		template<class InputIterator>
		vector(InputIterator first, InputIterator last)
		{
			//这里传的是别人的迭代器,不知道会传多少数据,不能提前扩容,只能让pushback的时候去判断
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}
		//拷贝构造(传统写法)
		vector(const vector<T>& v)
		{
			_start = new T[v.capacity()];
			//memcpy(_start, v._start, sizeof(T)*v.size());  不能用memcpy 是浅拷贝
			for (size_t i = 0; i < v.size(); ++i)
				_start[i] = v._start[i];//实现重载运算符
			_finish = _start + v.size();
			_end_of_storage = _start + v.capacity();
		}
		//拷贝构造(现代写法)
		//vector(const vector<T>& v)
		//{
		//	vector<T> temp(v.begin(), v.end());//让临时对象借助迭代器区间构造出来
		//	swap(temp);//窃取革命成果
		//}
		//交换
		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=(const vector<T>& v)
		{
			T* temp = new T[v.capacity()];
			for (int i = 0; i < v.size(); ++i)
				temp[i] = v[i];
			delete[]_start;
			_start = temp;
			_finish = _start + v.size();
			_end_of_storage = _start + v.capacity();
			return *this;
		}
		//赋值重载现代写法
		//vector<T>& operator=(vector<T> v)
		//{
		//	swap(v);//反正我原来的空间也要销毁,我跟你传值过来的v直接交换,而且不会改变你
		//	return *this;
		//}
		//析构函数
		~vector()
		{
			/*if (_start)*///delete 会自动检查空指针  没必要检查
			delete[] _start;
			_start = _finish = _end_of_storage = nullptr;
		}

 2.2 常见接口

2.2.1 获取size和capacity
代码语言:javascript
复制
//获取size
size_t size() const
{
	return _finish - _start;
}
//获取capacoty
size_t capacity() const
{
	return _end_of_storage - _start;
}
 2.2.2 判空
代码语言:javascript
复制
		//判空
		bool empty() const
		{
			return _start == _finish;
		}
2.2.3 重载[ ]

1.可读可写[ ]

代码语言:javascript
复制
	//重载[](可读可写)
	T& operator[](size_t pos)
	{
		assert(pos < size());
		return _start[pos];
	}

2.可读不可写[]

代码语言:javascript
复制
	//重载[](可读不可写)
	const T& operator[](size_t pos) const
	{
		assert(pos < size());
		return _start[pos];
	}

3.三种访问方法

下标

代码语言:javascript
复制
//下标遍历
for (int i = 0; i < v1.size(); ++i)
	cout << v1[i] << " ";
cout << endl;

迭代器

代码语言:javascript
复制
	//迭代器遍历
	vector<int>::const_iterator it = v1.begin();
	while (it != v1.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

范围for 

代码语言:javascript
复制
//范围for遍历
for (auto e : v1)
	cout << e << " ";
cout << endl;

v1.resize(100);
cout << v1.size() << endl;

for (auto e : v1)
	cout << e << " ";
cout << endl;
 2.2.4 提前扩容
代码语言:javascript
复制
void reserve(size_t n)
{
	size_t sz = size();//防止丢失
	if (n > capacity())
	{
		T* temp = new T[n];
		if (_start)//如果为空,就不需要拷贝也不需要释放
		{
			for (size_t i = 0; i < sz; ++i)
				temp[i] = _start[i];
			delete[] _start;
		}
		_start = temp;
		_finish = _start + sz;
		_end_of_storage = _start + n;
	}
}

 考虑到之前的memcpy拷贝问题,这里不能用memcpy了!!

还要注意的是要提前记录size(),否则原空间销毁了就找不到了。

2.2.5 提前扩容+初始化

有三种情况,第一种是给的n比原来的size小,第二种是n比size大但是比capacity小,第三种是n比capacity大,这个时候需要扩容

代码语言:javascript
复制
	//提前扩容+初始化
	void resize(size_t n, T val = T())
	{
		//给小
		if (n < size())
			_finish = _start + n;
		//给大
		else
		{
			//容量不够就扩
			if (n > capacity())
				reserve(n);
			while (_finish != _start + n)
			{
				*_finish = val;
				++_finish;
			}
		}
	}
2.2.6 尾插和尾删
代码语言:javascript
复制
void push_back(const T& val)
{
	if (_finish == _end_of_storage)
		reserve(capacity() == 0 ? 4 : 2 * capacity());
	*_finish = val;
	++_finish;
}
//尾删
void pop_back()
{
	//防止没有元素可删
	assert(!empty());
	--_finish;
}

 尾插要注意扩容之前要判断一下,因为如果是0的话怎么扩都是0

我们会发现这次的指定位置插入删除不像string那样用size_t pos 而是iterator pos

2.2.7 指定位置插入

 这样写有什么问题吗??

看似好像没有什么问题,但是如果把pushback(5)去掉

 为什么会这样呢?

原因就是扩容后空间变了,但是pos还是指向原来的空间!!

所以我们解决方案就是pos在扩容的时候要更新一下

代码语言:javascript
复制
iterator insert(iterator pos, const T& val)
{
	assert(pos >= _start);
	assert(pos <= _finish);
	if (_finish == _end_of_storage)
	{
		size_t len = pos - _start;//记录相对距离,方便更新pos
		reserve(capacity() == 0 ? 4 : 2 * capacity());
		pos = _start + len;
	}
	iterator end = _finish - 1;
	while (end >= pos)
	{
		*(end + 1) = *end;
		--end;
	}
	*pos = val;
	++_finish;
	return pos;
}
2.2.8 指定位置删除

返回值是pos的下一个位置 

代码语言:javascript
复制
	iterator erase(iterator pos)
	{
		assert(pos >= _start);
		assert(pos < _finish);
		iterator start = pos + 1;
		while (start != _finish)
		{
			*(start - 1) = *start;
			++start;
		}
		--_finish;
		return pos;
	}

2.3 迭代器失效问题

会引起其底层空间改变的操作,都有可能使得迭代器失效。

 比如:resize、reserve、insert、erase、 push_back等。

2.3.1.insert的失效

就是因为扩容导致pos失效,我们需要去及时更新pos

      但是我们传的pos是值传递,所以我们更新的后pos更新,我们在后面解引用pos就会出现经典的解引用野指针问题。

 那我们怎么传回pos呢??就得用返回值!!这也是为什么insert的返回值用iterator的原因,我们想继续用的话就得去接收一下返回值,就可以了

 虽然有了返回值,我们可以去接收更新后的pos,但是一旦我们使用了任意一个可能扩容的函数,都会到时pos的失效,从而有可能回引发野指针问题,这个问题是不太好避免的,所以我们认为迭代器只能用一次,因为结果不可预测!

2.3.2 erase的失效

erase 删除 pos 位置元素后,pos 位置之后的元素会往前搬移,没有导致底层空间的改变,理论上讲迭代器不应该会失效,但是:如果 pos 刚好是最后一个元素,删完之后 pos 刚好是 end 的位置,而 end 位置是没有元素的,那么 pos 就失效了。因此删除 vector 中任意位置上元素时,vs 就认为该位置迭代器失效了。

vs和g++对比

 结果是未定义的!!不同编译器场景可能不同,严格来说vs更严谨 

思考:

假设没有强制检查(比如我们自己写的vector),想删除删除 vector 中所有偶数

 但是如果只有4个

为什么会这样呢,我们画图分析

   从这边我们也能看到为什么erase返回值也要用iterator的原因,我们想继续用的话就得去接收一下返回值

2.3.3 扩容导致的失效

可能本来还能用,但是中间扩容过,所以也不能用了

用pos前用一样reserve,也会失效

总而言之:尽量不要复用pos迭代器,因为任何一个可能扩容的操作都会导致失效

2.4 比较不常用的接口

2.4.1 清理元素
代码语言:javascript
复制
	void clear() const
	{
		_finish = _start;
	}
2.4.2 缩容
代码语言:javascript
复制
void shrink_to_fit()
{
	size_t sz = size();//记录
	T* temp = new T[sz];
	for (size_t i = 0; i < sz; ++i)
		temp[i] = _start[i];
	delete _start;
	_start = temp;
	_finish = _start + sz;
	_end_of_storage = _start + sz;
}

2.5 反向迭代器 

这里博主直接上代码,等list模拟实现的时候再放在一起分析

1、利用正向迭代器去封装反向迭代器

代码语言:javascript
复制
//反向迭代器的封装
template<class iterator, class Ref>
struct ReverseIterator
{
	typedef ReverseIterator<iterator, Ref>  Self;//Ref单纯是为了控制解引用的时候是否可以被写

	//利用反向迭代器的类来封装正向迭代器,同时在类里面设置反向迭代器的行为
	ReverseIterator(iterator it)
		:_cur(it)
	{}

	Ref operator*()
	{
		iterator temp = _cur;
		--temp;
		return *temp;
	}

	Self& operator++()
	{
		--_cur;
		return *this;
	}

	Self operator++(int)
	{
		iterator temp = _cur;
		--_cur;
		return temp;
	}

	Self& operator--()
	{
		++_cur;
		return *this;
	}

	Self operator--(int)
	{
		iterator temp = _cur;
		++_cur;
		return temp;
	}

	Self operator+(int n)
	{
		iterator temp = _cur;
		temp-=n;
		return temp;
	}

	Self operator-(int n)
	{
		iterator temp = _cur;
		temp+= n;
		return temp;
	}

	bool operator!=(const Self& s)
	{
		return _cur != s._cur;
	}

	bool operator==(const Self& s)
	{
		return _cur == s._cur;
	}

	//成员变量
	iterator _cur;
};

2、rebegin和rend

代码语言:javascript
复制
//反向迭代器(可读可写)
reverse_iterator rbegin()
{
	return reverse_iterator(end());
}

reverse_iterator rend()
{
	return reverse_iterator(begin());
}
//反向迭代器(可读不可写)
const_reverse_iterator rbegin() const
{
	return const_reverse_iterator(end());
}

const_reverse_iterator rend() const
{
	return const_reverse_iterator(begin());
}

三,vector实现的全部代码

代码语言:javascript
复制
using namespace std;
namespace cyx
{
	//反向迭代器的封装
	template<class iterator, class Ref>
	struct ReverseIterator
	{
		typedef ReverseIterator<iterator, Ref>  Self;//Ref单纯是为了控制解引用的时候是否可以被写

		//利用反向迭代器的类来封装正向迭代器,同时在类里面设置反向迭代器的行为
		ReverseIterator(iterator it)
			:_cur(it)
		{}

		Ref operator*()
		{
			iterator temp = _cur;
			--temp;
			return *temp;
		}

		Self& operator++()
		{
			--_cur;
			return *this;
		}

		Self operator++(int)
		{
			iterator temp = _cur;
			--_cur;
			return temp;
		}

		Self& operator--()
		{
			++_cur;
			return *this;
		}

		Self operator--(int)
		{
			iterator temp = _cur;
			++_cur;
			return temp;
		}

		Self operator+(int n)
		{
			iterator temp = _cur;
			temp-=n;
			return temp;
		}

		Self operator-(int n)
		{
			iterator temp = _cur;
			temp+= n;
			return temp;
		}

		bool operator!=(const Self& s)
		{
			return _cur != s._cur;
		}

		bool operator==(const Self& s)
		{
			return _cur == s._cur;
		}

		//成员变量
		iterator _cur;
	};



	template<class T>
	class vector
	{
	public:
		//正向迭代器
		typedef T* iterator;
		typedef const T* const_iterator;
		//反向迭代器
		typedef ReverseIterator<iterator, T&> reverse_iterator;
		typedef ReverseIterator<iterator, const T&> const_reverse_iterator;
		//正向迭代器(可读可写)
		iterator begin()
		{
			return _start;
		}

		iterator end()
		{
			return _finish;
		}
		//正向迭代器(可读不可写)
		iterator begin() const
		{
			return _start;
		}
		iterator end() const
		{
			return _finish;
		}
		//反向迭代器(可读可写)
		reverse_iterator rbegin()
		{
			return reverse_iterator(end());
		}

		reverse_iterator rend()
		{
			return reverse_iterator(begin());
		}
		//反向迭代器(可读不可写)
		const_reverse_iterator rbegin() const
		{
			return const_reverse_iterator(end());
		}

		const_reverse_iterator rend() const
		{
			return const_reverse_iterator(begin());
		}
		//无参构造函数
		vector()
		{}
		//有参构造函数(对n个存储的类型去调用他们的构造)
		vector(size_t n, const T& val = T())
		{
			reserve(n);//因为我们知道会进多少数据,所以可以提前开空间
			for (int i = 0; i < n; ++i)
				push_back(val);
		}
		//重载一个防止间接寻址
		vector(int n, const T val = T())
		{
			reserve(n);//因为我们知道会进多少数据,所以可以提前开空间
			for (int i = 0; i < n; ++i)
				push_back(val);
		}
		//传别人的迭代器进行构造
		template<class InputIterator>
		vector(InputIterator first, InputIterator last)
		{
			//这里传的是别人的迭代器,不知道会传多少数据,不能提前扩容,只能让pushback的时候去判断
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}
		//拷贝构造(传统写法)
		vector(const vector<T>& v)
		{
			_start = new T[v.capacity()];
			//memcpy(_start, v._start, sizeof(T)*v.size());  不能用memcpy 是浅拷贝
			for (size_t i = 0; i < v.size(); ++i)
				_start[i] = v._start[i];//实现重载运算符 完成深拷贝
			_finish = _start + v.size();
			_end_of_storage = _start + v.capacity();
		}
		//拷贝构造(现代写法)
		//vector(const vector<T>& v)
		//{
		//	vector<T> temp(v.begin(), v.end());//让临时对象借助迭代器区间构造出来
		//	swap(temp);//窃取革命成果
		//}
		//交换
		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=(const vector<T>& v)
		{
			T* temp = new T[v.capacity()];
			for (int i = 0; i < v.size(); ++i)
				temp[i] = v[i];
			delete[]_start;
			_start = temp;
			_finish = _start + v.size();
			_end_of_storage = _start + v.capacity();
			return *this;
		}
		//赋值重载现代写法
		//vector<T>& operator=(vector<T> v)
		//{
		//	swap(v);//反正我原来的空间也要销毁,我跟你传值过来的v直接交换,而且不会改变你
		//	return *this;
		//}
		//析构函数
		~vector()
		{
			/*if (_start)*///delete 会自动检查空指针
			delete[] _start;
			_start = _finish = _end_of_storage = nullptr;
		}
		//获取size
		size_t size() const
		{
			return _finish - _start;
		}
		//获取capacoty
		size_t capacity() const
		{
			return _end_of_storage - _start;
		}
		//判空
		bool empty() const
		{
			return _start == _finish;
		}
		//重载[](可读可写)
		T& operator[](size_t pos)
		{
			assert(pos < size());
			return _start[pos];
		}
		//重载[](可读不可写)
		const T& operator[](size_t pos) const
		{
			assert(pos < size());
			return _start[pos];
		}
		//提前扩容+初始化
		void resize(size_t n, T val = T())
		{
			//给小
			if (n < size())
				_finish = _start + n;
			//给大
			else
			{
				//容量不够就扩
				if (n > capacity())
					reserve(n);
				while (_finish != _start + n)
				{
					*_finish = val;
					++_finish;
				}
			}
		}
		//提前扩容
		void reserve(size_t n)
		{
			size_t sz = size();//防止丢失
			if (n > capacity())
			{
				T* temp = new T[n];
				if (_start)//如果为空,就不需要拷贝也不需要释放
				{
					for (size_t i = 0; i < sz; ++i)
						temp[i] = _start[i];
					delete[] _start;
				}
				_start = temp;
				_finish = _start + sz;
				_end_of_storage = _start + n;
			}
		}
		//尾插
		void push_back(const T& val)
		{
			if (_finish == _end_of_storage)
				reserve(capacity() == 0 ? 4 : 2 * capacity());
			*_finish = val;
			++_finish;
		}
		//尾删
		void pop_back()
		{
			//防止没有元素可删
			assert(!empty());
			--_finish;
		}
		//指定位置插入
		iterator insert(iterator pos, const T& val)
		{
			assert(pos >= _start);
			assert(pos <= _finish);
			if (_finish == _end_of_storage)
			{
				size_t len = pos - _start;
				reserve(capacity() == 0 ? 4 : 2 * capacity());
				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 start = pos + 1;
			while (start != _finish)
			{
				*(start - 1) = *start;
				++start;
			}
			--_finish;
			return pos;
		}
		//清理元素
		void clear() const
		{
			_finish = _start;
		}
		//缩容
		void shrink_to_fit()
		{
			size_t sz = size();//记录
			T* temp = new T[sz];
			for (size_t i = 0; i < sz; ++i)
				temp[i] = _start[i];
			delete _start;
			_start = temp;
			_finish = _start + sz;
			_end_of_storage = _start + sz;
		}
	private:
		iterator _start= nullptr;
		iterator _finish= nullptr;
		iterator _end_of_storage= nullptr;
	};

有什么不懂得可以问博主哦!后面有时间再来细化接口

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2024-03-07,如有侵权请联系 cloudcommunity@tencent.com 删除

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

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

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一,前言 
  • 二,vector的模拟实现
    • 2.1 构造函数和析构函数
      • 2.1.1 无参构造函数
      • 2.1.2 迭代器区间构造
      •  2.1.3 有参构造函数(对n个存储的类型去调用他们的构造)
      •  2.1.4 拷贝构造+memcpy拷贝问题+赋值重载
      •  2.1.5 拷贝构造和赋值重载的现代写法
      • 2.1.6 析构函数 
      • 2.1.7 构造函数相关的全部代码
    •  2.2 常见接口
      • 2.2.1 获取size和capacity
      •  2.2.2 判空
      • 2.2.3 重载[ ]
      •  2.2.4 提前扩容
      • 2.2.5 提前扩容+初始化
      • 2.2.6 尾插和尾删
      • 2.2.7 指定位置插入
      • 2.2.8 指定位置删除
    • 2.3 迭代器失效问题
      • 2.3.1.insert的失效
      • 2.3.2 erase的失效
      • 2.3.3 扩容导致的失效
    • 2.4 比较不常用的接口
      • 2.4.1 清理元素
      • 2.4.2 缩容
    • 2.5 反向迭代器 
      • 1、利用正向迭代器去封装反向迭代器
        • 2、rebegin和rend
          • 三,vector实现的全部代码
          领券
          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档