目錄

創(chuàng)新互聯(lián)主要從事網(wǎng)站制作、網(wǎng)站設(shè)計(jì)、網(wǎng)頁設(shè)計(jì)、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)通化,十載網(wǎng)站建設(shè)經(jīng)驗(yàn),價(jià)格優(yōu)惠、服務(wù)專業(yè),歡迎來電咨詢建站服務(wù):13518219792

1.什么是空間配置器

2.為什么需要空間配置器

3.SGI-STL空間配置器實(shí)現(xiàn)原理

4.STL空間配置器的使用

---

1.什么是空間配置器

空間配置器，顧名思義就是 為各個(gè)容器高效的管理空間(空間的申請(qǐng)與回收)，在默默地工作。雖然在常規(guī)使用STL時(shí)，可能用不到它，但站在學(xué)習(xí)研究的角度，學(xué)習(xí)它的實(shí)現(xiàn)原理對(duì)我們有很大的幫助。

---

2.為什么需要空間配置器

前面在模擬實(shí)現(xiàn)vector、list、map、unordered_map等容器時(shí)，所有需要空間的地方都是通過new申請(qǐng)的，雖然代碼可以正常運(yùn)行，但是有以下不足之處： 空間申請(qǐng)與釋放需要用戶自己管理，容易造成內(nèi)存泄漏 頻繁向系統(tǒng)申請(qǐng)小塊內(nèi)存塊，容易造成內(nèi)存碎片 頻繁向系統(tǒng)申請(qǐng)小塊內(nèi)存，影響程序運(yùn)行效率 直接使用malloc與new進(jìn)行申請(qǐng)，每塊空間前有額外空間浪費(fèi)（因?yàn)槊繅K空間都要開額外的內(nèi)存空間記錄這塊空間的大小） 申請(qǐng)空間失敗怎么應(yīng)對(duì) 代碼結(jié)構(gòu)比較混亂，代碼復(fù)用率不高 未考慮線程安全問題

因此需要設(shè)計(jì)一塊高效的內(nèi)存管理機(jī)制。

---

3.SGI-STL空間配置器實(shí)現(xiàn)原理

在windows和Linux下都有直接向堆申請(qǐng)空間的接口，windows下接口為VirtualAlloc，Linux下接口為brk。malloc是封裝了irtualAlloc和brk在VirtualAlloc和brk之上，malloc本身其實(shí)也是一個(gè)內(nèi)存池，該內(nèi)存池是面向整個(gè)程序的?？臻g配置器對(duì)malloc進(jìn)行封裝 ，其是在malloc之上針對(duì)STL容器來設(shè)計(jì)的，空間配置器是一個(gè)內(nèi)存池，該內(nèi)存池僅面向STL的容器。

第二節(jié)中提到的幾點(diǎn)不足之處，最主要還是：頻繁向系統(tǒng)申請(qǐng)小塊內(nèi)存造成的。那什么才算是小塊內(nèi)存？SGI-STL以128字節(jié)作為小塊內(nèi)存與大塊內(nèi)存的分界線，將空間配置器其分為兩級(jí)結(jié)構(gòu)，一級(jí)空間配置器處理大塊內(nèi)存，二級(jí)空間配置器處理小塊內(nèi)存。

下面我們根據(jù)STL配置器的源碼來進(jìn)行介紹。?

一級(jí)空間配置器__malloc_alloc_template：

__malloc_alloc_template中allocate成員函數(shù)進(jìn)行malloc的封裝，deallocate成員函數(shù)進(jìn)行free的封裝，如下圖所示。所以說一級(jí)空間配置器其實(shí)就是malloc和free，唯一的區(qū)別就是一級(jí)空間配置器中如果malloc空間失敗會(huì)去調(diào)用oom_malloc函數(shù)。

oom_malloc函數(shù)的功能是先利用my_malloc_handler函數(shù)釋放內(nèi)存空間，如果函數(shù)指針my_malloc_handler為空則無法釋放內(nèi)存空間，拋異常，如果函數(shù)指針my_malloc_handler不為空則可以釋放空間，調(diào)用my_malloc_handler釋放空間然后再嘗試malloc，如果malloc成功返回空間的指針結(jié)果。如下圖所示。

總結(jié)：一級(jí)空間配置器和operator new很像，是malloc和free的封裝，其特點(diǎn)是申請(qǐng)內(nèi)存失敗了拋異常。

二級(jí)空間配置器__default_alloc_template：

__default_alloc_template類中allocate成員函數(shù)中如果大于__MAX_BYTES，__MAX_BYTES是一個(gè)枚舉常量為128，如果大于128則調(diào)用一級(jí)空間配置器來處理，如果小于128則在此處的二級(jí)空間配置器處理，如下圖所示。

注：這里可以看出STL容器申請(qǐng)空間其實(shí)會(huì)直接找二級(jí)空間配置器，如果申請(qǐng)空間大于128字節(jié)才會(huì)跳到一級(jí)空間配置器中。

二級(jí)空間配置器allocate成員函數(shù)，如下圖所示，free_list是一個(gè)哈希表。三個(gè)成員變量start_free、end_free和heap_size用來支持內(nèi)存池，內(nèi)存池是提前開辟好的128字節(jié)空間，其中start_free和end_free指針指向內(nèi)存的頭和尾。

每當(dāng)需要申請(qǐng)128字節(jié)以內(nèi)的空間時(shí)，讓一個(gè)指針指向start_free指向的位置，然后start_free向后移動(dòng)跳過此時(shí)申請(qǐng)空間的大小，將前面跳過的空間分配出去使用，最后如果這個(gè)內(nèi)存池空間用完了，再去malloc開辟128字節(jié)空間作為新內(nèi)存池即可。分配出去的某一小塊內(nèi)存不再使用回收后可以再次分配出去使用，如何管理分配出去小塊內(nèi)存的回收呢？

如果將回收的小塊內(nèi)存使用鏈表進(jìn)行鏈接，再次申請(qǐng)空間時(shí)，通過鏈表依次查找回收的小塊內(nèi)存空間大小是否滿足申請(qǐng)大小，滿足則該小塊內(nèi)存空間可以再分配出去使用。使用鏈表進(jìn)行管理依次查找的效率很低，可以使用哈希表來進(jìn)行優(yōu)化，對(duì)回收的小塊內(nèi)存進(jìn)行管理。

那是否需要128桶個(gè)空間來管理用戶已經(jīng)歸還的內(nèi)存塊呢？答案是不需要，因?yàn)橛脩羯暾?qǐng) 的空間基本都是4的整數(shù)倍，其他大小的空間幾乎很少用到。因此SGI-STL將用戶申請(qǐng)的內(nèi)存塊向上對(duì)齊到了8的整數(shù)倍，如上圖所示哈希表，哈希表0號(hào)桶掛的是8字節(jié)的內(nèi)存空間......15號(hào)桶掛的是128字節(jié)的內(nèi)存空間。

內(nèi)存池空間申請(qǐng)的流程：申請(qǐng)小于128字節(jié)空間時(shí)，首先算出申請(qǐng)空間大小對(duì)應(yīng)哈希表的幾號(hào)桶（如果申請(qǐng)1-8字節(jié)空間則都找哈希表的0號(hào)桶，如果申請(qǐng)9-16字節(jié)空間則都找哈希表的1號(hào)桶......如果申請(qǐng)121-128字節(jié)空間則都找哈希表的15號(hào)桶），如果對(duì)應(yīng)桶中有回收的小塊內(nèi)存空間則直接獲取，如果對(duì)應(yīng)桶中沒有回收的小塊內(nèi)存空間，則去start_free和end_free指針管理的內(nèi)存池獲取空間，在內(nèi)存池獲取空間也是在申請(qǐng)空間大小的基礎(chǔ)上向上對(duì)齊到8的整數(shù)倍獲取空間。

注：申請(qǐng)小空間內(nèi)存時(shí)往往會(huì)申請(qǐng)多個(gè)，因此這里編譯器會(huì)進(jìn)行一個(gè)優(yōu)化，如果申請(qǐng)小于128字節(jié)空間時(shí)，首先是算出申請(qǐng)空間大小對(duì)應(yīng)哈希表的幾號(hào)桶，如果對(duì)應(yīng)桶中沒有回收的小塊內(nèi)存空間會(huì)去內(nèi)存池獲取空間，如果要申請(qǐng)的空間大小為n，這里往往會(huì)向內(nèi)存池申請(qǐng)多個(gè)n空間大小，start_free跳過這多個(gè)n空間大小指向后面，第一個(gè)n空間地址返回，其余的n空間掛在哈希表中以備下次申請(qǐng)時(shí)使用。

__default_alloc_template類中deallocate成員函數(shù)和allocate成員函數(shù)相同，如果大于__MAX_BYTES，__MAX_BYTES是一個(gè)枚舉常量為128，如果大于128則調(diào)用一級(jí)空間配置器來處理，如果小于128則在此處的二級(jí)空間配置器處理，如下圖所示。

注：這里可以看出STL容器釋放空間其實(shí)會(huì)直接找二級(jí)空間配置器，如果申請(qǐng)空間大于128字節(jié)才會(huì)跳到一級(jí)空間配置器中。

二級(jí)空間配置器deallocate成員函數(shù)中，如果申請(qǐng)的內(nèi)存空間不再使用要釋放，則根據(jù)要釋放空間大小計(jì)算出哈希表對(duì)應(yīng)的桶號(hào)，將要釋放空間頭插在哈希表對(duì)應(yīng)的桶中。

問題：哈希表每個(gè)桶中掛的是一個(gè)單向鏈表，這里掛的是內(nèi)存空間，內(nèi)存空間如何像鏈表一樣掛起來呢？

答：每一個(gè)內(nèi)存空間如果要掛在哈希表中，首先要將指向該空間的指針強(qiáng)制轉(zhuǎn)換成下圖所示的聯(lián)合體obj*類型，該空間前四個(gè)字節(jié)就存的是聯(lián)合體指針free_list_link，free_list_link指向下一個(gè)被強(qiáng)轉(zhuǎn)成聯(lián)合體的空間地址，最后一個(gè)被強(qiáng)轉(zhuǎn)成聯(lián)合體的空間中前四個(gè)字節(jié)的free_list_link變量存的是空，這樣就可以像鏈表一樣鏈接起來。

當(dāng)申請(qǐng)空間，哈希表桶中空間被拿走使用時(shí)，該空間所有的字節(jié)都可以隨便使用，該空間釋放時(shí)，再將該空間指針強(qiáng)轉(zhuǎn)成聯(lián)合體obj*類型，頭插在哈希表對(duì)應(yīng)桶中，并與桶中原本掛著的空間進(jìn)行鏈接。

問題：SGI-STL將用戶申請(qǐng)的內(nèi)存塊向上對(duì)齊到了8字節(jié)的整數(shù)倍，這里為什么是8字節(jié)的整數(shù)倍，而不是4字節(jié)的整數(shù)倍？ 原因：哈希表的桶中要將空間的指針強(qiáng)制轉(zhuǎn)換成聯(lián)合體obj*類型，通過聯(lián)合體的前四個(gè)字節(jié)的free_list_link指針進(jìn)行空間鏈接。在32位機(jī)器下指針是4字節(jié)的，在64位機(jī)器下指針是8字節(jié)的，如果申請(qǐng)內(nèi)存塊向上對(duì)齊到了4字節(jié)的整數(shù)倍，而申請(qǐng)空間剛好為4字節(jié)的話這里就無法強(qiáng)轉(zhuǎn)，因?yàn)閒ree_list_link指針要占8字節(jié)空間，而申請(qǐng)空間本身才4字節(jié)。

一個(gè)進(jìn)程里面應(yīng)該只有一個(gè)空間配置器，因此空間配置器的類可以設(shè)置成單例模式的類，這樣哈希表變量、管理內(nèi)存池的各指針變量都對(duì)應(yīng)只有一個(gè)，每次容器要開辟和釋放空間時(shí)通過GetInstance函數(shù)調(diào)用allocate和deallocate成員函數(shù)即可。

如下圖所示，這里源代碼沒有使用前面我們所學(xué)的單例模式，源代碼是把所有的成員變量都設(shè)置為靜態(tài)的，這樣雖然可以創(chuàng)建多個(gè)對(duì)象，但一個(gè)進(jìn)程中空間配置器類的每個(gè)成員變量都只有對(duì)應(yīng)的一個(gè)，這也近似算是一種近似單例。

如果頻繁申請(qǐng)小塊內(nèi)存，空間配置器相比于malloc，效率更高，且可以在一定程度內(nèi)緩解內(nèi)存碎片的問題。

內(nèi)存碎片問題：

內(nèi)存內(nèi)碎片問題：申請(qǐng)下來的內(nèi)存空間沒有全部使用就是內(nèi)碎片問題?？臻g配置器中將內(nèi)存掛在哈希表中管理，申請(qǐng)空間時(shí)申請(qǐng)的內(nèi)存塊向上對(duì)齊到了8字節(jié)的整數(shù)倍，就會(huì)導(dǎo)致內(nèi)碎片問題。

內(nèi)存外碎片問題：在有足夠的內(nèi)存的條件下，頻繁小塊的內(nèi)存空間申請(qǐng)，小塊內(nèi)存如果間隔的釋放，那么可用內(nèi)存被分隔開，就導(dǎo)致了內(nèi)存的碎片化，因此無法開辟大塊內(nèi)存空間，這就是內(nèi)存外碎片問題。內(nèi)存外碎片問題其實(shí)就是頻繁向內(nèi)存申請(qǐng)小塊內(nèi)存空間導(dǎo)致的。

空間配置器緩解外碎片問題：空間配置器一次性開辟大塊內(nèi)存空間，將大塊內(nèi)存空間切割成小塊內(nèi)存空間掛在哈希表中，以滿足自己的需求，這里小塊內(nèi)存空間是連續(xù)的，因此在一定程度內(nèi)緩解內(nèi)存外碎片的問題。

---

4.STL空間配置器的使用

以list為例如下圖所示，list類模板的第二個(gè)參數(shù)就是空間配置器Alloc，缺省參數(shù)給的是alloc，那么alloc是什么呢？

如下圖所示，alloc是STL庫中二級(jí)的空間配置器，作為STL容器的默認(rèn)空間配置器。如果容器申請(qǐng)空間大小大于128字節(jié)就會(huì)跳到STL庫中的一級(jí)空間配置器，如果容器申請(qǐng)空間大小小于128字節(jié)就會(huì)繼續(xù)執(zhí)行二級(jí)空間配置器。

如下圖一所示，在list類中使用simple_alloc類對(duì)二級(jí)空間配置器alloc進(jìn)行封裝，生成一個(gè)專門針對(duì)list_node的空間申請(qǐng)類list_node_allocator。如下圖二所示是simple_alloc類中對(duì)alloc的封裝，分別調(diào)用了二級(jí)空間配置器alloc的allocate函數(shù)和deallocate函數(shù)進(jìn)行二級(jí)空間適配器的空間申請(qǐng)和釋放。

如下圖三所示，在list類中g(shù)et_node和put_node調(diào)用封裝的空間申請(qǐng)類list_node_allocator中allocate函數(shù)和deallocate函數(shù)進(jìn)行節(jié)點(diǎn)空間的申請(qǐng)和釋放。

如下圖三所示，在create_node函數(shù)中，先調(diào)用get_node函數(shù)申請(qǐng)節(jié)點(diǎn)空間，因?yàn)間et_node只申請(qǐng)了節(jié)點(diǎn)空間沒有初始化，所以調(diào)用construct函數(shù)針對(duì)新申請(qǐng)的節(jié)點(diǎn)的data進(jìn)行初始化，construct函數(shù)中使用了定位new來調(diào)用data對(duì)應(yīng)類型的構(gòu)造函數(shù)進(jìn)行初始化工作（因?yàn)閐ata可能是自定義類型的變量），如下圖四所示。

如下圖三所示，destroy_node函數(shù)中顯式的調(diào)用data對(duì)應(yīng)類型的析構(gòu)函數(shù)，并調(diào)用put_node函數(shù)將節(jié)點(diǎn)釋放掉。

注：STL各容器模板的Alloc參數(shù)可以傳自己實(shí)現(xiàn)的空間適配器類，只要空間適配器類中定義實(shí)現(xiàn)了allocate函數(shù)和deallocate函數(shù)即可。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

文章題目：c++-第25節(jié)-STL之空間配置器-創(chuàng)新互聯(lián)
瀏覽路徑：http://aaarwkj.com/article24/cocdje.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供商城網(wǎng)站、全網(wǎng)營銷推廣、網(wǎng)站維護(hù)、定制網(wǎng)站、品牌網(wǎng)站制作、Google

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)