###vector底層相當(dāng)于是數(shù)組，查看源碼可以發(fā)現(xiàn)，這個(gè)類的私有成員變量是三個(gè)迭代器；在實(shí)現(xiàn)時(shí)迭代器就可以當(dāng)作是vector里面的元素的指針類型；

###vector是一個(gè)類模板，實(shí)現(xiàn)時(shí)也應(yīng)當(dāng)按照這樣的寫法用一個(gè)模板去實(shí)現(xiàn)，類模板vector中數(shù)據(jù)類型是T；

	private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;

_start指向vector的開始地址，_finish指向vector的有效元素的結(jié)束地址，_end_of_storage指向vector最大存儲(chǔ)數(shù)據(jù)的地址；?

一、迭代器

typedef T* iterator;
typedef const T* const_iterator;//迭代器
iterator begin()
{return _start;
}
const_iterator begin()const
{return _start;
}
iterator end()
{return _finish;
}
const_iterator end()const
{return _finish;
}

二、容量

		size_t size()const{return _finish - _start;}size_t capacity()const{return _end_of_storage - _start;}bool empty()const{return size() == 0;}void reserve(size_t n){if (n > capacity()){size_t old_size = size();T* tmp = new T[n];//memcpy(tmp, _start, size() * sizeof(T));//淺拷貝for (size_t i = 0; i < old_size; i++)//深拷貝{tmp[i] = _start[i];}delete[] _start;_start = tmp;_finish = tmp + old_size;_end_of_storage = tmp + n;}}void resize(size_t n, const T& val = T())//匿名對象作為缺省值{if (n < capacity()){_finish = _start + n;}else{reserve(n);for (iterator i = _finish ; i < _start + n; i++){Insert(i,val);}}}

1、reserve

基本思路：開辟一個(gè)臨時(shí)的數(shù)組存放T類型的數(shù)據(jù)，讓這個(gè)數(shù)組的大小為指定的n，將vector對象中的數(shù)據(jù)全部放到這個(gè)臨時(shí)數(shù)組中，再清空vector中的數(shù)據(jù)，最后讓vector對象存放數(shù)據(jù)的地址就是這個(gè)臨時(shí)數(shù)組的地址；

兩個(gè)關(guān)鍵點(diǎn)：

1. old_size：若是不先記錄下size的話，后面給_finish重新賦值時(shí)使用到size()，size（）函數(shù)中_size不再是原來的_size,而是tmp，此時(shí)用_size去減_finish會(huì)出錯(cuò);
2. 深、淺拷貝問題：若是使用memcpy就是淺拷貝，對于vector中是內(nèi)置類型的數(shù)據(jù)可以，但是若是vector對象中涉及到自定義類型，例如string為數(shù)據(jù)的情況，淺拷貝拷貝的是地址，那么tmp中的數(shù)據(jù)的地址就是vector對象中的數(shù)據(jù)地址，之后再delete掉_start，就相當(dāng)于把要存放數(shù)據(jù)的tmp中的數(shù)據(jù)給釋放了，這樣會(huì)讓數(shù)據(jù)丟失；所以一個(gè)一個(gè)賦值，對于內(nèi)置類型無影響，對于自定義類型，例如string的類型，就是賦值重載，string實(shí)現(xiàn)時(shí)是深拷貝，這樣就解決了。

2、resize

基本思路：若是比原來的size小，那么就讓_finish等于_start+n，這樣就訪問不到n之后的數(shù)據(jù)了；若是比原來的size大，沒有給值就用匿名對象T()，對于內(nèi)置類型給初始值（0、空指針、0.0一類），對于自定義類型，調(diào)用默認(rèn)構(gòu)造函數(shù)，實(shí)現(xiàn)部分：先擴(kuò)容，再插入數(shù)據(jù)。

三、元素獲取

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

重載運(yùn)算符[]，在內(nèi)部通過數(shù)組的方式返回對應(yīng)下標(biāo)的位置。

四、修改

		void push_back(const T& val){if (_end_of_storage == _finish){reserve(size() == 0 ? 4 : 2 * capacity());}*_finish = val;_finish++;}void pop_back(){assert(size() > 0);_finish--;}iterator Insert(iterator pos, const T& val){assert(pos >= _start);assert(pos <= _finish);if (_end_of_storage == _finish){size_t len = pos - _start;reserve(size() == 0 ? 4 : 2 * capacity());pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *(end);end--;}*pos = val;_finish++;return pos;}iterator Erase(iterator pos){assert(pos >= _start && pos < _finish);iterator tmp = pos + 1;while (tmp < _finish){*(tmp - 1) = *tmp;tmp++;}--_finish;return pos;}

1、insert和erase調(diào)用時(shí)迭代器失效的問題

insert：實(shí)現(xiàn)時(shí)若是涉及到空間不夠要擴(kuò)容，擴(kuò)容時(shí)要先記錄下pos和_start之間的距離，擴(kuò)容之后_start不是之前的了，那么pos也要跟著更新;此時(shí)在調(diào)用insert時(shí)若是插入之后還要訪問pos就要更新pos（因?yàn)閜os已經(jīng)改變了，若是不更新就使用原來的pos會(huì)找不到原來的數(shù)據(jù)）

就算沒有擴(kuò)容，空間夠，insert之后使用到pos還是要先更新，因?yàn)榇藭r(shí)的pos指向的是新插入進(jìn)來的數(shù)據(jù)，而不是我們想要訪問的原來的數(shù)據(jù)。

erase：erase的迭代器失效舉一個(gè)例子：

	vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);container_print(v);cout << "size:" << v.size() << endl;cout << "capacity:" << v.capacity() << endl;vector<int>::iterator p = v.begin();while(p < v.end()){if (*p % 2 == 0){v.Erase(p);}p++;}container_print(v);

運(yùn)行結(jié)果似乎很正確，那再看：

	vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(4);v.push_back(5);container_print(v);cout << "size:" << v.size() << endl;cout << "capacity:" << v.capacity() << endl;vector<int>::iterator p = v.begin();while(p < v.end()){if (*p % 2 == 0){v.Erase(p);}p++;}container_print(v);

此時(shí)會(huì)發(fā)現(xiàn)有偶數(shù)沒有刪除完全，這是因?yàn)榈魇Я?/p>

原因：erase的實(shí)現(xiàn)中刪除了pos指向的數(shù)據(jù)之后返回pos，此時(shí)的pos指向的是原來要?jiǎng)h除的數(shù)據(jù)的下一個(gè)數(shù)據(jù)，在這個(gè)刪除偶數(shù)的例子中，{1，2，3，4，5}pos指向2.刪除之后pos指向3，再加加就是指向4，剛好到了下一個(gè)偶數(shù)，刪除之后，pos指向5，再加加，循環(huán)結(jié)束，這里只是一個(gè)巧合；數(shù)據(jù)是{1，2，3，4，4，5}刪除完2，pos指向第一個(gè)4，刪除之后，pos指向第二個(gè)4，再加加那么pos指向是5了，就跳過了這個(gè)4，此時(shí)就是迭代器失效了；

為了解決，erase要使用到pos就要更新迭代器；

	while(p < v.end()){if (*p % 2 == 0){p=v.Erase(p);}else{p++;}}

這樣寫，每次刪除完之后，pos指向就是原來要?jiǎng)h除數(shù)據(jù)的下一個(gè)數(shù)據(jù)，若是這個(gè)數(shù)是偶數(shù)那就繼續(xù)刪，是奇數(shù)就加加跳過，這樣就能夠不錯(cuò)過數(shù)據(jù)了。

五、構(gòu)造

1、強(qiáng)制的默認(rèn)構(gòu)造寫法

	vector() = default;//強(qiáng)制的默認(rèn)構(gòu)造

2、拷貝構(gòu)造

		//拷貝構(gòu)造vector(const vector<T>& v){reserve(v.capacity());for (auto it : v){push_back(it);}}

?3、賦值重載

		void clear(){_finish = _start;}void swap(const vector<T>& tmp){std::swap(_start, tmp._start);std::swap(_finish, tmp._finish);std::swap(_end_of_storage, tmp._end_of_storage);}//賦值重載（傳統(tǒng)寫法）vector<T>& operator=(const vector<T>& v){if (_start)//說明被賦值的對象不是空，要先清除{clear();}reserve(v.capacity());for (auto it : v){push_back(it);}}//賦值重載（現(xiàn)代寫法）vector<T>& operator=(vector<T> tmp){swap(tmp);return *this;}

a、傳統(tǒng)寫法：

若是原vector不為空，先置為空，之后再擴(kuò)容，擴(kuò)到和v一樣的大小，再使用拷貝構(gòu)造那一套，將v的數(shù)據(jù)一個(gè)一個(gè)尾插進(jìn)入要被賦值的vector

b、現(xiàn)代寫法：

傳參時(shí)用tmp接收賦值等式右邊的vector，進(jìn)行拷貝構(gòu)造，之后再和賦值等式左邊的vector進(jìn)行交換；（現(xiàn)代寫法一般要在拷貝構(gòu)造寫好的情況下進(jìn)行）；

4、迭代器初始化

		//迭代器初始化template <class InputIterator>//可以接收不同的迭代器，但是迭代器里面的數(shù)據(jù)的類型要相同vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);first++;}}

這里使用到模板是為了接收各種類型的迭代器，但是值得注意的是這些迭代器的各自的容器里面的數(shù)據(jù)類型應(yīng)該和此時(shí)的待構(gòu)造的vector里面的數(shù)據(jù)保持一致，再不濟(jì)也可以強(qiáng)制類型轉(zhuǎn)換；

5、n個(gè)val去初始化

		//n個(gè) val 去初始化vector(size_t n, const T& val = T())//不給值就用匿名對象,這個(gè)對象是 vector 里面的值{reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}

6、析構(gòu)

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

六、容器打印函數(shù)模板中的注意事項(xiàng)：

	template <class T>void vector_print(const vector<T>& v){//要寫 typename,否則沒有實(shí)例化的 vector<T> 不知道const_iterator是類型還是靜態(tài)成員變量typename vector<T>:: const_iterator it = v.begin();//auto it = v.begin();while (it != v.end()){cout << *it << " ";it++;}cout << endl;}

這個(gè)函數(shù)模板定義在我們自己實(shí)現(xiàn)的vector類外面，用來打印vector，使用到迭代器，但是在寫時(shí)注意這一行：

typename vector<T>:: const_iterator it = v.begin();

?要加上typename，否則編譯器分不清這是類里面的靜態(tài)成員變量還是類型，當(dāng)然若是寫成靜態(tài)成員變量去使用，那就一定是靜態(tài)成員變量，但是這里不能直接寫，要在前面加上tyepname；第二種方法可以直接用auto自動(dòng)生成類型去使用。