---

前言

提前在這說明下，vector增刪查改模擬實現的成員變量博主采用SGI版本。下面給出其庫中成員變量是哪些，后續的模擬實現都基于此。

我們發現庫中定義了3個T*的變量。同時3個成員變量的意義如下：

一、迭代器

1.1 非const迭代器：begin()、end()

typedef T* iterator;iterator begin()
{return _start;
}iterator end()
{return _finish;
}

1.2 const迭代器：begin()、end()

typedef const T* const_iterator;const_iterator begin()const
{return _start;
}const_iterator end()const
{return _finish;
}

二、構造函數、拷貝構造函數、賦值重載、析構函數模擬實現

2.1 構造函數

我們先來看看vector庫中的構造類型如下：

我們知道有三種構造方式，下面給出各種的實現方式。

2.1.1 無參構造

vector():_start(nullptr),_finish(nullptr), _endofstorage{}

2.1.2 迭代器區間構造

template<class InputIterator>//使用模板是為了，當數據類型匹配時就可以使用
vector(InputIterator first, InputIterator last)
{while (first != last){push_back(*first);first++;}
}

2.1.3 n個值構造

vector(size_t  n, const T& value = T())
{reserve(n);for (size_t i = 0; i < n; i++){push_back(value);}
}//防止定義vector<int>這種類型走迭代區間的構造函數，我們在多實現一個以下類型函數
//當使用vector<int>類型的去構造時，此時調用的構造函數兩個參數都是int。所有他會走最匹配的函數，即迭代器區間構造生成的構造函數，程序會出錯。
//而下面給出了現成的最匹配構造函數，編譯器調用時就不會走模板。
vector(int n, const T& value = T())
{reserve(n);for (size_t i = 0; i < n; i++){push_back(value);}
}

2.2 拷貝構造

拷貝構造我們先調用開好一塊空間，在依次插入數據即可。

//vector(const vector& x) //庫中實現模式, 直接使用類名。但C++，類型不是類名。
//這里各位讀者了解下這里直接類名做類型也正確即可，但不建議各位這樣做。
vector(const vector<T>& v)
{reserve(v.capacity());//后面會給出實現for (auto& e : v){push_back(e);}
}

2.3 賦值重載

賦值重載這里我們不要傳引用，而是直接傳參即可。編譯器調用拷貝構造生成形參后，在調用swap()函數依次交換形參和this即可。

//賦值重載
void swap(vector<T>& v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v_endofstorage);
}vector<T>& operator= (vector<T> tmp)
{swap(tmp);return *this;
}		

3 析構函數

~vector()
{delete[] _start;_start = _finish = _endofstorage = nullptr;
}

三、容量相關：capacity()、size()、reserve()、resize()

3.1 capacity()

size_t capacity()const
{return _endofstorage - _start;
}

3.2 size()

size_t size()const
{return _finish - _start;
}

3.3 reserve()

由于stl中我們一般不縮容，所以先判斷reserve的空間大小是否比當前空間容量大。
如果reserve的空間更大，所以我們需要先開好目標大小的空間，在將原數據拷貝過去，最后析構原來空間即可。
但下面這兩種實現方式對嗎？

第一種：

void reserve(size_t n)
{if (n > capacity()){T* tmp = new T[n];if (_start)//如果原來空間有數據，拷貝到新空間{memcpy(tmp, _start, sizeof(T) * size());delete[] _start;}//更新_start、_finish、_endofstorage。指向新空間中相應位置_start = tmp;_finish = _start + size();_endofstorage = _start + n;}
}

先說結論：上訴這段代碼是錯的。
在我們調試后會發現_finish的值沒有更新。（這里大家自行驗證下接口）
?
原因：(win11畫圖一直很模糊，博主也很無奈，各位將就看吧)

---

第二種：
為了解決上訴問題，我們可以先記錄_finish和_start的偏移量，用來代替size()函數。
所以初學者很容易寫出以下代碼：

void reserve(size_t n)
{if (n > capacity()){size_t sz = size();//記錄_finish 和 _start 的偏移量T* tmp = new T[n];if (_start){//memcpy(tmp, _start, sizeof(T) * sz);delete[] _start;}_start = tmp;_finish = _start + sz;//不能用size()代替sz，否則會導致迭代器失效_endofstorage = _start + n;}
}

那這是否正確呢？答案是否定的。
我們來看看下面這種場景：

---

實際上對于這種情況，可以自己循環依次賦值即可。內置類型直接拷貝數據；內置類型調用賦值重載，是一種深拷貝。

最終代碼如下：

void reserve(size_t n)
{if (n > capacity()){size_t sz = size();//記錄_finish 和 _start 的偏移量T* tmp = new T[n];if (_start){//memcpy(tmp, _start, sizeof(T) * sz);for (size_t i = 0; i < sz; i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + sz;//不能用size()代替sz，否則會導致迭代器失效_endofstorage = _start + n;}
}

3.4 resize()

resize邏輯還是很簡單的。
首先判斷resize()的目標大小n和有效數據個數size()誰大。如果有效個數size()更大，只需更改_finish即可；否則要先進行擴容（reserve會將原有數據拷貝到新空間），然后從_finish開始向擴充的空間插入新的值。
?
代碼如下：

//const會延長匿名對象的生命周期, 匿名對象具有常性
//模板出來后，對類進行了升級，內置類型也有構造函數
//void resize(size_t n, T val = T())
void resize(size_t n, const T& val = T())
{if (n < size()){_finish = _start + n;}else{reserve(n);while (_finish < _start + n){*_finish = val;_finish++;}}
}

四、operator[ ]重載

T& operator[](size_t pos)
{assert(pos < size());return _start[pos];
}const T& operator[](size_t pos)const
{assert(pos < _finish);return _start[pos];
}

五、元素相關：insert、erase、push_back、pop_back

5.1 insert()

任意位置插入數據，首先需判斷是否需要擴容。然后將插入位置pos開始往后的數據向后移動，最后將新數據插入到pos處即可。
tips：

• 如果發生擴容，需要先記錄pos和_start之間的偏移量。在將pos位置跟新，指向新空間中對應位置。否則會導致迭代器失效

void insert(iterator pos, const T& x)
{assert(pos >= _start);assert(pos <= _finish);if (_finish == _endofstroage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}//挪動數據iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;end--;}//插入數據*pos = x;_finish++;
}

5.2 erase()

任意位置刪除數據，只需要從pos+1開始，將后續數據全部依次向前移動覆蓋，最后更新_finish即可。

iterator erase(iterator pos)
{assert(pos >= _start);assert(pos < _finish);iterator it = pos + 1;while (it < _finish){*(it - 1) = *it;++it;}--_finish;return pos;
}

5.2.1 erase迭代器失效

void testvector4()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(2);v.push_back(4);v.push_back(5);v.push_back(6);auto it = v.begin();while (it < v.end()){if (*it % 2 == 0){v.erase(it);}it++;}for (auto e : v){cout << e << " ";}cout << endl;
}

上述代碼本意是將偶數全部刪除，結果本該是1 、5。但結果卻是：

為什么呢？
這是因為我們刪除元素后，后續數據會補上空缺。所以當使用erase后，迭代器會失效。（上述結果是g++的實現機制，在vs2019下上述代碼會直接報錯。原因在于vs2019對erase后的空間做強制檢查，不允許訪問）。為此stl庫給出的解決方案是接受刪除位置的下一個元素的返回值。（這也是為什么整個模擬實現中只有erase函數具有返回值）,并接收返回值。
?
正確刪除偶數方法：

void testvector4(){//std::vector<int> v;vector<int> v;v.push_back(1);v.push_back(2);v.push_back(2);v.push_back(4);v.push_back(5);v.push_back(6);auto it = v.begin();//迭代器失效/*while (it < v.end()){if (*it % 2 == 0){v.erase(it);}it++;}*/while (it < v.end()){if (*it % 2 == 0){it = v.erase(it);}else{it++;}}for (auto e : v){cout << e << " ";}cout << endl;}

5.3 push_bach()

頭插復用insert函數即可。

void push_back(const T& x)
{//if (_finish == _endofstroage)//{//	reserve(capacity() == 0 ? 4 : capacity() * 2);//}插入數據//*_finish = x;//_finish++;insert(_finish, x);
}

5.4 pop_back()

復用erase，尾刪

void pop_back()
{erase(--end());
}

六、所有代碼

vector增刪查改模擬實現gitee鏈接