C++模擬實現(xiàn)vector的示例代碼
1.前言
大家在學(xué)習(xí)C++的時候一定會學(xué)到STL（標準模板庫），這是C++標準庫中最重要的組成部分，它包含了常用的數(shù)據(jù)結(jié)構(gòu)和算法。今天呢，我們首先來學(xué)習(xí)STL中的vector容器
2.vector介紹
vector的數(shù)據(jù)安排和操作方式與我們平時使用的數(shù)組非常相似，唯一的區(qū)別在于數(shù)組是一個固定空間，而vector的空間可以隨著元素的改變而發(fā)生改變。
還是和之前一樣，vector的使用方式大家可以去查閱官方文檔std::vector - cppreference.com
3.vector模擬實現(xiàn)
vector維護的是一個線性空間，所以無論其元素為什么類別，普通指針都可以作為vector的迭代器而滿足所有必要條件。vector要和普通數(shù)組一樣支持隨機存取，而普通指針正有這樣的能力。
為了維護一個vector我們只需要三個指針，一個使用空間的頭，一個使用空間的尾，一個指向可用空間的尾。
第一個和第二個指針的作用我知道，但是為什么要有第三個指針呢？
這是為了降低計算機空間配置的成本，每次申請一塊小空間和申請一塊大空間的時間成本差不多，所以vector在申請空間的時候，通常會多申請一些空間，以備將來可能的擴充。
template <typename T>
class vector
{
private:
iterator _start;
iterator _end;
iterator _endOfStorage;
public:
typedef T* iterator;
typedef const T* const_iterator;
};
3.1 迭代器接口
接下來我們來補充一下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的迭代器就是原生指針，我們只是將這個原生指針進行一下封裝，讓使用者按照我們想要的方式來使用即可。
3.2 vector元素操作
3. 2. 1 刪除元素
首先，我們實現(xiàn)一個比較簡單的操作：pop_back()，將指向使用空間的尾的迭代器向前移動
void pop_back()
{
if (_end > _start)
{
--_end;
}
}
實現(xiàn)完簡單的pop_back，接下來我們?nèi)崿F(xià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;
}
因為我們沒有實現(xiàn)空間配置器，所以在這里的刪除我們并不釋放空間，只是將后面的內(nèi)容往前挪動后，改變_end的指向就好了。
實現(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());
}
細心的朋友會發(fā)現(xiàn)，erase的返回值不是void，而是起始位置的迭代器，這是為什么呢？
迭代器失效
迭代器失效，實際就是迭代器底層對應(yīng)指針所指向的空間被銷毀了，而使用一塊已經(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位置之后的元素會往前搬移，沒有導(dǎo)致底層空間的改變，理論上講迭代器不應(yīng)該會失效，但是：如果p剛好是最后一個元素，刪完之后p剛好是end的位置，而end位置是沒有元素的，那么p就失效了。
所以為了避免迭代器失效的問題，給erase添加了返回值，通過這個返回值來更新迭代器的值，防止迭代器失效。
3. 2. 2 空間配置
接下來我們來實現(xiàn)對vector的存儲空間進行配置的兩個接口reserve 和 resize。
首先是reserve，它只需要改變空間大小，并將原本vector空間內(nèi)的內(nèi)容拷貝到新空間中即可
void reserve(size_t n)
{
size_t sz = size();
//申請空間大于當(dāng)前空間，擴容
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還可以進行初始化
void resize(size_t n, const T &val = T())
{
//空間不夠，復(fù)用reserve進行擴容
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);
//空間不夠，進行擴容
if (_end == _endOfStorage)
{
size_t n = pos - _start;
size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newCapacity);
pos = _start + n;
}
//挪動數(shù)據(jù)，給新元素空出位置插入
iterator finish = _end - 1;
while (finish >= pos)
{
*(finish + 1) = *finish;
--finish;
}
*pos = x;
++_end;
return pos;
}
完成了困難的insert后，我們再去實現(xiàn)簡單的push_back
void push_back(const T &x)
{
//空間不夠 擴容
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ù)平時用的比較多的有以下三個版本
//無參構(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)建一個臨時對象，然后將臨時對象的資源與此對象進行一個互換
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++模擬實現(xiàn)vector的示例代碼的文章就介紹到這了,更多相關(guān)C++ vector內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
解析c語言中"函數(shù)調(diào)用中缺少哨兵"的情況分析
本篇文章是對c語言中"函數(shù)調(diào)用中缺少哨兵"的情況進行了詳細的分析介紹，需要的朋友參考下2013-05-05
這篇文章主要介紹了C和C++之間的區(qū)別，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-10-10
優(yōu)先隊列(priority_queue)的C語言實現(xiàn)代碼
本文簡要介紹一種基于數(shù)組二叉堆實現(xiàn)的優(yōu)先隊列，定義的數(shù)據(jù)結(jié)構(gòu)和實現(xiàn)的函數(shù)接口說明如下2013-10-10
這篇文章主要為大家詳細介紹了C++實現(xiàn)浮點數(shù)精確加法，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-05-05
貪心算法（又稱貪婪算法）是指，在對問題求解時，總是做出在當(dāng)前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解2022-03-03
這篇文章主要介紹了C++實現(xiàn)顯示MP3文件信息的方法,可實現(xiàn)顯示如作者、專輯等（libZPlay）信息的功能,需要的朋友可以參考下2015-06-06
這篇文章主要介紹了C語言多媒體開源框架GStreamer,本文總結(jié)了多媒體框架GStreamer一些基本概念及流程，希望能給使用GStreamer開源庫的朋友提供一個借鑒或參考，需要的朋友可以參考下2022-07-07
本文主要介紹了OpenCV 圖像拼接和圖像融合，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-08-08
這篇文章主要給大家介紹了關(guān)于C++基于消息隊列的多線程實現(xiàn)的相關(guān)資料，文中通過示例代碼介紹的非常詳細，對大家學(xué)習(xí)或者使用C++具有一定的參考學(xué)習(xí)價值，需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧2019-04-04
這篇文章主要介紹了C++語言實現(xiàn)線性表之鏈表,實例分析了C++實現(xiàn)線性表中鏈表的原理與相關(guān)技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-04-04