如何用STL源碼剖析vector容器

如何用STL源碼剖析vector容器，針對這個問題，這篇文章詳細介紹了相對應的分析和解答，希望可以幫助更多想解決這個問題的小伙伴找到更簡單易行的方法。

vector是我們在STL中最常用的容器，我們對它的各種操作也都了然于胸。然而我們在使用vector的時候總會有一種很虛的感覺，因為我們不清楚接口內部是如何實現的。在我們眼里宛如一個黑箱，既危險又迷人。

為了打破這種顧慮，接下來我就帶大家深入vector底層，徹底弄懂vector接口內部實現細節，打開這個黑箱。這樣在使用vector的時候我們也就不會慌了，做到真正的了然于胸。

vector 底層原理概述

vector是動態空間，隨著元素的增加，其內部機制會自行擴充空間來容納新元素。

vector動態增加大小時，并不是在原空間之后持續新空間（因為根本無法保證原空間之后尚有可供配置的空間），而是以原大小的兩倍另外配置一塊較大的空間，然后將內容拷貝過來，然后才開始在原內容之后構造新元素，并釋放原空間，

重點源碼理解

１．迭代器內部型別

下面我們來看看STL源碼里面是如何來定義迭代器的吧。

template <class T, class Alloc = alloc>

class vector {

public:

// vector 的嵌套型別定義

typedef T value_type;

typedef value_type* iterator; // 迭代器本身是一個模板類的對象

typedef value_type& reference;

...

};

如上面代碼所示，迭代器iterator本身是一個類類型，運算符*被重載。迭代器iterator指向vector的內部元素，可以理解為iterator與vector的內部元素捆綁在一起，其行為類似指針，但是又不能把它當作指針。

靈魂拷問一：迭代器與指針有什么區別？

我們可以這樣理解，迭代器本質上就是模板類產生的一個對象，而其運算符*和->都是經過運算符重載實現的。這個對象指向vector的內部元素（元素又是迭代器的對象），所以當迭代器指向的元素被刪除或者移動，迭代器與元素就斷開鏈接，迭代器也就沒有用了，也就是我們通常說的迭代器失效。迭代器的行為類似指針，但是又有所區別。

反觀指針，指針與內存是聯系在一起的。如果指針指向的內存地址存儲的元素被刪除或者移動，指針并不會因此失效，它依然指向了該地址。

根據上述定義，迭代器可以這樣聲明：

vector::iterator ivite;

vector::iterator svite;

看完上面的源碼，我們也就清楚為什么迭代器要這樣聲明了。

２．vector 的數據結構

vector使用兩個迭代器start和finish來表示已使用空間的范圍，并以迭代器end_of_storage指向分配空間的尾端。代碼如下：

template <class T, class Alloc = alloc>

class vector {

...

protected:

iterator start; // 表示目前使用空間的頭

iterator finish; // 表示目前使用空間的尾，即最后一個元素的下一個元素

iterator end_of_storage; // 表示目前分配的整個空間的尾

...

};

利用以上三個迭代器，我們能夠封裝vector的各種成員函數。

template <class T, class Alloc = alloc>

class vector {

...

public:

iterator begin() { return start; }

iterator end() { return finish; }

size_type size() const { return size_type(end() - begin()); }

bool empty() const { return begin() == end(); }

reference front() { return *begin(); }

reference back() { return *(end() - 1); }

reference operator[](size_type n) { return *(begin() + n); }// 運算符[]重載，能夠使用迭代器來訪問元素

};

上面一些基礎操作已經一目了然了，這里就不一一述說了。這里只提兩點，第一，從上面代碼可以看出operator對運算符[]進行了重載，這樣能夠使迭代器像數組索引一樣遍歷vector。

第二，迭代器finish指向的是vector最后一個元素的下一個元素，封裝的end()函數也如此。這也就是我們常常說的vector的前閉后開特性。

靈魂拷問二：為什么容器要設計成前閉后開的特性？

這樣做是為了在遍歷容器元素時減少判斷條件。因為STL的核心是泛型編程，使得設計的接口是通用的。由于只有部分容器支持>和<運算符重載，而!=則是全部容器都支持，所以遍歷元素的時候優先使用!=重載運算符。

如果將end()指向容器最后一個元素的下一個，則遍歷操作只需要寫成：

vector vec;

auto it = vec.begin();

while (it != vec.end()) {

...

++it;

}

但是如果end()指向的是最后一個元素，上述代碼會少遍歷一個元素，這就需要在while循環里增加額外的判斷條件，并且這個判斷條件可能因容器的不同要進行修改，而上述代碼在任何順序容器都能這樣調用，減少了很多多余工作。

３．vector 的元素操作

vector 的構造函數

vector的構造函數有多種形式，下面摘取源碼中的部分代碼：

// 構造函數，允許指定 vector 大小和初值

vector() : start(0), finish(0), end_of_storage(0) {}

vector(size_type n, const T& value) { fill_initialize(n, value); }

explicit vector(size_type n) { fill_initialize(n, T()); }

分別對應如下初始化：

vector vec;

vector vec(2,3);

vector vec(2);

push_back() 與 pop_back()

當我們以push_back()將新元素插入vector尾端時，該函數首先檢查是否還有備用空間，如果有就直接在備用空間上構造元素，并調整迭代器finish。如果沒有備用空間了，就擴充空間（重新配置、移動數據、釋放原空間）。

void push_back(const T& x) {

if (finish != end_of_storage) { // 還有備用空間

construct(finish, x);

++finish;

}

else // 已無備用空間

insert_aux(end(), x); // 插入函數

}

插入函數原型為：

void insert_aux(iterator position, const T& x);

這個函數比較長，具體思路：在有備用空間情況下，在備用空間起始處構造一個元素，迭代器finish自增一；在無備用空間情況下，重新配置兩倍的原內存空間，將原vector的內容拷貝到新vector中，再釋放掉原空間。

注：插入函數是將元素插入到對應位置，原先該位置以及后面的元素都向后移動一位。

刪除vector尾部元素操作pop_back()更加簡單。

void pop_back() {

--finish;

destroy(finish);

}

直接將尾部迭代器finish向前移動一位，然后釋放掉。由于尾部迭代器finish指向的是最后一個元素的下一位，所以減一后正好是原來的最后一個元素。

erase() 與 clear()

erase()表示刪除vector的某一個元素或者某一區間內的所有元素。

// 刪除 vector 的某一個位置的元素

iterator erase(iterator position) {

if (position + 1 != end())

copy(position + 1, finish, position);

--finish;

destroy(finish);

return position;

}

// 刪除 vector 的某一個區間的元素

iterator erase(iterator first, iterator last) {

iterator i = copy(last, finish, first);

destroy(i, finish);

finish = finish - (last - first);

return first;

}

如果不對erase()函數謹慎使用，可能會出現迭代器失效的問題。

靈魂拷問三：在什么情況下使用erase()函數迭代器會失效？

通常我們寫出這樣的代碼迭代器會失效。

for(auto it = vec.begin();it != vec.end();++it) {

if(/* 刪除某元素的判斷條件 */) {

vec.erase(it);

}

}

由靈魂拷問一可知，刪除元素后由于被刪除元素后面的數據都會發生移動，所以后面的迭代器都會失效。故上述代碼在刪除了某個迭代器后，后面的++it遍歷已經失去意義，不會得到正確的結果。

那應該如何更改呢？由前面刪除vector的某一個位置的元素的源代碼可知，erase()返回的是一個迭代器，這個迭代器實際上是被刪除元素的下一個元素綁定的迭代器，這個迭代器是數據移動后新的有效的迭代器。也可以說是更新了迭代器。

正確的寫法為：

for(auto it = vec.begin();it != vec.end();) {

if(/* 刪除某元素的判斷條件 */) {

it = vec.erase(it); // 更新了迭代器

}

else {

++it;

}

}

clear()表示清空vector上的所有元素。

void clear() { erase(begin(), end()); }

關于如何用STL源碼剖析vector容器問題的解答就分享到這里了，希望以上內容可以對大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關注億速云行業資訊頻道了解更多相關知識。