c++-第25節(jié)-STL之空間配置器-創(chuàng)新互聯(lián)

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

1.什么是空間配置器

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

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

4.STL空間配置器的使用

1.什么是空間配置器

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

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

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

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

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

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

一級空間配置器__malloc_alloc_template：
__malloc_alloc_template中allocate成員函數(shù)進行malloc的封裝，deallocate成員函數(shù)進行free的封裝，如下圖所示。所以說一級空間配置器其實就是malloc和free，唯一的區(qū)別就是一級空間配置器中如果malloc空間失敗會去調(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é)：一級空間配置器和operator new很像，是malloc和free的封裝，其特點是申請內(nèi)存失敗了拋異常。

二級空間配置器__default_alloc_template：
__default_alloc_template類中allocate成員函數(shù)中如果大于__MAX_BYTES，__MAX_BYTES是一個枚舉常量為128，如果大于128則調(diào)用一級空間配置器來處理，如果小于128則在此處的二級空間配置器處理，如下圖所示。
注：這里可以看出STL容器申請空間其實會直接找二級空間配置器，如果申請空間大于128字節(jié)才會跳到一級空間配置器中。
二級空間配置器allocate成員函數(shù)，如下圖所示，free_list是一個哈希表。三個成員變量start_free、end_free和heap_size用來支持內(nèi)存池，內(nèi)存池是提前開辟好的128字節(jié)空間，其中start_free和end_free指針指向內(nèi)存的頭和尾。
每當(dāng)需要申請128字節(jié)以內(nèi)的空間時，讓一個指針指向start_free指向的位置，然后start_free向后移動跳過此時申請空間的大小，將前面跳過的空間分配出去使用，最后如果這個內(nèi)存池空間用完了，再去malloc開辟128字節(jié)空間作為新內(nèi)存池即可。分配出去的某一小塊內(nèi)存不再使用回收后可以再次分配出去使用，如何管理分配出去小塊內(nèi)存的回收呢？
如果將回收的小塊內(nèi)存使用鏈表進行鏈接，再次申請空間時，通過鏈表依次查找回收的小塊內(nèi)存空間大小是否滿足申請大小，滿足則該小塊內(nèi)存空間可以再分配出去使用。使用鏈表進行管理依次查找的效率很低，可以使用哈希表來進行優(yōu)化，對回收的小塊內(nèi)存進行管理。
那是否需要128桶個空間來管理用戶已經(jīng)歸還的內(nèi)存塊呢？答案是不需要，因為用戶申請的空間基本都是4的整數(shù)倍，其他大小的空間幾乎很少用到。因此SGI-STL將用戶申請的內(nèi)存塊向上對齊到了8的整數(shù)倍，如上圖所示哈希表，哈希表0號桶掛的是8字節(jié)的內(nèi)存空間......15號桶掛的是128字節(jié)的內(nèi)存空間。
內(nèi)存池空間申請的流程：申請小于128字節(jié)空間時，首先算出申請空間大小對應(yīng)哈希表的幾號桶（如果申請1-8字節(jié)空間則都找哈希表的0號桶，如果申請9-16字節(jié)空間則都找哈希表的1號桶......如果申請121-128字節(jié)空間則都找哈希表的15號桶），如果對應(yīng)桶中有回收的小塊內(nèi)存空間則直接獲取，如果對應(yīng)桶中沒有回收的小塊內(nèi)存空間，則去start_free和end_free指針管理的內(nèi)存池獲取空間，在內(nèi)存池獲取空間也是在申請空間大小的基礎(chǔ)上向上對齊到8的整數(shù)倍獲取空間。
注：申請小空間內(nèi)存時往往會申請多個，因此這里編譯器會進行一個優(yōu)化，如果申請小于128字節(jié)空間時，首先是算出申請空間大小對應(yīng)哈希表的幾號桶，如果對應(yīng)桶中沒有回收的小塊內(nèi)存空間會去內(nèi)存池獲取空間，如果要申請的空間大小為n，這里往往會向內(nèi)存池申請多個n空間大小，start_free跳過這多個n空間大小指向后面，第一個n空間地址返回，其余的n空間掛在哈希表中以備下次申請時使用。
__default_alloc_template類中deallocate成員函數(shù)和allocate成員函數(shù)相同，如果大于__MAX_BYTES，__MAX_BYTES是一個枚舉常量為128，如果大于128則調(diào)用一級空間配置器來處理，如果小于128則在此處的二級空間配置器處理，如下圖所示。
注：這里可以看出STL容器釋放空間其實會直接找二級空間配置器，如果申請空間大于128字節(jié)才會跳到一級空間配置器中。
二級空間配置器deallocate成員函數(shù)中，如果申請的內(nèi)存空間不再使用要釋放，則根據(jù)要釋放空間大小計算出哈希表對應(yīng)的桶號，將要釋放空間頭插在哈希表對應(yīng)的桶中。

問題：哈希表每個桶中掛的是一個單向鏈表，這里掛的是內(nèi)存空間，內(nèi)存空間如何像鏈表一樣掛起來呢？
答：每一個內(nèi)存空間如果要掛在哈希表中，首先要將指向該空間的指針強制轉(zhuǎn)換成下圖所示的聯(lián)合體obj*類型，該空間前四個字節(jié)就存的是聯(lián)合體指針free_list_link，free_list_link指向下一個被強轉(zhuǎn)成聯(lián)合體的空間地址，最后一個被強轉(zhuǎn)成聯(lián)合體的空間中前四個字節(jié)的free_list_link變量存的是空，這樣就可以像鏈表一樣鏈接起來。
當(dāng)申請空間，哈希表桶中空間被拿走使用時，該空間所有的字節(jié)都可以隨便使用，該空間釋放時，再將該空間指針強轉(zhuǎn)成聯(lián)合體obj*類型，頭插在哈希表對應(yīng)桶中，并與桶中原本掛著的空間進行鏈接。

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

一個進程里面應(yīng)該只有一個空間配置器，因此空間配置器的類可以設(shè)置成單例模式的類，這樣哈希表變量、管理內(nèi)存池的各指針變量都對應(yīng)只有一個，每次容器要開辟和釋放空間時通過GetInstance函數(shù)調(diào)用allocate和deallocate成員函數(shù)即可。
如下圖所示，這里源代碼沒有使用前面我們所學(xué)的單例模式，源代碼是把所有的成員變量都設(shè)置為靜態(tài)的，這樣雖然可以創(chuàng)建多個對象，但一個進程中空間配置器類的每個成員變量都只有對應(yīng)的一個，這也近似算是一種近似單例。

如果頻繁申請小塊內(nèi)存，空間配置器相比于malloc，效率更高，且可以在一定程度內(nèi)緩解內(nèi)存碎片的問題。
內(nèi)存碎片問題：
內(nèi)存內(nèi)碎片問題：申請下來的內(nèi)存空間沒有全部使用就是內(nèi)碎片問題?？臻g配置器中將內(nèi)存掛在哈希表中管理，申請空間時申請的內(nèi)存塊向上對齊到了8字節(jié)的整數(shù)倍，就會導(dǎo)致內(nèi)碎片問題。
內(nèi)存外碎片問題：在有足夠的內(nèi)存的條件下，頻繁小塊的內(nèi)存空間申請，小塊內(nèi)存如果間隔的釋放，那么可用內(nèi)存被分隔開，就導(dǎo)致了內(nèi)存的碎片化，因此無法開辟大塊內(nèi)存空間，這就是內(nèi)存外碎片問題。內(nèi)存外碎片問題其實就是頻繁向內(nèi)存申請小塊內(nèi)存空間導(dǎo)致的。
空間配置器緩解外碎片問題：空間配置器一次性開辟大塊內(nèi)存空間，將大塊內(nèi)存空間切割成小塊內(nèi)存空間掛在哈希表中，以滿足自己的需求，這里小塊內(nèi)存空間是連續(xù)的，因此在一定程度內(nèi)緩解內(nèi)存外碎片的問題。

4.STL空間配置器的使用

以list為例如下圖所示，list類模板的第二個參數(shù)就是空間配置器Alloc，缺省參數(shù)給的是alloc，那么alloc是什么呢？
如下圖所示，alloc是STL庫中二級的空間配置器，作為STL容器的默認空間配置器。如果容器申請空間大小大于128字節(jié)就會跳到STL庫中的一級空間配置器，如果容器申請空間大小小于128字節(jié)就會繼續(xù)執(zhí)行二級空間配置器。
如下圖一所示，在list類中使用simple_alloc類對二級空間配置器alloc進行封裝，生成一個專門針對list_node的空間申請類list_node_allocator。如下圖二所示是simple_alloc類中對alloc的封裝，分別調(diào)用了二級空間配置器alloc的allocate函數(shù)和deallocate函數(shù)進行二級空間適配器的空間申請和釋放。
如下圖三所示，在list類中g(shù)et_node和put_node調(diào)用封裝的空間申請類list_node_allocator中allocate函數(shù)和deallocate函數(shù)進行節(jié)點空間的申請和釋放。
如下圖三所示，在create_node函數(shù)中，先調(diào)用get_node函數(shù)申請節(jié)點空間，因為get_node只申請了節(jié)點空間沒有初始化，所以調(diào)用construct函數(shù)針對新申請的節(jié)點的data進行初始化，construct函數(shù)中使用了定位new來調(diào)用data對應(yīng)類型的構(gòu)造函數(shù)進行初始化工作（因為data可能是自定義類型的變量），如下圖四所示。
如下圖三所示，destroy_node函數(shù)中顯式的調(diào)用data對應(yīng)類型的析構(gòu)函數(shù)，并調(diào)用put_node函數(shù)將節(jié)點釋放掉。
注：STL各容器模板的Alloc參數(shù)可以傳自己實現(xiàn)的空間適配器類，只要空間適配器類中定義實現(xiàn)了allocate函數(shù)和deallocate函數(shù)即可。

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

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

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

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

猜你還喜歡下面的內(nèi)容