|
寫在前面 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()); } 作者：編程異思坊 鏈接：https://www.jianshu.com/p/8b98cdc6f7a4 著作權(quán)歸作者所有,。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處,。 |
|
|
