C++模擬實(shí)現(xiàn)vector的示例代碼
1.前言
大家在學(xué)習(xí)C++的時(shí)候一定會(huì)學(xué)到STL（標(biāo)準(zhǔn)模板庫(kù)），這是C++標(biāo)準(zhǔn)庫(kù)中最重要的組成部分，它包含了常用的數(shù)據(jù)結(jié)構(gòu)和算法。今天呢，我們首先來(lái)學(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è)線性空間，所以無(wú)論其元素為什么類別，普通指針都可以作為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)一些空間，以備將來(lái)可能的擴(kuò)充。
template <typename T>
class vector
{
private:
iterator _start;
iterator _end;
iterator _endOfStorage;
public:
typedef T* iterator;
typedef const T* const_iterator;
};
3.1 迭代器接口
接下來(lái)我們來(lái)補(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)行一下封裝，讓使用者按照我們想要的方式來(lái)使用即可。
3.2 vector元素操作
3. 2. 1 刪除元素
首先，我們實(shí)現(xiàn)一個(gè)比較簡(jiǎn)單的操作：pop_back()，將指向使用空間的尾的迭代器向前移動(dòng)
void pop_back()
{
if (_end > _start)
{
--_end;
}
}
實(shí)現(xiàn)完簡(jiǎn)單的pop_back，接下來(lái)我們?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)槲覀儧](méi)有實(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);
//訪問(wèn)3
cout << *p << endl; //輸出4
return 0;
}
erase刪除p位置元素后，p位置之后的元素會(huì)往前搬移，沒(méi)有導(dǎo)致底層空間的改變，理論上講迭代器不應(yīng)該會(huì)失效，但是：如果p剛好是最后一個(gè)元素，刪完之后p剛好是end的位置，而end位置是沒(méi)有元素的，那么p就失效了。
所以為了避免迭代器失效的問(wèn)題，給erase添加了返回值，通過(guò)這個(gè)返回值來(lái)更新迭代器的值，防止迭代器失效。
3. 2. 2 空間配置
接下來(lái)我們來(lái)實(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;
}接下來(lái)是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)簡(jiǎ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è)版本
//無(wú)參構(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)造
在這里我選擇的是一種比較簡(jiǎn)單的寫法，使用迭代器區(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出來(lái)的空間，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語(yǔ)言中"函數(shù)調(diào)用中缺少哨兵"的情況分析
本篇文章是對(duì)c語(yǔ)言中"函數(shù)調(diào)用中缺少哨兵"的情況進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
這篇文章主要介紹了C和C++之間的區(qū)別，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-10-10
優(yōu)先隊(duì)列(priority_queue)的C語(yǔ)言實(shí)現(xiàn)代碼
本文簡(jiǎn)要介紹一種基于數(shù)組二叉堆實(shí)現(xiàn)的優(yōu)先隊(duì)列，定義的數(shù)據(jù)結(jié)構(gòu)和實(shí)現(xiàn)的函數(shù)接口說(shuō)明如下2013-10-10
C++實(shí)現(xiàn)浮點(diǎn)數(shù)精確加法
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)浮點(diǎn)數(shù)精確加法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-05-05
貪心算法（又稱貪婪算法）是指，在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇。也就是說(shuō)，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解2022-03-03
這篇文章主要介紹了C++實(shí)現(xiàn)顯示MP3文件信息的方法,可實(shí)現(xiàn)顯示如作者、專輯等（libZPlay）信息的功能,需要的朋友可以參考下2015-06-06
這篇文章主要介紹了C語(yǔ)言多媒體開源框架GStreamer,本文總結(jié)了多媒體框架GStreamer一些基本概念及流程，希望能給使用GStreamer開源庫(kù)的朋友提供一個(gè)借鑒或參考，需要的朋友可以參考下2022-07-07
OpenCV 圖像拼接和圖像融合的實(shí)現(xiàn)
本文主要介紹了OpenCV 圖像拼接和圖像融合，文中通過(guò)示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-08-08
C++基于消息隊(duì)列的多線程實(shí)現(xiàn)示例代碼
這篇文章主要給大家介紹了關(guān)于C++基于消息隊(duì)列的多線程實(shí)現(xiàn)的相關(guān)資料，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家學(xué)習(xí)或者使用C++具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-04-04
C++語(yǔ)言實(shí)現(xiàn)線性表之鏈表實(shí)例
這篇文章主要介紹了C++語(yǔ)言實(shí)現(xiàn)線性表之鏈表,實(shí)例分析了C++實(shí)現(xiàn)線性表中鏈表的原理與相關(guān)技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-04-04