C++ vector類的模擬實(shí)現(xiàn)方法
vector和string雖然底層都是通過順序表來實(shí)現(xiàn)的，但是他們利用順序表的方式不同，string是指定好了類型，通過使用順序表來存儲(chǔ)并對(duì)數(shù)據(jù)進(jìn)行操作，而vector是利用了C++中的泛型模板，可以存儲(chǔ)任何類型的數(shù)據(jù)，并且在vector中，并沒有什么有效字符和容量大小的說法，底層都是通過迭代器進(jìn)行操作的，迭代器底層實(shí)現(xiàn)也就是指針，所以說，vector是利用指針對(duì)任何順序表進(jìn)行操作的。
vector屬性
_start用于指向第一個(gè)有效元素_finish用于指向最后一個(gè)有效元素的下一個(gè)位置_endOfStorage用于指向已經(jīng)開辟了的空間的最后一個(gè)位置的下一個(gè)位置vector的迭代器是原生態(tài)T*迭代器
template<class T>
class Vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
private:
iterator _start;
iterator _finish;
iterator _endOfStorage;
};
構(gòu)造函數(shù)
- 無參默認(rèn)構(gòu)造函數(shù)，將所有屬性都置空
- 以n個(gè)val初始化的構(gòu)造函數(shù)，先開辟n個(gè)空間，再將這些空間的值都置為val，并更新_finish和_endOfStorage的位置
- 通過迭代器傳參初始化的構(gòu)造函數(shù)，使用新的迭代器，通過尾插將數(shù)據(jù)插入到新的空間
使用新的迭代器的原因是使傳入的迭代器可以是任意類型的，如果使用Vector的迭代器，那么傳入的迭代器的類型只能和Vector的類型一樣，這里拿string舉例，創(chuàng)建一個(gè)char類型的Vector，Vector，但是傳入的迭代器并不是char類型的，可以是字符數(shù)組的迭代器或者是string的迭代器。只要通過解引用是char類型就可以
//無參默認(rèn)構(gòu)造
Vector()
:_start(nullptr)
,_finish(nullptr)
,_endOfStorage(nullptr)
{}
//n個(gè)val的構(gòu)造函數(shù)
Vector(int n, const T& val = T())
:_start(new T[n])
,_finish(_start +n)
,_endOfStorage(_finish)
{
for (int i = 0; i < n; ++i)
{
_start[i] = val;
}
}
//通過迭代器產(chǎn)生的構(gòu)造函數(shù)
template<class InputIterator>
Vector(InputIterator first, InputIterator last)
:_start(nullptr)
, _finish(nullptr)
, _endOfStorage(nullptr)
{
while (first != last)
{
pushBack(*first);
++first;
}
}
運(yùn)行結(jié)果在begin() 和end()實(shí)現(xiàn)中
size()和capacity()
指針相減得到的值就是這兩個(gè)指針之間的元素個(gè)數(shù)
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _endOfStorage - _start;
}
pushBack()
- 檢查容量，如果_finish和_endOfStorage指針相等，說明容量已經(jīng)滿了，需要開辟更大的空間
- 在_finish位置插入新的數(shù)據(jù)
- 更新_finish
void pushBack(const T& val)
{
//檢查容量
if (_finish == _endOfStorage)
{
size_t newC = _endOfStorage == nullptr ? 1 : 2 * capacity();
reserve(newC);
}
//插入數(shù)據(jù)
*_finish = val;
//更新finish
++_finish
}
運(yùn)行結(jié)果在begin() 和end()實(shí)現(xiàn)中
reserve
- 檢查n的合理性，reserve只能擴(kuò)大不能縮小空間
- 保存有效元素的個(gè)數(shù)，用于后面更新_finish使用
- 申請(qǐng)空間并將數(shù)據(jù)拷貝到新的空間中，釋放舊的空
- 更新3個(gè)成員變量，注意_finish不能更新為_finish+size()，原因是size()是通過兩指針運(yùn)算得出來的，此時(shí)的_fiinsh已經(jīng)指向了釋放的空間，再去使用會(huì)出錯(cuò)，所以這也是有第二步的原因
以下代碼存在淺拷貝問題，文章末尾會(huì)給出正確深拷貝代碼和詳細(xì)解釋
void reserve(size_t n)
{
//reserve只能擴(kuò)大空間不能縮小空間
if (n > capacity())
{
//保存有效元素
size_t sz = size();
//申請(qǐng)空間
T* tmp = new T[n];
//將數(shù)據(jù)拷貝到新的空間
if (_start != nullptr)
{
//拷貝有效元素
memcpy(tmp, _start, sizeof(T) * size());
delete[] _start;
}
//更新
_start = tmp;
_finish = _start + sz;
_endOfStorage = _start + n;
}
}
運(yùn)行結(jié)果在begin() 和end()實(shí)現(xiàn)中
begin() 和end()
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
有了begin()和end就可以使用范圍for
template<class T>
void printVectorFor(Vector<T>& vec)
{
for (auto& e : vec)
{
cout << e;
}
cout << endl;
}
[]運(yùn)算符重載
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}
const T& operator[](size_t pos) const
{
assert(pos < size());
return _start[pos];
}
resize()
- n <= size 直接更新_finish的位置即可
- size < n <= capacity，從_finish開始補(bǔ)充元素，補(bǔ)充到_start+n的位置，然后執(zhí)行第一步
- n > capacity 增容，執(zhí)行第二和第一步
void resize(size_t n, const T& val = T())
{
//3.n >= capacity
if (n > capacity())
{
reserve(n);
}
//2.size < n <= capacity
if (n > size())
{
while (_finish != _start + n)
{
*_finish = val;
++_finish;
}
}
//1.n<=size
_finish = _start + n;
}
insert()
- 檢查插入的位置的有效性[_start, _finish)
- 檢查容量，由于增容會(huì)導(dǎo)致pos迭代器失效，所以我們可以先保存pos對(duì)于_start的偏移量
offset，增容后，再將pos重新賦值pos=_start+offset - 移動(dòng)元素，從后往前移動(dòng)，最后將pos位置的元素置為val
- 更新_finish
void insert(iterator pos, const T& val)
{
//檢查位置有效性
assert(pos >= _start || pos < _finish);
//檢查容量
if (_finish == _endOfStorage)
{
//增容會(huì)導(dǎo)致迭代器失效
//保存pos和_start的偏移量
size_t offset = pos - _start;
size_t newC = _endOfStorage == nullptr ? 1 : 2 * capacity();
reserve(newC);
//更新pos
pos = _start + offset;
}
//移動(dòng)元素
iterator end = _finish;
while (end != pos)
{
*end = *(end - 1);
--end;
}
//插入
*pos = val;
//更新
++_finish;
}
erase()
- 檢查位置有效性
- 移動(dòng)元素，從前向后移動(dòng)
- 更新_finish
iterator erase(iterator pos)
{
//檢查位置有效性
assert(pos >= _start || pos < _finish);
//移動(dòng)元素，從前往后
iterator start = pos + 1;
while (start != _finish)
{
*(start - 1) = *start;
++start;
}
//更新
--_finish;
}
void popBack()
利用erase接口進(jìn)行尾刪
void popBack()
{
if (size() > 0)
erase(end() - 1);
}
析構(gòu)函數(shù)
~Vector()
{
if (_start)
{
delete[] _start;
_start = _finish = _endOfStorage = nullptr;
}
}
算法庫中的find
頭文件<algorithm>
template <class InputIterator, class T> InputIterator find (InputIterator first, InputIterator last, const T& val)
參數(shù)內(nèi)容(從迭代器的begin起到end中，找到val值，找到返回該值所在的迭代器，找不到返回end)
reserve的深淺拷貝問題
當(dāng)我門使用自定義類型時(shí)，使用淺拷貝是效率最高的，但是當(dāng)我們使用自定義類型時(shí)，并且存在內(nèi)存資源的利用，就必須時(shí)刻注意存在的深淺拷貝問題。來看以下代碼測試
void test()
{
Vector<string> v;
string str1 = "123";
string str2 = "456";
string str3 = "789";
v.pushBack(str1);
v.pushBack(str2);
v.pushBack(str3);
}
調(diào)試結(jié)果：
當(dāng)我們?cè)诓迦氲谌齻€(gè)字符串時(shí)，就發(fā)生了內(nèi)存異常的問題，我們來看看到底是什么問題。
第一次插入str1，沒有問題
第二次插入str2，插入之前我們會(huì)擴(kuò)容，會(huì)創(chuàng)建2倍大的空間tmp，然后通過memcpy內(nèi)存拷貝(淺拷貝)將內(nèi)容拷貝到tmp中，此時(shí)就有兩個(gè)指向指向一個(gè)資源(123)，拷貝完后delete[]要?jiǎng)h除原有空間，將123釋放后，其實(shí)現(xiàn)在新的空間的第一個(gè)元素指向的是一個(gè)已經(jīng)釋放了的空間，但是問題并沒有暴露出來，第二個(gè)元素的插入也沒有問題
第三次str3的插入，這次插入也會(huì)進(jìn)行擴(kuò)容，會(huì)先開辟一個(gè)2倍大的空間tmp，然后通過memcpy內(nèi)存拷貝(淺拷貝)將內(nèi)容拷貝到tmp中，此時(shí)有兩個(gè)指針指向已經(jīng)釋放的資源（123），有兩個(gè)指針指向資源（456），當(dāng)拷貝完成后會(huì)釋放舊的空間，當(dāng)釋放原指針指向的（456）時(shí)不會(huì)報(bào)錯(cuò)，原因和第二次插入原因一樣。但是釋放原有空的第一個(gè)指針時(shí)，就會(huì)發(fā)生內(nèi)存報(bào)錯(cuò)異常，原因是資源（123）已經(jīng)被釋放了，如果再釋放就屬于二次釋放，是不安全的。內(nèi)存錯(cuò)誤就報(bào)異常。
所以我們?cè)跀U(kuò)容的時(shí)候不應(yīng)該只是單純的淺拷貝，也就是使用memcpy來拷貝內(nèi)容，我們應(yīng)該要使用深拷貝。將memcpy改為for (size_t i = 0; i < sz; ++i){tmp[i] = _start[i];}
整體代碼如下：
void reserve(size_t n)
{
//reserve只能擴(kuò)大空間不能縮小空間
if (n > capacity())
{
//保存有效元素
size_t sz = size();
//申請(qǐng)空間
T* tmp = new T[n];
//將數(shù)據(jù)拷貝到新的空間
if (_start != nullptr)
{
//拷貝有效元素
//memcpy(tmp, _start, sizeof(T) * size());
//深拷貝
for (size_t i = 0; i < sz; ++i)
{
//調(diào)用自定義類型的賦值運(yùn)算符重載函數(shù)，完成深拷貝
//前提是該重載函數(shù)也是深拷貝，string是STL庫中，是被深拷貝處理過
tmp[i] = _start[i];
}
delete[] _start;
}
//更新
_start = tmp;
_finish = _start + sz;
_endOfStorage = _start + n;
}
}
到此這篇關(guān)于C++ vector類的模擬實(shí)現(xiàn)方法的文章就介紹到這了,更多相關(guān)C++ vector類模擬內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)順序表的實(shí)現(xiàn)代碼，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-09-09
C語言編程中的聯(lián)合體union入門學(xué)習(xí)教程
這篇文章主要介紹了C語言編程中的聯(lián)合體union入門學(xué)習(xí)教程,也是C語言入門學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下2015-12-12
這篇文章主要介紹了C++模板template用法總結(jié) ，本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-03-03
這篇文章主要介紹了C/C++仿華容道小游戲的相關(guān)資料，模仿實(shí)現(xiàn)華容道游戲，感興趣的朋友可以參考一下2016-02-02
這篇文章主要介紹了C語言文件操作詳情，主要討論的是數(shù)據(jù)文件，通過處理的磁盤上的文件展開主題內(nèi)容介紹，需要的小伙伴可以參考一下，希望對(duì)你的學(xué)習(xí)有所幫助2022-04-04
深入理解:Java是類型安全的語言,而C++是非類型安全的語言
本篇文章是對(duì)Java是類型安全的語言,而C++是非類型安全的語言進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-06-06
C語言實(shí)現(xiàn)跨文件傳輸數(shù)據(jù)的幾種方式
C語言是一種強(qiáng)大的、通用的編程語言,常用于系統(tǒng)級(jí)編程,包括硬件交互,如中斷處理和數(shù)據(jù)采集,在本文中,我們將深入探討如何使用C語言進(jìn)行跨文件數(shù)據(jù)傳輸,文中有相關(guān)的代碼供大家參考,需要的朋友可以參考下2024-08-08
以下是對(duì)strncpy與snprintf的具體用法以及區(qū)別進(jìn)行了詳細(xì)的分析介紹，需要的朋友可以過來參考下2013-07-07
本文主要介紹了Qt菜單QMenu和菜單欄QMenuBar及自定義菜單用法，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-05-05
這篇文章主要介紹了全排列算法的原理和實(shí)現(xiàn)代碼,全排列是將一組數(shù)按一定順序進(jìn)行排列,如果這組數(shù)有n個(gè),那么全排列數(shù)為n!個(gè),需要的朋友可以參考下2014-08-08