C++入門之vector的底層實(shí)現(xiàn)詳解
前言
上一小節(jié),我們講解了vector的使用,也大概了解了其創(chuàng)建對(duì)象,增刪改查數(shù)據(jù)等操作.那么今天,我們就來(lái)大致實(shí)現(xiàn)一下吧.
定義初始結(jié)構(gòu)
在標(biāo)準(zhǔn)C++中,vector同樣是一個(gè)模板,并且其底層實(shí)現(xiàn)用的是三個(gè)指針,然后利用這三個(gè)指針相互加減,達(dá)到存儲(chǔ)效果.
而vector和string類似,本質(zhì)是都是一個(gè)順序表.
template <class T>
class vector
{
public:
~vector()
{
delete _start;
_start = _finish = _end_of_storage = nullptr;
}
private:
T* _start; //順序表的頭
T* _finish; //順序表有效長(zhǎng)度位置
T* _end_of_storage; //順序表末尾
};
聲明構(gòu)造函數(shù)
上一章節(jié)已經(jīng)講解,構(gòu)造函數(shù)比較多,這里只是為了簡(jiǎn)單實(shí)現(xiàn),所以博主就實(shí)現(xiàn)一個(gè)最簡(jiǎn)單的構(gòu)造函數(shù),即無(wú)參構(gòu)造.
vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr) {}
容量有關(guān)操作
獲取有效數(shù)據(jù)大小size()
想要獲取size,該怎么實(shí)現(xiàn)呢?我們?cè)诙x初始結(jié)構(gòu)的時(shí)候,已經(jīng)知道其底層是利用的三個(gè)指針,所以size等于_finish - _start.
size_t size() const //加const是保證const對(duì)象也可以用
{
return _finish - _start;
}
獲取數(shù)據(jù)容量capacity()
同樣的道理,capacity就應(yīng)是_end_of_storage - _start;
size_t capacity() //加const是保證const對(duì)象也可以用
{
return _end_of_storage - _start;
}
增加容量reserve()
我們?cè)诤竺鏁?huì)實(shí)現(xiàn)一個(gè)接口,叫做push_back(),它的作用是把數(shù)據(jù)放進(jìn)vector,但如果空間不足了呢?這就需要我們的增容函數(shù)reserve了.
其參數(shù)是無(wú)符號(hào)整型n,代表要開(kāi)n個(gè)空間
void reserve(size_t n)
{
if (n > capacity())
{
T* tmp = new T[n]; //先開(kāi)辟一塊空間
size_t sz = size(); //保留原來(lái)的有效數(shù)據(jù)大小,且一定要先保存
if (_start) //一定要判斷這個(gè),因?yàn)樽铋_(kāi)始_start為空,那么就只需要開(kāi)空間
{
memcpy(tmp, _start, sizeof(T) * n); //把原來(lái)的數(shù)據(jù)拷貝進(jìn)新空間
delete _start; //釋放原來(lái)的空間
}
_start = tmp; //移交空間
_finish = _start + sz; //更新_finish
_end_of_storage = _start + n; //更新_end_of_storage
}
}
重置大小resize()
這個(gè)想必大家現(xiàn)在已經(jīng)比較習(xí)慣了吧?他有兩個(gè)參數(shù),會(huì)分情況討論是否大于size()而進(jìn)行參數(shù)賦值.
void resize(size_t n,const T& val = T())
{
if(n>capacity()) reserve(n);
for(size_t i = size();i<n;i++)
{
_start[i] = val;
}
_finish = _start + n;
}
迭代器
前面講解string的時(shí)候說(shuō)過(guò),現(xiàn)階段我們就把迭代器當(dāng)做一個(gè)指針,**雖然指針一定是迭代器,但是迭代器不一定是指針.**但是目前階段我們用到的迭代器就是一個(gè)指針,因此這里便直接定義迭代器了
typedef T* iterator; //普通迭代器
typedef const T* const_iterator; //const迭代器
//因此返回首尾迭代器的接口,博主便一并寫下來(lái)
iterator begin() {return _start;}
iterator end() {return _finish;} //普通接口
const_iterator begin() const {return _start;}
const_iterator end() const {return _finish;} //const接口
數(shù)據(jù)操作
尾插push_back()
該接口的實(shí)現(xiàn)操作一般是先檢查容量是否充足,然后把數(shù)據(jù)放進(jìn)去,最后size大小加一.
void push_back(const T& val)
{
if(size() == capacity())
{
size_t newcapacity = size()==0?4:capacity()*2; //需要考慮到size是否有可能為0的情況
reserve(newcapacity);
}
*_finish = val;
_finish++;
}
尾刪pop_back()
實(shí)現(xiàn)該接口的操作一般是先檢查是否還存在數(shù)據(jù),然后size大小減一
void pop_back()
{
assert(size()>0);
_finish--;
}
某一位置插入 insert()
同樣的道理,一般先檢查容量是否充足,如果不夠,需要警惕迭代器失效問(wèn)題,然后移動(dòng)該位置及以后的所有數(shù)據(jù),最后插入數(shù)據(jù).
官方文檔定義其返回值為新插入數(shù)據(jù)的位置
iterator insert(iterator pos,const T& val)
{
assert(pos>=_start && pos <= _finish);
if(_finish == _end_of_storage)
{
int n = pos - _start;
size_t newcapacity = 0 ? 4 :capacity()*2;
pos = _start + n; //防止pos迭代器失效
}
iterator cur = end();
while(cur > pos)
{
*cur = *(cur-1);
cur--;
}
*pos = val;
_finish++;
return pos;
}
某一位置刪除 erase()
該接口的操作一般是從pos后位置開(kāi)始,所有數(shù)據(jù)前挪一單位.但是在挪之前,需要檢查是否還存在數(shù)據(jù)
官方文檔定義其返回值為刪除數(shù)據(jù)的下一位置
iterator erase(iterator pos)
{
assert(pos >= _start && pos < _finish);
iterator it = pos + 1;
while (it != _finish)
{
*(it-1) = *it;
++it;
}
--_finish;
return pos;
}
拷貝構(gòu)造
vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{
reserve(v.capacity());
for (const auto& e : v)
{
push_back(e);
}
}
[]訪問(wèn)操作
上面我們實(shí)現(xiàn)了迭代器,但是vector還支持[]索引取值,博主這里便實(shí)現(xiàn)兩個(gè)[]重載吧
T& operator[](size_t i)
{
assert(i < size());
return _start[i];
}
const T& operator[](size_t i) const
{
assert(i < size());
return _start[i];
}
=賦值操作
vector<T>& operator=(vector<T> v) //注意哦~,我這里故意寫的傳值參數(shù),而不是引用,是為了下面進(jìn)行交換
{
swap(*this,v);
return *this;
}
特別注意!!!
在實(shí)現(xiàn)了上面的一系列操作以后,有沒(méi)有覺(jué)得我們已經(jīng)大功告成了?其實(shí)這里還隱藏著一個(gè)小小bug!.為什么呢?看下面'
int main()
{
//我們假設(shè)最開(kāi)始創(chuàng)建的vector的容量是4
vector<string> vc;
vc.push_back("123"); //創(chuàng)建vc,并給其賦值
vc.push_back("234");
vc.push_back("345");
vc.push_back("456");
vc.push_back("567");
return 0;
}
初一看,好像并沒(méi)有什么錯(cuò)誤哎?但是一運(yùn)行就會(huì)發(fā)現(xiàn),當(dāng)插入第5個(gè)元素的時(shí)候,就報(bào)錯(cuò)了.這是什么原因呢?
調(diào)試發(fā)現(xiàn),問(wèn)題出在了reserve上面,因?yàn)閜ush_back之前,會(huì)檢查容量,那么我們現(xiàn)在重新瞅瞅 reserve存在什么問(wèn)題呢?
void reserve(size_t n)
{
if (n > capacity())
{
T* tmp = new T[n]; //先開(kāi)辟一塊空間
size_t sz = size(); //保留原來(lái)的有效數(shù)據(jù)大小,且一定要先保存
if (_start) //一定要判斷這個(gè),因?yàn)樽铋_(kāi)始_start為空,那么就只需要開(kāi)空間
{
memcpy(tmp, _start, sizeof(T) * n); //把原來(lái)的數(shù)據(jù)拷貝進(jìn)新空間
delete _start; //釋放原來(lái)的空間
}
_start = tmp; //移交空間
_finish = _start + sz; //更新_finish
_end_of_storage = _start + n; //更新_end_of_storage
}
}
大家有發(fā)現(xiàn)什么問(wèn)題了嗎?
沒(méi)錯(cuò),問(wèn)題出現(xiàn)在memcpy上面,當(dāng)容量不足,reserve就會(huì)增加容量,然后把原來(lái)空間的內(nèi)容值拷貝到新空間.
但是原來(lái)空間的內(nèi)容也就只有三個(gè)指針呀,拷貝過(guò)去后,新空間和源空間都指向了同一塊空間,而我們又會(huì)釋放原空間.
所以,當(dāng)繼續(xù)尾插第5個(gè)元素時(shí)候,就報(bào)錯(cuò)了,因?yàn)榭臻g已經(jīng)不存在了!!!,被釋放了.
那怎么解決呢?這里便只能用循環(huán),把string值賦給新空間了.
void reserve(size_t n)
{
if (n > capacity())
{
size_t sz = size();
T* tmp = new T[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;
}
總結(jié)
本篇文章就到這里了，希望能夠給你帶來(lái)幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!
相關(guān)文章
這篇文章主要介紹了拷貝構(gòu)造函數(shù)防篡改示例,需要的朋友可以參考下2014-04-04
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)雙人五子棋游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-06-06
這篇文章主要為大家詳細(xì)介紹了OpenGL通過(guò)中點(diǎn)法繪制直線和圓，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-02-02
本文主要介紹了C++通信器的示例代碼，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2022-11-11
C++LeetCode數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)詳解
關(guān)于C++中0是十進(jìn)制還是八進(jìn)制的問(wèn)題
C++程序自動(dòng)重啟的實(shí)現(xiàn)代碼
基于C++內(nèi)存分配、函數(shù)調(diào)用與返回值的深入分析
