C++入門之vector的底層實現(xiàn)詳解
前言
上一小節(jié),我們講解了vector的使用,也大概了解了其創(chuàng)建對象,增刪改查數(shù)據(jù)等操作.那么今天,我們就來大致實現(xiàn)一下吧.
定義初始結(jié)構(gòu)
在標(biāo)準(zhǔn)C++中,vector同樣是一個模板,并且其底層實現(xiàn)用的是三個指針,然后利用這三個指針相互加減,達(dá)到存儲效果.
而vector和string類似,本質(zhì)是都是一個順序表.
template <class T>
class vector
{
public:
~vector()
{
delete _start;
_start = _finish = _end_of_storage = nullptr;
}
private:
T* _start; //順序表的頭
T* _finish; //順序表有效長度位置
T* _end_of_storage; //順序表末尾
};
聲明構(gòu)造函數(shù)
上一章節(jié)已經(jīng)講解,構(gòu)造函數(shù)比較多,這里只是為了簡單實現(xiàn),所以博主就實現(xiàn)一個最簡單的構(gòu)造函數(shù),即無參構(gòu)造.
vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr) {}
容量有關(guān)操作
獲取有效數(shù)據(jù)大小size()
想要獲取size,該怎么實現(xiàn)呢?我們在定義初始結(jié)構(gòu)的時候,已經(jīng)知道其底層是利用的三個指針,所以size等于_finish - _start.
size_t size() const //加const是保證const對象也可以用
{
return _finish - _start;
}
獲取數(shù)據(jù)容量capacity()
同樣的道理,capacity就應(yīng)是_end_of_storage - _start;
size_t capacity() //加const是保證const對象也可以用
{
return _end_of_storage - _start;
}
增加容量reserve()
我們在后面會實現(xiàn)一個接口,叫做push_back(),它的作用是把數(shù)據(jù)放進(jìn)vector,但如果空間不足了呢?這就需要我們的增容函數(shù)reserve了.
其參數(shù)是無符號整型n,代表要開n個空間
void reserve(size_t n)
{
if (n > capacity())
{
T* tmp = new T[n]; //先開辟一塊空間
size_t sz = size(); //保留原來的有效數(shù)據(jù)大小,且一定要先保存
if (_start) //一定要判斷這個,因為最開始_start為空,那么就只需要開空間
{
memcpy(tmp, _start, sizeof(T) * n); //把原來的數(shù)據(jù)拷貝進(jìn)新空間
delete _start; //釋放原來的空間
}
_start = tmp; //移交空間
_finish = _start + sz; //更新_finish
_end_of_storage = _start + n; //更新_end_of_storage
}
}
重置大小resize()
這個想必大家現(xiàn)在已經(jīng)比較習(xí)慣了吧?他有兩個參數(shù),會分情況討論是否大于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的時候說過,現(xiàn)階段我們就把迭代器當(dāng)做一個指針,**雖然指針一定是迭代器,但是迭代器不一定是指針.**但是目前階段我們用到的迭代器就是一個指針,因此這里便直接定義迭代器了
typedef T* iterator; //普通迭代器
typedef const T* const_iterator; //const迭代器
//因此返回首尾迭代器的接口,博主便一并寫下來
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()
該接口的實現(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()
實現(xiàn)該接口的操作一般是先檢查是否還存在數(shù)據(jù),然后size大小減一
void pop_back()
{
assert(size()>0);
_finish--;
}
某一位置插入 insert()
同樣的道理,一般先檢查容量是否充足,如果不夠,需要警惕迭代器失效問題,然后移動該位置及以后的所有數(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后位置開始,所有數(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);
}
}
[]訪問操作
上面我們實現(xiàn)了迭代器,但是vector還支持[]索引取值,博主這里便實現(xiàn)兩個[]重載吧
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;
}
特別注意!!!
在實現(xiàn)了上面的一系列操作以后,有沒有覺得我們已經(jīng)大功告成了?其實這里還隱藏著一個小小bug!.為什么呢?看下面'
int main()
{
//我們假設(shè)最開始創(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;
}
初一看,好像并沒有什么錯誤哎?但是一運(yùn)行就會發(fā)現(xiàn),當(dāng)插入第5個元素的時候,就報錯了.這是什么原因呢?
調(diào)試發(fā)現(xiàn),問題出在了reserve上面,因為push_back之前,會檢查容量,那么我們現(xiàn)在重新瞅瞅 reserve存在什么問題呢?
void reserve(size_t n)
{
if (n > capacity())
{
T* tmp = new T[n]; //先開辟一塊空間
size_t sz = size(); //保留原來的有效數(shù)據(jù)大小,且一定要先保存
if (_start) //一定要判斷這個,因為最開始_start為空,那么就只需要開空間
{
memcpy(tmp, _start, sizeof(T) * n); //把原來的數(shù)據(jù)拷貝進(jìn)新空間
delete _start; //釋放原來的空間
}
_start = tmp; //移交空間
_finish = _start + sz; //更新_finish
_end_of_storage = _start + n; //更新_end_of_storage
}
}
大家有發(fā)現(xiàn)什么問題了嗎?
沒錯,問題出現(xiàn)在memcpy上面,當(dāng)容量不足,reserve就會增加容量,然后把原來空間的內(nèi)容值拷貝到新空間.
但是原來空間的內(nèi)容也就只有三個指針呀,拷貝過去后,新空間和源空間都指向了同一塊空間,而我們又會釋放原空間.
所以,當(dāng)繼續(xù)尾插第5個元素時候,就報錯了,因為空間已經(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é)
本篇文章就到這里了，希望能夠給你帶來幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!
相關(guān)文章
C語言修煉之路悟徹數(shù)組真妙理?巧用下標(biāo)破萬敵下篇
在C語言和C++等語言中，數(shù)組元素全為指針變量的數(shù)組稱為指針數(shù)組，指針數(shù)組中的元素都必須具有相同的存儲類型、指向相同數(shù)據(jù)類型的指針變量。指針數(shù)組比較適合用來指向若干個字符串，使字符串處理更加方便、靈活2022-02-02
這篇文章主要為大家詳細(xì)介紹了如何利用C語言實現(xiàn)計算雙色球的中獎率，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2022-12-12
C++與QML進(jìn)行數(shù)據(jù)交互的常見方法總結(jié)
這篇文章主要為大家詳細(xì)介紹了C++與QML進(jìn)行數(shù)據(jù)交互的常見方法,文中 的示例代碼講解詳細(xì),具有一定的參考價值,有需要的小伙伴可以跟隨小編一起了解一下2023-10-10
見縫插針游戲就是使用鼠標(biāo)左鍵點擊發(fā)射針，當(dāng)兩個針的夾角小于一定限制時，游戲結(jié)束。本文將用C語言實現(xiàn)這一有趣游戲，感興趣的可以了解一下2022-11-11
QT編寫窗口插件實現(xiàn)調(diào)用窗口的自適應(yīng)
這篇文章主要為大家詳細(xì)介紹了QT編寫窗口插件實現(xiàn)調(diào)用窗口的自適應(yīng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-06-06
C語言進(jìn)階二叉樹的基礎(chǔ)與銷毀及層序遍歷詳解
朋友們好,這篇播客我們繼續(xù)C++的初階學(xué)習(xí)，現(xiàn)在對我們對C++的二叉樹基礎(chǔ)oj與二叉樹銷毀和層序遍歷進(jìn)行練習(xí)，讓我們相互學(xué)習(xí),共同進(jìn)步2022-06-06
C語言數(shù)據(jù)結(jié)構(gòu)之算法的時間復(fù)雜度
這篇文章主要介紹了C語言數(shù)據(jù)結(jié)構(gòu)之算法的時間復(fù)雜度，文章基于c語言的相關(guān)資料展開詳細(xì)介紹，具有一定的參價值，需要的小伙伴可以參考一下2022-05-05
這篇文章主要介紹了C語言求矩陣主對角線元素及副對角線元素之和實例,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-01-01
這篇文章主要介紹了C++迭代器失效問題及解決方案，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-02-02
C語言數(shù)據(jù)結(jié)構(gòu)之隊列算法詳解
這篇文章介紹了C語言數(shù)據(jù)結(jié)構(gòu)之隊列的算法，文中通過示例代碼介紹的非常詳細(xì)。對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-12-12