溫馨提示×
您好，登錄后才能下訂單哦！
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶(hù)服務(wù)條款》
您好，登錄后才能下訂單哦！
這篇文章給大家分享的是有關(guān)C++中如何模擬實(shí)現(xiàn)vector的內(nèi)容。小編覺(jué)得挺實(shí)用的，因此分享給大家做個(gè)參考，一起跟隨小編過(guò)來(lái)看看吧。
namespace nzb
{
//模擬實(shí)現(xiàn)vector
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
//默認(rèn)成員函數(shù)
vector(); //構(gòu)造函數(shù)
vector(size_t n, const T& val); //構(gòu)造函數(shù)
template<class InputIterator>
vector(InputIterator first, InputIterator last); //構(gòu)造函數(shù)
vector(const vector<T>& v); //拷貝構(gòu)造函數(shù)
vector<T>& operator=(const vector<T>& v); //賦值重載
~vector(); //析構(gòu)函數(shù)
//迭代器相關(guān)函數(shù)
iterator begin();
iterator end();
const_iterator begin()const;
const_iterator end()const;
//容量相關(guān)函數(shù)
size_t size()const;
size_t capacity()const;
void reserve(size_t n);
void resize(size_t n, const T& val = T());
bool empty()const;
//修改容器相關(guān)函數(shù)
void push_back(const T& x);
void pop_back();
void insert(iterator pos, const T& x);
iterator erase(iterator pos);
void swap(vector<T>& v);
//訪(fǎng)問(wèn)容器相關(guān)函數(shù)
T& operator[](size_t i);
const T& operator[](size_t i)const;
private:
iterator _start; //指向容器的頭
iterator _finish; //指向有效數(shù)據(jù)的尾
iterator _endofstorage; //指向容器的尾
};
}1、無(wú)參構(gòu)造，將所有成員變量初始化為空指針即可
vector()
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{}2、構(gòu)造一個(gè)含有n個(gè)值為val的vector容器。
先將容器容量擴(kuò)大到n，再尾插val
vector(size_t n, const T& val)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
reserve(n); //擴(kuò)容
for (size_t i = 0; i < n; i++) //尾插
{
push_back(val);
}
}3、利用迭代器區(qū)間進(jìn)行構(gòu)造
因?yàn)榈鲄^(qū)間可以是其他迭代器區(qū)間，所以我們要重新定義一塊模板，再將迭代器中的數(shù)據(jù)尾插
template <class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
while (first != last)
{
push_back(*first);
first++;
}
}傳統(tǒng)寫(xiě)法
先將容器容量擴(kuò)大到n，再尾插原vector類(lèi)中的數(shù)據(jù)（這里擴(kuò)容和尾插調(diào)整了容器尾指針和數(shù)據(jù)尾指針，我們不必再次調(diào)整）
vector(const vector<T>& v)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
reserve(v.capacity());
for (const auto& e : v)
{
push_back(e);
}
}現(xiàn)代寫(xiě)法
利用迭代器構(gòu)造一份vector類(lèi)，再交換該類(lèi)和拷貝構(gòu)造的類(lèi)
vector(const vector<T>& v)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
vector<T> tmp(v.begin(), v.end());
swap(tmp);
}傳統(tǒng)寫(xiě)法
先初始化原來(lái)vector類(lèi)的空間，再將數(shù)據(jù)拷貝過(guò)來(lái)
vector<T>& operator=(const vector<T>& v)
{
if (this != &v)
{
delete[] _start;
_start = _finish = _endofstorage = nullptr;
reserve(v.capacity());
for (const auto& e : v)
{
push_back(e);
}
}
return *this;
}現(xiàn)代寫(xiě)法
現(xiàn)代寫(xiě)法極為巧妙，利用傳值的特性（出了函數(shù)立即銷(xiāo)毀）傳入vector類(lèi)，再交換該類(lèi)和拷貝構(gòu)造的類(lèi)達(dá)到賦值的效果
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}釋放開(kāi)辟存儲(chǔ)數(shù)據(jù)的空間，再將容器的各個(gè)成員變量置為空
~vector()
{
delete[] _start;
_start = _finish = _endofstorage = nullptr;
}vector當(dāng)中的迭代器實(shí)際上就是容器當(dāng)中所存儲(chǔ)數(shù)據(jù)類(lèi)型的指針。
typedef T* iterator; typedef const T* const_iterator;
vector當(dāng)中的begin函數(shù)返回容器的首地址，end函數(shù)返回容器當(dāng)中有效數(shù)據(jù)的下一個(gè)數(shù)據(jù)的地址。
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}我們還需寫(xiě)一份const版本，const版本只能讀不能寫(xiě)，防止vector中數(shù)據(jù)被修改
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}size表示vector容器中已存儲(chǔ)有效數(shù)據(jù)個(gè)數(shù)而capacity表示vector容器的最大容量，那如何得出該組數(shù)據(jù)呢？
我們知道vector成員函數(shù)_start,_finish,_endofstorage是指針，而指針減指針得到兩個(gè)指針間的數(shù)據(jù)個(gè)數(shù)，我們可以用_finish-_start得到size,用_endofstorage-_start得到capacity
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _endofstorage - _start;
}當(dāng)n大于當(dāng)前的capacity時(shí)，將capacity擴(kuò)大到n或大于n。
當(dāng)n小于當(dāng)前capacity時(shí)什么也不做。
void reserve(size_t n)
{
if (n > capacity())
{
size_t sz = size(); // 記錄原容器中數(shù)據(jù)個(gè)數(shù)
T* tmp = new T[n]; // 開(kāi)辟一塊容量為n的空間
if (_start) //判空
{
for (size_t i = 0; i < sz; i++) // 拷貝數(shù)據(jù)
{
tmp[i] = _start[i];
}
delete[] _start; // 釋放原容器中的數(shù)據(jù)
}
_start = tmp; // 調(diào)整指針
_finish = _start + sz;
_endofstorage = _start + n;
}
}注意：這里拷貝數(shù)據(jù)不能用memcpy。當(dāng)我們拷貝的是一些簡(jiǎn)單的常量時(shí)是沒(méi)有問(wèn)題的，但是當(dāng)我們拷貝的是另一個(gè)類(lèi)，如string類(lèi)時(shí)，拷貝的string還是指向原來(lái)string類(lèi)指向的空間。當(dāng)原來(lái)string被釋放時(shí)，原string類(lèi)指向的空間也被釋放，此時(shí)拷貝的string類(lèi)指向的是一塊已被釋放的空間，程序結(jié)束時(shí)它將再次被釋放，釋放一塊已被釋放的空間程序報(bào)錯(cuò)。
當(dāng)n大于當(dāng)前的size時(shí)，將size擴(kuò)大到n，擴(kuò)大的數(shù)據(jù)為val，若val未給出，則默認(rèn)為容器所存儲(chǔ)類(lèi)型的默認(rèn)構(gòu)造函數(shù)所構(gòu)造出來(lái)的值。
當(dāng)n小于當(dāng)前的size時(shí)，將size縮小到n。
void resize(size_t n, const T& val = T())
{
if (n <= size())// 當(dāng)n小于當(dāng)前的size時(shí)
{
_finish = n + _start;// 將size縮小到n
}
else // 當(dāng)n大于當(dāng)前的size時(shí)
{
if (n > capacity())// 當(dāng)n大于容量時(shí)，擴(kuò)容
{
reserve(n);
}
while (_finish < _start + n)// 給size到容器結(jié)尾賦值
{
*_finish = val;
_finish++;
}
}
}這里用了匿名對(duì)象T（）來(lái)作為缺省參數(shù)
通過(guò)比較_start和_finish指針來(lái)判斷容器是否為空
bool empty()const
{
return _start == _finish;
}先判斷容器是否已滿(mǎn)，如果滿(mǎn)了先擴(kuò)容再尾插，如果沒(méi)滿(mǎn)，直接尾插
void push_back(const T& x)
{
if (_finish == _endofstorage)// 判斷是否需要擴(kuò)容
{
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
}
// 尾插數(shù)據(jù)
*_finish = x;
_finish++;
}先判空處理，再–_finish
void pop_back()
{
assert(!empty());// 判空
--_finish;
}功能：利用迭代器再指定位置插入數(shù)據(jù)。
實(shí)現(xiàn)方式：插入前判斷是否需要擴(kuò)容，再將指定位置后的數(shù)據(jù)往后挪動(dòng)一位，把數(shù)據(jù)插入指定位置。
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start&&pos <= _finish);// 判斷傳入數(shù)據(jù)的合法性
if (_finish == _endofstorage)// 擴(kuò)容
{
size_t len = pos - _start;// 記錄pos的位置
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
pos = _start + len;
}
iterator end = _finish - 1;
while (end >= pos)// 挪動(dòng)數(shù)據(jù)
{
*(end + 1) = *end;
--end;
}
*pos = x;// 插入數(shù)據(jù)
_finish++;
return pos;
}注意:擴(kuò)容時(shí)要記錄pos和_start的相對(duì)位置，避免擴(kuò)容后迭代器失效問(wèn)題
功能：刪除指定位置數(shù)據(jù)。
實(shí)現(xiàn)方式：先判斷傳入數(shù)據(jù)的合法性，在將pos位置后的數(shù)據(jù)全部往前挪動(dòng)一位，覆蓋掉原pos位置的數(shù)據(jù)
iterator erase(iterator pos)
{
assert(pos >= _start&&pos < _finish);// 判斷傳入數(shù)據(jù)的合法性
iterator it = pos + 1;// 利用迭代器記錄pos的后一位
while (it != _finish)// 將pos后的數(shù)據(jù)往前挪動(dòng)一位
{
*(it - 1) = *it;
it++;
}
_finish--;
return pos;
}功能：交換兩個(gè)vector中的數(shù)據(jù)
實(shí)現(xiàn)方式：利用庫(kù)函數(shù)中的swap進(jìn)行交換
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._endofstorage);
}為了方便訪(fǎng)問(wèn)數(shù)據(jù)vector中也加入了“下標(biāo)+[ ]”操作
T& operator[](size_t i)// 可讀可寫(xiě)
{
assert(i < size());
return _start[i];
}
const T& operator[](size_t i) const// 只能讀
{
assert(i<size());
return _start[i];
}感謝各位的閱讀！關(guān)于“C++中如何模擬實(shí)現(xiàn)vector”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，讓大家可以學(xué)到更多知識(shí)，如果覺(jué)得文章不錯(cuò)，可以把它分享出去讓更多的人看到吧！
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀(guān)點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號(hào)
手機(jī)網(wǎng)站二維碼