目錄
1、基本結構
1.1成員變量
?1.2無參構造函數
1.3有參構造函數
preserve()的實現
代碼部分：?
push_back()的實現?
代碼部分：
代碼部分：
1.4拷貝構造函數
代碼部分：
1.5支持{}初始化的構造函數
?代碼部分：
?1.6支持迭代器區間初始化的構造函數
代碼部分：
?1.7支持一次插入多個相同元素的構造函數
代碼部分：
resize()函數的實現：改變大小?
代碼部分：
1.8析構函數
代碼部分：?
2、插入和刪除
2.1尾插
代碼部分：?
2.2在任意位置插入
代碼部分：?
?2.3尾刪
代碼部分：
2.4在任意位置刪除?
思路：
代碼部分：?
3、運算符的重載
3.1賦值運算符的重載
1、傳統寫法
代碼部分：?
2、現代寫法
swap()的實現
代碼部分：?
3.2operator []的實現
代碼實現：
4、迭代器失效問題(重點)
4.1迭代器失效的原因和后果
4.2常見迭代器失效的操作
4.2.1擴容相關操作
4.2.2刪除相關操作
總結：
1、基本結構
1.1成員變量
vector類有三個成員變量，_start指向數據塊起始位置，_finish指向有效數據塊的結尾位置，_end_of_storage指向有效空間容量的結束位置
在這里給它們去缺省值
namespace yyc
{template <class T>class vector{public:typedef T* iterator;private://成員變量初始化為空iterator _start = nullptr;//指向數據塊起始位置iterator _finish = nullptr;//指向有效數據的尾iterator _end_of_storage = nullptr;//指向空間容量的尾};
}?1.2無參構造函數
這里的無參構造函數，也可以不寫初始化列表(因為成員變量給的缺省值會自動給初始化列表)
vector()
{}
//vector()
//: _start(nullptr)
//, _finish(nullptr)
//, _endOfStorage(nullptr)
//{}1.3有參構造函數
初始化一個給定大小的vector，并使用默認值填充
在實現構造之前，我們可以實現一個擴容成員函數reserve()和一個尾插成員函數push_back()
preserve()的實現
實現reserve的過程還可以實現size()和capacity()函數
在實現preserve時要注意的是：
1、這里用到的并不是memcpy來進行數據拷貝，而是用for循環來一個一個賦值
這是因為在面對T為string類型時，使用memcpy會導致淺拷貝
2、在擴容后要進行迭代器的更新，防止出現迭代器失效的問題
代碼部分：?
size_t size() const{return _finish - _start;}size_t capacity() const{return _end_of_storage - _start;}void reserve(size_t n){if (n > capacity()){size_t oldsize = size();//將原有空間中有效數據長度記錄下來T* tmp = new T[n];//memcpy(tmp,_start,sizeof(T)*size())//memcpy進行的是淺拷貝，會導致迭代器失效for (size_t i = 0; i < oldsize; ++i){tmp[i] = _start[i];//將原有空間中的資源轉到新開的空間}delete[] _start;//銷毀舊空間_start = tmp;_finish = _start + oldsize;//finish重新指向原本要指向的位置_end_of_storage = _start + n;}}push_back()的實現?
代碼部分：
void push_back(const T& x){if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;++_finish;}然后我們直接復用這兩個成員函數就可以實現初始化
但要實現范圍for就必須先實現兩個返回首尾位置的迭代器
代碼部分：
typedef T* iterator;typedef const T* const_iterator;//實現范圍foriterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}通過一系列的復用來實現構造函數，這樣就極大的提高代碼的簡潔性以及易于修改?
代碼部分：
vector(const vector<T>& x){reserve(x.size());for (auto a : x){push_back(a);}}
1.4拷貝構造函數
拷貝構造函數實現的思路和有參構造函數差不多，也是進行復用來實現
代碼部分：
vector(const vector<T>& x){reserve(x.size());for (auto a : x){push_back(a);}}1.5支持{}初始化的構造函數
?這是C++版本才新出的一種初始化方式
它支持vector<int> v = {1,2,3,4,5};這種方式初始化
?代碼部分：
vector(initializer_list<T> il){reserve(il.size());for (auto& a : il){push_back(a);}}初始化實現：?
yyc::vector<int> v1 = { 1,2,3,4,5,6 };//一種一種隱式類型轉換yyc::vector<int> v2({ 1,2,3,4,5,6 });//調用對應構造?1.6支持迭代器區間初始化的構造函數
代碼部分：
template <class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}這種初始化方式就可以實現
yyc::vector<int> v1(10,1);
yyc::vector<int> v2(v1.begin(), v1.begin() + 3);?1.7支持一次插入多個相同元素的構造函數
可以實現初始化一次插入多個元素
代碼部分：
vector(int n, const T& val = T()):_start(new T[n]),_finish(_start+n),_end_of_storage(_finish){//while (n--)//{// push_back(val);//}for (int i = 0; i < n; ++i){_start[i] = val;}}初始化實現：?
yyc::vector<int> v1(10,1);但還有一種簡潔的方式實現該構造函數
1、一種是復用reserve()和push_back()l來實現
2、直接復用resize()函數
resize()函數的實現：改變大小?
代碼部分：
void resize(size_t n, const T& val = T())//這里的的val給缺省值{if (n <= size())//當n<=size()時，會進行數據的刪除{_finish =_start;return;}else if (n > capacity())//當n>capacity()時，就進行擴容{reserve(n);//復用寫好的reserve()//多出來的空間插入數據while (_finish != _start + n){//從原本的_finish處進行尾插*_finish = val;++_finish;}}}復用resize()，通過n的大小來進行數據的插入?
vector(size_t n, const T& val = T()) // 這里我們實現了兩個函數
{ // 一個是size_t 的 n 一個是intresize(n, val); // 可以有效的匹配不同調用場景
} // 防止負數隱式轉換
vector(int n, const T& val = T())
{resize(n, val);
}1.8析構函數
代碼部分：?
~vector(){delete[] _start;_start = _finish = _end_of_storage = nullptr;}2、插入和刪除
2.1尾插
代碼部分：?
void push_back(const T& x){if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;++_finish;}2.2在任意位置插入
?注意事項：
當插入過程中需要擴容時，就需要進行迭代器的更新，防止迭代器失效
代碼部分：?
void insert(iterator pos, const T& val){assert(pos >= _start);assert(pos <= _finish);if (_finish == _end_of_storage){//保留pos位置，防止擴容后迭代器失效size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;//更新迭代器}iterator it = _finish - 1;while (it >= pos){*(it + 1) = *it;//挪動數據--it;}*pos = val;//在指定位置插入數據++_finish;}?2.3尾刪
代碼部分：
void pop_back(){assert(_finish > _start);--_finish;}2.4在任意位置刪除?
思路：
將pos+1后面的數據一個一個往前移，進行數據的覆蓋
最后返回刪除位置的迭代器，以此來更新迭代器
代碼部分：?
iterator erase(iterator pos)//刪除指定位置數據{assert(pos >= _start);assert(pos <= _finish);//用后面的數據覆蓋前面的數據iterator it = pos + 1;while (it < _finish){*(it - 1) = *it;it++;}_finish--;return pos;}3、運算符的重載
3.1賦值運算符的重載
1、傳統寫法
· 先進行原有空間的釋放和迭代器的置空
· 在復用reserve()和push_back()來進行數據的拷貝
代碼部分：?
vector<T>& operator=(const vector<T>& v){if (*this != v){delete[] _start;_start = _finish = _end_of_storage = nullptr;reserve(v.size());for (auto& x : v){push_back(x);}}return *this;}2、現代寫法
?現代寫法就比較簡潔，不需要我們來做復雜的工作，，只要實現好了swap()和拷貝構造函數就可以實現
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);}代碼部分：?
void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}vector<T>& operator=(vector<T>& v){swap(v);return *this;}3.2operator []的實現
代碼實現：
T& operator[](size_t i){assert(i < size());return _start[i];}const T& operator[](size_t i) const{assert(i < size());return _start[i];}4、迭代器失效問題(重點)
4.1迭代器失效的原因和后果
使用迭代器的主要原因就是為了不暴露容器的底層結構，不需要關心底層結構，讓使用更簡單
它的底層實際上就是一個指針或對指針進行了封裝，比如：vector的迭代器就是原生態指針T*?
因此，迭代器失效就是迭代器底層對應指針所指向的空間被銷毀了，而使用一塊已經被釋放的空間，造成的后果是程序崩潰(即如果繼續使用已經失效的迭代器，程序可能會崩潰)
4.2常見迭代器失效的操作
4.2.1擴容相關操作
當?vector?需要擴展容量時，會分配新的內存空間并將原有元素搬移到新的位置。此時，所有的迭代器將會失效，它的本質其實就是野指針
· reserve()
· resize()
· insert()
· push_back()
· assign()
#include <iostream>
using namespace std;
#include <vector>
int main()
{vector<int> v{1,2,3,4,5,6};auto it = v.begin();// 將有效元素個數增加到100個，多出的位置使用8填充，操作期間底層會擴容// v.resize(100, 8);// reserve的作用就是改變擴容大小但不改變有效元素個數，操作期間可能會引起底層容量改變// v.reserve(100);// 插入元素期間，可能會引起擴容，而導致原空間被釋放// v.insert(v.begin(), 0);// v.push_back(8);// 給vector重新賦值，可能會引起底層容量改變v.assign(100, 8);/*出錯原因：以上操作，都有可能會導致vector擴容，也就是說vector底層原理舊空間被釋放掉而在打印時，it還使用的是釋放之間的舊空間，在對it迭代器操作時實際操作的是一塊已經被釋放的空間，而引起代碼運行時崩潰。解決方式：在以上操作完成之后，如果想要繼續通過迭代器操作vector中的元素，只需給it重新賦值即可。*/while(it != v.end()){cout<< *it << " " ;++it;}cout<<endl;return 0;
} // 程序運行會崩掉因此，在進行了擴容后默認迭代器就失效了?
4.2.2刪除相關操作
刪除操作會使指向被刪除元素及其后續元素的迭代器失效。
#include<iostream>
using namespace std;
#include <vector>
int main()
{int a[] = { 1, 2, 3, 4 };vector<int> v(a, a + sizeof(a) / sizeof(int));// 使用find查找3所在位置的iteratorvector<int>::iterator pos = find(v.begin(), v.end(), 3);// 刪除pos位置的數據，導致pos迭代器失效。v.erase(pos);cout << *pos << endl; // 此處會導致非法訪問return 0;
}
erase刪除pos位置元素后，pos位置之后的元素會往前搬移，沒有導致底層空間的改變，理論上講迭代器不應該會失效，但是：如果pos剛好是最后一個元素，刪完之后pos剛好是end的位置，而end位置是沒有元素的，那么pos就失效了。因此刪除vector中任意位置上元素時，vs就認為該位置迭代器失效了
int main()
{xxx::vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);for (const auto& e : v1){cout << e << " ";}cout << endl;// 迭代器失效 //刪除所有的偶數：在不同系統下實現結果各有所不同/*auto it = v1.begin();while (it != v1.end()){if (*it % 2 == 0){v1.erase(it);}++it;}*///刪除所有的偶數/*auto it = v1.begin();//這種方法在linux下可以進行，但在VS下無法實現//vs會強制檢查while (it != v1.end()){if (*it % 2 == 0){v1.erase(it);}else{++it;}}*/
// 前面兩種刪除方式都會使迭代器失效 it已經不是指向該指向的位置//該方法適用于多平臺 // 迭代器完全體 auto it = v1.begin();while (it != v1.end()){if (*it % 2 == 0){it = v1.erase(it); // 刪除之后重新賦值迭代器，這也是為什么earse要返回迭代器的原因}else{++it;}}for (const auto& e : v1){cout << e << " ";}cout << endl;return 0;
}
總結：
在進行了擴容或刪除操作后，參與其中的迭代器就默認失效了，解決辦法就是對迭代器進行更新
)
