C++STL——容器-vector(含部分模擬實現，即地層實現原理）(含迭代器失效問題）

容器——vector

1.構造

模擬實現

2.迭代器

模擬實現：

?編輯

3.容量

模擬實現：

?4.元素的訪問

模擬實現

5.元素的增刪查改

迭代器失效問題：

思考問題

【注】：這里的模擬實現所寫的參數以及返回值，都是按照庫里的來實現的。

大家都知道，萬事開頭難，但只要將開頭做好，后面的就輕松多了。學習容器也是一樣的，只要將第一個容器string學明白，底層實現了然于胸之后，再學習后面的容器之后，你會發現，換湯不換藥，也就有一些不一樣的地方而已。

? ? ? ? 那么今天咱們重點要講迭代器的失效問題。廢話少說，讓咱們開始吧。

容器——vector

????????

這里涉及到了一個東西——模板，這個東西博主會在后面進行講解，大家只要記住這是一個泛型編程，即這里面的class T,這個T可以是任何的類型，而后面有個Alloc，這個叫內存管理器，咱們不用去管他，這個東西，編譯器會自動進行內存管理的。所以這里只要關注第一個參數即可。vector就類似于順序表。只不過這個順序表，是有類似于指向開頭的指針?，指向有效個數下一個位置的指針，有指向容量結尾的指針。比如：咱們將整形int?存入一個vector中，即可這樣寫：vector<int>。

即可，vector<int>算是一種類吧。

1.構造

這里面的所有的const allocator_type& alloc = allocator_type()，不用去管，這只是一種內存管理器，編譯器會自動處理的，并且寫參數的時候也不需要去寫。那么第一個是無參構造，第二個是構造并初始化n個val，第三個是使用迭代器進行初始化構造（這是一種范圍式的構造），第四個是拷貝構造（這是重點，后面會講它的模擬實現）。來上代碼：

OK，那么通過以上的代碼，博友們大概就已經知道它的構造方式了。這里需要強調的一點是：這里的auto后面加不加&,看的是你模板T是什么類型，因為范圍for本質（就是不加&）是賦值拷貝，既然是拷貝?，就有空間的消耗，要是int型還好，要是string型的呢？那你這個空間的消耗可謂是巨大。所以加上了&：傳引用，對于一些開空間消耗較大的T來說，可謂是福音啊。所以，建議還是都加上&吧。（當然，你要是根據具體情況來，那也可以）。

模擬實現

第一個沒啥，就是為空，就不看他的模擬實現了。

第二個：

vector(int n, const T& val = T())

{

????????reserve(n);

????????for (int i = 0; i < n; i++)

????????{

????????????????push_back(val);

????????}

}

這里的T()的意思是T類型的默認構造。這里還需要強調一個問題，也是困擾博主的一個問題，不過還好博主將它解決了：后面的代碼中你會看見vector<T>&v或者T&v。那么什么時候用第一個呢？第一個是當你準備用這一整個類型的時候(比如范圍for，你是不是得用v去拷貝另一個對象，這個時候v是對象，那么這個時候，v的類型是vector<int>，所以才會用到第一個），參數才會寫第一個。而第二個的v是T類型的值，比如int類型的值，并不是對象，所以說第二個主要應用于類似于插入值的時候。沒事，慢慢的從后面的代碼中體會。

就拿這一個舉例，這一個是不是要尾插一個值，所以說，這里是T&val，后面的T(),相當于給val初始化了。

第三個：

template <class InputIterator>

vector(InputIterator first, InputIterator last)

{

????????while (first != last)

????????{

????????????????push_back(*first);

????????????????++first;

????????}

}

這里如果說push_back,擴容了，那么這里可能會涉及到迭代器失效的問題（下面將），但這里假定它沒有擴容。

第四個：

vector(const vector<T>& v)

{

????????reserve(v.capacity());

????????for (auto& e : v)

????????{

????????????????push_back(e);

????????}

}

這里是拷貝構造，是不是將咱們上面提到的兩個問題全都涉及到了，即&問題與參數vector<T>&問題。

再來一個列表初始化的模擬實現：

vector(initializer_list<T> il)

{

????????reserve(il.size());

????????for (auto& e : il)

????????{

????????push_back(e);

????????}

}

列表初始化本質就是通過push_back來尾插數據。

2.迭代器

由于vector不支持重載流插入流提取，所以不可以像string類一樣直接輸出，它只能一個元素一個元素的輸出，也跟string類一樣，三種方法：

1.下標+[]：

for (size_t i = 0; i < v.size(); i++)

{

????????cout << v[i] << " ";

}

????????cout << endl;

2.迭代器：

bit::vector<int>::iterator it = v.begin();

while (it != v.end())

{

????????cout << *it << " ";

????????++it;

}

????????cout << endl;

3.范圍for：

for (auto e : v)

{

????????cout << e << " ";

}

????????cout << endl;

這里vector的迭代器跟string的一樣，因為都是迭代器嘛，但這里給上兩個圖，幫助大家理解：

模擬實現：

?給定三個位置，_start,一開始的元素位置，_finish有效數據個數的下一個位置,end_of_storage，容量到頭的那個位置。

typedef T* iterator;

typedef const T* const_iterator;

iterator begin()

{

????????return _start;

}

iterator end()

{

????????return _finish;

}

const_iterator begin() const

{

????????return _start;

}

const_iterator end() const

{

????????return _finish;

}

3.容量

這里跟string類差不多，都是一樣的，但這里有兩個重點的，咱們模擬實現一下：1.size():獲取數據個數.2.capacity():獲取容量大小3.empty():判斷是否為空。4.resize():改變vector的size。5.reserve():?改變vector的capacity。

我記得string里面并沒有說capacity()的增長速度，那么在這咱們來講一下：

std::vector<int>::size_type sz;std::vector<int> foo;sz = foo.capacity();std::cout << "making foo grow:\n";for (int i=0; i<100; ++i) {foo.push_back(i);if (sz!=foo.capacity()) {sz = foo.capacity();std::cout << "capacity changed: " << sz << '\n';}}std::vector<int> bar;sz = bar.capacity();bar.reserve(100);   // this is the only difference with foo abovestd::cout << "making bar grow:\n";for (int i=0; i<100; ++i) {bar.push_back(i);if (sz!=bar.capacity()) {sz = bar.capacity();std::cout << "capacity changed: " << sz << '\n';}}

這是我直接截取的官方庫里的代碼，咱們來看邏輯分析：先定義一個sz用來存儲capacity()的變化情況。?之后寫一個for循環用來不斷的尾插數據，再來判斷容量等不等于之前的，再打印出容量，可以看出容量的變化方式，幾乎是成2倍的速度增長的。再來看一下子擴容好100個空間的，那么這個可以看出容量幾乎沒什么變化，因為空間提前被開好了。雖然容量在g++上是按照2倍增長的，但是在vs上是按照1.5倍增長的，所以說為什么我在string這一篇文章中說，擴容多少是看編譯器的，編譯器不同，擴容的速率也是不同的。

ok，那么接下來看兩個重點的，先來看第一個resize：

參數也是按照庫里來寫的。resize起到了對數據的判斷是否要插入以及刪除。以上就是resize的模擬實現。思路：如果說你要插入的數據個數n大于了這里的capacity，那么就需要擴容了，擴容之后，_start+n就是容量了（capacity），擴容馬上講。那么_finish不可以等于容量，且一定比容量小吧，之后在_finish這插入數據，之后++_finish。更新_finish的位置，直到n。如果說n比capacity小，說明要刪除數據了。刪除數據就直接?讓有效數據的下一個位置更新到你要保存的元素的個數即可（即_start+n）。

第二個：reserve

?這兒的邏輯跟string的邏輯差不多，唯一的一個坑就是我在代碼中注釋的，所以為了解決這個問題，你直接用原來的size不就可以了嗎，不用新的size，就可以避免_finish為0的問題。以上也是模擬實現。

模擬實現：

由于resize以及reserve的模擬實現咱們已經寫過了，下面咱們寫size的那幾個：

size_t capacity() const

{

????????return _end_of_storage - _start;

}

size_t size() const

{

????????return _finish - _start;

}

?4.元素的訪問

這里其實跟string差不多，咱們只講一個，

模擬實現

T& operator[](size_t i)

{

????????assert(i < size());

????????return _start[i];

}

5.元素的增刪查改

在這也會講到咱們最重要的部分：迭代器的失效問題。

1.尾插

來看它的模擬實現：

這里需要先確定一下是否需要擴容，如果說需要擴容，那么就先擴容，之后往_finish處插入數據，之后更新_finish的位置即可。

2.pop_back:尾刪

跟push_back的差不多。

3.insert:在position之前插入val

來看它的模擬實現：

這兒有一個迭代器失效問題，待會講完erase一塊講。這個代碼的邏輯：先判斷pos必須在_start與_finish之間。需要擴容的時候記得擴容。之后定義一個迭代器，讓_finish賦給它，之后一直到pos的位置，往后挪一位，之后在pos這個地方插入數據，更新_finish。不知道大家發沒發現一個規律：就是比如說我在pos插入元素，那么我一開始定義的地方一定是尾部，然后往后挪動數據，直到pos位置空出一個位置即可。而對于刪除pos位置的元素，一般都是從pos位置開始定義，然后往前挪數據，直到有效數據的最后位置。?

4.erase：刪除position位置的數據

來看模擬實現：

?這個代碼邏輯也很簡單，從pos位置開始定義，一直往前挪動一個數據，直到尾部為止，別忘了更新_finish。

迭代器失效問題：

迭代器的主要作用就是讓算法能夠不用關心底層數據結構，其底層實際就是一個指針，或者是對指針進行了封裝，比如：vector的迭代器就是原生態指針T* 。因此迭代器失效，實際就是迭代器底層對應指針所指向的空間被銷毀了，而使用一塊已經被釋放的空間，造成的后果是程序崩潰(即

如果繼續使用已經失效的迭代器，程序可能會崩潰)。類似于野指針，指向了一塊不存在空間。

1.擴容導致的迭代器失效：

看圖，再看咱們模擬實現的?insert，假設空間不夠了，但還要插入數據，是不是得擴容啊？擴容一般都是異地擴容，但是異地擴容，你的_start,_finish,enf_of_storge都更新過去了，但是迭代器it呢？它沒有更新啊同志們，它還指向了一塊已經被釋放的空間，你說這迭代器能不失效嗎？解決辦法也很簡單，記住原來it的位置，將它映射到新開的空間上即可。insert的模擬實現已經給出了答案。但你也可以，提前先reserve好足夠的空間（在定義迭代器之前先開好空間），這樣就完美的避開了這個問題。

2.由于刪除元素導致的迭代器失效

假定咱們刪除了一個元素2對吧，那么2后面的元素的3會往前1移動，代替2的位置，但是呢，你可以認為這個迭代器比較傻，它只認它一開始指向的那個元素，如果那個元素沒有了，那么它會認為那個元素所在的空間被銷毀了，那么這個迭代器也就失效了。比如上圖中的it迭代器，就是這個原理。那么以此類推，it后面的元素是不是都要往前移動啊，那么如果說it后面還有迭代器，那么自然it后面的迭代器全部失效。解決辦法也很簡單，就是再重新將被刪元素的下一個空間重新賦值給it，那么被刪元素的下一個空間其實就是it所指向的空間，因為被刪元素的下一個元素往前挪動了一格嘛，所以說，這個空間就是it所指向的空間，就是原被刪元素的空間。

那么失效后的迭代器，都不可再對他們進行++，--等操作，當然，在vs上會強制檢查，但在其他編譯器上，可能還可以正常運行，這也是看編譯器的。

那么insert的返回值是插入那個元素的空間位置。而erase的返回值是被刪元素的下一個元素的空間，其實都是it這個位置。

思考問題

vector v{ 1, 2, 3, 4 };

auto it = v.begin();

while (it != v.end())

{

????????if (*it % 2 == 0)

????????{

????????????????v.erase(it);

??????????????????++it;

????????}

??????

}

那么看上面這個代碼，對嗎？為什么不對？?

肯定不對啊，1.首先是迭代器失效的問題，你erase后是不可以對迭代器進行加減操作的。

2.erase刪除的迭代器如果是最后一個元素，刪除之后it已經超過end，此時迭代器是無效的，++it導致程序崩潰。是因為進去循環的條件是it不等于_finish（這個循環式erase中的循環），而刪除尾部元素的時候，it被定義為指向尾部的下一個元素，那么就可以進入循環，之后it會一直++，那這肯定不行，一直訪問的是沒有的空間。

3.就算你給erase重新賦值，但是又有一個問題：比如vector<int> v={1,2,2,3,4},有兩個連續的偶數，你刪除了第一個偶數之后，第二個偶數挪到了第一個偶數的位置，然后it++，會直接跳過第二個偶數，那這樣第二個偶數就刪不了了，不可以，所以，完美的解決辦法就是，當它是偶數的時候，直接刪，當它是奇數的時候，再++.即：

現在迭代器失效的問題，我已經全部講清楚了，也講的很透了。?

5.swap

void swap(vector<T>& v)

{

????????std::swap(_start, v._start);

????????std::swap(_finish, v._finish);

????????std::swap(_end_of_storage, v._end_of_storage);

}

那么現在咱們再來看一下現代寫法的賦值有多精妙。

// v1 = v3

vector<T>& operator=(vector<T> v)

{

????????swap(v);

????????return *this;

}

首先，先對v3進行傳值傳參，需要調用拷貝構造，那么拷貝構造就是再次構造出一個與v3一樣大的空間，完了之后，交換v1與v（v3），那么咱們v3是想要的，而v1是不想要的，通過交換正好拿到了v3，那么v1也給了v，而v是一個局部變量啊，出了作用域就銷毀了。所以說，v出了函數就銷毀了，反正也不要了，是不是很nice呀，哈哈哈哈哈，確實，我也這么想的，當年創造這個寫法的人肯定也是這么想的。?

OK，vector的內容就這些，由于咱們有了string的基礎，所以學起來vector就是很簡單了，除了一些特殊的坑外，其他的也沒什么了。

以上內容均我個人理解，若有不對，還請各位大佬指出，謝謝啦！

本篇完...................