C++STL中的空間配置器只有一種，是同過底層的malloc和free實(shí)現(xiàn)的，空間配置器中有四種方法：
創(chuàng)新互聯(lián)建站長期為1000+客戶提供的網(wǎng)站建設(shè)服務(wù)，團(tuán)隊(duì)從業(yè)經(jīng)驗(yàn)10年，關(guān)注不同地域、不同群體，并針對不同對象提供差異化的產(chǎn)品和服務(wù)；打造開放共贏平臺，與合作伙伴共同營造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為長順企業(yè)提供專業(yè)的成都網(wǎng)站建設(shè)、網(wǎng)站制作，長順網(wǎng)站改版等技術(shù)服務(wù)。擁有十載豐富建站經(jīng)驗(yàn)和眾多成功案例,為您定制開發(fā)。
SGI STL中有兩種空間配置器，一級allocator是與stl一致的malloc和free的方式，二級allocator是通過內(nèi)存池的方式實(shí)現(xiàn)的。
SGI STL中的vector容器的模板中用到了空間配置器，默認(rèn)用的是二級allocator。該容器底層存儲對象的構(gòu)造和析構(gòu)是通過全局的函數(shù)模板construct和destroy實(shí)現(xiàn)的。這里我們著重研究allocator中的allocate和deallocate方法。
allocate：
重慶分公司
重慶分公司
// breaks if we make these template class members:
enum {_ALIGN = 8};
enum {_MAX_BYTES = 128};
enum {_NFREELISTS = 16}; // _MAX_BYTES/_ALIGN
/* __n must be > 0 */
//分配大小為__n的內(nèi)存
static void* allocate(size_t __n)
{
void* __ret = 0;
if (__n > (size_t) _MAX_BYTES) {//如果需要的內(nèi)存塊大小超過最大內(nèi)存，則按照標(biāo)準(zhǔn)庫的方式分配內(nèi)存
__ret = malloc_alloc::allocate(__n);//調(diào)用一級allocator
}
else {
_Obj* __STL_VOLATILE* __my_free_list//是一個double*的類型，指向數(shù)組的位置，解引用之后是數(shù)組中元素的值
= _S_free_list + _S_freelist_index(__n);//根據(jù)_S_freelist_index(__n)定位數(shù)組中chunk塊的位置
//_S_free_list就是上圖中的數(shù)組
// Acquire the lock here with a constructor call.
// This ensures that it is released in exit or during stack
// unwinding.
# ifndef _NOTHREADS
/*REFERENCED*/
_Lock __lock_instance;//上鎖
# endif
_Obj* __RESTRICT __result = *__my_free_list;//result是數(shù)組中的__Obj*
if (__result == 0)//如果數(shù)組中的元素未初始化
__ret = _S_refill(_S_round_up(__n));//構(gòu)建鏈表，返回鏈表的地址
else {//已經(jīng)初始化
*__my_free_list = __result -> _M_free_list_link;//指向下一個節(jié)點(diǎn)
__ret = __result;//返回下一個節(jié)點(diǎn)的地址
}
}
return __ret;
};
指針的加法操作注意事項(xiàng)：
? 指針類型占用的內(nèi)存多大，其指針加一就會偏移多少字節(jié)。舉個例子：char類型只占1個字節(jié)，那么char* +1就只偏移一個字節(jié)，指向下一個內(nèi)存地址；int類型占4個字節(jié)，int* +1就會偏移4個字節(jié)，指向4個字節(jié)后的內(nèi)存地址。
_S_refill函數(shù)：
/* Returns an object of size __n, and optionally adds to size __n free list.*/
/* We assume that __n is properly aligned. */
/* We hold the allocation lock. */
template
void*
__default_alloc_template<__threads, __inst>::_S_refill(size_t __n)
{
int __nobjs = 20;
char* __chunk = _S_chunk_alloc(__n, __nobjs);//分配起始位置的地址
_Obj* __STL_VOLATILE* __my_free_list;
_Obj* __result;
_Obj* __current_obj;
_Obj* __next_obj;
int __i;
if (1 == __nobjs) return(__chunk);//如果數(shù)量為1，直接返回當(dāng)前塊
__my_free_list = _S_free_list + _S_freelist_index(__n);//指向數(shù)組塊的位置，這里先以 __n=8 為例
/* Build free list in chunk */
__result = (_Obj*)__chunk;//result加一次可以跳到下個節(jié)點(diǎn)
*__my_free_list = __next_obj = (_Obj*)(__chunk + __n);//使數(shù)組中的第一個元素指向第二個chunk
for (__i = 1; ; __i++) {
__current_obj = __next_obj;
__next_obj = (_Obj*)((char*)__next_obj + __n);//指向下一個節(jié)點(diǎn)
if (__nobjs - 1 == __i) {//到鏈表最后節(jié)點(diǎn)
__current_obj -> _M_free_list_link = 0;//使next節(jié)點(diǎn)等于nullptr表示最后一個節(jié)點(diǎn)
break;
} else {
__current_obj -> _M_free_list_link = __next_obj;
}
}
return(__result);//返回鏈表首節(jié)點(diǎn)地址
}
_S_chunk_alloc(size_t __size, int& __nobjs):
/* We allocate memory in large chunks in order to avoid fragmenting */
/* the malloc heap too much. */
/* We assume that size is properly aligned. */
/* We hold the allocation lock. */
template
char*
__default_alloc_template<__threads, __inst>::_S_chunk_alloc(size_t __size,
int& __nobjs)
{//還是以nobjs為20，size為8來假設(shè)
char* __result;
size_t __total_bytes = __size * __nobjs;//160
size_t __bytes_left = _S_end_free - _S_start_free;//0 兩者初始化都為0 //第二次_1 __bytes_left=320
if (__bytes_left >= __total_bytes) {//第二次_2 返回開辟的內(nèi)存
__result = _S_start_free;
_S_start_free += __total_bytes;
return(__result);
} else if (__bytes_left >= __size) {//如果想要申請其他大小的chunk塊，可能會調(diào)用此方法在上一步申請的備用內(nèi)存中查找有無可用的內(nèi)存
__nobjs = (int)(__bytes_left/__size);
__total_bytes = __size * __nobjs;
__result = _S_start_free;
_S_start_free += __total_bytes;
return(__result);
} else {//初始化_1首先進(jìn)入該分支
size_t __bytes_to_get =
2 * __total_bytes + _S_round_up(_S_heap_size >> 4);//_S_heap_size初始為0，初始化__bytes_to_get=320
// Try to make use of the left-over piece.
if (__bytes_left > 0) {
_Obj* __STL_VOLATILE* __my_free_list =
_S_free_list + _S_freelist_index(__bytes_left);
((_Obj*)_S_start_free) -> _M_free_list_link = *__my_free_list;
*__my_free_list = (_Obj*)_S_start_free;
}
_S_start_free = (char*)malloc(__bytes_to_get);//初始化_2跳到這一步
if (0 == _S_start_free) {//如果開辟內(nèi)存失敗
size_t __i;
_Obj* __STL_VOLATILE* __my_free_list;
_Obj* __p;
// Try to make do with what we have. That can't
// hurt. We do not try smaller requests, since that tends
// to result in disaster on multi-process machines.
for (__i = __size;
__i <= (size_t) _MAX_BYTES;
__i += (size_t) _ALIGN) {
__my_free_list = _S_free_list + _S_freelist_index(__i);
__p = *__my_free_list;
if (0 != __p) {
*__my_free_list = __p -> _M_free_list_link;
_S_start_free = (char*)__p;
_S_end_free = _S_start_free + __i;
return(_S_chunk_alloc(__size, __nobjs));
// Any leftover piece will eventually make it to the
// right free list.
}
}
_S_end_free = 0; // In case of exception.
_S_start_free = (char*)malloc_alloc::allocate(__bytes_to_get);
// This should either throw an
// exception or remedy the situation. Thus we assume it
// succeeded.
}
_S_heap_size += __bytes_to_get;//初始化_3 _S_heap_size=320
_S_end_free = _S_start_free + __bytes_to_get;//_S_end_free是 char*類型，開辟一塊320字節(jié)的內(nèi)存塊
return(_S_chunk_alloc(__size, __nobjs));//初始化_4 遞歸調(diào)用自己
}
}
deallocate
/* __p may not be 0 */
static void deallocate(void* __p, size_t __n)
{
if (__n > (size_t) _MAX_BYTES)//如果大于_MAX_BYTES，就用標(biāo)準(zhǔn)庫的方法來
malloc_alloc::deallocate(__p, __n);
else {
_Obj* __STL_VOLATILE* __my_free_list
= _S_free_list + _S_freelist_index(__n);//取數(shù)組中的元素
_Obj* __q = (_Obj*)__p;
// acquire lock
# ifndef _NOTHREADS
/*REFERENCED*/
_Lock __lock_instance;
# endif /* _NOTHREADS */
__q -> _M_free_list_link = *__my_free_list;
*__my_free_list = __q;//回收原來數(shù)組Obj*指向的內(nèi)存
// lock is released here
}
}
