Vector底層實現 vector的三個私有成員 :_start 記錄初始位置 , _finish 記錄有效字元 , _endofstoage 記錄容量大小 vector會存儲的類型不同，所以要用模版來定類型 typedef T* iterator; iterator _start; iterato ...
Vector底層實現
vector的三個私有成員
:_start 記錄初始位置
, _finish 記錄有效字元
, _endofstoage 記錄容量大小
vector會存儲的類型不同，所以要用模版來定類型
typedef T* iterator;
iterator _start;
iterator _finish;
iterator _endofstoage;
也就是T*
構造函數的方法很多 可以用迭代器的範圍來構造
//用迭代器構造的構造函數
傳過來的是它的迭代器的類型 我們也用它的類型來接收 不比加* &
三個屬性先初始化
只要根據傳過來的範圍來push_back（）即可
push_back函數後面會實現
//用迭代器構造的構造函數 template <class InputIterator> vector(InputIterator first, InputIterator last) : _start(nullptr) , _finish(nullptr) , _endofstoage(nullptr) { while (first != last) { push_back(*first); ++first; } }
構造是 也可以根據n分val來構造 所以這個功能也需要提供
傳過來的是n個 用size_t接收 因為n必須是>=0的 而val是根據類型 所以用模版類型接受
有些情況下 val會不傳參 那麼我們就會提供他的預設構造 （註意 在C++中，內置類型也是有預設構造的）
三個屬性初始話
先用reserve函數創建n個空間
在分別push_back（）添加val
//構造n個val的構造函數 vector(size_t n, const T& val = T()) : _start(nullptr) , _finish(nullptr) , _endofstoage(nullptr) { reserve(n); for (size_t i = 0; i < n; ++i) { push_back(val); } }
因為某些情況 第一個參數是int 第二個參數也是int 會調用到迭代器的函數 因為這兩個類型更加適配，所以會出問題，所以需要再提供一個第一個參數為int的相同函數，來避免這種情況
//構造n個val的構造函數 //因為用int會調用到其他函數 所以為了區分 單獨寫出一個第一個為int vector(int n, const T& val = T()) : _start(nullptr) , _finish(nullptr) , _endofstoage(nullptr) { reserve(n); for (int i = 0; i < n; ++i) { push_back(val); } }
swap函數
這個函數是用來給拷貝構造使用
交換類的三個屬性成員
//交換 void swap(vector<T>& v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_endofstoage, v._endofstoage); }
拷貝構造
拷貝的本質是把一個有數據的拷貝給一個無數據的，只需要用這個無數據的迭代器去調用迭代器構造，給一個臨時tmp，最後再用這個無數據的與臨時tmp交換 即可
因為傳過來的是另一個vector 所以必須用vector<T> 接收 C++傳參是特別需要註意的，真的很容易亂
//拷貝構造 vector(const vector<T>& v) : _start(nullptr) , _finish(nullptr) , _endofstoage(nullptr) { vector<T> tmp(v.begin(), v.end());//復用用迭代器構造的構造函數 swap(tmp); }
賦值重載
v1=v2 是兩個vector的數據賦值 所以它的返回值必須是vector<t> 而傳參數時 也必須是vector<t>
函數本質也是交換，所以直接調用swap 這裡之所以能直接調用 而不影響到v2 是因為函數是用傳值傳參，它是不會影響到v2本體的，（現代寫法）
返回時是返回本體 （*this）
vector<T>& operator=(vector<T> v)//賦值重載 不用引用 現代寫法 { swap(v);//現代寫法 return *this; }
析構函數
判斷是否為空 當不為空時才需要析構 如果為空 去析構 會崩潰
把數據釋放，並且它三個屬性置空
// 資源管理 ~vector() { if (_start) { delete[] _start; _start = _finish = _endofstoage = nullptr; } }
迭代器部分
vector的迭代器本質就是指針 根據傳進來的類型 iterator就是這個類型的指針
並且迭代器分為const版本和非const版本
所以需要提供兩個版本
//迭代器 typedef T* iterator; typedef const T* const_iterator;
註意 end返回的是你的實際有效字元 而不是你的的空間多大
iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin() const { return _start; } const_iterator end() const { return _finish; }
size
你的有效字元 _finish 而_finish實際上是有效字元的下一個位置
所以需要減去初始的位置 得到它真正的有效字元
size_t size() const { return _finish - _start; }
capacity
計算的是vector的空間大小 也就是你的記錄空間大小減去初始位置
size_t capacity() const { return _endofstoage - _start; }
【】重載
vector是支持隨意訪問的，所以【】的重載必不可少
返回的是vector里存儲的類型 實際上就是模版類型 因為傳出去也代表它需要改變 所以需要傳引用
T& operator[](size_t n) { assert(n < size()); //return *(_start + n); return _start[n]; //這個也可以 }
【】重載 有些地方是需要提供const版本 不允許更改的版本
const T& operator[](size_t n) const { assert(n < size()); //return *(_start + n); return _start[n]; //這個也可以 }
reserve
擴容空間 但不初始化
這裡需要註意擴容後的三個屬性更新出現的問題 正常運行會崩潰。 問題的關鍵：開闢一個新空間時，他們三個的類型是指針！而不是下標，一個地址更新，去用以前的指針，去更改這個新的地址，是會崩潰的，而下標是固定位置，地址在怎麼更新，下標的位置就是固定的。
我們需要記錄原先的有效字元個數
正常比較和擴容，只是這裡用memcpy函數時，出現嵌套情況時，會出現淺拷貝情況
需要用賦值 深拷貝
另外兩個要更新時，要用預先存儲好的數據來更新 詳情看註釋！
void reserve(size_t n) { size_t sz = size(); if (n > capacity()) { T* tmp = new T[n]; if (_start) //如果_start為空時 就不需要拷貝數據了 { //memcpy(tmp, _start, size() * sizeof(T));//把_start的數據拷貝到tmp //這樣做 在嵌套時，會發生淺拷貝 for (size_t i = 0; i < size(); i++)//正確做法是直接賦值 在vector<vector> 這種嵌套時 是深拷貝 { tmp[i] = _start[i]; } delete[] _start; } _start = tmp;//更新過後 _start就不再是nullptr } //_finish = _start + size();//× 結果為空 解引用無地址 賦值會崩潰 ==_start+(_finish-_start) 這裡的_finsih最後是等於空 //而跳出函數後 _finish解引用再賦值會崩潰 因為空地址無法賦值 _finish = _start + sz;//√ 結果為_start有地址。解引用能賦值 ==_start+0 == 這裡先讓原先的_finish-_start==0 再+上0 因為_start已經更新過了 所以需要在開頭記錄_size的大小 //而更新過的_start不是空 這時候在調用size _finish-_start就不是0了 而是其他值了 _endofstoage = _start + n; }
resize
擴容，但會初始化數據
要擴容的大小 大於實際 空間大小（不是實際字元大小！） 時，我們先開需要大小空間即可
如果n大於實際字元大小時
我們需要在實際字元的位置後開始不斷添加val（要初始化的值）
如果n小於實際字元大小
那麼就把實際字元大小改為 n個 即 初始值+n
void resize(size_t n, T val = T()) { if (n > capacity()) { reserve(n); } if (n > size()) { while (_finish < _start + n) { *_finish = val; ++_finish; } } else { _finish = _start + n; } }
push_back()
添加字元
只要需要添加字元的函數，基本是需要檢查空間是否足夠的
一種情況為 實際空間為0 還未擴容時 預設給它開4個空間，如果有空間，但滿時，擴二倍即可（為什麼擴容二倍？沒什麼！因為合適 或者1.5倍，擴容其他倍數要麼太小，要麼太大，1.5和2的倍數是適應性最好的）
擴容好後，或者空間足夠時
直接在有效字元的位置添加字元 （為什麼不先++？因為前面說過，實際字元的指針實際上是指向實際字元的後一位，所以你要添加，直接在實際字元指針添加即可）
最後添加好後，實際字元++ （這也是返回真實字元時，不直接返回_finish，而是返回_finish-_start
因為嵌套的作用，此函數在insert函數實現後，可以直接復用insert就可以了
void push_back(const T& x) { /*if (_finish == _endofstoage) { size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2; reserve(newCapacity); } *_finish = x; ++_finish;*/ insert(end(), x); }
pop_back()
此函數只需要把實際字元--即可
先判斷合法性，實際字元必須大於初始值
因為嵌套的作用，此函數在erase函數實現後，可以直接復用erase就可以了
void pop_back() { /* if (_finish > _start) { --_finish; }*/ erase(end() - 1); }
insert
註意此函數會有迭代器失效問題！
通常此函數是不需要返回的，但因為迭代器失效問題，所以必須有返回值，因為返回的就是此指向此函數的指針 也就是T* 模版類型指針 所以用重命名的iterator即可
pos是指向要插入的位置，這個函數都是用指針來指針，所以沒辦法使用下標，這也是它的失效的問題之一！
首先判斷是否需要擴容
上面的reserve提到過，擴容後，_start的地址是會變的，而pos也是迭代器，它也是指向這個地址的指針，它不會跟著更新地址而變化。
所以這個pos它指向的位置，是原來_start的位置，而這個位置已經被釋放了，所以再去使用這個pos時，是會崩潰的！
所以為了防止這種情況，我們需要先記錄這個pos的位置，等待_start的地址更新好後，我們要根據原先這個存儲好pos的位置，在去用_start的地址，去更新新的pos位置，並且pos的位置不變。
然後開始移動pos後的數據 給pos位置開出空間，能讓val插入
最後在pos的位置插入val
再++實際空間
最後需要放回插入後的位置
那麼我們在使用是，需要用迭代器去接收，才能防止迭代器的失效，因為原先的迭代器已經失效，需要根據這個返回值，來更新迭代器。
while (it != v1.end()) { if (*it % 2 == 0) { it = v1.insert(it, 100);//因為迭代器更新數據會失效 所以要用it接收 防止失效 ++ it;//返回的是插入的位置 再次++會再次遇到原來的位置 所以插入後 要自增++一次 } ++it; }
erase
此函數存在迭代器失效的問題
正常刪除即可
只是返回必須返回刪除後的下一個值
使用這個函數時，也是需要迭代器用函數返回值接收，來更新迭代器
while (it != v.end()) { if ((*it) % 2 == 0) { it = v.erase(it); } else { ++it; } }
clear
置空功能，只需要把有效字元置為初始值即可。
//置空 void clear() { _finish = _start;//把有效字元改為初始 }
接下來是源碼
#pragma once #include<iostream> #include<assert.h> using namespace std; namespace moxuan { template<class T> class vector { public: //迭代器 typedef T* iterator; typedef const T* const_iterator; //預設無參構造 vector() :_start(nullptr) , _finish(nullptr) , _endofstoage(nullptr) {} //用迭代器構造的構造函數 template <class InputIterator> vector(InputIterator first, InputIterator last) : _start(nullptr) , _finish(nullptr) , _endofstoage(nullptr) { while (first != last) { push_back(*first); ++first; } } //構造n個val的構造函數 vector(size_t n, const T& val = T()) : _start(nullptr) , _finish(nullptr) , _endofstoage(nullptr) { reserve(n); for (size_t i = 0; i < n; ++i) { push_back(val); } } //構造n個val的構造函數 //因為用int會調用到其他函數 所以為了區分 單獨寫出一個第一個為int vector(int n, const T& val = T()) : _start(nullptr) , _finish(nullptr) , _endofstoage(nullptr) { reserve(n); for (int i = 0; i < n; ++i) { push_back(val); } } //交換 void swap(vector<T>& v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_endofstoage, v._endofstoage); } //拷貝構造 vector(const vector<T>& v) : _start(nullptr) , _finish(nullptr) , _endofstoage(nullptr) { vector<T> tmp(v.begin(), v.end());//復用用迭代器構造的構造函數 swap(tmp); } vector<T>& operator=(vector<T> v)//賦值重載 不用引用 現代寫法 { swap(v);//現代寫法 return *this; } // 資源管理 ~vector() { if (_start) { delete[] _start; _start = _finish = _endofstoage = nullptr; } } iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin() const { return _start; } const_iterator end() const { return _finish; } size_t size() const { return _finish - _start; } size_t capacity() const { return _endofstoage - _start; } void reserve(size_t n) { size_t sz = size(); if (n > capacity()) { T* tmp = new T[n]; if (_start) //如果_start為空時 就不需要拷貝數據了 { //memcpy(tmp, _start, size() * sizeof(T));//把_start的數據拷貝到tmp //這樣做 在嵌套時，會發生淺拷貝 for (size_t i = 0; i < size(); i++)//正確做法是直接賦值 在vector<vector> 這種嵌套時 是深拷貝 { tmp[i] = _start[i]; } delete[] _start; } _start = tmp;//更新過後 _start就不再是nullptr } //_finish = _start + size();//× 結果為空 解引用無地址 賦值會崩潰 ==_start+(_finish-_start) 這裡的_finsih最後是等於空 //而跳出函數後 _finish解引用再賦值會崩潰 因為空地址無法賦值 _finish = _start + sz;//√ 結果為_start有地址。解引用能賦值 ==_start+0 == 這裡先讓原先的_finish-_start==0 再+上0 因為_start已經更新過了 所以需要在開頭記錄_size的大小 //而更新過的_start不是空 這時候在調用size _finish-_start就不是0了 而是其他值了 _endofstoage = _start + n; } void resize(size_t n, T val = T()) { if (n > capacity()) { reserve(n); } if (n > size()) { while (_finish < _start + n) { *_finish = val; ++_finish; } } else { _finish = _start + n; } } void push_back(const T& x) { /*if (_finish == _endofstoage) { size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2; reserve(newCapacity); } *_finish = x; ++_finish;*/ insert(end(), x); } void pop_back() { /* if (_finish > _start) { --_finish; }*/ erase(end() - 1); } T& operator[](size_t n) { assert(n < size()); //return *(_start + n); return _start[n]; //這個也可以 } const T& operator[](size_t n) const { assert(n < size()); //return *(_start + n); return _start[n]; //這個也可以 } //插入 註意會有迭代器失效問題! iterator insert(iterator pos, const T& val) { assert(pos >= _start && pos <= _finish); if (_finish == _endofstoage) { size_t n = pos - _start;//因為更新start後 pos無法跟著更新 所以要記錄pos的位置 size_t newsize = capacity() == 0 ? 4 : capacity() * 2; reserve(newsize); pos = _start + n; } iterator cur = _finish - 1; while (cur >= pos) { *(cur + 1) = *cur; --cur; } *pos = val; ++_finish; return pos; } //刪除 iterator erase(iterator pos)//返回刪除後的下一個位置 { assert(pos >= _start && pos < _finish); iterator it = pos+1; while (it != _finish) { *(it-1) = *it; ++it; } --_finish; return pos++;//返回刪除後的下一個位置 } //置空 void clear() { _finish = _start;//把有效字元改為初始 } private: iterator _start; iterator _finish; iterator _endofstoage; };
接下來是用來測試這個vector的可行性 楊輝三角
大家可以源碼拿去編譯器上，然後調用這個test4函數即可
class Solution { public: vector<vector<int>> generate(int numRows) { vector<vector<int>> vv; vv.resize(numRows); for (size_t i = 0; i < vv.size(); ++i) { // 楊輝三角，每行個數依次遞增 vv[i].resize(i + 1, 0); // 第一個和最後一個初始化成1 vv[i][0] = 1; 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) { // 中間位置等於上一行j-1 和 j個相加 vv[i][j] = vv[i - 1][j - 1] + vv[i - 1][j]; } } } for (size_t i = 0; i < vv.size(); ++i) { for (size_t j = 0; j < vv[i].size(); ++j) { cout << vv[i][j] << " "; } cout << endl; } cout << endl; return vv; } }; void test4() { 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; } }
這就是本文章的全部內容，感謝您能觀看到這裡，如有問題請評論或私信。感謝觀看！
