STL一級空間配置器

一、什麼是STL

STL（standard Template Library，标準模闆庫），從根本上說，STL是一些“容器”的集合，這些“容器”有list,vector,set,map等。

STL也是算法和其他一些元件的集合。

STL有六大元件，彼此可以組合套用，六大元件分别是：

1、容器（containers）:各種資料結構，如vector,list,deque,set,map等，用來存放資料。

2、算法（algorithms）：各種算法如sort,search,copy,erase等。

3、疊代器（iterators）:扮演容器與算法之間的膠合劑，共有五種類型。

4、仿函數（functors）:行為類似函數，可作為算法的某種謀略。

5、擴充卡（adapters）:一種用來修飾容器或仿函數或疊代器接口的東西。

6、配置器（allocators):負責空間配置與管理。

我們之前經常接觸容器與容器擴充卡，來複習一下吧！

1、容器

（1）序列式容器

比如：

向量(vector) ：連續存儲的元素

清單(list) ：由節點組成的雙向連結清單，每個結點包含着一個元素

雙端隊列(deque) ：連續存儲的指向不同元素的指針所組成的數組

（2）關聯式容器

比如：

集合(set):由節點組成的紅黑樹，每個節點都包含着一個元素，節點之間以某種作用于元素對的謂詞排列，沒有兩個不同的元素能夠擁有相同的次序

多重集合(multiset)：允許存在兩個次序相等的元素的集合

映射(map)：由{鍵，值}對組成的集合，以某種作用于鍵對上的謂詞排列

多重映射(multimap)：允許鍵對有相等的次序的映射

2、容器擴充卡

棧(stack)：後進先出的值的排列

隊列(queue)：先進先出的值的排列

優先隊列(priority_queue)：元素的次序是由作用于所存儲的值對上的某種謂詞決定的的一種隊列

二、空間配置器

1、什麼是空間配置器

所謂空間擴充卡，就是用來管理記憶體的一個器具。對于STL來說，空間擴充卡是它可以正常工作的基礎，也為它可以高效工作提供了動力。對于使用STL來說，它是不和使用者直接打交道的，而是隐藏在一切STL組建之後，默默為各種記憶體申請提供支援的。

注：這裡所指的空間不單單指記憶體，也可以是磁盤或者其他存儲媒體。

2、空間配置器有什麼好處

提高代碼複用率，功能子產品化
減少記憶體碎片問題
效率問題：頻繁的配置設定小塊記憶體，效率比較低
容易造成記憶體洩露
調用malloc/ new向系統配置設定的每塊記憶體都有一些額外的開銷
空間不足時應對措施
隐藏實際中對存儲空間的配置設定及釋放的細節&確定所有被配置設定的存儲空間都最終能獲得釋放

3、空間配置器的思想

對于我們來說，對new和delete很熟悉，這兩個函數可以分别完成記憶體的申請和釋放，和c裡面的malloc和free如出一轍。

Std::alloc的主要思想是：

（1）定義一個空間大小門檻值，128bytes；

（2）如果申請的空間大于128bytes，那麼就調用第一級空間擴充卡來完成配置設定工作；

（3）如果小于128bytes，那麼就調用第二級空間擴充卡來完成。

3、一級空間配置器

// 一級空間配置器
template <int __inst>
class __malloc_alloc_template {

private:
    //以下函數用來處理記憶體不足的情況
    static void* _S_oom_malloc(size_t);
    static void* _S_oom_realloc(void*, size_t);

#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
    //記憶體不足處理例程
    static void(*__malloc_alloc_oom_handler)(); //__malloc_alloc_oom_handler是函數指針
#endif

public:

    //空間配置函數
    static void* allocate(size_t __n)
    {
        //用malloc申請空間
        void* __result = malloc(__n);
        //如果申請空間失敗，則調用_S_oom_malloc重新申請空間
        if (0 == __result) __result = _S_oom_malloc(__n);
        return __result;
    }

    //空間釋放函數
    static void deallocate(void* __p, size_t /* __n */)
    {
        //調用free來釋放空間
        free(__p);
    }

    //空間重配置函數
    static void* reallocate(void* __p, size_t /* old_sz */, size_t __new_sz)
    {
        //用realloc來重新配置空間
        void* __result = realloc(__p, __new_sz);
        //如果由于空間不足配置失敗，則調用_S_oom_realloc重新申請空間
        if (0 == __result) __result = _S_oom_realloc(__p, __new_sz);
        return __result;
    }

    //該函數重新指定了記憶體配置設定異常處理函數，并傳回了原有的記憶體配置設定異常處理函數
    //該函數接受一個“傳回值和參數均為空的函數指針”作為參數
    //該函數最後傳回一個“傳回值和參數均為空的函數指針”
    static void(*__set_malloc_handler(void(*__f)()))()
    {
        void(*__old)() = __malloc_alloc_oom_handler;
        //重新指定記憶體配置設定異常處理函數
        __malloc_alloc_oom_handler = __f;
        //傳回原有的記憶體配置設定異常處理函數
        return(__old);
    }

};

// malloc_alloc out-of-memory handling

#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
template <int __inst>
//記憶體不足處理例程，初始值為0，待使用者自定義，考慮記憶體不足時的應變措施
void(*__malloc_alloc_template<__inst>::__malloc_alloc_oom_handler)() = 0;
#endif

template <int __inst>

//申請空間失敗時調用_S_oom_malloc重新申請空間
void* __malloc_alloc_template<__inst>::_S_oom_malloc(size_t __n)
{
    //定義一個函數指針__my_malloc_handler
    void(*__my_malloc_handler)();
    void* __result;
    //該循環有兩個退出條件
    //一個是成功申請到空間，最終傳回__result
    //另一個是最終申請空間失敗，抛出異常__THROW_BAD_ALLOC
    for (;;) {
        __my_malloc_handler = __malloc_alloc_oom_handler;
        //由于初值為0，如果使用者沒有自定義記憶體不足處理例程，那麼還是抛出異常
        if (0 == __my_malloc_handler) { __THROW_BAD_ALLOC; }
        //調用記憶體不足處理例程，嘗試釋放空間
        (*__my_malloc_handler)();
        //再次嘗試配置空間
        __result = malloc(__n);
        if (__result) return(__result);
    }
}

template <int __inst>

//重新配置空間失敗時調用_S_oom_realloc申請空間
void* __malloc_alloc_template<__inst>::_S_oom_realloc(void* __p, size_t __n)
{
    //定義一個函數指針__my_malloc_handler
    void(*__my_malloc_handler)();
    void* __result;
    //該循環有兩個退出條件
    //一個是成功申請到空間，最終傳回__result
    //另一個是最終申請空間失敗，抛出異常__THROW_BAD_ALLOC
    for (;;) {
        __my_malloc_handler = __malloc_alloc_oom_handler;
        //由于初值為0，如果使用者沒有自定義記憶體不足處理例程，那麼還是抛出異常
        if (0 == __my_malloc_handler) { __THROW_BAD_ALLOC; }
        //調用記憶體不足處理例程，嘗試釋放空間
        (*__my_malloc_handler)();
        //再次嘗試配置空間
        __result = realloc(__p, __n);
        if (__result) return(__result);
    }
}

//由于參數inst在這裡沒有排上用場，是以定義為數值0
typedef __malloc_alloc_template<0> malloc_alloc;

//一級空間配置器  >128
//函數指針
typedef void(*pMallocHandle)();
template<int inst>
class MallocAllocTemplate
{
public:
    void* Allocate(size_t size)
    {
        void* result = malloc(size);
        //申請失敗調用OOM_Malloc()函數
        if (NULL == result)
        {
            result = OOM_Malloc(size);
        }
        return result;
    }
    //重新配置設定空間
    void* ReAllocate(void* p,size_t,size_t newSize)              //三個參數
    {
        void* result = realloc(p, newSize);
        if (NULL == result)
        {
            result = OOM_Realloc(p, newSize);
        }
        return result;
    }
    void DeAllocate(void* p,size_t)  //底層是兩個參數
    {
        free(p);
    }

private:
    void* OOM_Malloc(size_t size)
    {
        pMallocHandle mallocHandle;
        void* res;
        for (;;)
        {
            mallocHandle = _mallocHandle;
            if (NULL == mallocHandle)
                throw std::bad_alloc();
            //嘗試去釋放已經擷取，但是不用的堆空間
            mallocHandle();
            //嘗試重新配置設定記憶體
            res = malloc(size);
            if (res)
                return res;
        }
    }
    void* OOM_Realloc(void *p, size_t size)
    {
        pMallocHandle mallocHandle;
        void* res;
        for (;;)
        {
            mallocHandle = _mallocHandle;
            if (NULL == mallocHandle)
                throw std::bad_alloc();
            //嘗試去釋放已經擷取但是不用的堆空間
            mallocHandle();

            res = realloc(p, size);
            if (res)
                return res;
        }
    }

    //若申請失敗，釋放方法   
    pMallocHandle SetMallocHandle(pMallocHandle mallocHandle)
    {
        pMallocHandle old = _mallocHandle;
        _mallocHandle = mallocHandle;
        return old;
    }
private:
    static pMallocHandle _mallocHandle;
};

pMallocHandle MallocAllocTemplate<0>::_mallocHandle = NULL;

STL一級空間配置器

一、什麼是STL

二、空間配置器

1、什麼是空間配置器

2、空間配置器有什麼好處

3、空間配置器的思想

3、一級空間配置器

繼續閱讀

閱讀開源引擎源代碼的方式學習遊戲引擎好嗎？

gdb腳本 - 檢視stl變量

<Effectives STL>筆記之在STL容器中删除元素的方法選擇

C++ STL基本容器比較

STL--vector容器STL—vector容器

STL相關

【CF 125D】 Two progressions 劃分等差數列

STL六大元件以及互相關系

STL 六大元件概要

初識 STL

STL——deque 雙向隊列

c++中指針的指針和指針的引用的使用

pat（B）1009. 說反話（逆疊代器）

C++ heap學習

C#入門基礎程式設計（第一章）

ASP.NET大型績效考核評估系統源碼