vector的使用和模擬實現

vector的使用

vector介紹

對于STL中各類容器的學習其實是很相似的，因為c++的封裝性。雖然是不同的容器，但是c++標準庫在實現的時候是對各類的容易實現了一些一樣的接口，我們只需要關注其封裝的接口的使用即可。所以各類容器的操作是很類似的。

而對于vector其實是一個類模板，其底層的實現本質還是順序表。只不過與string的底層實現是略有區別。更大的不同是vector中存儲的元素不僅僅是一些內置類型，也可以是類，如string，甚至是vector類。

當然學習STL容易是先學會如何使用其對應接口，我們得學會查閱文檔：https://cplusplus.com/reference/vector/vector/

重點接口的講解

迭代器部分

vector的接口其實沒有string實現的那么多。因為string是更早寫進標準庫中的，這是歷史遺留問題。

對于string，我們在增刪的時候，更多的是傳入對應的位置，也就是下標。而當我們查閱vector使用的文檔的時候，我們發現參數竟然是使用迭代器的：

如erase函數，可以傳一個迭代器的位置，也可以傳迭代器指向的一段區間(左閉右開)。

其實迭代器的使用和string是一樣的的，有八種。end型的迭代器都是指向最后一個有效元素的后一個位置。

使用的話重點掌握begin、rbegin、end、rend這四個就可以了。

默認成員函數

函數	使用
vector()（重點）	無參構造
vector（size_type n, const value_type& val =value_type()）	構造并初始化n個val
vector (const vector& x); （重點）	拷貝構造
vector (InputIterator first, InputIterator last);	使用迭代器進行初始化構造
~vector()	析構 編譯器會自行調用
vector& operator= (const vector& x);	賦值重載

這里面有很多不認識的符號，下面給出這些符號的對應表：

我們直到，vector其實是一個類模板，內部的數據類型其實都是由模板參數T來替代的。但是為了代碼的可讀性更好，所以對一些常用的類型取別名。

我們只需要知道常用的那幾個就可以了。

而還有一個很奇怪的構造函數：vector (InputIterator first, InputIterator last)，使用迭代器進行初始化構造。這個InputIterator是什么呢？

其實這是一個模板參數的聲名，template< class InputIterator >，聲名這一個模板參數是因為在構造一個vector的時候，我們很可能需要用別的迭代器進行構造。
舉一個很常見的例子：

有時候我們想對鏈表(STL中的list)中的數據進行排序。但是鏈表排序其實是效率較低的。所以我們會經常的使用鏈表的迭代器區間來構造一個vector，vector的本質是順序表，使用順序表排序是比較高效率的。然后排好序后再依次將數據覆蓋回鏈表中。

當然這個迭代器也可以是指向數組的：

在這里我們可以認為是數組也有自己的迭代器。

空間操作

函數	使用
size	獲取數據個數
capacity	獲取容量大小
empty	判斷是否為空
resize（重點）	改變vector的size
reserve （重點）	改變vector的capacity

重點我們來看看resize和reserve的使用。

對于resize:

這是調整數據個數的函數。如果傳入的n是小于當前數據個數，那么就會刪除數據。
如果n大于當前數據個數，會往后續新加入的位置插入數據，空間不夠的時候會擴容。

這個插入的數據是帶有缺省參數的，即value_type val = value_type()；。這個其實是調用了匿名類的默認構造函數。

很多人會疑惑，如果是int等內置類型也能這樣使用嗎？答案是當然可以。在以往我們會認為，只有自定義類型才會有默認構造函數。但其實在c++內，對于內置類型也是可以有默認構造函數的：

如果我們進行初始化了，那么值當然就是初始化的值。但是如果我們像上面參數顯示的那樣去調用默認構造，我們發現不傳參的時候默認值是0，傳參的時候就是將參數的值給變量。這個用法和自定義類型是一樣的。所以我們不用擔心自定義類型會使用不了的問題。

對于reserve：
reserve函數就是預留空間，因為c++標準沒有明確規定一些細節，導致不同平臺對于其實現是有差異的。

vs編譯器下堅決不縮容，只會擴容，且擴容大致是1.5倍。
而g++編譯器是會縮容的，擴容的方式是很標準的2倍擴容。

增刪查改操作

函數	說明
push_back（重點）	尾插
pop_back （重點）	尾刪
find	查找（注意這個是算法模塊實現，不是vector的成員接口）
insert	在position之前插入val
erase	刪除position位置的數據
swap	交換兩個vector的數據空間
operator[]	（重點） 像數組一樣訪問

只需要注意的是insert和erase的操作是要傳入對應位置的迭代器。還有就是vector內并沒有像string內實現find接口，我們要使用的話就得在算法庫algorithm中去調用。

而其余的用法是很簡單的，自行查閱文檔即可。

迭代器失效問題(重要)

string中也有迭代器，但是我們并沒有說迭代器失效的問題。這是因為對于string我們更偏向于用下標來訪問內部數據。就連刪除插入等操作也是用下標進行訪問元素的。而vector卻是用迭代器實現的，而在實現的時候發現了一些問題，這些問題統稱為迭代器失效，下面讓我們一起來看看：

在這里我們先說明一個事情：vector的正向迭代器其實就是數據類型的原生指針。

1.迭代器變為野指針，原來指向的空間被釋放
這種問題通常出現在vector容量被修改的時候。我們在模擬實現string的時候就對容量進行修改的時候，是需要新開辟一個空間，然后再將原來空間進行釋放。是沒有像c語言中realloc一樣功能的函數的。

問題就出現在這里：

當然如果要進行縮容也是一樣的。所以插入和刪除函數在實現的時候，就考慮到這個問題，進行了修正。使得這兩個功能能夠正常的使用并且達到想要的效果。

2.非法使用迭代器和非法訪問元素
這個點也是需要非常注意的，下面我們舉一個例子看看：

現有vector v1，指向內容是{1,2,2,3,4,4,5}

我們來看一下下面這個代碼：

int main(){vector<int>:: iterator it = v1.begin();while(it != v1.end()){if(*it % 2){erase(it);*it = -1;}++it;}return 0;
}

乍一看沒啥問題，但其實問題很大。

首先這個代碼在不同平臺下的結果是不一樣的。在vs2022上是會斷言報錯的。而在g++編譯器上能夠正常運行，但是達不到想要的效果。

我們先來說g++下的情況：
運行結果為 1 -1 3 -1 5，這是為什么呢？
這是因為我們非法使用迭代器了：

當遍歷到第一個2的時候，就會進行刪除操作，那后續的數據會被移動到前面來，數據變成{1,2,3,4,4,5}。原來的2的位置被后面一個2頂上來了。但此時原來的空間并沒有被銷毀，而正向迭代器的本質是原生指針，所以指向的仍然是原來的那個位置，也就是后頂上來的2的位置，然后對此時位置進行修改，數組變成{1,-1,3,4,4,5}。然后++it會走到3的那個位置。

然后以此類推，最后變成了輸出的結果。變成-1的位置就是為了告訴我們，如果使用這個代碼去刪除偶數項，會有被遺漏的偶數。這其實也是迭代器失效的一個方面。就是會導致訪問元素出現問題。

如果在vs2022下：
編譯器會直接斷言報錯。這是因為vs編譯器做了嚴格的檢查，如果再執行了刪除和插入操作后，迭代器會失效，一般是不能訪問的。所以編譯器內部自動檢查是否有修正迭代器的情況。如果沒有就會報錯。因為編譯器認為這樣子是非法訪問。

當然對于上面那段代碼，如果被刪除的元素在末尾也是會出現問題，因為刪除后數量減一，但是又要執行++it操作，那么it會越界。也是會觸發斷言報錯的。

調整迭代器

這些都是迭代器失效的問題。為了 防止這種現象發生，我們就得調整迭代器的值。實際上vs編譯器也是這么做的。

對于插入操作，編譯器會返回新插入的元素的第一個的迭代器。插入操作可能會插入一個怨怒是，有可能插入多個元素。對此返回的是插入元素的第一個位置的迭代器。

對于刪除操作，返回的是刪除元素的最后一個的后一個元素的新位置的迭代器：
如1 3 5 6 7，刪除3 和 5 ，變成 1 6 7，返回的就是指向6的迭代器。如果刪除的最后一個元素正好是原本空間中的最后一個元素，那么返回的迭代器其實是數組結束位置。

所以要想真正的能把上面例子種數組的偶數全部刪除，需要改進代碼：

int main(){vector<int>:: iterator it = v1.begin();while(it != v1.end()){if(*it % 2){it = v1.erase(it);}else ++it;}return 0;
}

這樣子就能在vs的編譯器上跑起來了。

vector的模擬實現

當然要想更好的學會使用vector，我們也是需要了解如何對vector中的一些重要功能進行實現的。

實現的版本

c++只是規定了容器對應的功能應該完成什么樣的效果，但是并沒有明確要求應該如何實現。所以不同的版本實現是有一些區別的。

vs2022中的實現其實是非常復雜的，涉及到內存池等內容。由于當前還未學習內存池等相關技術，所以并不適合模仿。而我們可以查看一下g++編譯器的底層是如何實現的：

這個是g++編譯器下實現版本的比較早期的源代碼，我們發現protected成員里面有三個迭代器，分別是start、finish、end_of_storage。

我們再翻看一下迭代器是怎么實現的：

正向迭代器其實就是value_type*這個指針，也就是數據類型的指針。所以對于vector來講，其正向迭代器就是原生指針。

而以往我們在實現順序表的時候，都是一個指針配合整形數據空間、容量進行管理內容。但是在vector的源代碼中我們發現是通過指針管理的。

start就是指向開頭數據的指針，finish其實是有效數據的后一個位置，end_of_storage指示容量，就是當前已有空間的后一個位置。

我們實現的版本主要是這個版本。

模擬實現

源碼放在我的碼云上了：vector imitate achievement

既然是使用指針實現的，那我們就特別需要注意指針的一些問題，特別是野指針。需要我們能夠正確的操作這幾個指針變量。

結構

vector是一個類模板，和string不太一樣。所以我們聲名的是一個類模板，需要定義模板參數。使用模板的話就盡量不要將函數的聲名和定義進行分離了，因為會導致鏈接錯誤。

所以我們采取以下策略：
在MyVector這個命名空間內定義類模板，將短小多次調用的函數放在類里面進行定義。因為默認內聯，方便多次調用。而代碼量比較長的就放在類外進行定義。

預先處理的函數

還是一樣的，有一些函數由于會被很多次的調用，所以我們需要先處理一下。

尾插函數push_back

尾插函數是非常重要的。特別是在寫構造函數的時候，我們可以提前開好空間，然后將需要的數據依次插入到vector指向的空間中。

所以我們可以實現一下尾插函數：

void push_back(const T& x){if (_end_of_storage == _finish) {reserve((size() == 0) ? 4 : size() * 2);}*_finish = x;++_finish;
}

這里的reserve函數雖然還沒寫，但是當前符合邏輯就可以。只要能在調用方尾插函數前寫完就好。

當然目前先不寫的原因是會有特殊情況，這一點我們等下會說。

swap函數

這個交換函數最大的目的就是為了方便進行深拷貝，其實現也是非常簡單：

void swap(vector<T>& v) {std::swap(_start, v._start);  std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage); 
}

我們直接調用標準庫內的交換函數就可以了。

賦值重載

這個是非常重要的，在等一下的reserve函數中也是需要調用。

這個方法很簡單的，在上一節string實現深拷貝的優化中我們就已經實現過了，所以就不再過多贅述。

T& operator=(vector<T> v) {swap(v);return *this;
}

其實就是調用拷貝構造，構造一個v，使得v就是需要賦值的數據。當然當前我們也沒有實現拷貝構造。但是不要急，我們當前主要還是得厘清邏輯。保證當前接口主邏輯不會出錯即可。

使用這個方法最大的有點就是不用擔心自己給自己賦值。如果要自己開空間來操作賦值，就得先刪掉空間，再來賦值。但是當自己給自己賦值的時候，就會導致原有數據被銷毀。所以需要判斷這個特殊情況。

size函數

這個沒太多好說的，返回容量就好。

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

reserve函數

因為空間的浪費不會太大，所以為了效率更高，防止頻繁擴容，所以我們采用vs底層一樣的實現方法，reserve堅決不縮容。

template<class T>
void vector<T>::reserve(size_t n) {if (n <= size()) return; size_t old_size = size(); T* tmp = new T[n]; //復制for (int i = 0; i < old_size; ++i) { tmp[i] = _start[i]; }delete[] _start; _start = tmp; _finish = _start + old_size;  _end_of_storage = _start + n; 
}

由于代碼量還是比較長的，我們放在類外面進行定義。

這里會有幾個很容易出錯的點：
1.管理內容的三個指針失效
此時我們不再是使用整形變量管理空間。而是使用指針。使用指針最怕的就是野指針。當我們擴容的時候，又需要將舊空間進行釋放。那就會導致_finish和end_of_storage兩個指針變成野指針。所以需要調整這兩個指針的位置。

但是很多人這么寫的：

    _start = tmp; _finish = _start + size();  _end_of_storage = _start + n; 

這樣子會出問題。因為size返回的是當前_start和_finish的位置之差。但是我們發現一個事情，就是當我們先讓_start指向新空間的時候，_finish會指向被釋放的空間。那么這樣算出來的size肯定不對。

還有就是從代入表達式的角度看，size()返回的是_start - _finish，代入表達式，
_finish = _start + _start - _finish = _finish，這根本沒有改變啊。

所以我們得先記錄一下_start和_finish原本的差值，也就是有效數據個數old_size，然后再以此進行調整。源碼中也是這么干的：

所以我們就學習這個方法進行調整這三個管理指針。

還有一個問題就是復制，在之前模擬實現string的時候我們是使用memcpy函數進行操作的。但是再vector中萬萬不能。

假設我們現在聲名的是一個vector< string >，如果使用的是memcpy函數，就是將里面內容一個字節一個字節拷貝過去，這個方式是淺拷貝。那一旦碰到有指向資源的數據類型如string那就糟了，那資源是沒有辦法復制過去的。又或者是vector，也是有指向資源。這是萬萬不能的。具體內容可以看類和對象章節。

所以復制部分是要調用賦值重載的。這也就是為什么我們要先寫賦值重載函數，就是怕內部存儲的也是vector(自己寫的)，那就需要調用其賦值重載函數，那我們就得提供。

迭代器

//實現正向迭代器用的
typedef T* iterator;
typedef const T* const_iterator;//iterator
iterator begin() {return _start;
}
iterator end() {return _finish;
}
const_iterator cbegin() const { return _start;
}
const_iterator cend() const {return _finish;
}

迭代器就是原生指針，實現非常簡單。

默認成員函數

默認構造

vector()
{}

我們會在定義三個管理指針的時候給定缺省參數nullptr，所以不需要存儲任何東西的時候就不需要進行任何操作，所以無參構造函數這樣寫即可。

普通構造

vector(size_t n, const T& val = T()) {reserve(n);while (_finish != _end_of_storage){push_back(val);   ++_finish; }
}vector(int n, const T& val = T()) {reserve(n);while (_finish != _end_of_storage) {push_back(val);}
}template<class InputIterator>
vector(InputIterator first, InputIterator last) {while (first != last) {push_back(*first);++first;}
}

這里的const T& val = T()是調用默認構造函數，前面部分已經講過了。
這里有三個函數，最后一個是迭代器區間構造。

有人看到前面兩個僅僅是n參數類型不同，為什么要多次一舉寫多一個呢？

這是因為當我們想要這樣寫的時候vector(5, 4);，會導致一個問題，因為不寫第二個的那個版本，5在編譯器中默認為int，4也為int，那么第一個就不是那么的匹配。而傳給迭代器區間的時候會更加匹配一些，所以編譯器會調用迭代器區間構造的那個。所以我們需要多寫一個。而使用其他類型的時候就不會有這個問題。

拷貝構造

vector(const vector<T>& v) {reserve(v.size());const_iterator it = v.cbegin();while (it != v.cend()) {push_back(*it);++it;}
}

這里沒有采用以往的那個深拷貝的優化方法。因為在string實現中，我們可以把傳入的string的指向字符串的指針拿去構造出一個一樣的string。而我們在這里并沒有實現這么一個函數，因為只有字符出啊怒這樣做是比較方便。所以我們直接自己開空間進行尾插即可。

析構函數

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

析構函數比較簡單，就不再贅述。

容量操作

現在來對容量的操作進行實現

容量 、判空

size_t capacity() const {return _end_of_storage - _start;
}bool empty() const {return (_start == _finish);
}

數據個數已經在預處理部分處理過了，所以只需要實現一下容量和判空即可。

resize函數

template<class T> 
void vector<T>::resize(size_t n, const T& val) {  //聲名與定義分離時 定義中不能有缺省參數if (n <= size()) {_finish = _start + n; }else {if (_finish + n > _end_of_storage) { size_t old_size = size();size_t old_capacity = capacity();reserve( old_size + n > old_capacity * 2 ? (old_size + n) : old_capacity * 2);}while (_finish != _end_of_storage) { push_back(val); } }
}

根據文檔的要求進行實現即可。注意是否需要刪除數據以及擴容即可。

修改操作

尾刪

void pop_back() {assert(!empty());   --_finish;
}

需要注意是否為空，否則無法刪除。

insert函數

template<class T>
typename vector<T>::iterator vector<T>::insert
(typename vector<T>::iterator pos, const T& val) { assert(pos <= _finish);assert(pos >= _start);size_t old_size = size();size_t posdiff = pos - _start;//必須寫這個 要不然迭代器失效了if (_finish == _end_of_storage) {reserve((old_size == 0) ? 4 : 2 * old_size);pos = _start + posdiff;}//挪動數據typename vector<T>::iterator it = end() - 1;while (it >= pos) {*(it + 1) = *it;--it;}*pos = val;++_finish;return pos;
}

很多人會疑問，為什么要加typename這個關鍵字呢？這是因為我們是在類外面定義這個函數。而這個類此時還沒有實例化，那要從里面取東西是需要特別注意的。對于iterator，編譯器會不知道這是一個變量還是類型名稱。所以加上typename就是告訴編譯器這是一個類型。

注意一下之前講過的迭代器失效的問題即可。

clear函數

這個函數只對數據進行清空，但是不進行縮容：

void clear() {_finish = _start;
}

erase函數

這個函數實現了兩個版本：

template<class T>
typename vector<T>::iterator vector<T>::erase
(typename vector<T>::iterator pos) {assert(pos >= _start);assert(pos <= _finish);//不考慮縮容typename vector<T>::iterator it = pos;while (it != end()) {*it = *(it + 1);++it;}--_finish;return pos;
}template<class T>
typename vector<T>::iterator vector<T>::erase
(typename vector<T>::iterator first, typename vector<T>::iterator last) {assert(first <= last);assert(first >= _start);assert(last <= _finish);assert(!(first == end() && last == end()));vector<T>::iterator prev = first; vector<T>::iterator rear = last + 1;while (rear != end()) {*prev = *rear;++prev;++rear;}_finish = prev;return first;
}

當然insert函數也是可以實現迭代器區間插入的(我忘記了哈哈哈哈哈)，邏輯都不難，最主要的就是注意一下刪除的位置是否合法(通過斷言報錯)，然后實現數據挪動邏輯。然后需要注意迭代器失效得問題，要通過返回值來修正。

最好是通過畫圖來賦值寫代碼，然后考慮一下一些特殊位置即可。

打印函數(針對不同容器)

template<class Container>
void Print_container(Container& con) { for (auto& x : con) { cout << x << " "; }cout << endl;  
}

通過傳入容器以及范圍for得使用就可以實現了，這是十分簡單的。

到此所有的操作就完成了，想要更詳細代碼的可以進入我的碼云空間獲取。