一、空間分配器 allocator

從使用上看，空間分配在任何語言的任何組件都不需要我們?nèi)ミ^多關(guān)心，因?yàn)檎Z言、組件的底層肯定都比較完整的做了這件事情。

從實(shí)現(xiàn)上看，學(xué)習(xí) allocator 的原理在源碼學(xué)習(xí)中是首當(dāng)其沖。因?yàn)闆]有空間分配，則無從談起對象創(chuàng)建。這里說是空間分配，而不是內(nèi)存分配，是因?yàn)橐部梢栽趦?nèi)存之外的地方（如硬盤）分配空間。

分配器主要作用就是分配空間，根據(jù)規(guī)范，其需要實(shí)現(xiàn)一些接口，完成一些關(guān)于空間分配的功能。標(biāo)準(zhǔn)接口規(guī)范見附錄（一）。

本文會提到以下幾個(gè)方面：

• SGI STL 分配器介紹
• construct 和 destroy
  • destroy 接收指針和迭代器的方法
• alloc 分配器
  • 一層分配器
  • 二層分配器 和 free-list
    • 分配
    • 釋放
    • 補(bǔ)充
• 全局函數(shù)
  • uninitialized_copy
  • uninitialized_fill
  • uninitialized_fill_n

二、SGI STL 的 alloc

SGI STL 的分配器與眾不同，也與標(biāo)準(zhǔn)規(guī)范不同，其名稱是 alloc 而非 allocator，而且不接受任何參數(shù)。具體來說，想在程序中明確使用 SGI 分配器，不能寫std::allocator<int>，而要寫成std::alloc。

即使它不符合標(biāo)準(zhǔn)規(guī)范，也不會對我們使用造成任何影響，因?yàn)橥ǔＮ覀兌际褂萌笔〉姆峙淦?#xff0c;而不會自己指定。而 STL 的每一個(gè)容器都指定缺省分配器為 alloc。

當(dāng)然了，SGI 也定義了符合部分標(biāo)準(zhǔn)、名為 allocator 的分配器，但出于其效率原因，STL 從未使用它，也不推薦程序員使用。它只是把 ::operator new 和 ::operator delete 做了一層薄薄的封裝，沒有做優(yōu)化。詳細(xì)代碼見附錄（二）。

下面詳細(xì)聊聊 SGI STL 實(shí)現(xiàn)的 alloc 。

一般而言，C++的內(nèi)存分配和釋放操作如下：

class Foo {...}; Foo * pf = new Foo; // 分配內(nèi)存，構(gòu)造對象 delete pf; // 析構(gòu)對象，釋放內(nèi)存

• new 內(nèi)含兩步操作：（1）調(diào)用 ::operator new 分配內(nèi)存（2）調(diào)用 Foo::Foo() 構(gòu)造對象內(nèi)容。
• delete 內(nèi)含兩步操作：（1）調(diào)用 Foo::~Foo() 析構(gòu)對象（2）調(diào)用 ::operator delete 釋放內(nèi)存。

為了精細(xì)分工，分配器將這兩個(gè)步驟分開做。內(nèi)存分配由 alloc::allocate() 負(fù)責(zé)，內(nèi)存釋放由 alloc::deallocate() 負(fù)責(zé)；對象構(gòu)造由 ::construct() 負(fù)責(zé)，對象析構(gòu)由 ::destroy() 負(fù)責(zé)。

// STL規(guī)定分配器 allocator 定義于 memory 中 #include <memory>// memory 中含有兩個(gè)文件 #include <stl_alloc.h> // 負(fù)責(zé)內(nèi)存空間的分配和釋放，定義了 一級、二級分配器。 #include <stl_construct.h> // 負(fù)責(zé)對象內(nèi)容的構(gòu)造和析構(gòu)，有 construct 和 destroy 方法。// memory 中還有一個(gè)文件 #include <stl_uninitialized.h> // 定義了一些全局函數(shù)，用來填充fill 或者 復(fù)制copy 大塊內(nèi)存的數(shù)據(jù) // 其中有如下方法 // un_initialized_copy() // un_initialized_fill() // un_initialized_fill_n() // 這些方法不屬于分配器的范疇，但與對象初值設(shè)置有關(guān)，對大規(guī)模元素初值設(shè)置很有幫助。 // 在效率上，最差會調(diào)用 construct，最佳會調(diào)用C的 memmove 進(jìn)行內(nèi)存移動。

（一）construct 和 destroy

對于對象的 construct 和 destroy 可以概括如下圖所示。其源碼見附錄（三）

• construct 接收 指針p 和 初值value，會將value設(shè)置到p所指的空間上。
• destroy 可以接收 指針、迭代器。
  • 基本類型指針：不做處理
  • 對象類型指針：調(diào)用析構(gòu)函數(shù)
  • 迭代器：會判斷析構(gòu)函數(shù)是否為 trivial destructor（無用的、沒必要的、無意義的析構(gòu)函數(shù)）
    • 是：則不做處理
    • 否：調(diào)用 迭代器中每個(gè)元素的析構(gòu)函數(shù)。

這里有個(gè)問題是，如何判斷是否為 trivial呢？

答案是：使用 __type_traits<T>::has_trivial_destructor() ，該函數(shù)會返回 __true_type 或 __false_type，前者代表是trivial，后者代表是有意義的。

該類的具體實(shí)現(xiàn)需要去研究下 traits，這里先不展開。

（二）STL alloc

<stl_alloc.h> 負(fù)責(zé)了對象構(gòu)造前的空間分配和對象析構(gòu)前的空間釋放，有下面幾個(gè)設(shè)計(jì)原則：

• 向 system heap 申請空間
• 考慮多線程狀態(tài)（為了將問題簡化，這里不討論多線程狀態(tài)）
• 考慮內(nèi)存不足的應(yīng)變措施
• 考慮過多小塊內(nèi)存造成的碎片問題

C++ 的內(nèi)存分配和釋放主要使用 ::operator new() 和 ::operator delete()，這兩個(gè)相當(dāng)于C的 malloc() 和 free()，SGI 正是以 malloc 和 free 完成的內(nèi)存分配和釋放。

SGI 設(shè)計(jì)了雙層分配器，如下圖所示：

• 第一級直接使用 malloc 和 free
• 第二級，當(dāng)需求大于128 bytes 時(shí)，調(diào)用一級分配器；小于等于128 bytes 則調(diào)用二級分配器。

具體采用哪種分配器，需要看 __USE_MALLOC 是否被定義。定義了則用一級分配器，否則調(diào)用二級分配器。

SGI 為 alloc 提供了一個(gè) simple_alloc 的接口封裝，使得外層使用時(shí)無需考慮內(nèi)部具體用的一級還是二級。SGI STL 的容器都使用這個(gè) simple_alloc 接口，而非直接使用 alloc。代碼見附錄（四）。

一級分配器的原理比較簡單，正常情況就是調(diào)用 malloc 和 free 做分配和釋放。當(dāng)內(nèi)存不夠時(shí)需要使用 oom_malloc，在該函數(shù)中，會循環(huán)調(diào)用一個(gè) handler 來處理內(nèi)存不足的情況。這個(gè) handler 是需要自己指定的，如果沒有指定，則拋出 std::bad_alloc 異常。這個(gè) handler 一般稱為 new-handler，在 《Effective C++》2e item7 中有特定的解決模式。

（三）STL 二級分配器

下面著重說說二級分配器。

二級分配器可以避免產(chǎn)生過多的小區(qū)塊，可以解決內(nèi)存碎片和過多的額外開銷（系統(tǒng)需要多出來的空間管理內(nèi)存，可以說是給系統(tǒng)“交稅”）。

二級分配器以內(nèi)存池（memory pool）管理小于128 bytes 的內(nèi)存，稱為次層分配（sub-allocation）：先分配一大塊內(nèi)存，組成一個(gè)自由鏈表（free-list），每次要取一定量內(nèi)存時(shí)，從 free-list 中取；在用完后，分配器就歸還給 free-list。

分配器會維護(hù) 空間為 8、16、24、……、128 這16個(gè) free-list，在分配小內(nèi)存時(shí)，會向上取整（Round Up），尋找最近的 free-list。

free-list 節(jié)點(diǎn)結(jié)構(gòu)是一個(gè)聯(lián)合體，該節(jié)點(diǎn)在free-list中時(shí)，內(nèi)容是一個(gè)指向 下一個(gè)節(jié)點(diǎn)的指針，在客戶端使用時(shí)，是具體的數(shù)據(jù)。這樣一物二用，不會造成維護(hù)鏈表指針的內(nèi)存浪費(fèi)。這個(gè)技巧在強(qiáng)類型語言（Strong Typed）中如 Java 行不通，但在弱類型語言（Weak Typed）中如 C++十分常見。

union obj{union obj * free_list_link; char client_data[1]; // client use }

free-list 的實(shí)現(xiàn)技巧

次層分配中從 free list 分出內(nèi)存的步驟 allocate 如下圖所示：

次層分配中釋放內(nèi)存，往 free list 中歸還的步驟 deallocate 如下圖所示：

當(dāng) free-list 的空間用盡后，會觸發(fā) refill 操作，重新給 free-list 補(bǔ)充 20個(gè)節(jié)點(diǎn)。refill 會調(diào)用 chunk_alloc，該函數(shù)中會做具體從內(nèi)存池中取內(nèi)存的操作。其過程如下所示。

簡而言之就是，先找自己（32找32），再找親友（64找32），實(shí)在不行就求助大家（96找32）。

三、內(nèi)存基本處理工具

STL 定義了五個(gè)全局函數(shù)，除了前文提到的 construct 和 destroy，還有3個(gè)用來處理大塊內(nèi)存的復(fù)制和移動的 unitialized_copy、uninitialized_fill、uninitialized_fill_n 分別對應(yīng)高層次的函數(shù) copy、fill、fill_n。

unitialized_copy 函數(shù)讓內(nèi)存配置與對象構(gòu)造行為分開。如果目標(biāo)地址指向的空間都是未初始化區(qū)域，則會直接把源區(qū)域的對象產(chǎn)生復(fù)制品直接放到目標(biāo)地址。STL 規(guī)范中要求該函數(shù)具有原子性，要么全部構(gòu)造出來，要么全部不構(gòu)造。

uninitialized_fill、uninitialized_fill_n 也和 unitialized_copy 類似。

這三個(gè)函數(shù)都會判斷 對象是否為 POD（Plain Old Data，標(biāo)量 or 傳統(tǒng) C 結(jié)構(gòu)體），POD 會具有 trivial 函數(shù)，如果是 POD 則用最有效率的方法，如果非 POD 則用最安全的方法。過程大致如下所示。

附錄

（一）標(biāo)準(zhǔn)接口規(guī)范

根據(jù) STL 規(guī)范，allocator 必須要實(shí)現(xiàn)以下接口。

（二）SGI allocator 源碼

下面是 SGI 實(shí)現(xiàn)的 allocator 全貌

（三）construct 和 destroy 源碼

（四）simple_alloc 和 vector

總結(jié)

以上是生活随笔為你收集整理的stl源码剖析_STL源码剖析 阅读笔记（二）allocator的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。