配置器allocator

對(duì)于stl使用者基本接觸不到allocator，需要分析源碼才可以接觸到allocator，也叫分配子，幾乎所有的stl都使用分配子，用來非常高效的分配和釋放內(nèi)存。一般stl都默認(rèn)使用alloc配置器。

template<class T, class Alloc=alloc>
class vector {};

首先需要理解operator new和new operator區(qū)別，簡單來說new operator是關(guān)鍵字，而operator new是操作符，new operator = operator new分配內(nèi)存+X::X()構(gòu)造對(duì)象，operator delete 和delete operator類似。
operator new 相當(dāng)于malloc， operator delete相當(dāng)于 free

alloc包含兩級(jí)配置器，第一級(jí)配置器和第二級(jí)配置器，第一級(jí)配置器其實(shí)就是malloc和free，第二級(jí)配置器則是針對(duì)于小內(nèi)存，使用內(nèi)存鏈表以及內(nèi)存池來優(yōu)化內(nèi)存碎片問題。
當(dāng)申請(qǐng)內(nèi)存或釋放內(nèi)存>128bytes時(shí)，使用第一級(jí)配置器，當(dāng)小于128byte時(shí)使用第二級(jí)配置器，這里詳細(xì)說第二級(jí)配置器。
第二級(jí)配置器配置16個(gè)內(nèi)存區(qū)塊的鏈表，第一個(gè)鏈表所指向的都是8byte的內(nèi)存塊，第二個(gè)第三個(gè)鏈表依次是16，24，32等8的倍數(shù)大小的內(nèi)存塊。當(dāng)申請(qǐng)的內(nèi)存<128時(shí)，則向?qū)?yīng)的這些鏈表中獲取，如果是需要9，則去找16大小的鏈表，如果是需要20，則去找24大小的鏈表，
假設(shè)申請(qǐng)內(nèi)存大小為n，若對(duì)應(yīng)鏈表有空閑的內(nèi)存塊，則分配成功，
若沒有空閑塊，則去向內(nèi)存池請(qǐng)求n×20大小的內(nèi)存區(qū)，若內(nèi)存池有足夠空間，則分配成功，其中一個(gè)內(nèi)存塊返回給上層，另外19塊供內(nèi)存鏈表使用，若沒有足夠內(nèi)存但是卻可以分配多余1個(gè)n的內(nèi)存，則找到最大的n分配，其中一塊返回，另外的供鏈表使用，如果連1塊大小的內(nèi)存都沒有，則malloc出n*40大小的內(nèi)存，其中20個(gè)內(nèi)存池留用，一個(gè)返回上層，另外19個(gè)給內(nèi)存鏈表，如果malloc都失敗，則遍歷鏈表，找到第一個(gè)空閑的內(nèi)存釋放掉，再遞歸上述步驟申請(qǐng)內(nèi)存。