vector 模擬實現代碼的核心

下面從類設計、核心接口、內存安全、常見陷阱、測試場景5 個維度，提煉需重點掌握的知識點，覆蓋面試高頻考點與實踐易錯點：

一、類結構與成員變量（基礎框架）

vector 的核心是通過三個迭代器（指針） 管理動態內存，這是理解所有接口的前提：

• _start：指向動態數組的起始位置（首元素）

• _finish：指向動態數組中已使用元素的下一個位置（size = _finish - _start）

• _end_of_storage：指向動態數組的末尾位置（capacity = _end_of_storage - _start）

• 成員變量用C++11 類內初始值（= nullptr）初始化，因此默認構造可空實現（vector() {}），簡化代碼。

二、構造函數設計（重載與模板陷阱）

構造函數是 vector 的 “入口”，需重點關注重載匹配問題與通用性：

1. 避免模板構造函數的匹配陷阱

代碼中提供了兩個n, val構造的重載：

vector(size_t n, const T& val = T()); // 1. size_t版本
vector(int n, const T& val = T());    // 2. int版本

為什么需要int版本？（沒懂）

若只寫size_t n版本，當用戶傳入int類型的n（如vector<int> v(10, 5)，10 是int），編譯器會優先匹配模板迭代器構造（vector(InputIterator first, InputIterator last)）—— 因為int可被推導為InputIterator類型，導致將10和5當作 “迭代器范圍”，而int不是迭代器，直接編譯報錯。

注：

• 在 C++ 中，像 10、5 這樣的整數字面量，默認類型是 int（有符號整型），而不是 size_t（無符號整型，通常是 unsigned int 或 unsigned long long，取決于平臺）。

• 只有顯式寫 10u（加 u 表示無符號）或 size_t(10)，才會被視為 size_t 類型。

• 若只有 size_t 版本，編譯器會優先選擇模板迭代器構造函數（精確匹配），但 int 不是迭代器，導致報錯；

• 加個 int 版本后，它會作為 “非模板的精確匹配” 優先被選中，確保調用的是 “n 個 val 初始化” 的正確邏輯。

結論：必須重載int n版本，避免模板構造函數 “搶錯” 匹配。

1. 模板迭代器構造（通用性關鍵）

template <class InputIterator>
vector(InputIterator first, InputIterator last);

• 作用：支持從任意 “迭代器范圍”（[first, last)）初始化，如string的迭代器、原生數組指針、其他容器的迭代器。

• 示例：

std::string s1("hello");
vector<int> v3(s1.begin(), s1.end()); // char轉int，存儲ASCII值
int a[] = {100,10,2};
vector<int> v4(a, a+3); // 原生數組指針作迭代器

• 注意：迭代器類型需支持*解引用和++自增（符合 InputIterator 概念）。

1. 拷貝構造（深拷貝的正確實現）

代碼中拷貝構造的核心是避免淺拷貝：

vector(const vector<T>& v) {_start = new T[v.capacity()]; // 開和原對象capacity相同的空間// 循環賦值（深拷貝），而非memcpy（淺拷貝）for (size_t i = 0; i < v.size(); ++i) {_start[i] = v._start[i]; }_finish = _start + v.size();_end_of_storage = _start + v.capacity();
}

關鍵對比：為什么不用memcpy？

• memcpy是字節級拷貝（淺拷貝），僅適用于 POD 類型（如int、double）；

• 若T是復雜類型（如string、自定義類），memcpy會導致兩個對象的成員指針指向同一塊內存，析構時重復釋放（崩潰）；

• 循環賦值會調用T的賦值運算符（如string::operator=），完成深拷貝（為新string開辟獨立內存）。

結論：動態數組存儲非 POD 類型時，必須用循環賦值實現深拷貝。

三、核心接口實現（易錯點與設計思路）

vector 的核心接口（reserve/resize/insert/erase）是面試高頻考點，需關注功能差異、迭代器失效、擴容策略。

1. reserve vs resize（最易混淆的接口）

兩者均可能擴容，但核心作用完全不同：

示例：

v1.resize(10); // size從5→10，新增5個元素（int()=0），capacity若不足則擴容
v1.resize(3);  // size從10→3，僅移動_finish（_start+3），不釋放內存

1. insert（迭代器失效的典型場景）

insert(pos, val)的核心是解決擴容導致的 pos 失效：

iterator insert(iterator pos, const T& val) {if (_finish == _end_of_storage) {size_t len = pos - _start; // 記錄pos到起始的距離（關鍵）reserve(/*擴容*/);pos = _start + len; // 擴容后更新pos（舊pos指向已釋放內存）}// 元素后移（從后往前）iterator end = _finish - 1;while (end >= pos) {*(end + 1) = *end;--end;}*pos = val;++_finish;return pos; // 返回更新后的pos，方便用戶后續使用
}

關鍵注意點：

• 擴容后必須重新計算 pos：因為擴容會分配新內存，舊pos指向的舊內存已被釋放（野指針）；

• 返回新pos：避免用戶使用失效的迭代器（如 test_vector3 中pos = v1.insert(pos, 30)后，可安全修改*pos）。

1. erase（循環刪除的正確寫法）

erase(pos)的核心是迭代器失效范圍（僅pos之后的迭代器失效，pos本身被返回的新迭代器替代）：

iterator erase(iterator pos) {// 元素前移（從pos+1開始）iterator start = pos + 1;while (start != _finish) {*(start - 1) = *start;++start;}--_finish;return pos; // 返回指向“原pos下一個元素”的迭代器
}

典型場景：循環刪除滿足條件的元素

錯誤寫法（會導致迭代器失效，漏刪或越界）：'

for (auto it = v1.begin(); it != v1.end(); ++it) {if (*it % 2 == 0) {v1.erase(it); // erase后it失效，++it操作非法}
}

正確寫法（用 erase 的返回值更新迭代器）：

auto it = v1.begin();
while (it != v1.end()) {if (*it % 2 == 0) {it = v1.erase(it); // 用返回值更新it，指向刪除后的下一個元素} else {++it; // 不刪除則正常后移}
}

1. push_back（擴容策略)

void push_back(const T& x) {if (_finish == _end_of_storage) {// 擴容策略：初始capacity=0→4，否則擴為2倍reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;++_finish;
}

擴容策略的意義：

• 避免每次push_back都擴容（減少內存分配次數，提高效率）；

• 2 倍擴容是平衡 “內存利用率” 和 “分配次數” 的經典方案（1.5 倍擴容更優，但 2 倍實現簡單）。

四、const 正確性（規范設計）

代碼嚴格遵循 “const 對象只能調用 const 接口”，這是 C++ 的規范設計，需關注：

1. const 迭代器：提供const_iterator begin() const和const_iterator end() const，支持 const 對象遍歷（如func(const vector<int>& v)中使用v.begin()）；

2. const 版本 operator []：

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

1. 確保 const 對象只能讀取元素，不能修改（如func中v[i]無法賦值）。

五、測試用例中的典型場景（實踐鞏固）

代碼中的測試用例覆蓋了 vector 的核心使用場景，復習時需結合案例理解：

1. test_vector5（循環刪除）：掌握erase后迭代器更新的正確寫法；

2. test_vector7（嵌套 vector）：vector<vector<int>>實現楊輝三角，理解二維動態數組的管理（外層 vector 存儲內層 vector，內層 vector 各自管理自己的內存）；

3. test_vector7（復雜類型拷貝）：vector<string> v4(v3)驗證深拷貝正確性（若用memcpy，v3和v4的string會共享內存，析構崩潰）；

4. test_vector6（sort 排序）：sort(v1.begin(), v1.end())說明 vector 的迭代器是隨機訪問迭代器（支持sort的要求），而 list 的迭代器不支持。

六、總結

1. 三個迭代器的作用與size()/capacity()的計算方式；

2. 拷貝構造為什么不能用memcpy（深拷貝 vs 淺拷貝）；

3. reserve與resize的功能差異（是否改變 size、是否初始化元素）；

4. insert和erase的迭代器失效問題（如何避免、返回值的作用）；

5. 循環刪除元素的正確寫法（結合erase的返回值）；

6. 模板構造函數的匹配陷阱（為什么需要int n的重載）。

#pragma once
#include<assert.h>namespace bit
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;//vector()//        :_start(nullptr)//        , _finish(nullptr)//        , _end_of_storage(nullptr)//{}//vector(size_t n, const T& val = T())//        : _start(nullptr)//        , _finish(nullptr)//        , _end_of_storage(nullptr)//{//        reserve(n);//        for (size_t i = 0; i < n; ++i)//        {//                push_back(val);//        }//}//// [first, last)//template <class InputIterator>//vector(InputIterator first, InputIterator last)//        : _start(nullptr)//        , _finish(nullptr)//        , _end_of_storage(nullptr)//{//        while (first != last)//        {//                push_back(*first);//                ++first;//        }//}vector(){}//vector<int> v(10, 5);vector(size_t n, const T& val = T()){reserve(n);for (size_t i = 0; i < n; ++i){push_back(val);}}vector(int n, const T& val = T()){reserve(n);for (int i = 0; i < n; ++i){push_back(val);}}/*vector(const vector<T>& v){reserve(v.capacity());for (auto e : v){push_back(e);}}*/vector(const vector<T>& v){_start = new T[v.capacity()];//memcpy(_start, v._start, sizeof(T)*v.size());for (size_t i = 0; i < v.size(); ++i){_start[i] = v._start[i];}_finish = _start + v.size();_end_of_storage = _start + v.capacity();}// [first, last)template <class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}~vector(){delete[] _start;_start = _finish = _end_of_storage = nullptr;}iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}void resize(size_t n, T val = T()){if (n < size()){// 刪除數據_finish = _start + n;}else{if (n > capacity())reserve(n);while (_finish != _start+n){*_finish = val;++_finish;}}}void reserve(size_t n){if (n > capacity()){size_t sz = size();T* tmp = new T[n];if (_start){//memcpy(tmp, _start, sizeof(T)*size());//深拷貝for (size_t i = 0; i < sz; ++i){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + sz;_end_of_storage = _start + n;}}void push_back(const T& x){if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity()*2);}*_finish = x;++_finish;}void pop_back(){assert(!empty());--_finish;}iterator insert(iterator pos, const T& val){assert(pos >= _start);assert(pos <= _finish);if (_finish == _end_of_storage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);// 擴容后更新pos，解決pos失效的問題pos = _start + len;}iterator end = _finish-1;while (end >= pos){*(end + 1) = *end;--end;}*pos = val;++_finish;return pos;}iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);iterator start = pos + 1;while (start != _finish){*(start - 1) = *start;++start;}--_finish;return pos;}size_t capacity() const{return _end_of_storage - _start;}size_t size() const{return _finish - _start;}bool empty(){return _start == _finish;}T& operator[](size_t pos){assert(pos < size());return _start[pos];}const T& operator[](size_t pos) const{assert(pos < size());return _start[pos];}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;};void func(const vector<int>& v){for (size_t i = 0; i < v.size(); ++i){cout << v[i] << " ";}cout << endl;vector<int>::const_iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl << endl;}void test_vector1(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);func(v1);for (size_t i = 0; i < v1.size(); ++i){cout << v1[i] << " ";}cout << endl;v1.pop_back();v1.pop_back();vector<int>::iterator it = v1.begin();while (it != v1.end()){cout << *it << " ";++it;}cout << endl;v1.pop_back();v1.pop_back();v1.pop_back();//v1.pop_back();for (auto e : v1){cout << e << " ";}cout << endl;//func(v1);}//template<class T>//void f()//{//        T x = T();//        cout << x << endl;//}//void test_vector2()//{//        // 內置類型有沒有構造函數///*        int i = int();//        int j = int(1);*///        f<int>();//        f<int*>();//        f<double>();//}void test_vector2(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);cout << v1.size() << endl;cout << v1.capacity() << endl;v1.resize(10);cout << v1.size() << endl;cout << v1.capacity() << endl;func(v1);v1.resize(3);func(v1);}void test_vector3(){std::vector<int> v1;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;/*v1.insert(v1.begin(), 0);for (auto e : v1){cout << e << " ";}cout << endl;*/auto pos = find(v1.begin(), v1.end(), 3);if (pos != v1.end()){//v1.insert(pos, 30);pos = v1.insert(pos, 30);}for (auto e : v1){cout << e << " ";}cout << endl;// insert以后我們認為pos失效了，不能再使用(*pos)++;for (auto e : v1){cout << e << " ";}cout << endl;}void test_vector4(){std::vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (auto e : v1){cout << e << " ";}cout << endl;//auto pos = find(v1.begin(), v1.end(), 2);auto pos = find(v1.begin(), v1.end(), 4);if (pos != v1.end()){v1.erase(pos);}(*pos)++;for (auto e : v1){cout << e << " ";}cout << endl;}void test_vector5(){bit::vector<int> v1;v1.push_back(10);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);v1.push_back(50);bit::vector<int>::iterator it = v1.begin();while (it != v1.end()){if (*it % 2 == 0){it = v1.erase(it);}else{++it;}}for (auto e : v1){cout << e << " ";}cout << endl;for (auto e : v1){cout << e << " ";}cout << endl;}void test_vector6(){//vector<int> v(10u, 5);vector<int> v1(10, 5);for (auto e : v1){cout << e << " ";}cout << endl;vector<int> v2(v1.begin()+1, v1.end()-1);for (auto e : v2){cout << e << " ";}cout << endl;std::string s1("hello");vector<int> v3(s1.begin(), s1.end());for (auto e : v3){cout << e << " ";}cout << endl;int a[] = { 100, 10, 2, 20, 30 };vector<int> v4(a, a+3);for (auto e : v4){cout << e << " ";}cout << endl;v1.insert(v1.begin(), 10);for (auto e : v1){cout << e << " ";}cout << endl;sort(v1.begin(), v1.end());for (auto e : v1){cout << e << " ";}cout << endl;for (auto e : a){cout << e << " ";}cout << endl;//sort(a, a+sizeof(a)/sizeof(int));/*        greater<int> g;sort(a, a + sizeof(a) / sizeof(int), g);*/sort(a, a + sizeof(a) / sizeof(int), greater<int>());for (auto e : a){cout << e << " ";}cout << endl;}class Solution {public:vector<vector<int>> generate(int numRows) {vector<vector<int>> vv;vv.resize(numRows, vector<int>());for (size_t i = 0; i < vv.size(); ++i){vv[i].resize(i + 1, 0);vv[i][0] = vv[i][vv[i].size() - 1] = 1;}for (size_t i = 0; i < vv.size(); ++i){for (size_t j = 0; j < vv[i].size(); ++j){if (vv[i][j] == 0){vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];}}}return vv;}};void test_vector7(){vector<int> v1(10, 5);for (auto e : v1){cout << e << " ";}cout << endl;vector<int> v2(v1);for (auto e : v2){cout << e << " ";}cout << endl;vector<std::string> v3(3, "111111111111111111111");for (auto e : v3){cout << e << " ";}cout << endl;vector<std::string> v4(v3);for (auto e : v4){cout << e << " ";}cout << endl;v4.push_back("2222222222222222222");v4.push_back("2222222222222222222");v4.push_back("2222222222222222222");for (auto e : v4){cout << e << " ";}cout << endl;vector<vector<int>> ret = Solution().generate(5);for (size_t i = 0; i < ret.size(); ++i){for (size_t j = 0; j < ret[i].size(); ++j){cout << ret[i][j] << " ";}cout << endl;}cout << endl;}
}