@TOC(手搓一個STL風格的vector容器)
手搓一個STL風格的vector容器
github地址
有夢想的電信狗
0. 前言：動態數組的工程實踐
? 在C++標準庫中，vector容器作為最核心的序列式容器，其設計融合了動態數組的高效性與安全性。本文將通過完整實現一個簡化版vector容器，重點剖析迭代器失效、深拷貝控制、動態擴容等關鍵問題。代碼實現將保持與STL兼容的接口設計。
? 有了之前實現string的經驗，我們實現vector也就相對容易了。
1. 基礎架構設計
1.1 成員變量與迭代器
- 為了和標準庫中的
vector區分，我們把自己實現的vector封裝在m_vector這個命名空間中 vector的底層是就是順序表，采用順序表的結構來實現即可，重點掌握和STL中的順序表普通的順序表的實現有哪些不同- 基本結構如下：
namespace m_vector {template<class T>class vector {public://將原生指針封裝為迭代器typedef T* iterator; typedef const T* const_iterator;//迭代器與const對象迭代器iterator begin() { return _start; }const_iterator begin() const { return _start; }iterator end() { return _finish; }const_iterator end() const { return _finish; }public:// ... 一系列成員函數實現private://與標準庫STL中的命名風格保持一致iterator _start; // 指向數組首元素iterator _finish; // 指向最后一個元素的下一個位置iterator _end_of_storage; // 指向存儲空間末尾};
}
設計要點：
-
三指針架構是
STL vector的經典實現，結合上圖理解三指針架構：_start：數據起始位置_finish：有效數據結束標記_end_of_storage：容量邊界標記
-
原生指針實現迭代器，保持與
STL兼容typedef T* iterator，typedef const T* const_iteratorbegin()返回_start，分別實現普通對象版本和const對象版本end()返回_finish，分別實現普通對象版本和const對象版本
-
模板化設計支持任意元素類型
-
成員變量設為訪問權限設為
private, 對外提供public的成員函數和定義的類型，符合面向對象中封裝的思想
1.2 容量獲取
// 指針 - 指針 得到中間的元素個數
size_t capacity() const {return _end_of_storage - _start;
}
size_t size() const {return _finish - _start;
}
bool empty() const {return _start == _finish;
}
-
指針 - 指針：可以實現返回兩個指針中間的元素個數
_end_of_storage - _start：得到總容量個數_finish - _start：得到有效元素個數
-
==判空：==數據標記指針
_start == _finish時，表示順序表中無數據
2. 構造與析構
2.1 默認構造與析構函數
//默認構造函數
//我們寫的邏輯是 構造時暫不開空間
vector():_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{ }//析構函數
~vector() {if (_start) {delete[] _start;_start = _finish = _end_of_storage = nullptr;}
}
默認構造函數
- 將指針都初始化為
nullptr - 默認構造（無需傳參即可調用的構造函數），我們設計為空構造，不開辟空間
析構函數
-
_start不為空時再進行析構，即有數據時才進行析構 -
delete[] _start：清理連續的數組空間。- 若數組內為內置類型，直接清理空間
- 若數組內為自定義類型，
delete[]會依次調用數組內每個對象的析構函數
-
_start = _finish = _end_of_storage = nullptr：設置三指針為nullptr
2.2 深拷貝控制
這里的相較于string中的深拷貝，有著更高的要求：string中存放的是內置類型char，而vector中內置類型和自定義類型都可能存放
- 首先需要保證
vector之間互相拷貝時，vector對象本身的數據獨立性 - 其次還要保證：當
vector中存放的數據是自定義類型時，拷貝時也要為每個自定義類型實現深拷貝
- **寫法1：**手動開空間，手動釋放內存
// 拷貝構造函數
vector(const vector<T>& v): _start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{_start = new T[v.capacity()];//memcpy(_start, v._start, sizeof(T) * v.size()); // 不能使用memcpy,memcpy拷貝自定義類型時會出現錯誤for (size_t i = 0; i < v.size(); ++i) {_start[i] = v[i];}_finish = _start + v.size();_end_of_storage = _start + v.capacity();
}
-
初始化列表將待構造對象的指針初始化為
nullptr -
_start = new T[v.capacity()]：為該對象申請空間，new會為數組中的每個元素，調用類型T的默認構造函數 -
vector中既可能存放內置類型，也可能存放自定義類型，因此拷貝數據時應該實現深層次的深拷貝。不能使用memcpy，因為memcpy進行的是值拷貝，也就是淺拷貝。淺拷貝會導致兩個指針指向同一塊空間，對象生命周期結束時，對同一塊空間析構兩次會導致報錯-
//memcpy(_start, v._start, sizeof(T) * v.size());for (size_t i = 0; i < v.size(); ++i) {_start[i] = v[i]; // 用自定義類中的 = 重載實現深拷貝類型的拷貝// 該寫法也可以滿足內置類型的拷貝的需求，內置類型本身就可以用=賦值} -
這里使用
for循環依次賦值，調用了自定義類型的operator=來實現深拷貝。內置類型可以直接用=賦值，自定義類型的operator=應當實現深拷貝
-
-
更新狀態指針：終地址等于起始地址 + 偏移量
_finish = _start + v.size()：_finish的偏移量為已有對象的size()_end_of_storage = _start + v.capacity()：_end_of_storage的偏移量為已有對象的capacity()
**寫法2：**復用類中的其他函數
vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{reserve(v.capacity());for (auto& e : v)push_back(e);
}
-
首先初始化列表，初始化當前對象為空
vector對象 -
調用
reserve開空間，同時將當前vector對象內成員變量存儲的地址更新為有效地址。reserve有兩個作用：- 為數據開辟足夠的空間
- 更新三指針指向非0地址，也就是有效地址
-
再將需要拷貝的數據依次尾插到當前對象中。
-
由于我們的
push_back的實現中采用的是**=賦值**，因此內置類型會直接值拷貝，自定義類型會調用其operator=函數，完成深拷貝。
2.3 用n個val構造和迭代器區間構造
n個val構造
// 用n個val構造 復用resize 時，三個指針應該初始化
vector(size_t n, const T& val = T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr) // 成員變量給了缺省值時，可以不寫初始化列表{ resize(n, val);}
- 用
n個val初始化時，我們可以直接復用resize。但使用n個val初始化時，val是可以有默認值的，但如何確定參數的類型？
內置類型的默認構造函數：
resize初始化，val是可以有默認值(缺省參數)的，但如何確定缺省參數的類型?- 此時形參
T()本質是一個T類型的匿名對象 ，會調用T類型的默認構造。因此寫一個類，一定要提供默認構造 - 如果傳入的是
int等內置類型resize怎么運行？理論上不能運行。但C++有了模板后，C++對內置類型進行了升級，也支持內置類型有默認構造函數
內置類型的默認構造函數使用示例：
- 內置類型的默認構造：
int默認構造為0double默認構造為0.0- 指針類型默認構造為
nullptr
- 因此
T()匿名對象既可以滿足內置類型，也可以滿足自定義類型。
迭代器區間構造
- 用一個迭代器區間進行構造初始化
// 類模板內的成員函數，依然可以再是另一個模板函數
// [first, last]
template<typename InputIterator>
vector(InputIterator first, InputIterator last) {while (first != last) {push_back(*first); // vector<int> v(10, 1); 構造時匹配錯誤，匹配成了迭代器區間初始化// 然后 int 不能解引用，因此報錯++first;}
}
-
我們的實現思路十分簡單：
- 對所有支持迭代器的容器，將區間
[first, last)區間內的數據構造成為一個vector - 我們只需循環遍歷區間，
push_back(*first)對每個地址的元素解引用后尾插入vector即可。之后first指針再++
- 對所有支持迭代器的容器，將區間
-
但是當我們編譯時，卻發生了錯誤：
-
-
-
錯誤輸出信息如上，我們閱讀后，初步推斷該報錯信息與模板有關。可能是和模板的匹配有關！
-
觀察我們的構造函數：
mm_vector::vector<int> v1(10, 1);參數類型為10, 1。10和1這樣的字面量，在C++中默認是int。再看我們現有的構造函數：參數數量為2的構造函數只有以下兩個：vector(size_t n, const T& val = T());類型為size_t, T，兩參數類型不同- ``vector(InputIterator first, InputIterator last);
類型為T, T`，兩參數類型想通
-
由于
v1(10, 1)兩個參數的類型為int, int，類型相同，因此在模版函數匹配時，編譯器自動匹配了類型更合適的T, T。而我們該構造函數的實現中，有*first行為，而int類型無法解引用，因此報錯。 -
解決該問題，只需額外為
int, int類型提供一個構造函數，使int, int類型的調用不要匹配到迭代器區間初始化即可。
// mm_vector::vector<int> v(10, 1); int int 匹配 size_t int 還是 int int(T, T)
// 當然是 int int(T, T)
// mm_vector::vector<int> v1(10u, 1); unsigned int, int 匹配 size_t int 還是 int int。
// 當然是 size_t int
// mm_vector::vector<string> v2(10, "hello"); int char* 匹配 int T 更加合適
vector(size_t n, const T& val = T()) {resize(n, val);
}
//多提供一個 int int 類型的構造
vector(int n, const T& val = T()) { resize(n, val);
}
// 用一個迭代器區間進行初始化
// [first, last]
template<typename InputIterator>
vector(InputIterator first, InputIterator last) {while (first != last) {push_back(*first); ++first;}
}
- 多提供一個形參類型為
int int的構造后就不報錯了
3. 容量管理
3.1 reserve擴容策略
- 我們的擴容策略是針對
capacity的，拷貝空間時，不僅拷貝[_start, _finish)之間的數據，同時拷貝[_start, _end_of_storage)之間的所有空間
void reserve(size_t newCapacity) {if (newCapacity > capacity()) {T* newSpace = new T[newCapacity];size_t old_sz = size(); // 記錄 _finish 相對于 _start 的偏移量// 拷貝數據if (_start) {//memcpy(newSpace, _start, sizeof(T) * old_sz);for (size_t i = 0; i < old_sz; ++i) {newSpace[i] = _start[i]; // 用自定義類中的 = 重載實現深拷貝類型的拷貝// 該寫法也可以滿足內置類型的拷貝的需求，內置類型本身就可以用=賦值}delete[] _start;}// 如果原vector無數據，但申請了更大的空間，該函數也會擴容并分配空間_start = newSpace;_finish = _start + old_sz;_end_of_storage = _start + newCapacity;}
}
// 不能用以下方法計算 _finsih, 只能通過記錄偏移量的方式來計算 _finish
// _finish = _start + size(); // 該實現有問題，這樣寫_finish的值沒變
// 上述表達式size() _start 指向新空間了，但此時_finish仍然指向舊空間
思路分析與關鍵點：
-
異地擴容保證強異常安全
-
reserve擴容不是只給push_back用，使用需要檢查是否需要擴容 -
newSpace記錄新空間的起始地址。old_sz記錄有效元素數量，可標識_finish相對于_start的位置，方便擴容后更新_finsih- 形參
newCapacity記錄容量個數，可表示_end_of_storage相對于_start的位置，方便擴容后更新_end_of_storage
-
vector中既可能存放內置類型，也可能存放自定義類型，因此拷貝數據時應該實現深層次的深拷貝。不能使用memcpy，因為memcpy進行的是值拷貝，也就是淺拷貝-
for (size_t i = 0; i < old_sz; ++i) {newSpace[i] = _start[i]; // 用自定義類中的 = 重載實現深拷貝類型的拷貝// 該寫法也可以滿足內置類型的拷貝的需求，內置類型本身就可以用=賦值} -
這里使用
for循環依次賦值，調用了自定義類型的operator=來實現深拷貝。內置類型可以直接用=賦值，自定義類型的operator=應當實現深拷貝
-
-
delete[] _start釋放舊空間 -
最終利用相對偏移量更新指針：
_start = newSpace;_finish = _start + old_sz;_end_of_storage = _start + newCapacity;
reserve中的其他關鍵實現：
void reserve(size_t newCapacity) {if (newCapacity > capacity()) {T* newSpace = new T[newCapacity];size_t old_sz = size(); // 記錄 _finish 相對于 _start 的偏移量// 拷貝數據if (_start) {for (size_t i = 0; i < old_sz; ++i) newSpace[i] = _start[i]; delete[] _start;}_start = newSpace;_finish = _start + old_sz;_end_of_storage = _start + newCapacity;}
}
- 關鍵點：
- 在該
reserve函數的實現中：如果一個空構造的vector對象(初始指針均為nullptr)，也就是該vector對象沒有實際的內存空間。若該被空構造出來的對象，直接調用reserve后，對象內的三個指針就都變成了有效地址。可以大膽的對這三個指針進行解引用訪問操作。
- 在該
- 原理分析：
- 空對象的
capacity()一定為0，因此調用reserve時會進入擴容邏輯。我們的reserve函數的實現，不管_start掌管的空間中是否有數據，都會開辟一段大小為newCapacity的空間。空對象的_start指針為nullptr，不會進入拷貝數據的邏輯。之后，_start被賦值為newSpace（開辟的新空間的地址）。_finsih和_end_of_storage經過相對偏移地址計算后，也就變成了有效地址
- 空對象的
3.2 resize彈性調整
// 初始化 n 個數據
void resize(size_t n, const T& val = T()) {// 要求size 變小時，直接 改 _finishif (n < size())_finish = _start + n;// 要求size 變大時，多出來的空間用val初始化else {reserve(n); // n 小于 capacity時，reserve什么都不做，大于時擴容// 將多出來的空間用val填充while(_finish != _start + n){*_finish = val;++_finish;}}
}
雙重模式思路：
- 要求
size變小時，直接修改_finish指針 - 要求
size變大時，不管n是否大于capacity，都調用reserve，多出來的空間用val初始化n是新空間中總容量的個數，_start + n表示了_end_of_storage的位置- 從
[_finish, _start + n)這塊連續空間是需要用val初始化的，面對自定義類型時，采用調用operator=的方式依然可以完成深拷貝。
內置類型的默認構造函數：
resize初始化，val是可以有默認值(缺省參數)的，但如何確定缺省參數的類型?- 此時形參
T()本質是一個T類型的匿名對象 ，會調用T類型的默認構造。因此寫一個類，一定要提供默認構造 - 如果傳入的是
int等內置類型resize怎么運行？理論上不能運行。但C++有了模板后，C++對內置類型進行了升級，也支持內置類型有默認構造函數
內置類型的默認構造函數使用示例：
- 內置類型的默認構造：
int默認構造為0double默認構造為0.0- 指針默認構造為
nullptr
4. 迭代器失效專題
4.1 insert實現與失效分析
內部和外部迭代器失效
insert和erase的實現和順序表的插入實現思路一致，這里不在細致分析。我們直接關注insert的迭代器失效問題
**迭代器失效引入：**這里我們先使push_back通過調用insert函數來實現
void push_back(const T& obj) {//// 判斷是否需要擴容//if (_finish == _end_of_storage) {// size_t newCapacity = (capacity() == 0 ? 4 : capacity() * 2);// reserve(newCapacity);//}//// 插入邏輯//*_finish = obj;//++_finish;insert(end(), obj);
}
// 會出現迭代器失效的insert函數
void insert(iterator pos, const T& obj) {assert(pos >= _start && pos <= _finish); // 保證插入位置正確// 擴容邏輯if (_finish == _end_of_storage) {size_t newCapacity = (capacity() == 0 ? 4 : capacity() * 2);reserve(newCapacity);}// 挪動元素iterator end = _finish - 1;while (end >= pos) {*(end + 1) = *end;--end;}// 插入數據*pos = obj;++_finish;
}
// 測試迭代器失效的代碼
int main() {mm_vector::vector<int> v1;v1.reserve(4);v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);//v1.push_back(5);for (auto& e : v1)cout << e << " ";cout << endl;return 0;
}
- 將v1的空間設置為4，插入四個元素后，遍歷元素，這里結果正確
-
再插入第五個元素時，第五個元素變成了隨機值。
-
-
這就是著名的迭代器失效問題。insert的迭代器失效主要發生在擴容時
迭代器失效與我們insert函數的實現方式有關。
- insert函數使用時，是形參pos接受一個迭代器類型的指針，在pos位置插入。而
pos是一個指針，指向一段空間中的某個位置。 - 如果插入元素時，
vector內部的空間足夠，沒有發生擴容，那么不會出現迭代器失效。 - 如果因為空間不夠而發生了擴容，由于我們實現的擴容策略是異地擴容，擴容后數據的地址發生更新，而pos的值沒有更新，指向的仍然那是之前舊空間位置的地址。由于我們擴容拷貝數據后就將之前的空間釋放銷毀了，因此
pos指向的不是我們想要插入數據的位置。這樣pos就失效了。這種問題被稱為迭代器失效 - 上圖的場景就是如此：
reserve設置vector的空間為4個，插入前四個元素時一切正常。插入的第五個元素變成了隨機值，就是因為插入第五個元素時發生了擴容，原來的pos指針沒有更新，產生了迭代器失效問題
迭代器失效問題的圖解：
通過圖解，我們可以輕松得知，迭代器失效的本質是擴容后pos指針的失效。那么解決此類迭代器失效，只需要在擴容后，將pos的值設置正確即可解決。
pos是指針，記錄的是地址。雖然擴容后pos的具體值我們不知道是多少，但是我們知道，pos相對于_start的值是不變的- 因此我們可以記錄下pos相對于_start的位置，擴容后利用這個相對值，更新pos的值為正確的地址
完成更新pos值的insert函數
void insert(iterator pos, const T& obj) {assert(pos >= _start && pos <= _finish); // 保證插入位置正確// 擴容邏輯if (_finish == _end_of_storage) {size_t len = pos - _start; // 記錄 pos 相對于 _start 的位置size_t newCapacity = (capacity() == 0 ? 4 : capacity() * 2);reserve(newCapacity);// 擴容后更新pos的值，防止迭代器失效pos = _start + len;}// 挪動元素iterator end = _finish - 1;while (end >= pos) {*(end + 1) = *end;--end;}// 插入數據*pos = obj;++_finish;
}
-
可以看到，更新完pos之后，我們多插入一些數據，即便觸發了兩次擴容，插入結果依然是正確的
-
-
如上解決的問題，本質是解決了內部的迭代器失效，因為迭代器
pos的失效發生在函數內部
還有外部迭代器失效問題
-
我們不能排除有人會寫出這樣的代碼：
-
mm_vector::vector<int>::iterator p = v1.begin() + 3;v1.insert(p, 300);for (auto& e : v1)cout << e << " ";cout << endl;*p += 100; -
完整測試用例：
-
int main() {mm_vector::vector<int> v1;v1.reserve(4);v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (auto& e : v1)cout << e << " ";cout << endl;// 外部迭代器失效// 不能排除有人會這樣子調用insert函數mm_vector::vector<int>::iterator p = v1.begin() + 3;v1.insert(p, 300);for (auto& e : v1)cout << e << " ";cout << endl;*p += 100;for (auto& e : v1)cout << e << " ";cout << endl;return 0;}
-
-
對已有四個數據的
vector在進行插入，顯式定義了一個迭代器p，指向第四個位置。插入之后，又對p解引用修改第四個位置的值。但由于插入時發生了擴容，插入后p已經失效，因此對*p的修改不會發生。
可以看到，對p位置數據的修改沒有發生。這種問題被稱為外部的迭代器失效問題。
-
外部的迭代器失效問題我們無法解決，因為==不同編譯器平臺實現的擴容策略不同，我們無法預知庫中實現的vector何時發生擴容！==我們來看標準庫中的應對策略。
-
-
標準庫中，返回了指向新插入元素的位置的迭代器。因此最終解決方案如下：
-
// 解決內部和外部迭代器的最終insert實現方案iterator insert(iterator pos, const T& obj) {// 保證插入位置正確assert(pos >= _start && pos <= _finish);// 擴容邏輯if (_finish == _end_of_storage) {size_t len = pos - _start; // 記錄 pos 相對于 _start 的位置size_t newCapacity = (capacity() == 0 ? 4 : capacity() * 2);reserve(newCapacity);// 擴容后更新pos的值，防止迭代器失效pos = _start + len;}// 挪動元素iterator end = _finish - 1;while (end >= pos) {*(end + 1) = *end;--end;}// 插入數據*pos = obj;++_finish;return pos;} -
這樣的目的在于：
- 調用
insert之后，如果想訪問新插入的元素，應該通過insert函數的返回值來訪問，而不是通過原來傳給形參pos指針的實參來訪問。
- 調用
insert總結
insert之后，迭代器有可能會失效(主要會在發生 擴容時 迭代器失效)，但不同平臺的擴容策略不同。因此我們無法預知何時會發生擴容，也就無法預知何時迭代器會失效。insert之后，不要再使用這個實參迭代器了，因為insert后，迭代器可能失效- 正確的做法是，使用
insert返回的迭代器來訪問新插入的值。
- 正確的做法是，使用
- 綜上：
insert這樣的接口是不安全的，因此我們應當直接認為insert后，迭代器會失效
4.2 erase實現與失效處理
有了insert失效的例子，我們很容易可以理解erase的失效問題：
iterator erase(iterator pos) {assert(pos >= _start && pos < _finish);// 前移覆蓋元素iterator begin = pos + 1;while (begin < _finish) {*(begin-1) = *begin; // 深拷貝賦值++begin;}--_finish;return pos; // 返回刪除位置的新迭代器
}
- 我們的
erase的實現是挪動數據完成覆蓋，從而完成元素的刪除。 erase(pos)刪除pos位置的元素。當pos指向最后一個元素時，當我們通過erase(it)刪除完最后一個元素，再通過迭代器去訪問時，該位置可能會出現隨機值。- 這是因為，我們通過
erase刪除元素，會進行數據的挪動。挪動后，迭代器指向的值已經不再是刪除前的值了。此時再使用迭代器訪問，會導致迭代器失效，可能出現隨機值！并且VS平臺下，會對erase刪除后再利用先前的迭代器訪問元素進行強制報錯檢查！
auto it = v1.begin() + 3;
v1.erase(it);
for (auto& e : v1)cout << e << " "; cout << endl;
*it = 100; // 報錯！
cout << *it << endl;
- 可以看到，刪除最后一個元素后，最后一個位置的空間已經不屬于我們，因此不能再使用
*pos訪問元素了
5. 元素操作實現
push_back
void push_back(const T& obj) {if (_finish == _end_of_storage) {reserve(capacity() == 0 ? 4 : capacity()*2);}*_finish = obj; // 運算符=重載依賴++_finish;//insert(end(), obj);
}
if (_finish == _end_of_storage)：首先檢查當前vector是否需要擴容reserve(capacity() == 0 ? 4 : capacity()*2)：如果容器當前容量為0，那么擴容為4個空間。如果不為0但需要擴容，那么執行二倍擴容策略
- _finish指向最后一個元素的下一個位置：解引用，賦值，完成尾插
- 此處調用的是賦值：內置類型直接復制，自定義類型會調用其
operator=，保證了自定義類型的深拷貝正確 - 賦值后
_finish++，標識有效數據個數加一
- 此處調用的是賦值：內置類型直接復制，自定義類型會調用其
pop_back
void pop_back() {erase(--end());
}
-
這里的
pop_back尾刪，我們直接調用erase函數即可，傳入最后一個元素的位置指針，也就是--end() -
有興趣的讀者可以自主實現一個不依賴
erase函數的尾刪
6. 運算符重載
6.1 []下標訪問
// 普通vector對象[]重載
T& operator[](size_t pos) {assert(pos < size());return _start[pos];
}
// const vector對象[]重載
const T& operator[](size_t pos) const {assert(pos < size());return _start[pos];
}
operator[]的實現較為簡單assert(pos < size())對要訪問的位置進行斷言強制檢查，防止越界訪問- 之后返回空間中
pos位置的值_start[pos] - 普通對象返回
T&，const對象返回const T&;
6.2 流操作符
- 流操作符，我們為了符合使用習慣，我們將
operator<<聲明為友元函數
template<typename T>
class vector {
public:template<class T1> // 模板函數，聲明和定義處都要寫上 template<class T1>friend ostream& operator<<(ostream& out, const vector<T1>& v);
public:// 其他成員函數
private:// 成員變量
}
// 函數實現
template<class T1>
ostream& operator<<(ostream& out, const vector<T1>& v) {for (auto& e : v) out << e << " ";return out;
}
- 為了符合使用
<<的使用習慣，我們將operator<<聲明為友元函數 - 在函數內，實現對
vector中元素的遍歷 return ostream&類型的對象，滿足流插入運算符<<的連續調用
6.3 operator=
operator=的實現，我們同樣要實現深層次的深拷貝
// = 重載 深拷貝
// v2 = v1
// 自定義類型值傳參時，會調用拷貝構造函數，我們已經實現了深拷貝
// operator= 的深拷貝
vector<T>& operator=(vector<T> tmp) {swap(tmp);return *this;
}
// 兩個vector交換
void swap(vector<T>& v) {std::swap(v._start, _start);std::swap(v._finish, _finish);std::swap(v._end_of_storage, _end_of_storage);
}
- 由于我們已經有了實現
string的經驗，因此實現vector的operator=最好直接采用現代寫法 operator=調用時，由于參數類型為值傳遞，根據C++中函數參數傳遞的規則：- 函數調用要先傳參
- 內置類型值傳參：直接拷貝
- 自定義類型值傳參：調用其拷貝構造函數
- 用
v2 = v1賦值來舉例，傳參過后，調用swap函數之前的結果的結構圖如下：
- 現在
v2想要變得和v1一模一樣，且要內存資源獨立。我們調用swap(tmp)函數，結構圖如下： - v2和tmp中的所有指針的值進行了交換：
tmp接管了v2的數據，v2拿到了tmp中的和v1完全相同的數據，同時_finsih和_end_of_storage指針也和v1的一樣，這樣就完成了v2 = v1，即將v1對象的值內存安全地賦值給v2- 之后由于
tmp為函數局部對象，函數調用結束后自動銷毀，銷毀時自動調用析構函數，清理接管的v2中的資源，內存完全安全。
- 這樣我們就優雅地完成了
operator=的實現。
7. 成員變量缺省值與完整實現
成員變量缺省值優化初始化列表
? 我們知道，在C++11的更新中，成員變量可以有缺省值，用于初始化列表使用。這一特性可以使我們的構造函數無需再寫初始化列表了，只需在成員變量聲明的同時定義初始缺省值即可。
class vector{
public:// 成員函數...
private://成員變量命名與標準庫STL中的命名風格保持一致//可以用C++11中的 成員變量缺省值 給初始化列表使用 這樣在構造函數中，就不用寫初始化列表了iterator _start = nullptr; iterator _finish = nullptr; iterator _end_of_storage = nullptr;
public:// 優化后的構造函數vector() // 默認構造{ }// n 個 val構造vector(size_t n, const T& val = T()) { resize(n, val);}vector(int n, const T& val = T()) { //多提供一個 int int 類型的構造resize(n, val);}// 迭代器區間構造template<typename InputIterator>vector(InputIterator first, InputIterator last) {while (first != last) {push_back(*first); ++first;}}// 拷貝構造函數vector(const vector<T>& v) {_start = new T[v.capacity()];for (size_t i = 0; i < v.size(); ++i) {_start[i] = v[i];}_finish = _start + v.size();_end_of_storage = _start + v.capacity();}// 拷貝構造函數二選一即可vector(const vector<T>& v) {reserve(v.capacity());for (auto& e : v)push_back(e);}
};
優化后的完整代碼實現
#pragma once#include <iostream>
#include <vector>
#include <algorithm>
#include <assert.h>
#include <string.h>
#include <stdlib.h>
using namespace std;namespace mm_vector {template<typename T>class vector {public:template<class T1>friend ostream& operator<<(ostream& out, const vector<T1>& v);typedef T* iterator;typedef const T* const_iterator;iterator begin() { return _start; }iterator end() { return _finish; } // end是最后一個元素的下一個位置const_iterator begin() const { return _start; }const_iterator end() const { return _finish; }// 指針 - 指針 得到中間的元素個數size_t capacity() const {return _end_of_storage - _start;}size_t size() const {return _finish - _start;}bool empty() const {return _start == _finish;}private://與標準庫STL中的命名風格保持一致//可以用C++11中的 成員變量缺省值 給初始化列表使用 這樣在構造函數中，就不用寫初始化列表了iterator _start = nullptr; iterator _finish = nullptr; iterator _end_of_storage = nullptr;public:vector() // 默認構造{ }// n 個 val構造vector(size_t n, const T& val = T()) { resize(n, val);}vector(int n, const T& val = T()) { //多提供一個 int int 類型的構造resize(n, val);}// 迭代器區間構造template<typename InputIterator>vector(InputIterator first, InputIterator last) {while (first != last) {push_back(*first); ++first;}}// 拷貝構造函數vector(const vector<T>& v) {_start = new T[v.capacity()];for (size_t i = 0; i < v.size(); ++i) {_start[i] = v[i];}_finish = _start + v.size();_end_of_storage = _start + v.capacity();}// 拷貝構造函數二選一即可// vector(const vector<T>& v) {// reserve(v.capacity());// for (auto& e : v)// push_back(e);//}vector<T>& operator=(vector<T> tmp) {swap(tmp);return *this;}// 兩個vector交換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() {if (_start) {delete[] _start;_start = _finish = _end_of_storage = nullptr;}}T& operator[](size_t pos) {assert(pos < size());return _start[pos];}const T& operator[](size_t pos) const {assert(pos < size());return _start[pos];}void reserve(size_t newCapacity) {if (newCapacity > capacity()) {T* newSpace = new T[newCapacity];size_t old_sz = size();if (_start) {for (size_t i = 0; i < old_sz; ++i) {newSpace[i] = _start[i];}delete[] _start;}_start = newSpace;_finish = _start + old_sz;_end_of_storage = _start + newCapacity;}}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;}}}void push_back(const T& obj) {if (_finish == _end_of_storage) {size_t newCapacity = (capacity() == 0 ? 4 : capacity() * 2);reserve(newCapacity);}*_finish = obj;++_finish;//insert(end(), obj);}void pop_back() {erase(--end());}// 解決內部和外部迭代器的最終insert實現方案iterator insert(iterator pos, const T& obj) {// 保證插入位置正確assert(pos >= _start && pos <= _finish);// 擴容邏輯if (_finish == _end_of_storage) {size_t len = pos - _start; // 記錄 pos 相對于 _start 的位置size_t newCapacity = (capacity() == 0 ? 4 : capacity() * 2);reserve(newCapacity);// 擴容后更新pos的值，防止迭代器失效pos = _start + len;}// 挪動元素iterator end = _finish - 1;while (end >= pos) {*(end + 1) = *end;--end;}// 插入數據*pos = obj;++_finish;return pos;}// 為了解決迭代器失效問題，erase返回傳入的pos的下一個位置iterator erase(iterator pos) {assert(pos >= _start && pos < _finish);//刪除iterator begin = pos + 1;//while (begin < end()) {while (begin != _finish) {*(begin - 1) = *begin;++begin;}--_finish;// 為了解決迭代器失效問題，erase返回傳入的pos的下一個位置// 挪動數據后，pos 就是被刪除元素后面第一個元素的位置return pos; }};template<class T1>ostream& operator<<(ostream& out, const vector<T1>& v) {for (auto& e : v) out << e << " ";return out;}
}
8. 結語
在本文中，我們系統性地實現了STL風格的vector容器，深入剖析了動態數組的核心機制。通過手寫代碼，我們重點解決了以下幾個工程實踐中的關鍵問題：
- 三指針架構設計
采用_start、_finish、_end_of_storage三指針模型，精準控制容量邊界與數據邊界，為高效操作奠定基礎。 - 深拷貝控制
通過new[]/delete[]配合元素級的賦值操作，實現容器與元素的雙重深拷貝，確保內置類型與自定義類型的內存安全。 - 迭代器失效機制
重點剖析了insert/erase操作中的迭代器失效問題，通過相對位置計算和返回值設計，提供了標準化的解決方案。 - 現代C++特性應用
采用成員變量缺省值優化初始化邏輯，使用現代寫法實現拷貝賦值，保持代碼簡潔高效。
核心啟示：STL容器的設計精髓在于平衡效率與安全性。vector的擴容策略（異地擴容+二倍增長）既保證了O(1)的均攤時間復雜度，又通過迭代器失效機制強制規范了使用者的操作邊界。
以上就是本文的所有內容了，如果覺得文章對你有幫助，歡迎 點贊?收藏 支持！如有疑問或建議，請在評論區留言交流，我們一起進步
分享到此結束啦
一鍵三連，好運連連！你的每一次互動，都是對作者最大的鼓勵！
征程尚未結束，讓我們在廣闊的世界里繼續前行！🚀
 視頻教程 - 熱詞數量分析日期統計功能實現)
)
