C語言數(shù)據(jù)結(jié)構(gòu)之vector底層實(shí)現(xiàn)機(jī)制解析
一、vector底層實(shí)現(xiàn)機(jī)制刨析
通過分析 vector 容器的源代碼不難發(fā)現(xiàn),它就是使用 3 個(gè)迭代器(可以理解成指針)來表示的:
其中statrt指向vector 容器對(duì)象的起始字節(jié)位置;
finish指向當(dāng)前最后一個(gè)元素的末尾字節(jié)
end_of指向整個(gè) vector 容器所占用內(nèi)存空間的末尾字節(jié)。
如圖 演示了以上這 3 個(gè)迭代器分別指向的位置
如圖 演示了以上這 2個(gè)迭代器分別指向的位置
在此基礎(chǔ)上,將 3 個(gè)迭代器兩兩結(jié)合,還可以表達(dá)不同的含義,例如:
start 和 finish 可以用來表示 vector 容器中目前已被使用的內(nèi)存空間;
finish 和 end_of可以用來表示 vector 容器目前空閑的內(nèi)存空間;
start和 end_of可以用表示 vector 容器的容量。
二、vector的核心框架接口的模擬實(shí)現(xiàn)
1.vector的迭代器實(shí)現(xiàn)
typedef T* Iteratot;
typedef T* const_Iteratot;
Iteratot cend()const { return final_end; } Iteratot cbegin()const { return start; } Iteratot end() { return final_end; } Iteratot begin() { return start; }
vector的迭代器是一個(gè)原生指針,他的迭代器和String相同都是操作指針來遍歷數(shù)據(jù):
- begin()返回的是vector 容器對(duì)象的起始字節(jié)位置;
- end()返回的是當(dāng)前最后一個(gè)元素的末尾字節(jié);
2.reserve()擴(kuò)容
void reserve(size_t n) { if (n > capacity()) { T* temp = new T [n]; //把statrt中的數(shù)據(jù)拷貝到temp中 size_t size1 = size(); memcpy(temp, start, sizeof(T*) * size()); start = temp; final_end = start + size1; finally = start + n; } }
當(dāng) vector 的大小和容量相等(size==capacity)也就是滿載時(shí),如果再向其添加元素,那么 vector 就需要擴(kuò)容。vector 容器擴(kuò)容的過程需要經(jīng)歷以下 3 步:
- 完全棄用現(xiàn)有的內(nèi)存空間,重新申請(qǐng)更大的內(nèi)存空間;
- 將舊內(nèi)存空間中的數(shù)據(jù),按原有順序移動(dòng)到新的內(nèi)存空間中;
- 最后將舊的內(nèi)存空間釋放。
這也就解釋了,為什么 vector 容器在進(jìn)行擴(kuò)容后,與其相關(guān)的指針、引用以及迭代器可能會(huì)失效的原因。
由此可見,vector 擴(kuò)容是非常耗時(shí)的。為了降低再次分配內(nèi)存空間時(shí)的成本,每次擴(kuò)容時(shí) vector 都會(huì)申請(qǐng)比用戶需求量更多的內(nèi)存空間(這也就是 vector 容量的由來,即 capacity>=size),以便后期使用。
vector 容器擴(kuò)容時(shí),不同的編譯器申請(qǐng)更多內(nèi)存空間的量是不同的。以 VS 為例,它會(huì)擴(kuò)容現(xiàn)有容器容量的 50%。
使用memcpy拷貝問題
reserve擴(kuò)容就是開辟新空間用memcpy將老空間的數(shù)據(jù)拷貝到新開空間中。
假設(shè)模擬實(shí)現(xiàn)的vector中的reserve接口中,使用memcpy進(jìn)行的拷貝,以下代碼會(huì)發(fā)生什么問題?
int main() { bite::vector<bite::string> v; v.push_back("1111"); v.push_back("2222"); v.push_back("3333"); return 0; }
問題分析:
- memcpy是內(nèi)存的二進(jìn)制格式拷貝,將一段內(nèi)存空間中內(nèi)容原封不動(dòng)的拷貝到另外一段內(nèi)存空間中
- 如果拷貝的是自定義類型的元素,memcpy即高效又不會(huì)出錯(cuò),但如果拷貝的是自定義類型元素,并且自定義類型元素中涉及到資源管理時(shí),就會(huì)出錯(cuò),因?yàn)閙emcpy的拷貝實(shí)際是淺拷貝。
結(jié)論:如果對(duì)象中涉及到資源管理時(shí),千萬不能使用memcpy進(jìn)行對(duì)象之間的拷貝,因?yàn)閙emcpy是淺拷貝,否則可能會(huì)引起內(nèi)存泄漏甚至程序崩潰。
3.尾插尾刪(push_back(),pop_back())
void push_back(const T&var) { if (final_end ==finally) { size_t newcode = capacity() == 0 ? 4 : capacity() * 2; reserve(newcode); } *final_end = var; ++final_end; void pop_back() { final_end--; }
插入問題一般先要判斷空間是否含有閑置空間,如果沒有,就要開辟空間。我們final_end==finally來判斷是否含有閑置空間。如果容器含沒有空間先開辟4字節(jié)空間,當(dāng)滿了后開2capacoity()空間。在final_end部插入數(shù)據(jù)就行了。對(duì)final_end加以操作。
4.對(duì)insert()插入時(shí)迭代器失效刨析
Iteratot insert(Iteratot iterator,const T&var) { assert(iterator <= final_end && iterator >= start); size_t pos = iterator - start; if (final_end == finally) { size_t newcode = capacity() == 0 ? 4 : capacity() * 2; reserve(newcode); } //插入操作 auto it = final_end; while (it >= start+pos) { *(it+1)=*it; it--; } *iterator = var; final_end++; return iterator; }
假設(shè)這是一段vector空間要在pos插入數(shù)據(jù),但是剛剛好final_end和final在同一位置,這個(gè)容器滿了,要對(duì)這這個(gè)容器做擴(kuò)容操作。首先對(duì)開辟和這個(gè)空間的2唄大小的空間
接著把老空間數(shù)據(jù)拷貝到新空間中釋放老空間。
由于老空間釋放了pos指向的內(nèi)存不見了。pos指針就成了野指針。
這如何解決呢就是在老空間解決之間保存這個(gè)指針,接著讓他重新指向新空間的原來位置。
而insert()函數(shù)返回了這個(gè)位置迭代器這為迭代器失效提供了方法,這個(gè)方法就是重新賦值。讓這個(gè)指針重新指向該指向的位置。
5.對(duì)erase()數(shù)據(jù)刪除時(shí)迭代器失效刨析
Iteratot erase(Iteratot iterator) { assert(iterator <= final_end && iterator >= start); auto it = iterator; while (it <final_end) { *it = *(it+1); it++; } final_end--; return iterator; }
vector使用erase刪除元素,其返回值指向下一個(gè)元素,但是由于vector本身的性質(zhì)(存在一塊連續(xù)的內(nèi)存上),刪掉一個(gè)元素后,其后的元素都會(huì)向前移動(dòng),所以此時(shí)指向下一個(gè)元素的迭代器其實(shí)跟剛剛被刪除元素的迭代器是一樣的。
以下為解決迭代器失效方案:
#include <vector> #include <iostream> using namespace std; int main() { int a[] = {1, 4, 3, 7, 9, 3, 6, 8, 3, 3, 5, 2, 3, 7}; vector<int> vector_int(a, a + sizeof(a)/sizeof(int)); /*方案一*/ // for(int i = 0; i < vector_int.size(); i++) // { // if(vector_int[i] == 3) // { // vector_int.erase(vector_int.begin() + i); // i--; // } // } /*方案二*/ // for(vector<int>::iterator itor = vector_int.begin(); itor != vector_int.end(); ++itor) // { // if (*itor == 3) // { // vector_int.erase(itor); // --itor; // } // } /*方案三*/ vector<int>::iterator v = vector_int.begin(); while(v != vector_int.end()) { if(*v == 3) { v = vector_int.erase(v); cout << *v << endl; } else{ v++; } } /*方案四*/ // vector<int>::iterator v = vector_int.begin(); // while(v != vector_int.end()) // { // if(*v == 3) // { // vector_int.erase(v); // } // else{ // v++; // } // } for(vector<int>::iterator itor = vector_int.begin(); itor != vector_int.end(); itor++) { cout << * itor << " "; } cout << endl; return 0; }
一共有四種方案。
方案一表明vector可以用下標(biāo)訪問元素,顯示出其隨機(jī)訪問的強(qiáng)大。并且由于vector的連續(xù)性,且for循環(huán)中有迭代器的自加,所以在刪除一個(gè)元素后,迭代器需要減1。
方案二與方案一在迭代器的處理上是類似的,不過對(duì)元素的訪問采用了迭代器的方法。
方案三與方案四基本一致,只是方案三利用了erase()函數(shù)的返回值是指向下一個(gè)元素的性質(zhì),又由于vector的性質(zhì)(連續(xù)的內(nèi)存塊),所以方案四在erase后并不需要對(duì)迭代器做加法。
以上就是C語言數(shù)據(jù)結(jié)構(gòu)之vector底層實(shí)現(xiàn)機(jī)制解析的詳細(xì)內(nèi)容,更多關(guān)于C語言 vector底層機(jī)制的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
- 使用C語言實(shí)現(xiàn)vector動(dòng)態(tài)數(shù)組的實(shí)例分享
- C語言數(shù)據(jù)結(jié)構(gòu)之單向鏈表詳解分析
- C語言數(shù)據(jù)結(jié)構(gòu)之復(fù)雜鏈表的拷貝
- C語言數(shù)據(jù)結(jié)構(gòu)進(jìn)階之棧和隊(duì)列的實(shí)現(xiàn)
- C語言數(shù)據(jù)結(jié)構(gòu)時(shí)間復(fù)雜度及空間復(fù)雜度簡(jiǎn)要分析
- C語言數(shù)據(jù)結(jié)構(gòu)單鏈表接口函數(shù)全面講解教程
- C語言數(shù)據(jù)結(jié)構(gòu)創(chuàng)建及遍歷十字鏈表
- C語言編程數(shù)據(jù)結(jié)構(gòu)線性表之順序表和鏈表原理分析
相關(guān)文章
C++編寫LINUX守護(hù)進(jìn)程的實(shí)現(xiàn)代碼
這篇文章主要介紹了如何使用C++實(shí)現(xiàn)LINUX守護(hù)進(jìn)程,文中代碼非常詳細(xì),供大家學(xué)習(xí)參考,感興趣的小伙伴可以了解下2020-06-06Cocos2d-x UI開發(fā)之CCControlSlider控件類使用實(shí)例
這篇文章主要介紹了Cocos2d-x UI開發(fā)之CCControlSlider控件類使用實(shí)例,本文代碼中包含大量注釋講解了CCControlSlider控件類的使用,需要的朋友可以參考下2014-09-09QT實(shí)現(xiàn)TCP網(wǎng)絡(luò)聊天室
這篇文章主要為大家詳細(xì)介紹了QT實(shí)現(xiàn)TCP網(wǎng)絡(luò)聊天室,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-08-08超詳細(xì)解析C++實(shí)現(xiàn)歸并排序算法
歸并排序是比較穩(wěn)定的排序方法。它的基本思想是把待排序的元素分解成兩個(gè)規(guī)模大致相等的子序列。本文將用C++實(shí)現(xiàn)這一排序算法,需要的可以參考一下2022-09-09