C++模擬實(shí)現(xiàn)vector的示例代碼
1.前言
大家在學(xué)習(xí)C++的時(shí)候一定會(huì)學(xué)到STL（標(biāo)準(zhǔn)模板庫），這是C++標(biāo)準(zhǔn)庫中最重要的組成部分，它包含了常用的數(shù)據(jù)結(jié)構(gòu)和算法。今天呢，我們首先來學(xué)習(xí)STL中的vector容器
2.vector介紹
vector的數(shù)據(jù)安排和操作方式與我們平時(shí)使用的數(shù)組非常相似，唯一的區(qū)別在于數(shù)組是一個(gè)固定空間，而vector的空間可以隨著元素的改變而發(fā)生改變。
還是和之前一樣，vector的使用方式大家可以去查閱官方文檔std::vector - cppreference.com
3.vector模擬實(shí)現(xiàn)
vector維護(hù)的是一個(gè)線性空間，所以無論其元素為什么類別，普通指針都可以作為vector的迭代器而滿足所有必要條件。vector要和普通數(shù)組一樣支持隨機(jī)存取，而普通指針正有這樣的能力。
為了維護(hù)一個(gè)vector我們只需要三個(gè)指針，一個(gè)使用空間的頭，一個(gè)使用空間的尾，一個(gè)指向可用空間的尾。
第一個(gè)和第二個(gè)指針的作用我知道，但是為什么要有第三個(gè)指針呢？
這是為了降低計(jì)算機(jī)空間配置的成本，每次申請(qǐng)一塊小空間和申請(qǐng)一塊大空間的時(shí)間成本差不多，所以vector在申請(qǐng)空間的時(shí)候，通常會(huì)多申請(qǐng)一些空間，以備將來可能的擴(kuò)充。
template <typename T>
class vector
{
private:
iterator _start;
iterator _end;
iterator _endOfStorage;
public:
typedef T* iterator;
typedef const T* const_iterator;
};
3.1 迭代器接口
接下來我們來補(bǔ)充一下vector的迭代器接口，
template <typename T>
class vector
{
private:
//...
public:
iterator begin() { return _start; }
iterator end() { return _end; }
size_t size() const
{
return size_t(_end - _start);
}
size_t capacity() const
{
return size_t(_endOfStorage - begin());
}
bool empty() const
{
return begin() == end();
}
T& operator[](size_t n)
{
return *(begin() + n);
}
T& fornt(){return *begin()};
T& back() { return *(end() - 1); }
};vector的迭代器就是原生指針，我們只是將這個(gè)原生指針進(jìn)行一下封裝，讓使用者按照我們想要的方式來使用即可。
3.2 vector元素操作
3. 2. 1 刪除元素
首先，我們實(shí)現(xiàn)一個(gè)比較簡單的操作：pop_back()，將指向使用空間的尾的迭代器向前移動(dòng)
void pop_back()
{
if (_end > _start)
{
--_end;
}
}
實(shí)現(xiàn)完簡單的pop_back，接下來我們?nèi)?shí)現(xiàn)一個(gè)較為困難的接口，可以在任意位置進(jìn)行刪除的erase接口。
//清除[first, last)的元素
iterator erase(iterator first, iterator last)
{
assert(first >= _start && last <= _end);
iterator ret = first;
while(last != end())
{
*first = *last;
first++;
last++;
}
_end = first;
return ret;
}
因?yàn)槲覀儧]有實(shí)現(xiàn)空間配置器，所以在這里的刪除我們并不釋放空間，只是將后面的內(nèi)容往前挪動(dòng)后，改變_end的指向就好了。
實(shí)現(xiàn)完區(qū)間erase之后，之后的位置erase和clear我們都可以去復(fù)用了
//清除指定位置元素
iterator erase(iterator positon)
{
assert(positon + 1 <= end());
return erase(positon, positon + 1);
}
//清空
void clear()
{
erase(begin(), end());
}
細(xì)心的朋友會(huì)發(fā)現(xiàn)，erase的返回值不是void，而是起始位置的迭代器，這是為什么呢？
迭代器失效
迭代器失效，實(shí)際就是迭代器底層對(duì)應(yīng)指針?biāo)赶虻目臻g被銷毀了，而使用一塊已經(jīng)被釋放的空間，造成的后果是程序崩潰。
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int a[] = {0, 1, 2, 3, 4};
vector<int> v(a, a + sizeof(a) / sizeof(int));
//尋找3的位置
auto p = find(v.begin(), v.end(), 3);
//刪除3
v.erase(p);
//訪問3
cout << *p << endl; //輸出4
return 0;
}
erase刪除p位置元素后，p位置之后的元素會(huì)往前搬移，沒有導(dǎo)致底層空間的改變，理論上講迭代器不應(yīng)該會(huì)失效，但是：如果p剛好是最后一個(gè)元素，刪完之后p剛好是end的位置，而end位置是沒有元素的，那么p就失效了。
所以為了避免迭代器失效的問題，給erase添加了返回值，通過這個(gè)返回值來更新迭代器的值，防止迭代器失效。
3. 2. 2 空間配置
接下來我們來實(shí)現(xiàn)對(duì)vector的存儲(chǔ)空間進(jìn)行配置的兩個(gè)接口reserve 和 resize。
首先是reserve，它只需要改變空間大小，并將原本vector空間內(nèi)的內(nèi)容拷貝到新空間中即可
void reserve(size_t n)
{
size_t sz = size();
//申請(qǐng)空間大于當(dāng)前空間，擴(kuò)容
if (n > capacity())
{
T *tmp = new T[n];
if (_start)
{
//將原本空間內(nèi)容拷貝到新空間
for (int i = 0; i < size(); ++i)
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
}
//改變指針
_end = _start + sz;
_endOfStorage = _start + n;
}接下來是resize，它和reserve有所不同，reserve只是開辟新空間，而resize還可以進(jìn)行初始化
void resize(size_t n, const T &val = T())
{
//空間不夠，復(fù)用reserve進(jìn)行擴(kuò)容
if (n > capacity())
{
reserve(n);
}
//元素不夠，將后面的內(nèi)容初始化
if (n > size())
{
for (int i = size(); i < n; i++)
{
_start[i] = val;
}
_end = _start + n;
}
else
{
_end = _start + n;
}
}3. 2. 3 添加元素
這次我們先從比較難的insert開始吧，insert可以在指定位置插入元素
iterator insert(iterator pos, const T &x)
{
assert(pos >= _start && pos <= _end);
//空間不夠，進(jìn)行擴(kuò)容
if (_end == _endOfStorage)
{
size_t n = pos - _start;
size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newCapacity);
pos = _start + n;
}
//挪動(dòng)數(shù)據(jù)，給新元素空出位置插入
iterator finish = _end - 1;
while (finish >= pos)
{
*(finish + 1) = *finish;
--finish;
}
*pos = x;
++_end;
return pos;
}
完成了困難的insert后，我們?cè)偃?shí)現(xiàn)簡單的push_back
void push_back(const T &x)
{
//空間不夠 擴(kuò)容
if (_end == _endOfStorage)
{
size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newCapacity);
}
*_end = x;
++_end;
}
3. 3 構(gòu)造與析構(gòu)
構(gòu)造函數(shù)
首先是構(gòu)造函數(shù)，vector的構(gòu)造函數(shù)平時(shí)用的比較多的有以下三個(gè)版本
//無參構(gòu)造
vector()
: _start(nullptr), _end(nullptr), _endOfStorage(nullptr)
{
}
//迭代器區(qū)間構(gòu)造
template <class InputIterator>
vector(InputIterator first, InputIterator last)
: _start(nullptr), _end(nullptr), _endOfStorage(nullptr)
{
while (first != last)
{
push_back(*first);
++first;
}
}
vector(int n, const T &val)
: _start(nullptr), _end(nullptr), _endOfStorage(nullptr)
{
reserve(n);
while (n--)
{
push_back(val);
}
}
拷貝構(gòu)造
在這里我選擇的是一種比較簡單的寫法，使用迭代器區(qū)間構(gòu)造函數(shù)去創(chuàng)建一個(gè)臨時(shí)對(duì)象，然后將臨時(shí)對(duì)象的資源與此對(duì)象進(jìn)行一個(gè)互換
vector(const vector<T> &t)
: _start(nullptr), _end(nullptr), _endOfStorage(nullptr)
{
vector<T> tmp(t.begin(), t.end());
swap(tmp);
}
void swap(vector<T> &t)
{
std::swap(_start, t._start);
std::swap(_end, t._end);
std::swap(_endOfStorage, t._endOfStorage);
}
析構(gòu)函數(shù)
析構(gòu)函數(shù)將new出來的空間，delete掉即可
~vector()
{
if (_start)
{
delete[] _start;
_start = _end = _endOfStorage = nullptr;
}
}到此這篇關(guān)于C++模擬實(shí)現(xiàn)vector的示例代碼的文章就介紹到這了,更多相關(guān)C++ vector內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C++ deque與vector對(duì)比的優(yōu)缺點(diǎn)
這篇文章主要介紹了C++中deque與vector相比的優(yōu)勢(shì)與劣勢(shì)，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)吧2023-01-01
C++中4種強(qiáng)制類型轉(zhuǎn)換的區(qū)別詳析
這篇文章主要給大家介紹了關(guān)于C++中4種強(qiáng)制類型轉(zhuǎn)換區(qū)別的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-03-03
c++類型轉(zhuǎn)換及RTTI運(yùn)行階段類型識(shí)別
這篇文章主要為大家介紹了c++類型轉(zhuǎn)換及RTTI運(yùn)行階段類型識(shí)別詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步早日升職加薪2023-05-05
詳解C語言gets()函數(shù)與它的替代者fgets()函數(shù)
這篇文章主要介紹了詳解C語言gets()函數(shù)與它的替代者fgets()函數(shù)的相關(guān)資料,非常不錯(cuò)，具有參考借鑒價(jià)值，需要的朋友可以參考下2016-10-10
Qt將數(shù)據(jù)庫中的數(shù)據(jù)導(dǎo)出為html
這篇文章主要為大家詳細(xì)介紹了Qt如何實(shí)現(xiàn)將數(shù)據(jù)庫中的數(shù)據(jù)導(dǎo)出為html,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2024-12-12
大家好，本篇文章主要講的是C++中allocator類使用示例，感興趣的同學(xué)趕快來看一看吧，對(duì)你有幫助的話記得收藏一下2022-02-02
C語言實(shí)現(xiàn)宿舍管理課程設(shè)計(jì)
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)宿舍管理課程設(shè)計(jì)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-03-03
函數(shù)是一組一起執(zhí)行一個(gè)任務(wù)的語句。每個(gè) C 程序都至少有一個(gè)函數(shù)，即主函數(shù) main() ，所有簡單的程序都可以定義其他額外的函數(shù)2022-03-03
這篇文章主要介紹了c++讀寫文件流實(shí)例，大家參考使用吧2013-12-12
這篇文章主要介紹了C++遍歷文件夾目錄的方法，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-04-04