C++模擬實(shí)現(xiàn)vector流程詳解

第C++模擬實(shí)現(xiàn)vector流程詳解目錄模擬vector總結(jié)

模擬vector

我們可以通過模板實(shí)現(xiàn)類似vector的類。我們實(shí)現(xiàn)一個(gè)StrVecTemp類，其內(nèi)部通過allocator開辟空間，存儲(chǔ)的類型用T來(lái)表示，T是模板類型。

templatetypenameT

classStrVecTemp

public:

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

cap(nullptr){}

//拷貝構(gòu)造函數(shù)

StrVecTemp(constStrVecTemp

//拷貝賦值運(yùn)算符

StrVecTempoperator=(constStrVecTemp

//移動(dòng)構(gòu)造函數(shù)

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

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

//將源數(shù)據(jù)置空

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

templateclass...Args

voidemplace_back(Args...args);

//析構(gòu)函數(shù)

~StrVecTemp();

//拷貝元素

voidpush_back(constT

//拋出元素

voidpop_back(T

//返回元素個(gè)數(shù)

size_tsize()const{returnfirst_free-elements;}

//返回capacity返回容量

size_tcapacity()const{returncap-elements;}

//返回首元素的指針

T*begin()const

returnelements;

//返回第一個(gè)空閑元素指針

T*end()const

returnfirst_free;

private:

//判斷容量不足靠皮新空間

voidchk_n_alloc()

if(size()==capacity())

reallocate();

//重新開辟空間

voidreallocate();

//copy指定范圍的元素到新的內(nèi)存中

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

//釋放空間

voidfree();

//數(shù)組首元素的指針

T*elements;

//指向數(shù)組第一個(gè)空閑元素的指針

T*first_free;

//指向數(shù)組尾后位置的指針

T*cap;

//初始化alloc用來(lái)分配空間

staticstd::allocatorTalloc;

templatetypenameT

std::allocatorTStrVecTempT::alloc;

alloc在使用前要在類外初始化，因?yàn)槭悄０孱悾苑旁?h中初始化即可。

接下來(lái)我們要實(shí)現(xiàn)根據(jù)迭代器開始和結(jié)束的區(qū)間copy舊元素到新的空間里

//實(shí)現(xiàn)區(qū)間copy

templatetypenameT

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

autonewdata=alloc.allocate(e-b);

//用舊的數(shù)據(jù)初始化新的空間

autofirst_free=uninitialized_copy(b,e,newdata);

return{newdata,first_free};

實(shí)現(xiàn)copy構(gòu)造

//實(shí)現(xiàn)拷貝構(gòu)造函數(shù)

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;

實(shí)現(xiàn)copy賦值

//拷貝賦值運(yùn)算符

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;

析構(gòu)函數(shù)要先銷毀數(shù)據(jù)再回收內(nèi)存

//析構(gòu)函數(shù)

templateclassT

StrVecTempT::~StrVecTemp()

//判斷elements是否為空

if(elements==nullptr)

return;

//緩存第一個(gè)有效元素的地址

autodest=elements;

//循環(huán)析構(gòu)

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

//析構(gòu)每一個(gè)元素

alloc.destroy(dest++);

//再回收內(nèi)存

alloc.deallocate(elements,cap-elements);

elements=nullptr;

cap=nullptr;

first_free=nullptr;

}

重新開辟空間

templateclassT

voidStrVecTempT::reallocate()

T*newdata=nullptr;

//數(shù)組為空的情況

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

newdata=alloc.allocate(1);

elements=newdata;

first_free=newdata;

//cap指向數(shù)組尾元素的下一個(gè)位置

cap=newdata+1;

return;

//原數(shù)據(jù)不為空，則擴(kuò)充size兩倍大小

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

//新內(nèi)存空閑位置

autodest=newdata;

//就內(nèi)存的有效位置

autosrc=elements;

//通過移動(dòng)操作將舊數(shù)據(jù)放到新內(nèi)存中

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

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

//移動(dòng)完舊數(shù)據(jù)后一定要?jiǎng)h除

free();

//更新數(shù)據(jù)位置

elements=newdata;

first_free=dest;

cap=newdata+size()*2;

}

上面的函數(shù)用到了free函數(shù)，我們自己實(shí)現(xiàn)一個(gè)free

templatetypenameT

voidStrVecTempT::free()

//先判斷elements是否為空

if(elements==nullptr)

return;

autodest=elements;

//遍歷析構(gòu)每一個(gè)對(duì)象

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

//destroy會(huì)析構(gòu)每一個(gè)元素

alloc.destroy(dest++);

//再整體回收內(nèi)存

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

}

接下來(lái)要實(shí)現(xiàn)emplace_back，因?yàn)閑mplace_back支持多種構(gòu)造函數(shù)的參數(shù)，所以要用模板參數(shù)列表的方式定義該函數(shù)。

模板參數(shù)列表和形參列表都要用參數(shù)包的方式

templateclassT

templateclass...Args

voidStrVecTempT::emplace_back(Args...args)

chk_n_alloc();

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

}

Args是模板參數(shù)包，args是參數(shù)列表。因?yàn)閏onstruct的參數(shù)可能為右值引用，所以要用forward將原參數(shù)列表類型原樣轉(zhuǎn)發(fā)。

//forward既擴(kuò)展了模板參數(shù)包Args，