1. 認識vector

• vector是向量、矢量的意思
• vector其實就是數據結構階段學過的順序表，行為看起來像指針一樣的容器，底層不一定是用指針實現的，具體根據編譯器的底層實現結構為準
• vector的使用：vector<數據類型> 對象名

---

2. vector的遍歷

---

3. vector的構造

---

• 對于vector的析構，跟string類似，它會自動調用

4. vector常用的接口

---

• vector上述的接口與string的接口并無二異

---

• cbegin( )和cend( )的用法與begin和end類似，無非就是常量迭代器不能改變數據而已

5. vector的容量

---

---

• 對于判空empty和請求縮容shrink_to_fit不再過多贅述，string里面都有講到

6. vector的元素訪問

---

---

• at和下標訪問操作符[ ]都是用來訪問vector內的元素，區別是越界時下標操作符[ ]會報錯，而at會拋出異常，關于這點string已經講過，后續講到捕獲異常時可重溫復習以加深理解

7. vector的修改

---

---

• 其余的像swap用來交換兩個vector對象，使用時可參考官方文檔，大部分與string類模版中的用法類似

8. vector<vector<int>>的使用

• vector<vector<int>>其實就是類似二維數組的用法，使用vector實例化出int類型的對象，再使用vector<vector<int>>實例化出vector<int>的對象

---

---

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main()
{
//vector<vector<int>>的使用(楊輝三角)
size_t numRows = 0;
cin >> numRows; //行數
vector<vector<int>> vv(numRows);
//所有數設置為1
for (size_t i = 0; i < numRows; i++)
{vv[i].resize(i + 1, 1);
}
//中間元素為上面兩個元素之和
for (size_t i = 2; i < numRows; i++)
{for (size_t j = 1; j < vv[i].size() - 1; j++){vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];}
}
//打印
for (size_t i = 0; i < numRows; i++)
{//打印前面的空格for (size_t k = 0; k < numRows - i - 1; k++){cout << " ";}for (size_t j = 0; j < vv[i].size(); j++){cout << vv[i][j] << " ";}cout << endl;
}
return 0;
}

9. vector的使用

• 對于vector容器，也可以使用string類型，其插入string類型的數據如下

---

• 關于vector和C++算法庫的一些使用，以下先作為一個了解

---

10. 模擬實現vector

• 之前講述過，迭代器都是左閉右開的區間，對于begin指向第一個數，而end則指向最后一個數的下個位置
• 因此對于vector的成員變量_start和_finish、_end_of_storage來講，_finish就是指向有效數據的下個位置，_end_of_storage就指向容量的下個位置

---

---

• 接下主要講reserve擴容的坑，其余較容易實現

---

• insert在pos位置插入字符
• 注意：pos的類型是迭代器iterator，因為vector的成員變量是iterator類型，類似迭代器begin()和end()

---

• 對于上述insert插入數據的代碼，存在一個巨大隱患：迭代器失效的問題，接下來主要講容器中的迭代器失效的問題

11. 迭代器失效

11.1 insert插入數據內部迭代器失效

---

• 解決上面迭代器失效的方法：擴容后更新pos

---

11.2 insert插入數據外部迭代器失效

---

• 即使是庫里面實現的vector，對于insert插入數據也會出現迭代器失效的問題
• 迭代器失效的根本原因就是擴容，擴容前后外部迭代器指向的是舊空間，而擴容后舊空間被釋放，再訪問就會報錯
• 因此對于insert插入數據后外部傳參的迭代器，由于不同的平臺結果可能不同，統一認為該迭代器失效
• 解決辦法:insert插入數據后更新迭代器

---

11.3 erase刪除數據迭代器失效

---

---

• 解決辦法：在erase刪除數據后即使更新迭代器it

---

• 總結
• 對于迭代器失效的問題，主要存在于容器插入和刪除元素時，這里以vector為例，在insert插入數據和erase刪除數據后，迭代器就處于失效的狀態，這是因為插入數據擴容導致以及刪除數據縮容導致的一系列問題
• 對于不同的編譯器，結果可能不同，并且vs對于迭代器失效的檢查尤為嚴格，它會對失效的迭代器進行標記，如果嘗試使用這些失效的迭代器，它就會報錯
• 因此統一認為容器插入數據和刪除數據后迭代器處于失效的狀態
• 如果想繼續使用失效的迭代器，解決辦法就是在插入數據或刪除數據前后根據實際情況及時更新迭代器，使迭代器正確指向對應的數據

12. 模擬實現resize

---

---

13. 模擬實現vector的拷貝構造

---

14. 模擬實現vector的賦值操作符重載

---

15. 模擬實現reserve存在的坑

• reserve擴容的第一個坑

---

• reserve擴容的第二個坑

• 插入前四個字符串時沒有問題，但是插入第5個字符串時，為什么會出現問題呢？
• 因為插入第5個字符串時會擴容，reserve擴容中的memcpy其實就是一個淺拷貝，之前再C語言階段實現過memcpy這個函數，它是一個字節一個字節拷貝的
• 參考鏈接:memcpy的使用和模擬實現

---

---

• 解決方案

---

16. 模擬實現vector初始化

• C++11提供了vector初始化列表來進行初始化

---

• inltializer_list是C++11設置一個模版類型
• 其用法和之前創建數組有點類似

---

---

• C++還提供了迭代器區間初始化

---

---

• 當然數組也可以當做迭代器使用

---

17. vector構造時容易出現的坑

• 用n個val值構造vector對象

---

---

• 解決措施

---

18. 模擬實現vector代碼

//模版
template <class T>
class vector
{
public://迭代器typedef T* iterator;typedef const T* const_iterator;//構造函數vector(){}//初始化列表初始化vector(initializer_list<T> il){reserve(il.size());for (auto& e : il){push_back(e);}cout << "初始化列表初始化:" << endl;}//迭代器區間初始化//類模板函數的成員函數，也可以是函數模版template <class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}//vector的構造--->n個valvector(int n, const T& val = T()){resize(n, val);}vector(size_t n, const T& val = T()){resize(n, val);}//拷貝構造 vector(const vector<T>& v){reserve(v.size());for (auto& e : v){//this->push_back(e);push_back(e);}}//有效數據sizesize_t size() const{return _finish - _start;}//容量size_t capacity() const{return _end_of_storage - _start;}//beginiterator begin(){return _start;}//enditerator end(){return _finish;}//const beginconst_iterator begin() const{return _start;}//const endconst_iterator end() const{return _finish;}//resize改變有效數據個數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 reserve(size_t n){if (n > capacity()){size_t oldsize = size();T* tmp = new T[n];/*memcpy(tmp, _start, sizeof(T) * size());*/for (size_t i = 0; i < oldsize; i++){tmp[i] = _start[i];}delete[] _start;_start = tmp;_finish = oldsize + _start;_end_of_storage = n + _start;}}//尾插void push_back(const T& x){if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : 2 * capacity());}*_finish = x;_finish++;}//尾刪void pop_back(){assert(_finish > _start);_finish--;}//重載下標操作符[]T& operator[](size_t i){return _start[i];}//賦值操作符---第一種寫法//vector<T>& operator=(const vector<T>& v)//{//	if (this != &v)//	{//		delete[] _start;//		_start = _finish = _end_of_storage = nullptr;//		reserve(v.size());//		for (auto& e : v)//		{//			//this->push_back(e);//			push_back(e);//		}//	}//	return *this;//}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=(const vector<T>& v){swap(v);return *this;}//任意位置插入,insert插入數據后迭代器失效void insert(iterator pos, const T& x){assert(pos >= _start);assert(pos <= _finish);//滿了擴容if (_finish == _end_of_storage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : 2 * capacity());pos = _start + len;}//挪動數據iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}//插入數據*pos = x;++_finish;}//erase刪除數據iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);iterator begin = pos + 1;while (begin < _finish){*(begin - 1) = *begin;++begin;}--_finish;return pos;}//析構~vector(){delete[] _start;_start = _finish = _end_of_storage = nullptr;}
private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;
};