第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，