一般而言，我們習(xí)慣的 C++ 內(nèi)存配置操作和釋放操作是這樣的：

1 class FOO{}; 2 FOO *pf = new FOO; 3 delete pf;

　　我們看其中第二行和第三行，雖然都是只有一句，當(dāng)是都完成了兩個(gè)動(dòng)作。但你 new 一個(gè)對(duì)象的時(shí)候兩個(gè)動(dòng)作是：先調(diào)用::operator new 分配一個(gè)對(duì)象大小的內(nèi)存，然后在這個(gè)內(nèi)存上調(diào)用FOO::FOO()構(gòu)造對(duì)象。同樣，當(dāng)你 delete 一個(gè)對(duì)象的時(shí)候兩個(gè)動(dòng)作是：先調(diào)用FOO::~FOO()?析構(gòu)掉對(duì)象，再調(diào)用::operator delete將對(duì)象所處的內(nèi)存釋放。為了精密分工，STL 將allocator決定將這兩個(gè)階段分開。分別用 4 個(gè)函數(shù)來(lái)實(shí)現(xiàn)：

　　1.內(nèi)存的配置：alloc::allocate();

　　2.對(duì)象的構(gòu)造：::construct();

　　3.對(duì)象的析構(gòu)：::destroy();

　　4.內(nèi)存的釋放：alloc::deallocate();

　　其中的?construct() 和?destroy()定義在 STL的庫(kù)文件中，源代碼如下：

1 template <class T> 2 inline void destroy(T* pointer) { 3 pointer->~T(); //只是做了一層包裝，將指針?biāo)傅膶?duì)象析構(gòu)---通過直接調(diào)用類的析構(gòu)函數(shù) 4 } 5 6 template <class T1, class T2> 7 inline void construct(T1* p, const T2& value) { 8 new (p) T1(value); //用placement new在 p 所指的對(duì)象上創(chuàng)建一個(gè)對(duì)象，value是初始化對(duì)象的值。 9 } 10 11 template <class ForwardIterator> //destory的泛化版，接受兩個(gè)迭代器為參數(shù) 12 inline void destroy(ForwardIterator first, ForwardIterator last) { 13 __destroy(first, last, value_type(first)); //調(diào)用內(nèi)置的 __destory(),value_type()萃取迭代器所指元素的型別 14 } 15 16 template <class ForwardIterator, class T> 17 inline void __destroy(ForwardIterator first, ForwardIterator last, T*) { 18 typedef typename __type_traits<T>::has_trivial_destructor trivial_destructor; 19 __destroy_aux(first, last, trivial_destructor()); //trival_destructor()相當(dāng)于用來(lái)判斷迭代器所指型別是否有 trival destructor 20 } 21 22 23 template <class ForwardIterator> 24 inline void //如果無(wú) trival destructor ，那就要調(diào)用destroy()函數(shù)對(duì)兩個(gè)迭代器之間的對(duì)象元素進(jìn)行一個(gè)個(gè)析構(gòu) 25 __destroy_aux(ForwardIterator first, ForwardIterator last, __false_type) { 26 for ( ; first < last; ++first) 27 destroy(&*first); 28 } 29 30 template <class ForwardIterator> //如果有 trival destructor ，則什么也不用做。這更省時(shí)間 31 inline void __destroy_aux(ForwardIterator, ForwardIterator, __true_type) {} 32 33 inline void destroy(char*, char*) {} //針對(duì) char * 的特化版 34 inline void destroy(wchar_t*, wchar_t*) {} //針對(duì) wchar_t*的特化版

　　看到上面這么多代碼，大家肯定覺得 construct() 和 destroy() 函數(shù)很復(fù)雜。其實(shí)不然，我們看到construct()函數(shù)只有幾行代碼。而 destroy() 稍微多點(diǎn)。但是這么做都是為了提高銷毀對(duì)象時(shí)的效率。為什么要判斷迭代器所指型別是否有 trival destructor，然后分別調(diào)用不同的執(zhí)行函數(shù)？因?yàn)楫?dāng)你要銷毀的對(duì)象很多的時(shí)候，而這樣對(duì)象的型別的destructor 都是 trival 的。如果都是用__destroy_aux(ForwardIterator first, ForwardIterator last, __false_type)來(lái)進(jìn)行銷毀的話很費(fèi)時(shí)間，因?yàn)闆]必要那樣做。而當(dāng)你對(duì)象的destructor 都是 non-trival 的時(shí)候，你又必須要用__destroy_aux(ForwardIterator first, ForwardIterator last, __false_type)來(lái)析構(gòu)。所以，我們要判斷出對(duì)象型別的destructor 是否為 trival，然后調(diào)用不同的__destroy_aux。

　　說(shuō)完 construct() 和 destory() ，我們來(lái)說(shuō)說(shuō)?alloc::allocate() 和?alloc::deallocate()，其源代碼在 <stl_alloc.h>中。stl_alloc.h中代碼設(shè)計(jì)的原則如下：

　　1.向 system heap 要求空間

　　2.考慮多線程狀態(tài)

　　3.考慮內(nèi)存不足時(shí)的應(yīng)變措施

　　4.考慮過多“小型區(qū)塊”可能造成的內(nèi)存碎片問題。

　　stl_alloc.h中的代碼相當(dāng)復(fù)雜，不過沒關(guān)系。我們今天只看其中的allocate() 和 deallocate()。在講這兩個(gè)函數(shù)之前，我們還必須來(lái)了解一下SGI? STL(SGI限定詞是STL的一個(gè)版本，因?yàn)檎嬲腟TL有很多不同公司實(shí)現(xiàn)的版本，我們所討論的都是SGI版本) 配置器的工作原理：

　　考慮到小型區(qū)塊可能造成內(nèi)存破碎問題(即形成內(nèi)存碎片)，SGI STL 設(shè)計(jì)了雙層級(jí)配置器。第一層配置器直接使用malloc() 和 free().第二層配置器則視情況采用不同的策略：但配置區(qū)塊超過 128 bytes時(shí)，調(diào)用第一級(jí)配置器。當(dāng)配置區(qū)塊小于 128 bytes時(shí)，采用復(fù)雜的 memory pool 方式。下面我們分別簡(jiǎn)單的介紹一下第一級(jí)和第二級(jí)配置器：

第一級(jí)配置器 _ _malloc_alloc_template：

　　由于第一級(jí)配置器的配置方法比較簡(jiǎn)單，代碼也容易理解，我在這里全部貼出：

1 //以下是第第一級(jí)配置器 2 template <int inst> 3 class __malloc_alloc_template { 4 5 private: 6 7 //以下函數(shù)用來(lái)處理內(nèi)存不足的情況 8 static void *oom_malloc(size_t); 9 10 static void *oom_realloc(void *, size_t); 11 12 static void (* __malloc_alloc_oom_handler)(); 13 14 public: 15 16 static void * allocate(size_t n) 17 { 18 void *result = malloc(n); //第一級(jí)配置器，直接使用malloc() 19 //如果內(nèi)存不足，則調(diào)用內(nèi)存不足處理函數(shù)oom_alloc()來(lái)申請(qǐng)內(nèi)存 20 if (0 == result) result = oom_malloc(n); 21 return result; 22 } 23 24 static void deallocate(void *p, size_t /* n */) 25 { 26 free(p); //第一級(jí)配置器直接使用 free() 27 } 28 29 static void * reallocate(void *p, size_t /* old_sz */, size_t new_sz) 30 { 31 void * result = realloc(p, new_sz); //第一級(jí)配置器直接使用realloc() 32 //當(dāng)內(nèi)存不足時(shí)，則調(diào)用內(nèi)存不足處理函數(shù)oom_realloc()來(lái)申請(qǐng)內(nèi)存 33 if (0 == result) result = oom_realloc(p, new_sz); 34 return result; 35 } 36 37 //設(shè)置自定義的out-of-memory handle就像set_new_handle()函數(shù) 38 static void (* set_malloc_handler(void (*f)()))() 39 { 40 void (* old)() = __malloc_alloc_oom_handler; 41 __malloc_alloc_oom_handler = f; 42 return(old); 43 } 44 }; 45 46 template <int inst>　　　　 47 void (* __malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = 0;　　//內(nèi)存處理函數(shù)指針為空，等待客戶端賦值 48 49 template <int inst> 50 void * __malloc_alloc_template<inst>::oom_malloc(size_t n) 51 { 52 void (* my_malloc_handler)(); 53 void *result; 54 55 for (;;) { //死循環(huán) 56 my_malloc_handler = __malloc_alloc_oom_handler; //設(shè)定自己的oom(out of memory)處理函數(shù) 57 if (0 == my_malloc_handler) { __THROW_BAD_ALLOC; } //如果沒有設(shè)定自己的oom處理函數(shù)，毫不客氣的拋出異常 58 (*my_malloc_handler)(); //設(shè)定了就調(diào)用oom處理函數(shù) 59 result = malloc(n); //再次嘗試申請(qǐng) 60 if (result) return(result); 61 } 62 } 63 64 template <int inst> 65 void * __malloc_alloc_template<inst>::oom_realloc(void *p, size_t n) 66 { 67 void (* my_malloc_handler)(); 68 void *result; 69 70 for (;;) { 71 my_malloc_handler = __malloc_alloc_oom_handler; 72 if (0 == my_malloc_handler) { __THROW_BAD_ALLOC; } //如果自己沒有定義oom處理函數(shù)，則編譯器毫不客氣的拋出異常 73 (*my_malloc_handler)(); //執(zhí)行自定義的oom處理函數(shù) 74 result = realloc(p, n); //重新分配空間 75 if (result) return(result); //如果分配到了，返回指向內(nèi)存的指針 76 } 77 }

　　上面代碼看似繁雜，其實(shí)流程是這樣的：

　　1.我們通過allocate()申請(qǐng)內(nèi)存，通過deallocate()來(lái)釋放內(nèi)存，通過reallocate()重新分配內(nèi)存。

　　2.當(dāng)allocate()或reallocate()分配內(nèi)存不足時(shí)會(huì)調(diào)用oom_malloc()或oom_remalloc()來(lái)處理。

　　3.當(dāng)oom_malloc() 或 oom_remalloc()還是沒能分配到申請(qǐng)的內(nèi)存時(shí)，會(huì)轉(zhuǎn)如下兩步中的一步：

　　　　a).調(diào)用用戶自定義的內(nèi)存分配不足處理函數(shù)(這個(gè)函數(shù)通過set_malloc_handler() 來(lái)設(shè)定)，然后繼續(xù)申請(qǐng)內(nèi)存！

　　　　b).如果用戶未定義內(nèi)存分配不足處理函數(shù)，程序就會(huì)拋出bad_alloc異常或利用exit(1)終止程序。

　　看完這個(gè)流程，再看看上面的代碼就會(huì)容易理解多了！

第二級(jí)配置器 _ _default_alloc_template：

　　第二級(jí)配置器的代碼很多，這里我們只貼出其中的 allocate() 和 dellocate()函數(shù)的實(shí)現(xiàn)和工作流程(參考侯捷先生的《STL源碼剖析》)，而在看函數(shù)實(shí)現(xiàn)代碼之前，我大致的描述一下第二層配置器配置內(nèi)存的機(jī)制。

　　我們之前說(shuō)過，當(dāng)申請(qǐng)的內(nèi)存大于 128 bytes時(shí)就調(diào)用第一層配置器。當(dāng)申請(qǐng)的內(nèi)存小于 128bytes時(shí)才會(huì)調(diào)用第二層配置器。第二層配置器如何維護(hù)128bytes一下內(nèi)存的配置呢？ SGI 第二層配置器定義了一個(gè) free-lists,這個(gè)free-list是一個(gè)數(shù)組，如下圖：

　　

　　這數(shù)組的元素都是指針，用來(lái)指向16個(gè)鏈表的表頭。這16個(gè)鏈表上面掛的都是可以用的內(nèi)存塊。只是不同鏈表中元素的內(nèi)存塊大小不一樣，16個(gè)鏈表上分別掛著大小為

　　 8,16,24,32,40,48,56,64,72,80,88,96,104,112,120,128 bytes的小額區(qū)塊，圖如下：

　　?

　　就是這樣，現(xiàn)在我們來(lái)看allocate()代碼：

static void * allocate(size_t n){obj * __VOLATILE * my_free_list;obj * __RESTRICT result;//要申請(qǐng)的空間大于128bytes就調(diào)用第一級(jí)配置if (n > (size_t) __MAX_BYTES) {return(malloc_alloc::allocate(n));}//尋找 16 個(gè)free lists中恰當(dāng)?shù)囊粋€(gè)my_free_list = free_list + FREELIST_INDEX(n);result = *my_free_list;if (result == 0) {//沒找到可用的free list，準(zhǔn)備新填充free listvoid *r = refill(ROUND_UP(n));return r;}*my_free_list = result -> free_list_link;return (result);};

　　其中有兩個(gè)函數(shù)我來(lái)提一下，一個(gè)是ROUND_UP()，這個(gè)是將要申請(qǐng)的內(nèi)存字節(jié)數(shù)上調(diào)為8的倍數(shù)。因?yàn)槲覀僨ree-lists中掛的內(nèi)存塊大小都是8的倍數(shù)嘛，這樣才知道應(yīng)該去找哪一個(gè)鏈表。另一個(gè)就是refill()。這個(gè)是在沒找到可用的free list的時(shí)候調(diào)用，準(zhǔn)備填充free lists.意思是：參考上圖，假設(shè)我現(xiàn)在要申請(qǐng)大小為 56bytes 的內(nèi)存空間，那么就會(huì)到free lists 的第 7 個(gè)元素所指的鏈表上去找。如果此時(shí) #7元素所指的鏈表為空怎么辦？這個(gè)時(shí)候就要調(diào)用refill()函數(shù)向內(nèi)存池申請(qǐng)N(一般為20個(gè))個(gè)大小為56bytes的內(nèi)存區(qū)塊，然后掛到 #7 所指的鏈表上。這樣，申請(qǐng)者就可以得到內(nèi)存塊了。當(dāng)然，這里為了避免復(fù)雜，誤導(dǎo)讀者我就不討論refill()函數(shù)了。allocate()過程圖如下：

　　

　　學(xué)過鏈表的操作的人不難理解上圖，我就不再講解。下面看deallocate()，代碼如下：

1 static void deallocate(void *p, size_t n) 2 { 3 obj *q = (obj *)p; 4 obj * __VOLATILE * my_free_list; 5 6 //如果要釋放的字節(jié)數(shù)大于128，則調(diào)第一級(jí)配置器 7 if (n > (size_t) __MAX_BYTES) { 8 malloc_alloc::deallocate(p, n); 9 return; 10 } 11 //尋找對(duì)應(yīng)的位置 12 my_free_list = free_list + FREELIST_INDEX(n); 13 //以下兩步將待釋放的塊加到鏈表上 14 q -> free_list_link = *my_free_list; 15 *my_free_list = q; 16 }

　　deallocate()函數(shù)釋放內(nèi)存的步驟如下圖：

　　其實(shí)這就是一個(gè)鏈表的插入操作，也很簡(jiǎn)單。不再贅述！上面忘了給鏈表結(jié)點(diǎn)的結(jié)構(gòu)體定義了，如下：

union obj{union obj * free_list_link;char client_date[1]; };

　　至此，SGI STL的對(duì)象的構(gòu)造與析構(gòu)、內(nèi)存的分配與釋放就介紹完畢了。

?

轉(zhuǎn)載于:https://www.cnblogs.com/zhuwbox/p/3699977.html

總結(jié)

以上是生活随笔為你收集整理的浅析STL allocator的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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