---

一、vector的介紹及使用

1. vector的介紹

1. vector是表示可變大小數(shù)組的序列容器。
2. 就像數(shù)組一樣，vector也采用的連續(xù)存儲(chǔ)空間來存儲(chǔ)元素。也就是意味著可以采用下標(biāo)對(duì)vector的元素進(jìn)行訪問，和數(shù)組一樣高效。但是又不像數(shù)組，它的大小是可以動(dòng)態(tài)改變的，而且它的大小會(huì)被容器自動(dòng)處理。
3. 本質(zhì)講，vector使用動(dòng)態(tài)分配數(shù)組來存儲(chǔ)它的元素。當(dāng)新元素插入時(shí)候，這個(gè)數(shù)組需要被重新分配大小，為了增加存儲(chǔ)空間。其做法是，分配一個(gè)新的數(shù)組，然后將全部元素移到這個(gè)數(shù)組。 就時(shí)間而言，這是一個(gè)相對(duì)代價(jià)高的任務(wù)，因?yàn)槊慨?dāng)一個(gè)新的元素加入到容器的時(shí)候，vector并不會(huì)每次都重新分配大小。
4. vector分配空間策略：vector會(huì)分配一些額外的空間以適應(yīng)可能的增長，因?yàn)榇鎯?chǔ)空間比實(shí)際需要的存儲(chǔ)空間更大。 不同的庫采用不同的策略權(quán)衡空間的使用和重新分配。但是無論如何，重新分配都應(yīng)該是對(duì)數(shù)增長的間隔大小，以至于在末尾插入一個(gè)元素的時(shí)候是在常數(shù)時(shí)間的復(fù)雜度完成的。
5. 因此，vector占用了更多的存儲(chǔ)空間，為了獲得管理存儲(chǔ)空間的能力，并且以一種有效的方式動(dòng)態(tài)增長。
6. 與其它動(dòng)態(tài)序列容器相比（deque, list and forward_list）， vector在訪問元素的時(shí)候更加高效，在末尾添加和刪除元素相對(duì)高效。 對(duì)于其它不在末尾的刪除和插入操作，效率更低。比起list和forward_list統(tǒng)一的迭代器和引用更好。

---

2. 構(gòu)造函數(shù)

vector學(xué)習(xí)時(shí)一定要學(xué)會(huì)查看文檔：vector文檔介紹，vector在實(shí)際中非常的重要，在實(shí)際中我們熟悉常見的接口就可以。當(dāng)然我們使用vector之前需要包頭文件#include<vector>。

下面我們來看一下vector的構(gòu)造函數(shù)：

因?yàn)樵趘ector中是重載了[]訪問運(yùn)算符的，所以我們可以直接使用[]訪問運(yùn)算符來訪問，vector中的元素。下面我們直接來舉幾個(gè)例子來看一下構(gòu)造函數(shù)的用法：

這里我們可以看到和string不同的是，這里的capacity表示的就是所開辟的空間中最多能存儲(chǔ)的元素的個(gè)數(shù)，但在string中則需要多開辟一個(gè)空間為’\0’預(yù)留位置。

迭代器區(qū)間構(gòu)造本質(zhì)上是一個(gè)函數(shù)模板，所以我們可以用任意類來構(gòu)造vector對(duì)象。

---

3. 遍歷方式

💕 [ ]遍歷

int main()
{vector<int> v2(5, 0);for (int i = 0; i < v2.size(); i++)cout << v2[i] << " ";cout << endl;return 0;
}

當(dāng)然了，因?yàn)?code>[ ]重載了const和非const兩個(gè)版本，所以[ ]既可以對(duì)const對(duì)象使用又可以對(duì)非const對(duì)象使用。

💕 使用迭代器遍歷

vector和string一樣，也有反向迭代器rbegin和rend，他們表示獲取最后一個(gè)數(shù)據(jù)位置的reverse_iterator和第一個(gè)數(shù)據(jù)前一個(gè)位置的reverse_iterator。

int main()
{vector<int> v2;v2.push_back(1);v2.push_back(2);v2.push_back(3);v2.push_back(4);v2.push_back(5);vector<int>::iterator it = v2.begin();while (it != v2.end()){cout << *it << " ";}cout << endl;vector<int>::reverse_iterator rit = v2.rbegin();while (rit != v2.rend()){cout << *rit << " ";}cout << endl;return 0;
}

💕 使用范圍for遍歷

int main()
{vector<int> v2;v2.push_back(1);v2.push_back(2);v2.push_back(3);v2.push_back(4);v2.push_back(5);for (auto e : v2)cout << e << " ";cout << endl;return 0;
}

當(dāng)然范圍for遍歷并不是什么高深的語法，它的本質(zhì)還是被替換成了迭代器進(jìn)行遍歷。

---

4. 容量操作及空間增長問題

💕 容量操作

這是vector中的容量操作的幾個(gè)api接口，其中第二個(gè)max_size和shrink_to_fit是我們在之前學(xué)習(xí)string的時(shí)候沒有見過的接口，其中max_size是返回這個(gè)容器中可以容納的最多的元素的個(gè)數(shù)，這個(gè)接口我們一般都不會(huì)用。shrink_to_fit是讓我們?nèi)萜鞯娜萘繙p少到容器中元素的個(gè)數(shù)。因?yàn)榭s容所消耗的代價(jià)是比較大的。一般都不會(huì)輕易縮容，所以這個(gè)接口我們一般也不會(huì)用。

最重要的兩個(gè)接口還是reserve和rsize，reserve只用于擴(kuò)容，不會(huì)改變size的大小，但是resize不僅會(huì)擴(kuò)容，他還會(huì)改變size的個(gè)數(shù)。

💕 空間增長問題

對(duì)于不同的STL版本，他的擴(kuò)容機(jī)制也是不同的。我們知道，vs下和g++分別用的是不同的STL版本，下面我們分別來看一下他們的擴(kuò)容機(jī)制有什么不同。

//測試vector的默認(rèn)擴(kuò)容機(jī)制
void TestVectorExpand()
{size_t sz;vector<int> v;sz = v.capacity();cout << "making v grow:\n";for (int i = 0; i < 100; ++i){v.push_back(i);if (sz != v.capacity()){sz = v.capacity();cout << "capacity changed: " << sz << '\n';}}
}

vs下的擴(kuò)容機(jī)制：

g++下的擴(kuò)容機(jī)制：

這里我們需要注意幾點(diǎn)：

• capacity的代碼在vs和g++下分別運(yùn)行會(huì)發(fā)現(xiàn)，vs下capacity是按1.5倍增長的，g++是按2倍增長的。這個(gè)問題經(jīng)常會(huì)考察，不要固化的認(rèn)為，vector增容都是2倍，具體增長多少是根據(jù)具體的需求定義的。vs是PJ版本STL，g++是SGI版本STL
• reserve只負(fù)責(zé)開辟空間，如果確定知道需要用多少空間，reserve可以緩解vector增容的代價(jià)缺陷問
  題。
• resize在開空間的同時(shí)還會(huì)進(jìn)行初始化，影響size

---

5. 增刪查改

push_back和push_back這兩個(gè)接口我們在string中見過，表示的是尾插和尾刪，這里我們不再細(xì)說。

find和swap

注意： 這里的find函數(shù)是算法庫里的一個(gè)函數(shù)，而并非vector提供的接口。

這里需要提供一段迭代器區(qū)間，然后在后面跟上我們需要查找的元素，如果查找成功就返回他的迭代器，如果查找不成功，就返回end迭代器位置。

既然算法庫里面已經(jīng)有swap這個(gè)接口了，為什么在vector中還要再次設(shè)計(jì)一個(gè)呢？

其實(shí)這是因?yàn)樗惴◣熘械膕wap函數(shù)具有深拷貝的問題，深拷貝的代價(jià)是很大的，對(duì)于vector這樣的類來說直接使用算法庫里面的swap函數(shù)的拷貝代價(jià)太大，所以vector自己提供了一個(gè)自己的swap函數(shù)，其實(shí)vector中的swap函數(shù)的內(nèi)部也是用了算法庫中的swap。

insert和erase

這里的insert和erase和string也有所不同，string中的這兩個(gè)接口在操作完成后會(huì)返回對(duì)象本身，但是在vector中則是操作完成后返回要插入或者刪除的那個(gè)位置的迭代器。當(dāng)然了，不光光是vector，STL中的所有容器的插入和刪除接口都是這樣設(shè)計(jì)的。

基本用法如下：

這里我們需要注意一點(diǎn)是：當(dāng)我們刪除一個(gè)元素的時(shí)候，刪除位置的范圍是【begin()，end()),但是當(dāng)我們插入一個(gè)元素的時(shí)候，插入位置的范圍是【begin()，end()】。

當(dāng)然了，這里存在一種迭代器失效的問題，下面我們在模擬實(shí)現(xiàn)的時(shí)候再來細(xì)說。

---

6. vector二維數(shù)組

int main()
{//設(shè)置二維數(shù)組的行數(shù)和列數(shù)int row = 5, col = 5;//創(chuàng)建二維數(shù)組并初始化為全0vector<vector<int>> vv(row, vector<int>(col, 0));//獲取二維數(shù)組的行數(shù)int size_row = vv.size();//獲取二維數(shù)組的列數(shù)int size_col = vv[0].size();//插入列元素vv[0].push_back(100);//插入行vv.push_back(vector<int>(5, 1));//遍歷二維數(shù)組for (size_t i = 0; i < vv.size(); i++){for (size_t j = 0; j < vv[i].size(); j++){cout << vv[i][j] << " ";}cout << endl;}return 0;
}

---

二、vector的模擬實(shí)現(xiàn)

當(dāng)我們在模擬實(shí)現(xiàn)vector容器之前，需要先來參考一下源碼，主要是為了整體看一下庫里面vector的底層實(shí)現(xiàn)邏輯。

那么我們應(yīng)該如何參考源碼呢？讓我們完全看懂源碼是不可能的，所以我們應(yīng)該抓住重點(diǎn)核心來看，最重要的就是這個(gè)類的成員變量和核心的成員函數(shù)，下面我們來看一下我們在模擬vector之前需要關(guān)注的源碼中的地方。

template <class T, class Alloc = alloc>
class vector
{
public:typedef T value_type;typedef value_type* iterator;typedef const value_type* const_iterator;//...size_type size() const { return size_type(end() - begin()); }size_type max_size() const { return size_type(-1) / sizeof(T); }size_type capacity() const { return size_type(end_of_storage - begin()); }iterator begin() {return start;}iterator end() {return finish;}
private:iterator start;iterator finish;iterator end_of_storage;
};

通過這一部分的源碼我們可以看到vector中的三個(gè)成員變量是由三個(gè)迭代器實(shí)現(xiàn)的，在這里迭代器是一個(gè)原生指針。然后我們根據(jù)源碼中的size()和capacity()等函數(shù)?？梢酝茢喑鲞@三個(gè)指針?biāo)淼囊饬x：

start指向第一個(gè)元素的位置，finish指向容器中有效元素中最后一個(gè)元素后面的位置，end_of_storage指向容器能容納最大容量之后的位置。其實(shí)和我們在C數(shù)據(jù)結(jié)構(gòu)階段實(shí)現(xiàn)的順序表沒有什么本質(zhì)的區(qū)別，不過是使用了三個(gè)指針來維護(hù)所開辟的空間罷了。

---

1. 構(gòu)造函數(shù)

💕 默認(rèn)無參構(gòu)造

//無參構(gòu)造
vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr)
{}

💕 n個(gè)val構(gòu)造

vector(size_t n, const T& val = T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{reserve(n);for (int i = 0; i < n; i++){push_back(val);}
}

我們在寫構(gòu)造函數(shù)的時(shí)候?yàn)榱朔乐挂爸羔樀某霈F(xiàn)，需要在初始化列表中將三個(gè)指針全部初始化為空。為了減少頻繁擴(kuò)容所帶來的消耗，可以先調(diào)用reserve函數(shù)預(yù)先開辟一塊空間，然后依次將要初始化的對(duì)象進(jìn)行尾插。這里我們可以要初始化的值val預(yù)先設(shè)定缺省參數(shù)，這里我們不能將缺省值設(shè)置為0，因?yàn)橐跏蓟膶?duì)象可能是int類型、double類型、還有可能是一個(gè)自定義類型，所以這里我們可以將缺省值給定為一個(gè)T類型的匿名對(duì)象。

這里我們還需要注意的是：引用會(huì)延長匿名對(duì)象的生命周期到引用對(duì)象域結(jié)束，因?yàn)檫@里的val就是匿名對(duì)象的別名，如果匿名對(duì)象在當(dāng)前行就之后就銷毀的話，val也會(huì)被銷毀。同時(shí)，因?yàn)槟涿麑?duì)象具有常性，所以我們需要用const來修飾val。

💕 迭代器區(qū)間構(gòu)造

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

這里我們提供一個(gè)迭代器模板，可以提供任意類型的迭代器。

在提供以上的函數(shù)接口之后，如果我們嘗試構(gòu)造一個(gè)內(nèi)容為5個(gè)10的對(duì)象時(shí)候，這里會(huì)出現(xiàn)間接尋址的錯(cuò)誤，這是因?yàn)榫幾g器在進(jìn)行模板實(shí)例化以及函數(shù)參數(shù)匹配時(shí)會(huì)調(diào)用最匹配的那一個(gè)函數(shù)，當(dāng)我們將T實(shí)例化為int之后，由于兩個(gè)參數(shù)都是int，所以迭代器構(gòu)造函數(shù)會(huì)直接將Inputlterator實(shí)例化為int，但是如果n個(gè)val構(gòu)造來說，不僅需要將T實(shí)例化為int，還需要將第一個(gè)參數(shù)隱式轉(zhuǎn)換為size_t；所以編譯器會(huì)優(yōu)先調(diào)用迭代器區(qū)間構(gòu)造函數(shù)，直接對(duì)int類型解引用的話就會(huì)報(bào)錯(cuò)。

為了防止這種情況發(fā)生，我們可以采取和STL中一樣的解決方式——重載一份第一個(gè)參數(shù)為int的構(gòu)造函數(shù)。

vector(int n, const T& val = T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{reserve(n);for (int i = 0; i < n; i++){push_back(val);}
}

💕 拷貝構(gòu)造

vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{_start = new T[v.capacity()];memcpy(_start, v._start, v.size() * sizeof(T));//——會(huì)導(dǎo)致淺拷貝問題_finish = _start + v.size();_end_of_storage = _start + v.capacity();
}

---

2. 迭代器和基本接口

💕 迭代器的實(shí)現(xiàn)

為了能夠使用范圍for循環(huán)和其他別的功能，這里我們來實(shí)現(xiàn)一下vector的迭代器，同時(shí)，為了能夠?qū)onst對(duì)象也使用迭代器，這里我們還需要設(shè)計(jì)一份const版本的迭代器。

typedef T* iterator;
typedef const T* const_iterator;
//迭代器的實(shí)現(xiàn)
iterator begin()
{return _start;
}
iterator end()
{return _finish;
}const_iterator begin() const
{return _start;
}
const_iterator end() const
{return _finish;
}

💕 基本接口的實(shí)現(xiàn)

size_t size() const
{return _finish - _start;
}
size_t capacity() const
{return _end_of_storage - _start;
}
size_t empty() const
{return _start == _finish;
}
void clear()
{_finish = _start;
}
//析構(gòu)函數(shù)
~vector()
{delete[] _start;_start = _finish = _end_of_storage = nullptr;
}T& operator[](size_t pos)
{assert(pos < size());return _start[pos];
}
const T& operator[](size_t pos) const
{assert(pos < size());return _start[pos];
}

由于以上的接口比較簡單，這里我們就不再做過多的解釋。

---

3. reserve和resize

💕 reserve的實(shí)現(xiàn)

void reserve(size_t n)
{if (n > capacity()){int sz = size();T* tmp = new T[n];if (_start){memcpy(tmp, _start, size() * sizeof(T));delete[] _start;}_start = tmp;_finish = _start + sz;_end_of_storage = _start + n;}
}

如果我們需要擴(kuò)的容量的大小小于原來的容量時(shí)，我們默認(rèn)不執(zhí)行擴(kuò)容操作。這里我們需要先定義一個(gè)臨時(shí)變量sz將擴(kuò)容之前的元素個(gè)數(shù)保存下來，因?yàn)閿U(kuò)容之后給finish賦值時(shí)，start已經(jīng)指向了新的空間，但是finishi還未改變，所以直接使用size()會(huì)出現(xiàn)問題，當(dāng)然了，在這個(gè)接口里面存在著一個(gè)嚴(yán)重的問題，我們到后面會(huì)指正。

💕 resize的實(shí)現(xiàn)

void resize(size_t n,T val = T())
{if (n < size()){//刪除數(shù)據(jù)_finish = _start + n;}else{if (n > capacity()){reserve(n);}while (_finish != _start + n){*_finish = val;_finish++;}}
}

這里我們和前面的構(gòu)造函數(shù)一樣，給一個(gè)匿名對(duì)象的缺省值，如果需要擴(kuò)的容量比原來的容量小時(shí)，
我們只需要將容器中的有效的數(shù)據(jù)個(gè)數(shù)size()減少即可。否則的話，如果n的個(gè)數(shù)大于原來的容量時(shí)，我們可以先使用reserve函數(shù)將原來的空間擴(kuò)大，然后再依次添加到finish之后即可。直到finish的大小等于capacity的大小。

---

4. push_back和pop_back

//push_back的實(shí)現(xiàn)
void push_back(const T& x)
{if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;_finish++;
}//pop_back的實(shí)現(xiàn)
void pop_back()
{assert(!empty());_finish--;
}

這兩個(gè)接口的實(shí)現(xiàn)就非常簡單了，push_back的實(shí)現(xiàn)，如果finish等于capacity容量的大小我們則需要先調(diào)用reserve函數(shù)進(jìn)行擴(kuò)容。當(dāng)然在這里我們判斷capacity的時(shí)候，需要特殊處理一下，因?yàn)槿绻谝淮蝿?chuàng)建的未初始化的對(duì)象的capacity是0時(shí)，直接調(diào)用reverse(capacity)會(huì)出現(xiàn)問題。對(duì)于pop_back的實(shí)現(xiàn)我們還需要先實(shí)現(xiàn)一個(gè)判空操作的函數(shù)。

---

5. insert和erase

💕 insert

iterator insert(iterator pos, const T& val)
{assert(pos >= _start && pos <= _finish);if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;end--;}*pos = val;_finish++;return pos;
}

這里的實(shí)現(xiàn)邏輯也很簡單，先判斷要插入的位置是否符合規(guī)范，在判斷是否需要擴(kuò)容，最后我們重后往前挪動(dòng)數(shù)據(jù)即可。當(dāng)然，最后別忘了finish需要++。

💕 erase

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

這里我們首先需要注意的是，pos位置不能等于finish，因?yàn)閒inish是最后一個(gè)有效元素的后一個(gè)位置，重前往后挪動(dòng)數(shù)據(jù)。最后記得finish–。

---

5. 迭代器失效問題

💕 野指針問題

這里我們可以看到，當(dāng)我們插入一個(gè)元素后，再次打印的時(shí)候就會(huì)出現(xiàn)問題，其實(shí)本質(zhì)上還是我們的insert函數(shù)寫的有問題。

這里我們修改一下insert函數(shù)，當(dāng)需要擴(kuò)容的時(shí)候先使用一個(gè)變量記錄一下pos位置相對(duì)于第一個(gè)元素的位置，再擴(kuò)容之后更新一下pos指針的位置。這樣第一種迭代器失效的問題就得到解決了。

iterator insert(iterator pos, const T& val)
{assert(pos >= _start && pos <= _finish);if (_finish == _end_of_storage){int sz = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + sz;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;end--;}*pos = val;_finish++;return pos;
}

💕 擴(kuò)容之后pos位置的迭代器失效

這里我們可以看到在我們將某個(gè)位置插入一個(gè)數(shù)字后，迭代器可能會(huì)失效，因?yàn)槭莻髦祩鬟f所以insert之后pos的地址可能已經(jīng)發(fā)生改變了，所以insert之后，默認(rèn)pos迭代器失效了的，因?yàn)椴恢滥囊淮螘?huì)進(jìn)行擴(kuò)容操作。所以insert之后的我們需要用pos接受一下就可以解決這種問題。

vector<int> v2;
v2.push_back(1);
v2.push_back(2);
v2.push_back(3);
v2.push_back(4);func(v2);
auto pos = find(v2.begin(), v2.end(), 3);
if (pos != v2.end())
{pos = v2.insert(pos, 100);
}
(*pos)++;
func(v2);

💕 erase之后默認(rèn)迭代器失效

其實(shí)不僅僅是insert，erase之后迭代器也會(huì)失效，下面我們來看一下erase之后迭代器失效的問題，這里我們先來舉三個(gè)例子——刪除一個(gè)序列中所有的偶數(shù)。

為什么同樣的代碼當(dāng)數(shù)據(jù)不同時(shí)會(huì)出現(xiàn)截然不同的結(jié)果呢？

• 第一份代碼能夠運(yùn)行出正確的結(jié)果完全是一個(gè)偶然?？梢钥吹?#xff0c;第二份代碼由于刪除元素后 pos 不再指向原位置，而是指向下一個(gè)位置，所以 erase 之后會(huì)導(dǎo)致一個(gè)元素被跳過，導(dǎo)致部分偶數(shù)沒有被刪除，但好在末尾是奇數(shù)，所以程序能夠正常運(yùn)行。
• 但是最后一份代碼就沒那么好運(yùn)了，由于最后一個(gè)元素是偶數(shù)，所以 erase 之后 pos 直接指向了 _finish 的下一個(gè)位置，循環(huán)終止條件失效，發(fā)生越界。

所以，我們統(tǒng)一認(rèn)為 insert 和 erase 之后迭代器失效，必須更新后才能再次使用。

那么正確的做法就是當(dāng)每次插入或者刪除數(shù)據(jù)后都是用pos來接受一下。更新一下pos位置的數(shù)據(jù)，如果沒有插入或者刪除數(shù)據(jù)，則直接pos++即可。

	auto it2 = v3.begin();while (it2 != v3.end()){if (*it2 % 2 == 0){it2 = v3.erase(it2);}else{it2++;}}for (auto e : v3){cout << e << " ";}cout << endl;

---

5. 淺拷貝問題

💕 拷貝構(gòu)造問題

//拷貝構(gòu)造
vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{_start = new T[v.capacity()];memcpy(_start, v._start, v.size() * sizeof(T));//——會(huì)導(dǎo)致淺拷貝問題_finish = _start + v.size();_end_of_storage = _start + v.capacity();
}

這份代碼在我們看來并沒有什么問題，但其實(shí)它存在一個(gè)隱藏的問題，當(dāng)我們實(shí)例化的對(duì)象是內(nèi)置類型時(shí)，并不會(huì)發(fā)生淺拷貝，但是如果我們實(shí)例化的對(duì)象是自定義類型時(shí)，特別是自定義類型的對(duì)象中有資源分配的時(shí)候，這份代碼就會(huì)導(dǎo)致嚴(yán)重的問題。

當(dāng)我們的vector中的元素是string類型時(shí)，直接這樣寫就會(huì)導(dǎo)致淺拷貝問題，這里我們來看一下原因。

在這里我們確實(shí)是開辟了一塊新的空間，同時(shí)也將原來對(duì)象中的數(shù)據(jù)拷貝到了新的空間中，但是由于這個(gè)對(duì)象是一個(gè)string字符串類型，直接使用memcpy進(jìn)行拷貝是按照字節(jié)進(jìn)行了拷貝，也就是說兩個(gè)對(duì)象中的vector中的string中的_str同時(shí)指向了一塊空間，所以最后調(diào)用自定義類型的析構(gòu)函數(shù)時(shí)，同一塊空間會(huì)被析構(gòu)兩次。最后程序奔潰。

正確的寫法：

vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{_start = new T[v.capacity()];for (size_t i = 0; i < v.size(); i++){_start[i] = v._start[i];}_finish = _start + v.size();_end_of_storage = _start + v.capacity();
}

💕 reserve問題

//reserve擴(kuò)容
void reserve(size_t n)
{if (n > capacity()){int sz = size();T* tmp = new T[n];if (_start){memcpy(tmp, _start, size() * sizeof(T));delete[] _start;}_start = tmp;_finish = _start + sz;_end_of_storage = _start + n;}
}

這份代碼和上面的代碼的原因大同小異，也是因?yàn)閙emcpy會(huì)帶來淺拷貝問題，下面我們來看一個(gè)例子：當(dāng)我們大量插入元素的時(shí)候，會(huì)導(dǎo)致擴(kuò)容的出現(xiàn)，那么擴(kuò)容又會(huì)帶來什么樣的問題呢？

當(dāng)在push_back內(nèi)部調(diào)用 reserve 函數(shù)進(jìn)行擴(kuò)容時(shí)，擴(kuò)容時(shí)我們雖然進(jìn)行了深拷貝，但是空間里面的內(nèi)容我們是使用 memcpy 按字節(jié)拷貝過來的，這就導(dǎo)致原來的 v 里面的 string 元素和臨時(shí)空間里面的string元素指向的是同一塊空間。所以當(dāng)拷貝完數(shù)據(jù)就會(huì)delete掉原來的空間，由于二者指向的是同一塊空間，所以現(xiàn)在v中的string元素指向的是一塊已經(jīng)被釋放掉的空間，當(dāng)最后出了作用域調(diào)用析構(gòu)的時(shí)候就會(huì)出現(xiàn)問題。

正確的寫法：

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

💕 賦值運(yùn)算符重載的問題

如果我們不重載=賦值運(yùn)算符，使用vector中的元素是vector類型時(shí)，這里還是會(huì)出現(xiàn)淺拷貝問題，因?yàn)閹熘械膕tring類重載了=，所以直接賦值進(jìn)行的是深拷貝，這里我們需要重載一下=，這樣無論我們的vector中存儲(chǔ)的是哪一種自定義類型都可以進(jìn)行深拷貝了。

vector<T>& operator=(const vector<T>& v)
{vector<T> tmp(v);swap(tmp);return *this;
}

---

三、vector模擬實(shí)現(xiàn)整體源碼

namespace cjl
{template <class T>class vector {public:typedef T* iterator;typedef const T* const_iterator;//迭代器的實(shí)現(xiàn)iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}無參構(gòu)造//vector()//	:_start(nullptr)//	,_finish(nullptr)//	,_end_of_storage(nullptr)//{}構(gòu)造函數(shù)//vector(size_t n, const T& val = T())//	:_start(nullptr)//	,_finish(nullptr)//	,_end_of_storage(nullptr)//{//	reserve(n);//	for (int i = 0; i < n; i++)//	{//		push_back(val);//	}//}//構(gòu)造函數(shù)的——現(xiàn)代寫法(在成員變量聲明的時(shí)候給缺省值)//無參構(gòu)造vector(){}//構(gòu)造函數(shù)vector(size_t n, const T& val = T()){reserve(n);for (int 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);}}//拷貝構(gòu)造vector(const vector<T>& v){_start = new T[v.capacity()];for (size_t i = 0; i < v.size(); i++){_start[i] = v._start[i];}_finish = _start + v.size();_end_of_storage = _start + v.capacity();}//迭代器區(qū)間構(gòu)造template <class InputIterator>		vector(InputIterator first, InputIterator end){while (first != end){push_back(*first);first++;}}//resize的實(shí)現(xiàn)void resize(size_t n,T val = T()){if (n < size()){//刪除數(shù)據(jù)_finish = _start + n;}else{if (n > capacity()){reserve(n);}while (_finish != _start + n){*_finish = val;_finish++;}}}//reserve的實(shí)現(xiàn)void reserve(size_t n){if (n > capacity()){int sz = size();T* tmp = new T[n];if (_start){for (size_t i = 0; i < sz; i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + sz;_end_of_storage = _start + n;}}//push_back的實(shí)現(xiàn)void push_back(const T& x){if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;_finish++;}//pop_back的實(shí)現(xiàn)void pop_back(){assert(!empty());_finish--;}//insert的實(shí)現(xiàn)iterator insert(iterator pos, const T& val){assert(pos >= _start && pos <= _finish);if (_finish == _end_of_storage){int sz = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + sz;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;end--;}*pos = val;_finish++;return pos;}//erase的實(shí)現(xiàn)iterator erase(iterator pos){assert(pos >= _start && pos < _finish);iterator end = pos + 1;while (end < _finish){*(end - 1) = *end;end++;}_finish--;return pos;}//重載[]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)算符vector<T>& operator=(const vector<T>& v){vector<T> tmp(v);swap(tmp);return *this;}//swap函數(shù)的實(shí)現(xiàn)void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}size_t size() const{return _finish - _start;}size_t capacity() const{return _end_of_storage - _start;}size_t empty() const{return _start == _finish;}void clear(){_finish = _start;}//析構(gòu)函數(shù)~vector(){delete[] _start;_start = _finish = _end_of_storage = nullptr;}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;};
}

---