C++模擬實現(xiàn)vector的示例代碼
1.前言
大家在學習C++的時候一定會學到STL（標準模板庫），這是C++標準庫中最重要的組成部分，它包含了常用的數(shù)據(jù)結構和算法。今天呢，我們首先來學習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，接下來我們去實現(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)空間配置器，所以在這里的刪除我們并不釋放空間，只是將后面的內容往前挪動后，改變_end的指向就好了。
實現(xiàn)完區(qū)間erase之后，之后的位置erase和clear我們都可以去復用了
//清除指定位置元素
iterator erase(iterator positon)
{
assert(positon + 1 <= end());
return erase(positon, positon + 1);
}
//清空
void clear()
{
erase(begin(), end());
}
細心的朋友會發(fā)現(xiàn)，erase的返回值不是void，而是起始位置的迭代器，這是為什么呢？
迭代器失效
迭代器失效，實際就是迭代器底層對應指針所指向的空間被銷毀了，而使用一塊已經被釋放的空間，造成的后果是程序崩潰。
#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位置之后的元素會往前搬移，沒有導致底層空間的改變，理論上講迭代器不應該會失效，但是：如果p剛好是最后一個元素，刪完之后p剛好是end的位置，而end位置是沒有元素的，那么p就失效了。
所以為了避免迭代器失效的問題，給erase添加了返回值，通過這個返回值來更新迭代器的值，防止迭代器失效。
3. 2. 2 空間配置
接下來我們來實現(xiàn)對vector的存儲空間進行配置的兩個接口reserve 和 resize。
首先是reserve，它只需要改變空間大小，并將原本vector空間內的內容拷貝到新空間中即可
void reserve(size_t n)
{
size_t sz = size();
//申請空間大于當前空間，擴容
if (n > capacity())
{
T *tmp = new T[n];
if (_start)
{
//將原本空間內容拷貝到新空間
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())
{
//空間不夠，復用reserve進行擴容
if (n > capacity())
{
reserve(n);
}
//元素不夠，將后面的內容初始化
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 構造與析構
構造函數(shù)
首先是構造函數(shù)，vector的構造函數(shù)平時用的比較多的有以下三個版本
//無參構造
vector()
: _start(nullptr), _end(nullptr), _endOfStorage(nullptr)
{
}
//迭代器區(qū)間構造
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);
}
}
拷貝構造
在這里我選擇的是一種比較簡單的寫法，使用迭代器區(qū)間構造函數(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);
}
析構函數(shù)
析構函數(shù)將new出來的空間，delete掉即可
~vector()
{
if (_start)
{
delete[] _start;
_start = _end = _endOfStorage = nullptr;
}
}到此這篇關于C++模擬實現(xiàn)vector的示例代碼的文章就介紹到這了,更多相關C++ vector內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了C++中deque與vector相比的優(yōu)勢與劣勢，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習吧2023-01-01
這篇文章主要給大家介紹了關于C++中4種強制類型轉換區(qū)別的相關資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-03-03
這篇文章主要為大家介紹了c++類型轉換及RTTI運行階段類型識別詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步早日升職加薪2023-05-05
詳解C語言gets()函數(shù)與它的替代者fgets()函數(shù)
這篇文章主要介紹了詳解C語言gets()函數(shù)與它的替代者fgets()函數(shù)的相關資料,非常不錯，具有參考借鑒價值，需要的朋友可以參考下2016-10-10
Qt將數(shù)據(jù)庫中的數(shù)據(jù)導出為html
這篇文章主要為大家詳細介紹了Qt如何實現(xiàn)將數(shù)據(jù)庫中的數(shù)據(jù)導出為html,文中的示例代碼講解詳細,感興趣的小伙伴可以跟隨小編一起學習一下2024-12-12
大家好，本篇文章主要講的是C++中allocator類使用示例，感興趣的同學趕快來看一看吧，對你有幫助的話記得收藏一下2022-02-02
這篇文章主要為大家詳細介紹了C語言實現(xiàn)宿舍管理課程設計，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
函數(shù)是一組一起執(zhí)行一個任務的語句。每個 C 程序都至少有一個函數(shù)，即主函數(shù) main() ，所有簡單的程序都可以定義其他額外的函數(shù)2022-03-03
這篇文章主要介紹了c++讀寫文件流實例，大家參考使用吧2013-12-12
這篇文章主要介紹了C++遍歷文件夾目錄的方法，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-04-04