一、vector的介紹及使用

1.1 vector的介紹

1.2 vector 的使用

1.21 vector的定義

演示：?

1.22 vector iterator 的使用

?1.begin+end

主要作用：獲取第一個數據位置的迭代器和最后一個數據的下一個位置的迭代器。

演示：

2.rbegin+rend

主要作用：rbegin獲取最后一個數據位置的迭代器，rend獲取第一個數據的前一個位置的迭代器。

演示：

1.23 vector空間增長問題

演示：

?注解：capacity的代碼在g++和vs下分別運行下會發現，vs下的capacity是按1.5倍增長的，g++是按2倍增長的，由此可以到底每一次增長多少是不確定的，需要看編譯器。

reserve是負責開辟空間的，如果提前知道需要多少空間可以使用reserve統一開辟，減少vector增容的代價問題

resize在開空間時，還會初始化，影響size.

1.23 vector增刪查改

演示：??

1.24迭代器失效

迭代器的主要作用就是讓算法不用關心底層數據結構，其實本質是指針或者是對指針進行了封裝，比如：vector的迭代器就是原生態指針T*。因此迭代器失效，實際就是迭代器底層對應的指針成為了野指針

例子一：

1.會引起其底層空間改變的操作，都有可能是迭代器失效，比如：resize、reserve、 insert、assgin、push_back（由于vector本質底層是數組，地址都是連在一起的，當他需要擴容的時候一般都是，開辟新的空間，并復制需要的值，釋放原來的空間，造成如果不更新迭代器，那么迭代器指向的是原來的空間，但是這時候原空間已經被釋放了）

做法：更新迭代器

?例子二：指定位置元素的刪除操作——erase

?解釋：如上圖，這段代碼崩了，有兩個問題，第一個問題是：erase本質其實是覆蓋，將該刪除位置的數據被后面的數據給覆蓋，上面這段代碼但他判斷一個數據為偶數的時候，會移動后面的數據到要被刪除的位置，再++t會錯過，移動數據的判斷(如下圖錯過3的判斷)。

?第二個錯誤：當最后一個數據是偶數時，end()的迭代器會-1，it會++，因此錯過end()和it的判斷，二者一直相等

如果將代碼改為如下圖所示，就沒有以上兩個錯誤了?，但是仍然報錯了

這是因為vs對迭代器的失效檢測比較極端，直接認為再erase后的迭代器失效了。再g++下就沒有這么嚴格這段程序就是正確的。

正確改法：erase會返回刪除值位置的迭代器

二、vector 的模擬實現

再模擬實現之前，我們可以看一看 vector的原碼，發現string不同的是vector的三個成員函數都是迭代器，這里值得注意的是，vector的模擬實現使用的是模板，模板不接受定義和實現分離，所以我們使用一個文件vector.h來實現

1.vector的構造和析構

代碼：

vector()
{}
//v2(v1)
vector(vector<T>& v)
{reserve(v.size());for (auto& e : v){push_back(e);}
}//v2 = v1
//現代寫法
/*swap(vector<T>& v)
{std::swap(this->_star = v._star);std::swap(this->_finish = v._finish);std::swap(this->_end_of_storage = v._end_of_storage);
}
vector<T>& operator=(vector<T> v)
{swap(v);
}*/
//傳統寫法
vector<T>& operator=(vector<T> v)
{delete[]_start;_start = _finish = _end_of_storage = nullptr;reserve(v.size());for (auto e : v){push_back(e);}return *this;
}

解析：為什么vector的構造什么東西的沒有寫，那是因為我們再成員變量給了一個缺省值，作用于初始化列表，vector再構造時會走初始化列表把_start,_finish，_end_of_storage置成nullptr

?能不能不寫vector的默認構造？不能，因為拷貝構造也屬于構造，如果不寫編譯器沒有辦法生成默認構造

能不能不寫缺省？不能因為拷貝構造也屬于構造，沒有默認構造成員變量會變成隨機值

賦值有兩種寫法一種傳統一種現代，現代主要利用自定義類型的傳值會調用拷貝構造，舉個例子:

v1 = v2調用賦值時v2需要傳值v，此時調用拷貝構造把v2的值傳給v，v中存儲的值就是v2的且兩者是獨立的不涉及淺拷貝，我們把v1與v2的內容交換，v是局部變量，出來作用域就自動釋放了，這是v會把原來v1的內容給釋放，v1現在的值與v2相同

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

2.end和begin的迭代器

代碼：

iterator begin()
{return _start;
}
iterator end()
{return _finish;
}
iterator begin()const
{return _start;
}
iterator end()const
{return _finish;
}

3.resize?

代碼：

void reserve(size_t n)
{if (n > capacity()){size_t Oldsize = size();T* tmp = new T[n];for (size_t i = 0; i < Oldsize(); i++){tmp[i] = _start[i];}delete[] _start;_start = tmp;_finsh = _start + Oldsize;_end_of_storage = _start + n;} 
}

?問題分析：為什么不用memcpy

1.memcpy是內存的二進制格式的拷貝，將一段內存空間中的內容原封不動的拷貝到另外一段內存空間中

2.如果拷貝的是內置類型的元素，memcpy即高效又不會出錯，但如果拷貝的是自定義類型的元素，并且自定義類型的元素中涉及到資源管理時，就會出錯，因為memcpy是淺拷貝。（結論：如果對象中涉及資源管理時，千萬不能使用memcpy進行對象之間的拷貝，因為memcpy是淺拷貝，否則可能會引起內存泄漏甚至程序崩潰）

4.size capacity?

?

size_t size()
{return _finsh - _start;
}
size_t capacity()
{return _end_of_storage - start;
}
size_t size()const
{return _finsh - _start;
}
size_t capacity()const
{return _end_of_storage - start;
}

5. push_back pop_back

void push_back(const T& x)
{if (_finish == _end_of_storage){reserve(capacity == 0 ? 4 : capacity() * 2);}*_finsh = x;finsh++;
}
void pop_back()
{assert(_finsh > _start);--finsh;
}

6. []

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

7.insert 和erase

?代碼：

void insert(iterator pos, const T& x)
{assert(pos > _start);assert(pos < _finish);if (_finish == _end_of_storage){size_t len = pos - _start;//reserve之后迭代器失效，記錄pos的位置，方便更新reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;//更新pos}iterator end = _finish - 1;while (pos <= end){*(end + 1) = *end;end--;}*pos = x;_finish++;
}
iterator erase(iterator pos)
{assert(pos >= _start);assert(pos < _finish);iterator end = pos + 1;while (end < _finish){*(end - 1) = *end;end++;}_finish--;return pos;
}