2022-08-13 10:36:11

vector接口总览

namespace nzb{//模拟实现vector
	template<class T>
	class vector{
	public:typedef T* iterator;typedefconst T* const_iterator;//默认成员函数vector();//构造函数vector(size_t n,const T& val);//构造函数
		template<class InputIterator>vector(InputIterator first, InputIterator last);//构造函数vector(const vector<T>& v);//拷贝构造函数
		vector<T>& operator=(const vector<T>& v);//赋值重载~vector();//析构函数//迭代器相关函数
		iteratorbegin();
		iteratorend();
		const_iteratorbegin()const;
		const_iteratorend()const;//容量相关函数size_tsize()const;size_tcapacity()const;voidreserve(size_t n);voidresize(size_t n,const T& val=T());
		boolempty()const;//修改容器相关函数voidpush_back(const T& x);voidpop_back();voidinsert(iterator pos,const T& x);
		iteratorerase(iterator pos);voidswap(vector<T>& v);//访问容器相关函数
		T& operator[](size_t i);const T& operator[](size_t i)const;

	private:
		iterator _start;//指向容器的头
		iterator _finish;//指向有效数据的尾
		iterator _endofstorage;//指向容器的尾};}

默认成员函数

构造函数

无参构造，将所有成员变量初始化为空指针即可

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

构造一个含有n个值为val的vector容器。
先将容器容量扩大到n，再尾插val

vector(size_t n,const T& val):_start(nullptr),_finish(nullptr),_endofstorage(nullptr){reserve(n);//扩容for(size_t i=0; i< n; i++)//尾插{push_back(val);}}

利用迭代器区间进行构造
因为迭代器区间可以是其他迭代器区间，所以我们要重新定义一块模板，再将迭代器中的数据尾插

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

拷贝构造

传统写法

先将容器容量扩大到n，再尾插原vector类中的数据（这里扩容和尾插调整了容器尾指针和数据尾指针，我们不必再次调整）

vector(const vector<T>& v):_start(nullptr),_finish(nullptr),_endofstorage(nullptr){reserve(v.capacity());for(constauto& e: v){push_back(e);}}

现代写法

利用迭代器构造一份vector类，再交换该类和拷贝构造的类

vector(const vector<T>& v):_start(nullptr),_finish(nullptr),_endofstorage(nullptr){
	vector<T>tmp(v.begin(), v.end());swap(tmp);}

赋值重载

传统写法

先初始化原来vector类的空间，再将数据拷贝过来

vector<T>& operator=(const vector<T>& v){if(this!=&v){
		delete[] _start;
		_start= _finish= _endofstorage= nullptr;reserve(v.capacity());for(constauto& e: v){push_back(e);}}return*this;}

现代写法

现代写法极为巧妙，利用传值的特性（出了函数立即销毁）传入vector类，再交换该类和拷贝构造的类达到赋值的效果

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

析构函数

释放开辟存储数据的空间，再将容器的各个成员变量置为空

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

迭代器相关函数

vector当中的迭代器实际上就是容器当中所存储数据类型的指针。

typedef T* iterator;typedefconst T* const_iterator;

begin和end

vector当中的begin函数返回容器的首地址，end函数返回容器当中有效数据的下一个数据的地址。

iteratorbegin(){return _start;}
iteratorend(){return _finish;}

我们还需写一份const版本，const版本只能读不能写，防止vector中数据被修改

const_iteratorbegin()const{return _start;}
const_iteratorend()const{return _finish;}

容量相关函数

size和capacity

size表示vector容器中已存储有效数据个数而capacity表示vector容器的最大容量，那如何得出该组数据呢？

我们知道vector成员函数_start,_finish,_endofstorage是指针，而指针减指针得到两个指针间的数据个数，我们可以用_finish-_start得到size,用_endofstorage-_start得到capacity

size_tsize()const{return _finish- _start;}size_tcapacity()const{return _endofstorage- _start;}

reserve

当n大于当前的capacity时，将capacity扩大到n或大于n。
当n小于当前capacity时什么也不做。

voidreserve(size_t n){if(n>capacity()){size_t sz=size();// 记录原容器中数据个数
		T* tmp= new T[n];// 开辟一块容量为n的空间if(_start)//判空{for(size_t i=0; i< sz; i++)// 拷贝数据{
				tmp[i]= _start[i];}
			delete[] _start;// 释放原容器中的数据}
		_start= tmp;// 调整指针
		_finish= _start+ sz; 
		_endofstorage= _start+ n;}}

注意：这里拷贝数据不能用memcpy。当我们拷贝的是一些简单的常量时是没有问题的，但是当我们拷贝的是另一个类，如string类时，拷贝的string还是指向原来string类指向的空间。当原来string被释放时，原string类指向的空间也被释放，此时拷贝的string类指向的是一块已被释放的空间，程序结束时它将再次被释放，释放一块已被释放的空间程序报错。
在这里插入图片描述

resize

当n大于当前的size时，将size扩大到n，扩大的数据为val，若val未给出，则默认为容器所存储类型的默认构造函数所构造出来的值。
当n小于当前的size时，将size缩小到n。

voidresize(size_t n,const T& val=T()){if(n<=size())// 当n小于当前的size时{
		_finish= n+ _start;// 将size缩小到n}else// 当n大于当前的size时{if(n>capacity())// 当n大于容量时，扩容{reserve(n);}while(_finish< _start+ n)// 给size到容器结尾赋值{*_finish= val;
			_finish++;}}}

这里用了匿名对象T（）来作为缺省参数

empty

通过比较_start和_finish指针来判断容器是否为空

boolempty()const{return _start== _finish;}

修改容器相关函数

push_back

先判断容器是否已满，如果满了先扩容再尾插，如果没满，直接尾插

voidpush_back(const T& x){if(_finish== _endofstorage)// 判断是否需要扩容{size_t newcapacity=capacity()==0?4:capacity()*2;reserve(newcapacity);}// 尾插数据*_finish= x;
	_finish++;}

pop_back

先判空处理，再–_finish

voidpop_back(){assert(!empty());// 判空--_finish;}

insert

功能：利用迭代器在指定位置插入数据。
实现方式：插入前判断是否需要扩容，再将指定位置后的数据往后挪动一位，把数据插入指定位置。

iteratorinsert(iterator pos,const T& x){assert(pos>= _start&&pos<= _finish);// 判断传入数据的合法性if(_finish== _endofstorage)// 扩容{size_t len= pos- _start;// 记录pos的位置size_t newcapacity=capacity()==0?4:capacity()*2;reserve(newcapacity);
		pos= _start+ len;}
	iterator end= _finish-1;while(end>= pos)// 挪动数据{*(end+1)=*end;--end;}*pos= x;// 插入数据
	_finish++;return pos;}

注意:扩容时要记录pos和_start的相对位置，避免扩容后迭代器失效问题

erase

功能：删除指定位置数据。
实现方式：先判断传入数据的合法性，在将pos位置后的数据全部往前挪动一位，覆盖掉原pos位置的数据

iteratorerase(iterator pos){assert(pos>= _start&&pos< _finish);// 判断传入数据的合法性
	iterator it= pos+1;// 利用迭代器记录pos的后一位while(it!= _finish)// 将pos后的数据往前挪动一位{*(it-1)=*it;
		it++;}
	_finish--;return pos;}

swap

功能：交换两个vector中的数据
实现方式：利用库函数中的swap进行交换

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

访问容器相关函数

operator[ ]

为了方便访问数据vector中也加入了“下标+[ ]”操作

T& operator[](size_t i)// 可读可写{assert(i<size());return _start[i];}const T& operator[](size_t i)const// 只能读{assert(i<size());return _start[i];}

C++vector的模拟实现

文章目录