一、vector的介紹
vector學(xué)習(xí)時(shí)一定要學(xué)會查看文檔：cplusplus網(wǎng)址：vector文檔介紹vector在實(shí)際中非常的重要，在實(shí)際中我們熟悉常見的接口就可以
【總結(jié)】
1.vector是表示可變大小數(shù)組的序列容器
2.就像數(shù)組一樣，vector也采用的連續(xù)存儲空間來存儲元素。也就是意味著可以采用下標(biāo)對vector的元素進(jìn)行訪問，和數(shù)組一樣高效。但是又不像數(shù)組，它的大小是可以動態(tài)改變的，而且它的大小會被容器自動處理
3.本質(zhì)講，vector使用動態(tài)分配數(shù)組來存儲它的元素。當(dāng)新元素插入時(shí)候，這個(gè)數(shù)組需要被重新分配大小為了增加存儲空間。其做法是，分配一個(gè)新的數(shù)組，然后將全部元素移到這個(gè)數(shù)組。就時(shí)間而言，這是一個(gè)相對代價(jià)高的任務(wù)，因?yàn)槊慨?dāng)一個(gè)新的元素加入到容器的時(shí)候，vector并不會每次都重新分配大小
4.vector分配空間策略：vector會分配一些額外的空間以適應(yīng)可能的增長，因?yàn)榇鎯臻g比實(shí)際需要的存儲空間更大。不同的庫采用不同的策略權(quán)衡空間的使用和重新分配。但是無論如何，重新分配都應(yīng)該是對數(shù)增長的間隔大小，以至于在末尾插入一個(gè)元素的時(shí)候是在常數(shù)時(shí)間的復(fù)雜度完成的
5.vector占用了更多的存儲空間，為了獲得管理存儲空間的能力，并且以一種有效的方式動態(tài)增長。
6.與其它動態(tài)序列容器相比（deque, list and forward_list）， vector在訪問元素的時(shí)候更加高效，在末尾添加和刪除元素相對高效。對于其它不在末尾的刪除和插入操作，效率更低。比起list和forward_list統(tǒng)一的迭代器和引用更好
使用STL的三個(gè)境界：能用，明理，能擴(kuò)展 ，那么下面學(xué)習(xí)vector，我們也是按照這個(gè)方法去學(xué)習(xí)
二、vector的使用
1.構(gòu)造函數(shù)
vector提供了四種構(gòu)造方式–無參構(gòu)造，n個(gè)val構(gòu)造，迭代區(qū)間構(gòu)造和拷貝構(gòu)造
| 構(gòu)造函數(shù)聲明 | 接口說明 |
|---|---|
| vector() | 無參構(gòu)造 |
| vector（size_type n, const value_type& val = value_type()） | 構(gòu)造并初始化n個(gè)val |
| vector (const vector& x) | 拷貝構(gòu)造 |
| vector (InputIterator fifirst, InputIterator last) | 使用迭代器進(jìn)行初始化構(gòu)造 |
// 測試構(gòu)造
void vector_test1()
{
vector<int> v1; // 無參構(gòu)造
vector<int> v2(5, 1); // n個(gè)val構(gòu)造
vector<int> v3(v2); // 拷貝構(gòu)造
string s("hello world");
vector<int> v4(s.begin(), s.end()); // 迭代器構(gòu)造
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
for (auto e : v2)
{
cout << e << " ";
}
cout << endl;
for (auto e : v3)
{
cout << e << " ";
}
cout << endl;
for (auto e : v4)
{
cout << e << " ";
}
cout << endl;
}
【注意】
1.對于構(gòu)造函數(shù)的最后一個(gè)參數(shù)alloc是空間配置器，它和內(nèi)存池有關(guān)，它的作用是提高空間分配的效率，我們一般情況下不需要管這個(gè)參數(shù)，使用它的缺省值即可，這個(gè)缺省值的原因是有極少數(shù)的人需要使用自己實(shí)現(xiàn)的空間配置器來代替STL庫里的
2.在n個(gè)val構(gòu)造中，val的缺省值是T的匿名對象，該對象使用T的默認(rèn)構(gòu)造來初始化，而不是使用0來作為這個(gè)缺省值，這個(gè)是因?yàn)門不僅僅是內(nèi)置類型，也可以是自定義類型，比如string,vector,list;當(dāng)T為自定義類型的時(shí)候，0就不一定能夠?qū)al進(jìn)行初始化，所以我們就用T的匿名對象去調(diào)用它的默認(rèn)構(gòu)造去進(jìn)行初始化，當(dāng)T為內(nèi)置類型的時(shí)候，內(nèi)置類型也會去調(diào)用它的構(gòu)造函數(shù)，大家可能很驚訝，內(nèi)置類型怎么可能有構(gòu)造函數(shù)呢，這是編譯器進(jìn)行了特殊的處理，使得內(nèi)置類型也具有了構(gòu)造函數(shù)。
2.擴(kuò)容機(jī)制
capacity的代碼在vs和g++下分別運(yùn)行會發(fā)現(xiàn)，vs下capacity是按1.5倍增長的，g++是按2倍增長的。這個(gè)問題經(jīng)常會考察，不要固化的認(rèn)為，vector增容都是2倍，具體增長多少是根據(jù)具體的需求定義的。vs是PJ版本STL，g++是SGI版本STL
測試用例如下：
// 測試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';
}
}
}
vs2019
g++
3.三種遍歷方式
vector和string一樣，也支持三種遍歷方式–下標(biāo)+[]，迭代器遍歷，范圍for遍歷
// 測試遍歷
void vector_test2()
{
vector<int> v(10, 1);
// 下標(biāo)+[]
for (size_t i = 0; i < v.size(); ++i)
{
cout << v[i] << " ";
}
cout << endl;
// 迭代器遍歷
vector<int>::iterator it = v.begin();
while (it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
// 范圍for遍歷
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
【注意】
vector和string支持下標(biāo)+[]的方式進(jìn)行遍歷的原因是string和vector的底層都是通過數(shù)組實(shí)現(xiàn)的，而數(shù)組支持隨機(jī)訪問，但是對于不是通過數(shù)組實(shí)現(xiàn)的容器，比如list,set map等等，他們就不能通過下標(biāo)+[]的方式進(jìn)行遍歷，此外，我們還需要注意，范圍for只是一個(gè)外殼，它在調(diào)用的時(shí)候也是去調(diào)用迭代器，所以迭代器是所有容器通用的遍歷方式
4.容量操作
| 容量空間 | 接口說明 |
|---|---|
| size | 獲取數(shù)據(jù)個(gè)數(shù) |
| capacity | 獲取容量大小 |
| empty | 判斷是否為空 |
| resize | 改變vector的size |
| reserve | 改變vector的capacity |
其中，最重要的兩個(gè)函數(shù)為resize和reserve，resize的作用的擴(kuò)容和初始化，既會改變size也會改變capacity，而reserve只用于擴(kuò)容，不改變size
// 測試resize reserve
void vector_test3()
{
vector<int> v(5);
cout << v.size() << endl;
cout << v.capacity() << endl << endl;
v.reserve(10);
cout << v.size() << endl;
cout << v.capacity() << endl << endl;
v.resize(3);
cout << v.size() << endl;
cout << v.capacity() << endl << endl;
}
但是我們需要注意，resize,reserve以及clear函數(shù)都不會縮容，因?yàn)榭s容需要重新開辟空間，拷貝數(shù)據(jù)和釋放空間，而對于自定義類型又可能存在深拷貝的問題，時(shí)間消耗很大，在迫不得已的情況下，比如開辟了一塊很大的空間，并且確定這塊空間只需要一小部分，這個(gè)時(shí)候我們可以使用shrink_to_fit函數(shù)，如果capacity大于size,它會進(jìn)行縮容，讓size==capacity
【總結(jié)】
1.reserve只負(fù)責(zé)開辟空間，如果確定知道需要用多少空間，reserve可以緩解vector增容的代價(jià)缺陷問題
2.resize在開空間的同時(shí)還會進(jìn)行初始化，影響size和capacity
5.元素訪問
vector提供了以下接口來進(jìn)行元素訪問
其中，operator[]和at都是返回pos位置的元素的引用，且他們內(nèi)部都會對pos進(jìn)行合法性檢查，二者不同的是，operator[]如果檢查到pos位置非法的時(shí)候，那么它會直接終止程序，報(bào)斷言錯(cuò)誤，而at是拋異常
operator[]
at
【注意】在release模式下檢查不出斷言錯(cuò)誤
6.增刪查改
| vector增刪查改 | 接口說明 |
|---|---|
| push_back | 尾插 |
| pop_back | 尾刪 |
| find | 查找（注意這個(gè)是算法模塊實(shí)現(xiàn)，不是vector的成員接口） |
| insert | 在position之前插入val |
| erase | 刪除position位置的數(shù)據(jù) |
| swap | 交換兩個(gè)vector的數(shù)據(jù)空間 |
| operator[] | 像數(shù)組一樣訪問 |
assign
assign函數(shù)用來替換vector對象中的數(shù)據(jù)，支持n個(gè)val替換和迭代區(qū)間替換
// 測試assign
void vector_test5()
{
vector<int> v1(5, 1);
v1.assign(5, 5);
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
vector<int> v2(3);
v2.assign(v1.begin(), v1.end());
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
}
push_back && pop_back
push_back是進(jìn)行尾插，pop_back是尾刪，這兩個(gè)函數(shù)比較簡單，我們看一下示例即可：
// 測試尾插 尾刪
void vector_test6()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
for (size_t i = 0; i < v.size(); ++i)
{
cout << v[i] << " ";
}
cout << endl;
v.pop_back();
v.pop_back();
for (size_t i = 0; i < v.size(); ++i)
{
cout << v[i] << " ";
}
cout << endl;
}
insert && erase
和string不同的是，為了提高規(guī)范性，STL的容器都統(tǒng)一使用iterator作為pos的類型，并且插入和刪除后會返回pos
所以我們?nèi)绻谥虚g插入或者刪除數(shù)據(jù)的時(shí)候，可以和算法庫里的find配合起來使用
// 測試插入 刪除
void vector_test7()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
vector<int>::iterator pos = find(v.begin(),v.end(),3);
if (pos != v.end())
{
v.insert(pos,30);
}
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
pos = find(v.begin(), v.end(), 2);
if (pos != v.end())
{
v.erase(pos);
}
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
【注意】
在VS在，insert和erase之后會導(dǎo)致pos迭代器失效，如果需要再次使用，需要更新pos
不過，在Linux下不會出現(xiàn)這個(gè)問題：
造成這個(gè)問題的根本原因是VS使用的是PJ版本對iterator進(jìn)行了封裝，在每次insert和earse之后會對迭代器進(jìn)行特殊處理，而g++使用的是SGI版本中的iterator原生指針，為了代碼的可移植性，我們統(tǒng)一認(rèn)為insert和earse使用之后迭代器會失效，所以需要再次使用迭代器，我們必須對其進(jìn)行更新，我們以移除vector中的所有偶數(shù)為例：
// 迭代器失效
void vecrtor8()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v.push_back(6);
vector<int>::iterator pos = v.begin();
while (pos != v.end())
{
if (*pos % 2 == 0)
{
pos = v.erase(pos);
}
else
{
++pos;
}
}
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
swap
和string一樣，由于算法庫里的swap函數(shù)存在深拷貝的問題，vector自己提供了一個(gè)不需要深拷貝的swap函數(shù)，用于交換兩個(gè)vector對象：
同時(shí)，為了避免我們不使用成員函數(shù)的swap，vector還將算法庫中的vector進(jìn)行了重載，然后該重載函數(shù)的內(nèi)部又去調(diào)用成員函數(shù)swap:
// 測試交換
void vector_test9()
{
vector<int> v1(5, 1);
vector<int> v2(5, 2);
vector<int> v3(5, 3);
v1.swap(v2);
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
std::swap(v1, v3);
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
}
三、vector深度剖析及模擬實(shí)現(xiàn)
1.核心框架
我們學(xué)習(xí)STL可以去閱讀別人優(yōu)秀的代碼，然后理解其中的邏輯和細(xì)節(jié)后我們自己去獨(dú)立實(shí)現(xiàn)幾次，因此我們可以對閱讀STL的源碼，但是當(dāng)前階段我們只需要學(xué)習(xí)STL庫的核心框架，并不需要逐行進(jìn)行的閱讀，其中有些語法我們也無法理解，我們也可以閱讀優(yōu)秀的書籍，我這里推薦侯捷老師的《STL源碼剖析》,這本書使用的是SGI版本，這個(gè)版本適合閱讀，《STL源碼剖析》電子版和《stl30》源碼我放在了下面，需要的自?。?/p>
STL源碼剖析：https://www.aliyundrive.com/s/Nc4mpLC43kj
stl30：https://www.aliyundrive.com/s/pnwMuB9uwEN
我們就可以得到vector源碼的核心框架：
namespace hdp
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
// 成員函數(shù)
// ......
private:
T* _start;
T* _finish;
T* _endofstorage;
};
}
我們可以看到，vector和string一樣，都是一個(gè)指針指向一個(gè)動態(tài)開辟的數(shù)組，但是二者不同的是，string是用_size和_capacity兩個(gè)size_t 的成員變量來維護(hù)這塊空間，而vector是用_finish和_endofstorage兩個(gè)指針來維護(hù)這塊空間，其中二者在本質(zhì)上是一樣的，其中_size=_finish-_start;_capacity=_endofstorage -_start;
2.reserve使用memcpy拷貝問題
我們模擬實(shí)現(xiàn)的reserve函數(shù)如下：
// 預(yù)留空間
void reserve(size_t n)
{
if (n > capacity())
{
size_t oldSize = size();
T* tmp = new T[n];
// 如果_start不為空則進(jìn)行拷貝
if (_start)
{
memcpy(tmp, _start, sizeof(T) * oldSize); // 深層次的深拷貝的時(shí)候會出錯(cuò)
delete[] _start;
}
_start = tmp;
_finish = tmp + oldSize;
_endofstorage = _start + n;
}
}
我們初步認(rèn)識的時(shí)候可能認(rèn)為這段代碼沒有問題，但是它對于內(nèi)置類型來說確實(shí)是沒有問題的，也進(jìn)行了深拷貝，但是它對于需要進(jìn)行深拷貝的自定義類型來說就有問題了，如下：
void vector_test_copy()
{
hdp::vector<vector<int>> vv;
vector<int> v(5, 1);
vv.push_back(v);
vv.push_back(v);
vv.push_back(v);
vv.push_back(v);
vv.push_back(v);
}
程序報(bào)錯(cuò)的原因如下：
當(dāng)我們插入4個(gè)v對象的時(shí)候，如上圖，pu_back內(nèi)部就會調(diào)用reserve函數(shù)進(jìn)行擴(kuò)容，擴(kuò)容時(shí)雖然我們進(jìn)行了深拷貝，但是空間的內(nèi)容我們是使用memcpy按字節(jié)拷貝的，這里導(dǎo)致原來的vv里面的v元素和現(xiàn)在的vv里的元素指向同一塊空間，當(dāng)我們拷貝完畢之后，使用delete[]釋放空間原來的空間的時(shí)候使得同一塊空間被釋放了兩次，因?yàn)関(自定義類型)會調(diào)用自身的析構(gòu)函數(shù)，所以現(xiàn)在的vv里面的元素都執(zhí)行已經(jīng)被釋放了的空間，如下圖：
所以我們在reserve函數(shù)的內(nèi)部不能時(shí)候memcpy函數(shù)直接按照字節(jié)為單位拷貝原來空間中的各個(gè)元素，因?yàn)檫@些元素也可能指向一塊動態(tài)開辟的空間，而是應(yīng)該調(diào)用每個(gè)元素的拷貝構(gòu)造進(jìn)行拷貝，如下圖：
對于reserve函數(shù)的具體實(shí)現(xiàn)如下：
// 預(yù)留空間
void reserve(size_t n)
{
if (n > capacity())
{
size_t oldSize = size();
T* tmp = new T[n];
// 如果_start不為空則進(jìn)行拷貝
if (_start)
{
for (size_t i = 0; i < oldSize; ++i)
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = tmp + oldSize;
_endofstorage = _start + n;
}
}
對于代碼中tmp[i] = _start[i],我們可能認(rèn)為是賦值運(yùn)算符重載，其實(shí)不是這樣的，因?yàn)檫@里只是為 了完成初始化工作，所以編譯或會自動調(diào)用拷貝構(gòu)造函數(shù)。
【總結(jié)】
1.memcpy是內(nèi)存的二進(jìn)制格式拷貝，將一段內(nèi)存空間中內(nèi)容原封不動的拷貝到另外一段內(nèi)存空間中
2.如果拷貝的是自定義類型的元素，memcpy既高效又不會出錯(cuò)，但如果拷貝的是自定義類型元素，并且自定義類型元素中涉及到資源管理時(shí)，就會出錯(cuò)，因?yàn)閙emcpy的拷貝實(shí)際是淺拷貝
【結(jié)論】如果對象中涉及到資源管理時(shí)，千萬不能使用memcpy進(jìn)行對象之間的拷貝，因?yàn)閙emcpy是淺拷貝，否則可能會引起內(nèi)存泄漏甚至程序崩潰
3.構(gòu)造函數(shù)錯(cuò)誤調(diào)用問題
我們模擬實(shí)現(xiàn)構(gòu)造函數(shù)中 的迭代區(qū)間構(gòu)造和n格val構(gòu)造后，會發(fā)現(xiàn)一個(gè)問題，我們使用n個(gè)val來構(gòu)造其他類型的對象的時(shí)候沒有問題，但是構(gòu)造int類型的對象時(shí)會編譯出錯(cuò)：
// n個(gè)val初始化
vector(size_t n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
reserve(n);
for (size_t i = 0; i < n; ++i)
{
push_back(val);
}
}
// 迭代器初始化
template <class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
while (first != last)
{
push_back(*first);
++first;
}
}
這是由于編譯器在進(jìn)行模板實(shí)例化和函數(shù)參數(shù)匹配時(shí)會調(diào)用最匹配的一個(gè)函數(shù)，當(dāng)我們將T實(shí)例化為int的時(shí)候，由于兩個(gè)參數(shù)都是int，所以對于迭代器構(gòu)造函數(shù)來說，它會直接將InputIterator實(shí)例化為int;對于n個(gè)val的構(gòu)造來說，它需要將T實(shí)例化為int，還需要將第一參數(shù)隱式轉(zhuǎn)換為size_t，所以這個(gè)時(shí)候，編譯器會調(diào)用迭代器構(gòu)造，同時(shí)迭代器構(gòu)造內(nèi)部會對first進(jìn)行解引用，所以這個(gè)報(bào)錯(cuò)"非法的間接尋址"
對于這個(gè)問題，我們有很多的解決方式：比如調(diào)用時(shí)將第一個(gè)參數(shù)強(qiáng)轉(zhuǎn)為size_t,又或?qū)個(gè)val構(gòu)造的第一個(gè)參數(shù)設(shè)置為int,我們這里和STL源碼保持一致–提供第一個(gè)參數(shù)為int的n個(gè)val構(gòu)造的重載函數(shù)：
// n個(gè)val初始化
vector(size_t n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
reserve(n);
for (size_t i = 0; i < n; ++i)
{
push_back(val);
}
}
vector(int n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
reserve(n);
for (int i = 0; i < n; ++i)
{
push_back(val);
}
}
// 迭代器初始化
template <class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
while (first != last)
{
push_back(*first);
++first;
}
}
4.insert和 erase迭代器失效問題
迭代器的主要作用就是讓算法能夠不用關(guān)心底層數(shù)據(jù)結(jié)構(gòu)，其底層實(shí)際就是一個(gè)指針，或者是對指針進(jìn)行了封裝，比如：vector的迭代器就是原生態(tài)指針T 。因此迭代器失效，實(shí)際就是迭代器底層對應(yīng)指針?biāo)赶虻目臻g被銷毀了，而使用一塊已經(jīng)被釋放的空間，造成的后果是程序崩潰(即如果繼續(xù)使用已經(jīng)失效的迭代器，程序可能會崩潰)。
對于vector可能會導(dǎo)致其迭代器失效的操作有：會引起其底層空間改變的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、push_back等
我們模擬實(shí)現(xiàn)的insert和earse函數(shù)如下：
// 在pos位置插入數(shù)據(jù)
// 迭代器失效 : 擴(kuò)容引起，野指針問題
iterator insert(iterator pos, const T& val)
{
// 斷言pos的位置
assert(pos >= _start);
assert(pos < _finish);
// 空間不夠進(jìn)行擴(kuò)容
if (_finish == _endofstorage)
{
size_t len = pos - _start;
size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newCapacity);
// 擴(kuò)容會導(dǎo)致pos迭代器失效，需要更新處理一下
pos = _start + len;
}
// 挪動數(shù)據(jù)
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = val;
++_finish;
return pos;
}
// 刪除pos位置數(shù)據(jù)
iterator erase(iterator pos)
{
// 斷言pos的位置
assert(pos >= _start);
assert(pos < _finish);
// 挪動數(shù)據(jù)
iterator begin = pos + 1;
while (begin < _finish)
{
*(begin - 1) = *begin;
++begin;
}
--_finish;
return pos;
}
我們在VS在insert和erase調(diào)用之后迭代器會失效，再次訪問的時(shí)候會報(bào)錯(cuò)，這是因?yàn)镻J版本下的iterator不是原生指針，如下：
可以看到，VS中的迭代器是一個(gè)類，當(dāng)我們進(jìn)行insert和erase調(diào)用之后，iterator中的某個(gè)函數(shù)可能會將pos置為空或者其他操作，所以我們再次訪問pos位置的數(shù)據(jù)就會報(bào)錯(cuò)，除非我們每次調(diào)用之后都更新pos:
在linux在，g++卻不會出現(xiàn)這樣的問題，這個(gè)是因?yàn)間++使用的是SGI版本，該版本的iterator是一個(gè)原生指針，同時(shí)它的insert和erase的內(nèi)部實(shí)現(xiàn)和我們模擬實(shí)現(xiàn)的類似。
這里也存在一個(gè)問題，lnsert 和erase 之后pos的意義變了–我們插入元素之后pos不再指向原來的元素，而是指向我們新插入元素的位置；erase之后也不再指向原來的元素，而是指向該元素的后一個(gè)元素，特別是當(dāng)erase尾部數(shù)據(jù)之后，pos就等于_finish
【總結(jié)】
erase刪除pos位置元素后，pos位置之后的元素會往前搬移，沒有導(dǎo)致底層空間的改變，理論上講迭代器不應(yīng)該會失效，但是：如果pos剛好是最后一個(gè)元素，刪完之后pos剛好是end的位置，而end位置是沒有元素的，那么pos就失效了。因此刪除vector中任意位置上元素時(shí)，vs就認(rèn)為該位置迭代器失效了
SGI STL中，迭代器失效后，代碼并不一定會崩潰，但是運(yùn)行結(jié)果肯定不對，如果it不在begin和end范圍內(nèi)，肯定會崩潰的
我們統(tǒng)一認(rèn)為insert和erase之后，迭代器失效了，更新之后才能繼續(xù)使用，這樣保證了代碼的跨平臺性文章來源：http://www.zghlxwxcb.cn/news/detail-421577.html
迭代器失效解決辦法：在使用前，對迭代器重新賦值即可文章來源地址http://www.zghlxwxcb.cn/news/detail-421577.html
5.模擬實(shí)現(xiàn)完整代碼
6.1 vector.h
#pragma once
namespace hdp
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
// 迭代器
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
// const 迭代器
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
// 重載[]
T& operator[](size_t pos)
{
assert(pos < size());
return *(_start + pos);
}
// const 重載[]
const T& operator[](size_t pos) const
{
assert(pos < size());
return *(_start + pos);
}
// 無參構(gòu)造
vector()
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{}
// n個(gè)val初始化
vector(size_t n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
reserve(n);
for (size_t i = 0; i < n; ++i)
{
push_back(val);
}
}
vector(int n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
reserve(n);
for (int i = 0; i < n; ++i)
{
push_back(val);
}
}
// 迭代器初始化
template <class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
while (first != last)
{
push_back(*first);
++first;
}
}
// 拷貝構(gòu)造
// v1(v2) 寫法1
/*vector(const vector<T>& v)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
reserve(v.capacity());
for (const auto& e : v)
{
push_back(e);
}
}*/
// 拷貝構(gòu)造 寫法2
vector(const vector<T>& v)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
vector<T> tmp(v.begin(), v.end());
swap(tmp);
}
// v1 = v2
// v1 = v1; // 極少數(shù)情況，能保證正確性，所以這里就這樣寫沒什么問題
// 賦值重載
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
// 析構(gòu)
~vector()
{
delete[] _start;
_start = _finish = _endofstorage = nullptr;
}
// 預(yù)留空間
void reserve(size_t n)
{
if (n > capacity())
{
size_t oldSize = size();
T* tmp = new T[n];
// 如果_start不為空則進(jìn)行拷貝
if (_start)
{
// memcpy(tmp, _start, sizeof(T) * oldSize); // 深層次的深拷貝的時(shí)候會出錯(cuò)
for (size_t i = 0; i < oldSize; ++i)
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = tmp + oldSize;
_endofstorage = _start + n;
}
}
//調(diào)整空間大小
void resize(size_t n, T val = T())
{
if (n > capacity())
{
reserve(n);
}
if (n > size())
{
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
else
{
_finish = _start + n;
}
}
// 在尾部插入數(shù)據(jù)
void push_back(const T& val)
{
if (_finish == _endofstorage)
{
size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newCapacity);
}
*_finish = val;
++_finish;
}
// 刪除尾部數(shù)據(jù)
void pop_back()
{
// 為空時(shí)不進(jìn)行刪除
assert(!empty());
--_finish;
}
// 交換
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._endofstorage);
}
// 在pos位置插入數(shù)據(jù)
// 迭代器失效 : 擴(kuò)容引起，野指針問題
iterator insert(iterator pos, const T& val)
{
// 斷言pos的位置
assert(pos >= _start);
assert(pos < _finish);
// 空間不夠進(jìn)行擴(kuò)容
if (_finish == _endofstorage)
{
size_t len = pos - _start;
size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newCapacity);
// 擴(kuò)容會導(dǎo)致pos迭代器失效，需要更新處理一下
pos = _start + len;
}
// 挪動數(shù)據(jù)
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = val;
++_finish;
return pos;
}
// 刪除pos位置數(shù)據(jù)
iterator erase(iterator pos)
{
// 斷言pos的位置
assert(pos >= _start);
assert(pos < _finish);
// 挪動數(shù)據(jù)
iterator begin = pos + 1;
while (begin < _finish)
{
*(begin - 1) = *begin;
++begin;
}
--_finish;
return pos;
}
// 清空
void clear()
{
_start = _finish;
}
// 判空
bool empty()
{
return _start == _finish;
}
// 獲取數(shù)據(jù)個(gè)數(shù)
size_t size()
{
return _finish - _start;
}
// 獲取容量
size_t capacity()
{
return _endofstorage - _start;
}
private:
iterator _start;
iterator _finish;
iterator _endofstorage;
};
}
6.2 test.cpp
#include <iostream>
#include <vector>
#include <assert.h>
#include <algorithm>
using namespace std;
#include "vector.h"
// 測試三種遍歷
void test_vector1()
{
hdp::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
// 下標(biāo)+[]遍歷
for (size_t i = 0; i < v.size(); ++i)
{
cout << v[i] << " ";
}
cout << endl;
// 迭代器遍歷
hdp::vector<int>::iterator it = v.begin();
while (it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
// 范圍for遍歷
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
// 測試尾插和容量改變
void test_vector2()
{
hdp::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
cout << v.capacity() << endl;
v.reserve(10);
cout << v.capacity() << endl;
// 比當(dāng)前容量小時(shí)，不縮容
v.reserve(4);
cout << v.capacity() << endl;
v.resize(8);
v.resize(15, 1);
v.resize(3);
}
// 測試插入
void test_vector3()
{
hdp::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.insert(v.begin(), 4);
v.insert(v.begin() + 2, 4);
// 沒有find成員
//vector<int>::iterator it = v.find(3);
hdp::vector<int>::iterator it = find(v.begin(), v.end(), 3);
if (it != v.end())
{
v.insert(it, 30);
}
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
hdp::vector<int> v1;
v1.push_back(10);
v1.push_back(20);
v1.push_back(30);
v1.swap(v);
swap(v1, v);
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
}
void test_vector4()
{
hdp::vector<vector<int>> vv;
vector<int> v(5, 1);
vv.push_back(v);
vv.push_back(v);
vv.push_back(v);
vv.push_back(v);
vv.push_back(v);
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;
}
cout << endl;
}
// 測試刪除
void test_vector5()
{
// 要求刪除所有偶數(shù)
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
vector<int>::iterator it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
it = v.erase(it);
}
else
{
++it;
}
}
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
int main()
{
try
{
//test_vector1();
//test_vector2();
//TestVectorExpand();
//test_vector3();
//test_vector4();
test_vector5();
}
catch (const exception& e)
{
cout << e.what() << endl;
}
return 0;
}
到了這里，關(guān)于【C++STL】vector的使用及其模擬實(shí)現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[C++] STL_vector使用與常用接口的模擬實(shí)現(xiàn)](https://imgs.yssmx.com/Uploads/2024/02/672071-1.png)
![[STL] vector 模擬實(shí)現(xiàn)詳解](https://imgs.yssmx.com/Uploads/2024/02/595014-1.png)
