【C++】vector容器實現

一、vector的成員變量

二、vector手動實現

（1）構造

（2）析構

（3）尾插

（4）擴容

（5）[ ]運算符重載

5.1 迭代器的實現：

（6）尾刪

（7）插入

（8）刪除

（9）迭代器失效

9.1 reserve擴容迭代器失效

9.2 insert后迭代器失效

9.3 erase迭代器失效

（10）resize初始化

（11）普通拷貝構造

（12）=運算符重載拷貝構造

三、其他構造方法

（一）initializer_list初始化

（二）迭代器初始化

四、動態二維數組

vector的開始也代表STL學習的開始。接下來將講解如何手動實現部分vector常用接口。

希望在看下面文章之前已經對string類的實現比較了解，或者看過我之前描述string類實現的文章，這樣對理解vector會比較友好。

正文：

一、vector的成員變量

vector學習時一定要學會查看文檔https://cplusplus.com/reference/vector/vector/，vector在實際中非常的重要，我們熟悉常見的接口就可以。

下面就不帶大家看整個vector源碼了，只截取了它成員變量在底層如何聲明的小部分原碼

下圖可知vector原碼核心成員變量就三個迭代器，迭代器跳轉過去其實也是個typedef原生指針（和string類似）所以三個變量就是三個指針。再去看構造函數，它把三個指針初始化成空（不展示），那么之前數組都有大小，vector沒有直接給出就進一步去看原碼怎么算大小和容量的（不展示）。下面實現就模仿庫的形式也定三個迭代器變量。

二、vector手動實現

類模版的聲明和定義一般寫在同一個文件下。創建一個vector.h（類實現過程）和test.cpp（接口測試），為了防止出現命名沖突，我外層套了一層命名空間zss，大家練習過程中可以不套。

下面是模擬原碼實現的vector基礎框架，成員就三個迭代器，vector本身是個順序結構_start代表整個數組，_finish指向最后一個數據的下一個位置，_end_of_storage表示整個數組空間大小。

（1）構造

由于我們在聲明的時候三個指針都給了缺省值nullptr，只要給缺省值了，用戶不傳參初始化列表會直接用缺省值初始化三個成員變量，所以我們提供的構造可以什么都沒有。雖然什么都沒有但是不能直接刪掉，因為如果實現其他構造函數，要初始化三個指針還是得先走初始化列表。

（2）析構

到時候插入數據是需要自己手動new申請一段數組空間的，自己申請的空間析構也要對應匹配delete[ ]清理數據，并把指針置為空。

（3）尾插

push_back尾插之前必須確保有足夠大的空間進行尾插數據，如果沒有就進行空間的擴容，而要獲取到數組空間大小用capacity()函數返回，順便把size也求一下。由于擴容這一操作后面會經常使用所以封裝成一個函數。

（4）擴容

reserve擴容采取深拷貝的思想，先開一段足夠大小的tmp新空間，memcpy將舊空間數據一個字節一個字節拷給新空間，再將舊空間_start釋放掉，把新空間tmp賦值給_start（reserve函數調用結束tmp自動銷毀）最后更新一下_finish和_end_of_storage數據。

這里要注意的點是size()大小問題，大家看我還要再定個oldsize 變量存size()大小可能感到很奇怪，上面不是已經實現了size()函數，已經可以獲取到數組大小了嗎，怎么還多此一舉存一下。

這里涉及到拷貝后_finish大小報錯問題：

一開始我們計算的size()大小是還沒替換空間前size的大小，替換空間后_start已經不再是原來空間而size卻還是原來空間，兩個不同空間的指針相加是會報錯的，所以要用oldsize 變量存size()大小，這樣_finish = _start + oldsize加的大小才是正確的。

（5）[ ]運算符重載

在數組的遍歷中，最常用的就是[ ]、迭代器和范圍for。內置類型下標遍歷轉換為解引用，自定義類型要實現下標遍歷得重載運算法。有時候打印的數據具有常性不允許改變需要調用const版本，所以下面也實現了個const版本。

[ ]的實現：

5.1 迭代器的實現：

迭代器的實現也有分普通類型和const類型，const類型迭代器并不是在迭代器前面加個const就行，這是限制迭代器本身不能改變，而我們要的是數據不能改變，所以要typedef提供一個新的迭代器類型。

迭代器的行為是模擬指針并不代表它就是指針

使用：

范圍for遍歷：
范圍for看起來很高大上，很便利，其實底層是依靠迭代器的實現，只要實現了迭代器范圍for直接用。所以變層看似有[ ]、迭代器和范圍for三種遍歷方式，實際上只有[ ]和迭代器。

（6）尾刪

pop_back尾刪很簡單，想象一下數組尾刪是不是只要改變數組個數就好，同理vector尾刪--_finish就行，到時候插入也是從_finish位置重新覆蓋插入。

（7）插入

insert在任意位置插入一個元素，只要和插入有關都先考慮內存夠不夠問題，不夠擴容。

如果是在中間插入是要把pos位置及之后數據向后移動一位再進行插入，移動利用迭代器更高效。

（8）刪除

erase刪除pos位置元素，同樣利用迭代器將數據移動覆蓋，最后--_finish個數。

要注意的是erase返回值還是一個迭代器，這是為了防止迭代器失效問題。

（9）迭代器失效

迭代器的主要作用就是讓算法能夠不用關心底層數據結構，其底層實際就是一個指針，或者是對指針進行了封裝，比如：vector的迭代器就是原生態指針T* 。因此迭代器失效，實際就是迭代器底層對應指針所指向的空間被銷毀了，而使用一塊已經被釋放的空間，造成的后果是程序崩潰(即如果繼續使用已經失效的迭代器，程序可能會崩潰)。對于vector可能會導致其迭代器失效的操作有：會引起其底層空間改變的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、push_back等。

9.1 reserve擴容迭代器失效

第一張圖代碼是一開始正常邏輯沒修改過的代碼，reserve內部會開新空間然后拷貝賦值銷毀，通過調試看到，原本指向上面空間的_start指針指向了下面新開的空間，這些都很合理，但是insert在pos位置插入數據，這個pos還指向被銷毀了的原空間，當下面while循環時it在新空間內向左移動找舊pos是永遠找不到的。

遇到這種問題，要更新迭代器讓pos指向新空間的原始位置，怎么計算就是：一開始要算出pos距離首元素大小，等擴容完了更新，請看第二張代碼圖。

9.2 insert后迭代器失效

VS默認insert后迭代器全部失效，這條沒有解決辦法，唯一的辦法就是：別用！！！

9.3 erase迭代器失效

通過以下部分代碼演示：刪除數組中的所有偶數，在刪除的過程中++it會使判斷條件被跳過

圖二：erase內部刪除pos位置元素，后面元素會自動向前移一位，這時3覆蓋2，但++it使3被跳過判斷了。

圖三：如果偶數在最后一個呢？_finish覆蓋4，但又++it使結束條件直接跳過，野指針訪問

圖一? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 圖二? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?圖三

以上情況也是更新一下迭代器就行，erase有返回值只要重新接收返回值就OK

（10）resize初始化

resize的改變會影響數組的數據個數，數據不夠就插入，太多就刪數據，不夠還空間不足就擴容+插入

第二個參數不是必須給的，當用戶沒給第二個參數時匿名對象初始化；int就是0，指針就nullptr

（11）普通拷貝構造

有兩種寫法v2(v1)和v2=v1，這兩種都可以考慮復用寫過的代碼實現

（12）=運算符重載拷貝構造

現代寫法：

一種很妙的寫法，通過參數傳遞的淺拷貝思想和swap實現。v里面的數據等函數運行結束自動銷毀，而我們想要的已經通過*this返回了。

三、其他構造方法

（一）initializer_list初始化

下面寫法大家在刷題時是不是經常看到，這是C++11的一種構造方式，專門用于支持花括號 {}?初始化語法。它提供了一種統一的方式來初始化各種容器和自定義類型。

用法：

實現：復用reserve和push_back

（二）迭代器初始化

迭代器初始化引入了一個新概念，類模板的成員函數也可以是模板，這樣不用固定整個類的迭代器，任意類型的迭代器都可以初始化了。

實現：還是復用了push_back，使整體代碼更簡潔

四、動態二維數組

vector<vector<int>>它本質上是一個二維動態數組，模版變量可以是任何類型的指針，當然也可以是vector<int>*指針類型。

想象?vector<vector<int>>?就像一組可以伸縮的抽屜柜：

外層 vector：這是一個大柜子，里面可以放很多抽屜（每個抽屜就是一個?vector<int>）

每個內層 vector：每個抽屜里可以放很多整數（int），而且每個抽屜的大小可以不一樣

案例：力扣——楊輝三角

與靜態數組對比的好處：

靜態數組（如?int arr[3][4]）：大小固定、每行長度必須相同、內存連續

vector<vector<int>>：大小可變、每行長度可以不同、內存不一定完全連續（外層連續，內層各自連續）

完整vector手動實現代碼如下：

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;namespace zss
{template<class T>class vector{public:typedef T* iterator;//const 迭代器typedef const T* const_iterator;size_t capacity()const{return _end_of_storage - _start;}size_t size()const{return _finish - _start;}//迭代器iterator begin(){return _start;}iterator end(){return _finish;}//const迭代器const_iterator begin()const{return _start;}const_iterator end()const{return _finish;}//1.構造//這玩意什么都不寫也不能因為在聲明給缺省值就刪掉//因為自己實現了拷貝構造或者其他構造刪掉就不是自動生成了//可能我們自己也會寫其他構造initialize_list，允許用 { } 初始化對象vector(){}//13.initializer_list初始化vector(initializer_list<T> il){//走初始化列表把三個指針初始化了然后直接開空間尾插reserve(il.size());for (auto& e : il){push_back(e);}}//14.迭代器初始化//類模板的成函數模板，這樣不用類的迭代器，任意迭代器都可以template<class InputIierator>vector(InputIierator first, InputIierator end){while (first != end){push_back(*first);++first;}}//2.析構~vector(){delete[] _start;_start = _finish = _end_of_storage = nullptr;}//3.尾插void push_back(const T& x){if (_finish == _end_of_storage){//擴容//沒有容量就通過capacity()函數獲取一個reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;++_finish;}//4.擴容void reserve(size_t n){//可能reserve被單獨調用所以再判斷一次容量if (n > capacity()){//這里原本_start、_finish、_end_of_storage都指向同一塊空間//拷貝了_start指向新的空間，你用兩個不同空間指針相減不可能得到size//所以更新前保存一下size()size_t oldsize = size();T* tmp = new T[n];//memcpy(tmp, _start, sizeof(T) * oldsize);//自定義類型string不能用memcpy，會指向同一塊空間釋放多次for (int i = 0; i < oldsize; i++){tmp[i] = _start[i];}delete[] _start;_start = tmp;_finish = _start + oldsize;_end_of_storage = _start + n;}}//5.[]T& operator[](size_t i){assert(i < size());return _start[i];}//6.const[]const T& operator[](size_t i)const{assert(i < size());return _start[i];}//7.尾刪void pop_back(){assert(_finish > _start);--_finish;}//8.插入void  insert(iterator pos, const T& x){assert(pos >= _start);assert(pos <= _finish);//擴容if (_finish == _end_of_storage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}//插入，因為是迭代器不存在沒有小于0的情況iterator it = _finish - 1;while (it >= pos){*(it + 1) = *it;--it;}*pos = x;++_finish;}//9.刪除元素iterator erase(iterator pos){assert(pos >= _start);assert(pos <= _finish);iterator it = pos + 1;while (it < _finish){*(it - 1) = *it;++it;}_finish--;return pos;}//10.迭代器失效處理//11.resizevoid resize(size_t n, const T& val = T()){if (n < size())_finish = _start + n;else{reserve(n);while (_finish != _start + n){*_finish = val;++_finish;}}}//12.拷貝構造v2(v1)vector(const vector<T>& v){reserve(v.size());for (auto& e : v){push_back(e);}}//v2=v1//vector<T>& operator=(const vector<T>& v)//{//	if (this != &v)//	{//		//如果有值先釋放掉//		delete[] _start;//		_start = _finish = _end_of_storage = nullptr;//		//開新的空間//		reserve(v.size());//		//拷貝數據//		for (auto& e : v)//		{//			push_back(e);//		}//	}//	return *this;//}//現代寫法void swap(vector<T>& v){std::swap(v._start, _start);std::swap(v._finish, _finish);std::swap(v._end_of_storage,_end_of_storage);}vector<T>& operator=(vector<T> v){swap(v);return *this;}private://模擬STL庫的實現iterator _start=nullptr;iterator _finish=nullptr;iterator _end_of_storage=nullptr;};
}

下次繼續一起學習，感謝觀看~