如何用STL源碼剖析vector容器

如何用STL源碼剖析vector容器，針對(duì)這個(gè)問(wèn)題，這篇文章詳細(xì)介紹了相對(duì)應(yīng)的分析和解答，希望可以幫助更多想解決這個(gè)問(wèn)題的小伙伴找到更簡(jiǎn)單易行的方法。

vector是我們?cè)赟TL中最常用的容器，我們對(duì)它的各種操作也都了然于胸。然而我們?cè)谑褂胿ector的時(shí)候總會(huì)有一種很虛的感覺(jué)，因?yàn)槲覀儾磺宄涌趦?nèi)部是如何實(shí)現(xiàn)的。在我們眼里宛如一個(gè)黑箱，既危險(xiǎn)又迷人。

為了打破這種顧慮，接下來(lái)我就帶大家深入vector底層，徹底弄懂vector接口內(nèi)部實(shí)現(xiàn)細(xì)節(jié)，打開(kāi)這個(gè)黑箱。這樣在使用vector的時(shí)候我們也就不會(huì)慌了，做到真正的了然于胸。

vector 底層原理概述

vector是動(dòng)態(tài)空間，隨著元素的增加，其內(nèi)部機(jī)制會(huì)自行擴(kuò)充空間來(lái)容納新元素。

vector動(dòng)態(tài)增加大小時(shí)，并不是在原空間之后持續(xù)新空間（因?yàn)楦緹o(wú)法保證原空間之后尚有可供配置的空間），而是以原大小的兩倍另外配置一塊較大的空間，然后將內(nèi)容拷貝過(guò)來(lái)，然后才開(kāi)始在原內(nèi)容之后構(gòu)造新元素，并釋放原空間，

重點(diǎn)源碼理解

１．迭代器內(nèi)部型別

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

template <class T, class Alloc = alloc>

class vector {

public:

// vector 的嵌套型別定義

typedef T value_type;

typedef value_type* iterator; // 迭代器本身是一個(gè)模板類的對(duì)象

typedef value_type& reference;

...

};

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

靈魂拷問(wèn)一：迭代器與指針有什么區(qū)別？

我們可以這樣理解，迭代器本質(zhì)上就是模板類產(chǎn)生的一個(gè)對(duì)象，而其運(yùn)算符*和->都是經(jīng)過(guò)運(yùn)算符重載實(shí)現(xiàn)的。這個(gè)對(duì)象指向vector的內(nèi)部元素（元素又是迭代器的對(duì)象），所以當(dāng)?shù)髦赶虻脑乇粍h除或者移動(dòng)，迭代器與元素就斷開(kāi)鏈接，迭代器也就沒(méi)有用了，也就是我們通常說(shuō)的迭代器失效。迭代器的行為類似指針，但是又有所區(qū)別。

反觀指針，指針與內(nèi)存是聯(lián)系在一起的。如果指針指向的內(nèi)存地址存儲(chǔ)的元素被刪除或者移動(dòng)，指針并不會(huì)因此失效，它依然指向了該地址。

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

vector::iterator ivite;

vector::iterator svite;

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

２．vector 的數(shù)據(jù)結(jié)構(gòu)

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

template <class T, class Alloc = alloc>

class vector {

...

protected:

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

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

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

...

};

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

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); }// 運(yùn)算符[]重載，能夠使用迭代器來(lái)訪問(wèn)元素

};

上面一些基礎(chǔ)操作已經(jīng)一目了然了，這里就不一一述說(shuō)了。這里只提兩點(diǎn)，第一，從上面代碼可以看出operator對(duì)運(yùn)算符[]進(jìn)行了重載，這樣能夠使迭代器像數(shù)組索引一樣遍歷vector。

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

靈魂拷問(wèn)二：為什么容器要設(shè)計(jì)成前閉后開(kāi)的特性？

這樣做是為了在遍歷容器元素時(shí)減少判斷條件。因?yàn)镾TL的核心是泛型編程，使得設(shè)計(jì)的接口是通用的。由于只有部分容器支持>和<運(yùn)算符重載，而!=則是全部容器都支持，所以遍歷元素的時(shí)候優(yōu)先使用!=重載運(yùn)算符。

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

vector vec;

auto it = vec.begin();

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

...

++it;

}

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

３．vector 的元素操作

vector 的構(gòu)造函數(shù)

vector的構(gòu)造函數(shù)有多種形式，下面摘取源碼中的部分代碼：

// 構(gòu)造函數(shù)，允許指定 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()); }

分別對(duì)應(yīng)如下初始化：

vector vec;

vector vec(2,3);

vector vec(2);

push_back() 與 pop_back()

當(dāng)我們以push_back()將新元素插入vector尾端時(shí)，該函數(shù)首先檢查是否還有備用空間，如果有就直接在備用空間上構(gòu)造元素，并調(diào)整迭代器finish。如果沒(méi)有備用空間了，就擴(kuò)充空間（重新配置、移動(dòng)數(shù)據(jù)、釋放原空間）。

void push_back(const T& x) {

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

construct(finish, x);

++finish;

}

else // 已無(wú)備用空間

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

}

插入函數(shù)原型為：

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

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

注：插入函數(shù)是將元素插入到對(duì)應(yīng)位置，原先該位置以及后面的元素都向后移動(dòng)一位。

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

void pop_back() {

--finish;

destroy(finish);

}

直接將尾部迭代器finish向前移動(dòng)一位，然后釋放掉。由于尾部迭代器finish指向的是最后一個(gè)元素的下一位，所以減一后正好是原來(lái)的最后一個(gè)元素。

erase() 與 clear()

erase()表示刪除vector的某一個(gè)元素或者某一區(qū)間內(nèi)的所有元素。

// 刪除 vector 的某一個(gè)位置的元素

iterator erase(iterator position) {

if (position + 1 != end())

copy(position + 1, finish, position);

--finish;

destroy(finish);

return position;

}

// 刪除 vector 的某一個(gè)區(qū)間的元素

iterator erase(iterator first, iterator last) {

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

destroy(i, finish);

finish = finish - (last - first);

return first;

}

如果不對(duì)erase()函數(shù)謹(jǐn)慎使用，可能會(huì)出現(xiàn)迭代器失效的問(wèn)題。

靈魂拷問(wèn)三：在什么情況下使用erase()函數(shù)迭代器會(huì)失效？

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

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

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

vec.erase(it);

}

}

由靈魂拷問(wèn)一可知，刪除元素后由于被刪除元素后面的數(shù)據(jù)都會(huì)發(fā)生移動(dòng)，所以后面的迭代器都會(huì)失效。故上述代碼在刪除了某個(gè)迭代器后，后面的++it遍歷已經(jīng)失去意義，不會(huì)得到正確的結(jié)果。

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

正確的寫法為：

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

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

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

}

else {

++it;

}

}

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

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

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