C++模拟实现vector流程详解

第C++模拟实现vector流程详解目录模拟vector总结

模拟vector

我们可以通过模板实现类似vector的类。我们实现一个StrVecTemp类，其内部通过allocator开辟空间，存储的类型用T来表示，T是模板类型。

templatetypenameT

classStrVecTemp

public:

StrVecTemp():elements(nullptr),first_free(nullptr),

cap(nullptr){}

//拷贝构造函数

StrVecTemp(constStrVecTemp

//拷贝赋值运算符

StrVecTempoperator=(constStrVecTemp

//移动构造函数

StrVecTemp(StrVecTempsrc)noexcept:elements(src.elements),

first_free(src.first_free),cap(src.cap)

//将源数据置空

src.elements=src.first_free=src.cap=nullptr;

templateclass...Args

voidemplace_back(Args...args);

//析构函数

~StrVecTemp();

//拷贝元素

voidpush_back(constT

//抛出元素

voidpop_back(T

//返回元素个数

size_tsize()const{returnfirst_free-elements;}

//返回capacity返回容量

size_tcapacity()const{returncap-elements;}

//返回首元素的指针

T*begin()const

returnelements;

//返回第一个空闲元素指针

T*end()const

returnfirst_free;

private:

//判断容量不足靠皮新空间

voidchk_n_alloc()

if(size()==capacity())

reallocate();

//重新开辟空间

voidreallocate();

//copy指定范围的元素到新的内存中

std::pairT*,T*alloc_n_copy(constT*,constT*);

//释放空间

voidfree();

//数组首元素的指针

T*elements;

//指向数组第一个空闲元素的指针

T*first_free;

//指向数组尾后位置的指针

T*cap;

//初始化alloc用来分配空间

staticstd::allocatorTalloc;

templatetypenameT

std::allocatorTStrVecTempT::alloc;

alloc在使用前要在类外初始化，因为是模板类，所以放在.h中初始化即可。

接下来我们要实现根据迭代器开始和结束的区间copy旧元素到新的空间里

//实现区间copy

templatetypenameT

std::pairT*,T*StrVecTempT::alloc_n_copy(constT*b,constT*e)

autonewdata=alloc.allocate(e-b);

//用旧的数据初始化新的空间

autofirst_free=uninitialized_copy(b,e,newdata);

return{newdata,first_free};

实现copy构造

//实现拷贝构造函数

templateclassT

StrVecTempT::StrVecTemp(constStrVecTempstrVec)

autorsp=alloc_n_copy(strVec.begin(),strVec.end());

//利用pair类型更新elements,cap,first_free

elements=rsp.first;

first_free=rsp.second;

cap=rsp.second;

实现copy赋值

//拷贝赋值运算符

templateclassT

StrVecTempTStrVecTempT::operator=(constStrVecTempstrVec)

if(this==strVec)

return*this;

//如果不是自赋值，就将形参copy给自己

autorsp=alloc_n_copy(strVec.begin(),strVec.end());

elements=rsp.first;

first_free=rsp.second;

cap=rsp.second;

析构函数要先销毁数据再回收内存

//析构函数

templateclassT

StrVecTempT::~StrVecTemp()

//判断elements是否为空

if(elements==nullptr)

return;

//缓存第一个有效元素的地址

autodest=elements;

//循环析构

for(size_ti=0;isize();i++)

//析构每一个元素

alloc.destroy(dest++);

//再回收内存

alloc.deallocate(elements,cap-elements);

elements=nullptr;

cap=nullptr;

first_free=nullptr;

}

重新开辟空间

templateclassT

voidStrVecTempT::reallocate()

T*newdata=nullptr;

//数组为空的情况

if(elements==nullptr||cap==nullptr||first_free==nullptr)

newdata=alloc.allocate(1);

elements=newdata;

first_free=newdata;

//cap指向数组尾元素的下一个位置

cap=newdata+1;

return;

//原数据不为空，则扩充size两倍大小

newdata=alloc.allocate(size()*2);

//新内存空闲位置

autodest=newdata;

//就内存的有效位置

autosrc=elements;

//通过移动操作将旧数据放到新内存中

for(size_ti=0;i!=size();++i)

alloc.construct(dest++,std::move(*src++));

//移动完旧数据后一定要删除

free();

//更新数据位置

elements=newdata;

first_free=dest;

cap=newdata+size()*2;

}

上面的函数用到了free函数，我们自己实现一个free

templatetypenameT

voidStrVecTempT::free()

//先判断elements是否为空

if(elements==nullptr)

return;

autodest=elements;

//遍历析构每一个对象

for(size_ti=0;isize();i++)

//destroy会析构每一个元素

alloc.destroy(dest++);

//再整体回收内存

alloc.deallocate(elements,cap-elements);

elements=nullptr;

cap=nullptr;

first_free=nullptr;

}

压入元素和弹出元素

//拷贝元素

templateclassT

voidStrVecTempT::push_back(constTt)

chk_n_alloc();

alloc.construct(first_free++,t);

//抛出元素

templateclassT

voidStrVecTempT::pop_back(Ts)

//先判断是否为空

if(first_free==nullptr)

return;

//判断size为1

if(size()==1)

s=*elements;

alloc.destroy(elements);

first_free=nullptr;

elements=nullptr;

return;

s=*(--first_free);

alloc.destroy(first_free);

}

接下来要实现emplace_back，因为emplace_back支持多种构造函数的参数，所以要用模板参数列表的方式定义该函数。

模板参数列表和形参列表都要用参数包的方式

templateclassT

templateclass...Args

voidStrVecTempT::emplace_back(Args...args)

chk_n_alloc();

alloc.construct(first_free++,forwardArgs(args)...);

}

Args是模板参数包，args是参数列表。因为construct的参数可能为右值引用，所以要用forward将原参数列表类型原样转发。

//forward既扩展了模板参数包Args，