歡迎來到Cefler的博客😁
🕌博客主頁：那個傳說中的man的主頁
🏠個人專欄：題目解析
🌎推薦文章：題目大解析2

---

👉🏻vector概念

作為C++STL中的一個類模板，vector是一個動態數組容器，可以存儲任意類型的元素。它提供了許多方便的方法來操作和管理數組。

以下是vector的一些特點和用法：

1. 動態大小：vector可以根據需要自動調整大小，無需手動指定數組的大小。
2. 隨機訪問：可以通過索引來訪問和修改vector中的元素，例如myVector[0]。
3. 插入和刪除：可以在任意位置插入和刪除元素，例如myVector.insert(position, value)和myVector.erase(position)。
4. 動態增長：當vector的容量不足時，會自動分配更多的內存空間，以容納更多的元素。
5. 迭代器支持：可以使用迭代器來遍歷vector中的元素，例如使用for循環或std::for_each函數。
6. 元素訪問：可以使用at()方法或[]運算符來訪問元素，例如myVector.at(index)或myVector[index]。
7. 大小和容量：可以使用size()方法獲取vector中元素的數量，使用capacity()方法獲取vector的容量。

vector官方文檔

👉🏻vector constructor

• vector()（重點） 無參構造
• vector（size_type n, const value_type& val = value_type()） 構造并初始化n個val
• vector (const vector& x); （重點） 拷貝構造
• vector (InputIterator first, InputIterator last); 使用迭代器進行初始化構造

👉🏻vector 容量

• size 獲取數據個數
• capacity 獲取容量大小
• empty 判斷是否為空
• resize（重點） 改變vector的size
• reserve （重點） 改變vector的capacity

capacity的代碼在vs和g++下分別運行會發現，vs下capacity是按1.5倍增長的，g++是按2倍增長的。
這個問題經常會考察，不要固化的認為，vector增容都是2倍，具體增長多少是根據具體的需求定義
的。vs是PJ版本STL，g++是SGI版本STL。
reserve只負責開辟空間，如果確定知道需要用多少空間，reserve可以緩解vector增容的代價缺陷問
題

👉🏻vector 增刪查改

• push_back（重點） 尾插

• pop_back （重點） 尾刪

• find 查找。（注意這個是算法模塊實現，不是vector的成員接口）
  

• insert 在position之前插入val
  

• erase 刪除position位置的數據

• swap 交換兩個vector的數據空間
  

• operator[] （重點） 像數組一樣訪問

🌅vector的模擬實現

構造函數和析構函數

 vector():_start(nullptr), _finish(nullptr), _endofstorage(nullptr){}

~vector(){delete[] _start;_start = _finish = _endofstorage = nullptr;}

拷貝構造、賦值、swap

 vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){reserve(v.capacity());//先開一個和v一樣大的空間//而后直接將v中的數據插入到_start中for (auto x : v){push_back(x);}}

 //寫完拷貝構造后，我們就可以開始寫賦值了vector<T>& operator=(vector<T> tmp){swap(tmp);return *this;}void  swap(vector<T>& v)//打工人swap{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}

size和capacity

size_t size(){return _finish - _start;}
size_t capacity(){return _endofstorage - _start;}

reserve

void reserve(size_t n){if (n > capacity())//不縮容{T* tmp = new T[n];size_t sz = size();//記錄一下_finish和_start的偏移量?if (_start != nullptr){memcpy(tmp, _start, sizeof(T) * sz);delete[] _start;//釋放舊空間}_start = tmp;_finish = tmp + sz;_endofstorage = _start + n;}}

這里memcpy()有個大坑，如果針對整型等淺拷貝的拷貝是沒問題的。
但是如果拷貝的類型是string呢？
我們這里舉個例子：

	void test_vector3(){vector<string> v;for (int i = 0; i < 5; i++){v.push_back("11111111111111111111");}for (auto str : v){cout << str << " ";}}

那么這里錯在哪呢？

所以為了避免淺拷貝，我們還是只能自己動手，豐衣足食了，就不借助memcpy了。
這里我們直接用string的賦值運算符，可以直接拷貝構造無需擔心淺拷貝問題。

void reserve(size_t n){if (n > capacity())//不縮容{T* tmp = new T[n];size_t sz = size();if (_start != nullptr){for (int i = 0; i < sz; i++){tmp[i] = _start[i];}delete[] _start;//釋放舊空間}_start = tmp;_finish = tmp + sz;_endofstorage = _start + n;}}

這樣就解決問題了😄

resize

void resize(size_t n, const T& val = T())//因為T()是匿名對象是臨時變量具有常性，所以引用傳參不能權限放大得加const{if (n <= size()){_finish = _start + n;}else{reserve(n);//先開辟n大的空間//然后再進行插入數據while (_finish < _start + n){*_finish = val;_finish++;}}}

push_back

void push_back(const T& x){if (_endofstorage == _finish){size_t cp = capacity() == 0 ? 4 : capacity() * 2;reserve(cp);//T* tmp = new T[cp];//if (_start != nullptr)//{//	memcpy(tmp, _start, sizeof(T) * size());//		delete[] _start;//釋放舊空間//}//_finish = tmp + size();//_finish = tmp + size()一定要先寫，那不然_start先修改，size()大小會不理想//_start = tmp;_endofstorage = _start + cp;}*_finish = x;_finish++;}

迭代器和訪問

typedef T* iterator;//記得要公有typedef const  T* const_iterator;//iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin()const{return _start;}const_iterator end()const{return _finish;}

T& operator[](size_t pos){assert(pos < size());return _start[pos];}T& operator[](size_t pos)const //寫個常量訪問{assert(pos < size());return _start[pos];}

insert

void insert(iterator pos, const T& x){assert(pos >= _start);assert(pos <= _finish);if (_finish == _endofstorage)//擴容情況{//迭代器失效問題：擴容后_start指向新空間,但是Pos仍然指向舊空間//我們先記錄原來_start和Pos的偏移量//擴容后，pos再指向新空間中新位置size_t offset = pos - _start;//記錄偏移量reserve(capacity() == 0 ? 0 : capacity() * 2);pos = _start + offset;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;//數據挪動end--;}*(pos) = x;++_finish;}

erase

會導致迭代器失效版本：

void erase(iterator  pos){assert(pos >= _start);assert(pos <= _finish);iterator end = _finish - 1;while (pos < end){*pos = *(pos + 1);pos++;}_finish--;}

模板構造函數(迭代器區間)

vector的構造函數中，還提供了模板構造函數。

 template <class InputIterator>vector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){while (first != last){push_back(*first);++first;}}

有人會問，既然是用迭代器區間初始化，為什么不能用vector自己本身的iterator呢？
可以是可以，但格局就小啦。

如果我是用vector自己本身的iterator區間，那么假如說我這個vector的iterator是int*,那初始化也就是整型。
那如果我想初始化為字符串呢？
所以這里模板構造函數就顯示出它的神通廣大了，只要是迭代器區間，我都可以接收，這不香嗎？😍

??補充小知識點

當我們寫了拷貝構造函數、模板構造函數、或者其它重載構造函數時
總之只要寫了，默認無參構造函數一定要寫出來（即使你并沒有做什么）
默認無參構造函數是最基本的，如果不寫，編譯器就會使用它自己的默認構造函數。而這時，你寫的其它構造函數都不會生效了

構造函數（初始化n個val值）

 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);}}

為什么這里還要多此一舉再寫個重載？
因為我們上面的模板函數緣故，為了使（int,int）的傳參更好的匹配到構造函數（初始化n個val值），我們寫了一個參數類型為int 的n

🌩迭代器失效問題

C++中的迭代器失效是指在對容器進行修改操作后，之前獲取的迭代器可能會變得無效。這意味著在迭代器失效后，嘗試使用該迭代器進行訪問或操作容器的行為將導致未定義的行為。

迭代器失效的常見情況包括：

• 在向容器中插入或刪除元素后，指向被修改位置的迭代器會失效。
• 在對容器進行重分配內存的操作后，所有指向容器元素的迭代器都會失效。
• 在使用迭代器遍歷容器時，如果在遍歷過程中對容器進行了修改操作，迭代器也會失效。

為了避免迭代器失效，可以采取以下措施：

• 在進行插入或刪除操作后，更新迭代器，使其指向有效的位置。
• 在遍歷容器時，避免在循環內部對容器進行修改操作。
• 在進行可能導致迭代器失效的操作之前，先將迭代器保存下來，以便需要時重新定位

insert和erase導致的迭代器失效

在上述的vector模擬實現中，我們實現了insert和erase的功能。
但是它們會導致怎樣的迭代器失效問題呢？
insert

	void insert(iterator pos, const T& x){assert(pos >= _start);assert(pos <= _finish);if (_finish == _endofstorage)//擴容情況{//迭代器失效問題：擴容后_start指向新空間,但是Pos仍然指向舊空間//我們先記錄原來_start和Pos的偏移量//擴容后，pos再指向新空間中新位置size_t offset = pos - _start;//記錄偏移量reserve(capacity() == 0 ? 0 : capacity() * 2);pos = _start + offset;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;//數據挪動end--;}*(pos) = x;++_finish;}

上述代碼是經過優化改正的，這個是已經解決迭代器問題了。
但我們還得分析一下問題所在
為什么要記錄pos和_start偏移量？
因為我們在擴容時，會開辟新空間，當_start指向新空間時，此時pos還是指向舊空間。
所以為了使pos指向正確的位置，我們得先記錄它和_start的偏移量，而后新的_start加上偏移量就是pos在新空間的位置。

erase
會導致迭代器失效版本

void erase(iterator  pos){assert(pos >= _start);assert(pos <= _finish);iterator end = _finish - 1;while (pos < end){*pos = *(pos + 1);pos++;}_finish--;}

我們舉個刪除偶數的例子。

void test_vector2(){vector<int> v;for (int i = 1; i <= 6; i++){v.push_back(i);}vector<int>::iterator it = v.begin();while (it != v.end()){if (*it % 2 == 0){v.erase(it);}it++;}for (auto x : v){cout << x << " ";}}

我們發現這里崩潰出錯了，而且問題是pos>_finish引起的。
我們看看具體過程

上述過程中的主要問題就是it進行++后指向出現的問題。
那么怎么解決這個問題呢？
實際上c++官方就已經注意到了這個問題，所以，它所設置的erase,會返回函數調用擦除的元素后面元素的新位置的迭代器。

所以，在模擬實現這里我們也要這么做。

iterator erase(iterator  pos){assert(pos >= _start);assert(pos <= _finish);iterator end = _finish - 1;iterator p = pos;while (p < end){*p = *(p + 1);p++;}_finish--;return pos;//返回被刪的位置}

所以可以有

while (it != v.end()){if (*it % 2 == 0){it = v.erase(it);}elseit++;//不是偶數再++}

總結：
上述中，我們解決迭代器失效問題的主要思路就是在進行插入或刪除操作后，更新迭代器，使其指向有效的位置。
而迭代器所謂失效，就是看看在具體情況中，它所指向的元素位置是否和我們預想的有所偏差，如果有偏差，則就會導致迭代器失效

👉🏻電話號碼的字母組合

原題鏈接：電話號碼的字母組合

class Solution {
public:const char* numsArr[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};void Combine(const string& digits,string combinestr,int i ,vector<string>& ret){if(i == digits.size())//當數字中的字母全部都進行完組合后{ret.push_back(combinestr);return;}int num = digits[i] - '0';string str = numsArr[num];for(auto ch:str)//將當前數字代表的全部字母拿去依次拿去跟其它數字的字母進行組合{Combine(digits,combinestr+ch,i+1,ret);}}vector<string> letterCombinations(const string& digits) {vector<string> v;//存儲全部組合的字符串if(digits=="")return v;string str;//這個是專門用來組合的字符串int i =0;Combine(digits,str,i,v);return v;}
};

---

如上便是本期的所有內容了，如果喜歡并覺得有幫助的話，希望可以博個點贊+收藏+關注🌹🌹🌹?? 🧡 💛,學海無涯苦作舟,愿與君一起共勉成長