STL空間適配器

配置器

空間適配器的標準接口

代碼片段1

代碼片段2

內(nèi)存分配釋放與構(gòu)造析構(gòu)

為了精密分工号俐，STL allocator決定將這兩階段操作區(qū)分開來防嗡。內(nèi)存配置操作由alloc::allocate（）負責，內(nèi)存釋放操作由alloc::deallocate（）負責；對象構(gòu)造操作由::construct（）負責，對象析構(gòu)操作由::destroy（）負責。

構(gòu)造和析構(gòu)的基本工具：construct()和destroy()

首先析構(gòu)分為有意義的析構(gòu)函數(shù)操作和無意義的析構(gòu)函數(shù)操作计技，有意義的就是類似釋放堆內(nèi)存操作，delete一個指針山橄；無意義的就是一些棧內(nèi)存的釋放垮媒，因為系統(tǒng)會自動幫助我們進行釋放，例如在類內(nèi)聲明的一個整型變量int a航棱。

構(gòu)造析構(gòu)

destroy()有兩個版本：

destroy()有兩個版本睡雇，第一版本接受一個指針，準備將該指針所指之物析構(gòu)掉饮醇。這很簡單它抱，直接調(diào)用該對象的析構(gòu)函數(shù)即可。

第二版本接受first和last兩個迭代器（所謂迭代器朴艰，第3章有詳細介紹）观蓄，準備將[first，last)范圍內(nèi)的所有對象析構(gòu)掉祠墅。我們不知道這個范圍有多大侮穿，萬一很大，而每個對象的析構(gòu)函數(shù)都無關(guān)痛癢（所謂trivial destructor)毁嗦，那么一次次調(diào)用這些無關(guān)痛癢的析構(gòu)函數(shù)亲茅，對效率是一種傷害。因此金矛，這里首先利用value_type（）獲得迭代器所指對象的型別芯急，再利用_type_traits<T>判斷該型別的析構(gòu)函數(shù)是否無關(guān)痛癢。若是（true_type)驶俊，則什么也不做就結(jié)束；若否（false_type)免姿，這才以循環(huán)方式巡訪整個范圍饼酿，并在循環(huán)中每經(jīng)歷一個對象就調(diào)用第一個版本的destroy(）。

空間配置與釋放胚膊，std::alloc

對象構(gòu)造前的空間配置和對象析構(gòu)后的空間釋放故俐，由<stl_alloc.h>負責，SGI對此的設(shè)計哲學(xué)如下：

向system heap 要求空間紊婉。
考慮多線程（multi-threads)狀態(tài)药版。
考慮內(nèi)存不足時的應(yīng)變措施。
考慮過多“小型區(qū)塊”可能造成的內(nèi)存碎片（fragment)問題喻犁。

C++的內(nèi)存配置基本操作是：：operator new（）槽片，內(nèi)存釋放基本操作是：：operator delete()何缓。這兩個全局函數(shù)相當于C的malloc（）和free（）函數(shù)。是的还栓，正是如此碌廓，SGI正是以malloc（）和free（）完成內(nèi)存的配置與釋放。

STL一級適配器和二級適配器

考慮到小型區(qū)塊所可能造成的內(nèi)存破碎問題剩盒，SGI 設(shè)計了雙層級配置器谷婆，第一級適配器用 malloc(）和 free()，第二級配置器則視情況采用不同的策略：當配置區(qū)塊超過 128 bytes 時辽聊，視之為 “足夠大”纪挎，便調(diào)用第一級配置器；當配置區(qū)塊小于 128 bytes 時跟匆，視之為 “過小”廷区，為了降低額外負擔，便采用復(fù)雜的內(nèi)存池(memory pool)整理方式贾铝，而不再求助于第一級配置器隙轻。

一級適配器和二級適配器

包裝接口和運用方式

包裝和接口

一級適配器

第一級配置器以 malloc(), free(), realloc(）等 C 函數(shù)執(zhí)行實際的內(nèi)存配置、釋放垢揩、重配置操作玖绿，并實現(xiàn)出類似 C++ new-handler7 的機制。

malloc(）和 realloc(）不成功后,改調(diào)用 oom_malloc() 和 oom_realloc()叁巨。
后兩者都有內(nèi)循環(huán)斑匪，不斷調(diào)用 “內(nèi)存不足處理例程”，期望在某次調(diào)用之后锋勺，獲得足夠的內(nèi)存而圓滿完成任務(wù)蚀瘸。但如果 “內(nèi)存不足處理例程”并未被客端設(shè)定,oom_malloc(）和 oom_realloc() 便老實不客氣地調(diào)用 __THROW_BAD_ALLOC,丟出 bad_alloc 異常信息，或利用 exit（1）硬生生中止程序庶橱。

相關(guān)代碼：

一級適配器代碼

一級適配器代碼2

C++ new-handler的機制

所謂C++new handler機制是贮勃，你可以要求系統(tǒng)在內(nèi)存配置需求無法被滿足時，調(diào)用一個你所指定的函數(shù)苏章。換句話說寂嘉，一旦：：operator new無法完成任務(wù)，在丟出stdl：bad_aloc異常狀態(tài)之前枫绅，會先調(diào)用由客端指定的處理例程泉孩。

相關(guān)信息：

注意，SGI以malloc而非：：operator new來配置內(nèi)存（我所能夠想象的一個原因是歷史因素并淋，另一個原因是C++并未提供相應(yīng)于realloc（）的內(nèi)存配置操作）寓搬，因此，SGI不能直接使用C++的set_new_handler(）县耽，必須仿真一個類似的 set_malloc_handler(）句喷。
請注意镣典，SGI第一級配置器的allocate（）和realloc（）都是在調(diào)用ma11oc（）和rea1loc（）不成功后，改調(diào)用oom_malloc（）和oom_realloc(）脏嚷。
后兩者都有內(nèi)循環(huán)骆撇，不斷調(diào)用“內(nèi)存不足處理例程”，期望在某次調(diào)用之后父叙，獲得足夠的內(nèi)存而圓滿完成任務(wù)神郊。但如果“內(nèi)存不足處理例程”并未被客端設(shè)定，oom_malloc（）和oom_realloc（）便老實不客氣地調(diào)用THROW_BAD_ALLOC趾唱，丟出bad alloc異常信息涌乳，或利用exit（1）硬生生中止程序。
記住甜癞，設(shè)計“內(nèi)存不足處理例程”是客端的責任夕晓，設(shè)定“內(nèi)存不足處理例程”
也是客端的責任。再一次提醒你悠咱，“內(nèi)存不足處理例程”解決問題的做法有著特定的模式

內(nèi)存不足處理例程是客端的責任蒸辆！

適配器

二級適配器

請求內(nèi)存的布局：(索求任何一塊內(nèi)存，都得有一些“稅”要繳給系統(tǒng))

請求布局

SGI 第二級配置器的做法是析既，如果區(qū)塊夠大躬贡，超過 128 bytes 時，就移交第一級配置器處理眼坏。當區(qū)塊小于 128 bytes 時拂玻，則以內(nèi)存池（memory pool）管理，此法又稱為次層配置（sub-allocation）：每次配置一大塊內(nèi)存宰译，并維護對應(yīng)之自由鏈表（free-list）檐蚜。下次若再有相同大小的內(nèi)存需求，就直接從 free-lists 中撥出沿侈。如果客端釋還小額區(qū)塊闯第，就由配置器回收到 free-lists 中——是的，別忘了肋坚，配置器除了負責配置乡括，也負責回收。為了方便管理智厌，SGI 第二級配置器會主動將任何小額區(qū)塊的內(nèi)存需求量上調(diào)至 8 的倍數(shù)（例如客端要求 30 bytes，就自動調(diào)整為 32 bytes）盲赊，并維護 16 個 free-lists铣鹏，各自管理大小分別為 8, 16, 24, 32, 40, 48, 56, 64, 72, 80, 88,96,104,112,120,128 bytes 的小額區(qū)塊。

但是哀蘑，我們通常會想到诚卸，為了維護這個鏈表葵第，每個節(jié)點都必須含有一個額外的指針，指向下一個節(jié)點合溺，這顯然會造成負擔卒密。所以我們使用union這個數(shù)據(jù)結(jié)構(gòu)解決這個問題。free-lists 的節(jié)點結(jié)構(gòu)如下：

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

該結(jié)構(gòu)中棠赛，從第一個字段來看哮奇，obj可以視為一個指針，指向相同形式的另一個obj睛约；從第二個字段看鼎俘，obj可以視為一個指針，指向?qū)嶋H區(qū)塊辩涝。一物二用的結(jié)果是贸伐，不會為了維護鏈表所必須的指針而造成內(nèi)存的另一種浪費。

下面是自由鏈表實現(xiàn)：

自由鏈表

空間配置函數(shù)allocate()

身為一個配置器怔揩，__default_alloc_template 擁有配置器的標準接口函數(shù)allocate()捉邢。此函數(shù)首先判斷區(qū)塊大小，大于128 bytes 就調(diào)用第一級配置器商膊，小于 128 bytes 就檢查對應(yīng)的 free list伏伐。如果 free list 之內(nèi)有可用的區(qū)塊，就直接拿來用翘狱，如果沒有可用區(qū)塊秘案，就將區(qū)塊大小上調(diào)至 8 倍數(shù)邊界，然后調(diào)用 refill（）,準備為free list重新填充空間潦匈。

填充空間的意思時從內(nèi)存池中拿出一部分空間填充到空閑鏈表中去阱高。

相關(guān)代碼

如下圖圖示：

假如當前空閑鏈表沒有指向空閑空間的時候，值為0茬缩，此時需要從內(nèi)存池中分配內(nèi)存去填充這個空閑鏈表赤惊；當空閑鏈表還有指向空閑空間的指針的時候，可以直接拿頭節(jié)點的指針指向的空間來用就可以凰锡，最后記得更新空閑鏈表未舟。

分配空閑空間

也就是說，當可以從空閑鏈表中找到可以分配的空間掂为，就從空閑鏈表調(diào)出一個空間裕膀，如下圖：

調(diào)出鏈表空閑節(jié)點

調(diào)出去之后后面的空閑節(jié)點向前移動：

更新鏈表

對應(yīng)的空閑鏈表沒有空閑分區(qū)的時候，就是下面這種情況

無空閑分區(qū)

空間釋放函數(shù) deallocate(）

身為一個配置器勇哗，_default_alloc_template擁有配置器標準接口函數(shù)deallocate()昼扛。該函數(shù)首先判斷區(qū)塊大小，大于128bytes就調(diào)用第一級配置器欲诺，小于128bytes就找出對應(yīng)的free list抄谐，將區(qū)塊回收渺鹦。

相關(guān)代碼如下：

空間釋放代碼片段

回收區(qū)塊的時候直接將這個區(qū)塊的指針插入到對應(yīng)節(jié)點的第一個空閑指針即可：

回收分區(qū)

也即：

回收分區(qū)

重新填充free lists

當申請空間的時候發(fā)現(xiàn)對應(yīng)的鏈表沒有空閑分區(qū)的時候，也就是下面這種情況

無空閑分區(qū)

我們就需要調(diào)用 refill（)蛹含，準備為 free list 重新填充空間毅厚。新的空間將取自內(nèi)存池（經(jīng)由chunk_alloc() 完成）。

<font color = 'pink'>缺省取得20 個新節(jié)點（新區(qū)塊）浦箱，但萬一內(nèi)存池空間不足吸耿，獲得的節(jié)點數(shù)（區(qū)塊數(shù)）可能小于20。</font>

總的來說：

向內(nèi)存池申請空間的起始地址

如果只申請到一個對象的大小, 就直接返回一個內(nèi)存的大小, 如果有更多的內(nèi)存, 就繼續(xù)執(zhí)行

從第二個塊內(nèi)存開始, 把從內(nèi)存池里面分配的內(nèi)存用鏈表給串起來, 并返回一個塊內(nèi)存的地址給用戶

refill相關(guān)代碼如下(假設(shè) n 已經(jīng)適當上調(diào)至 8 的倍數(shù)):

// 內(nèi)存填充
template <bool threads, int inst>
void* __default_alloc_template<threads, inst>::refill(size_t n)
{
    int nobjs = 20;
    char * chunk = chunk_alloc(n, nobjs);             // 向內(nèi)存池申請空間的起始地址
    obj * __VOLATILE * my_free_list;
    obj * result;
    obj * current_obj, * next_obj;
    int i;

    // 如果只申請到一個對象的大小, 就直接返回一個內(nèi)存的大小
    if (1 == nobjs) return(chunk);
    my_free_list = free_list + FREELIST_INDEX(n);

    // 申請的大小不只一個對象的大小的時候
    result = (obj *)chunk;
    // my_free_list指向內(nèi)存池返回的地址的下一個對齊后的地址
    *my_free_list = next_obj = (obj *)(chunk + n);
    // 這里從第二個開始的原因主要是第一塊地址返回給了用戶, 現(xiàn)在需要把從內(nèi)存池里面分配的內(nèi)存用鏈表給串起來
    for (i = 1; ; i++) 
    {
        current_obj = next_obj;
        next_obj = (obj *)((char *)next_obj + n);
        if (nobjs - 1 == i) 
        {
            current_obj -> free_list_link = 0;
            break;
        } 
        else 
        {
            current_obj -> free_list_link = next_obj;
        }
        }
    return(result);
}

內(nèi)存池（memory pool）

從內(nèi)存池中取空間給 freelist 使用憎茂，是 chunk_alloc(）的工作珍语，其主要做了下面的工作：

內(nèi)存池的大小大于需要的空間, 直接返回起始地址(nobjs默認設(shè)置為20, 所以每次調(diào)用都會給鏈表額外的19個內(nèi)存塊)

內(nèi)存池的內(nèi)存不足以馬上分配那么多內(nèi)存, 但是還能滿足分配一個即以上的大小, 那就全部分配出去

如果一個對象的大小都已經(jīng)提供不了了, 先將零碎的內(nèi)存塊給一個小內(nèi)存的鏈表來保存, 然后就準備調(diào)用malloc申請40塊+額外大小的內(nèi)存塊(額外內(nèi)存塊就由heap_size決定), 如果申請失敗跳轉(zhuǎn)到步驟4, 成功跳轉(zhuǎn)到步驟6

充分利用更大內(nèi)存的鏈表, 通過遞歸來調(diào)用他們的內(nèi)存塊

如果還是沒有內(nèi)存塊, 直接調(diào)用一級配置器來申請內(nèi)存, 還是失敗就拋出異常, 成功申請就繼續(xù)執(zhí)行

重新修改內(nèi)存起始地址和結(jié)束地址為當前申請的地址塊, 重新調(diào)用chunk_alloc分配內(nèi)存

內(nèi)存池的代碼如下：

<font color = 'pink'>注意，下面代碼函數(shù)參數(shù)nobjs傳的是引用</font>

// 內(nèi)存池
template <bool threads, int inst>
char* __default_alloc_template<threads, inst>::chunk_alloc(size_t size, int& nobjs)
{
    char * result;
    size_t total_bytes = size * nobjs;            // 鏈表需要申請的內(nèi)存大小
    size_t bytes_left = end_free - start_free;    // 內(nèi)存池里面總共還有多少內(nèi)存空間

      // 內(nèi)存池的大小大于需要的空間, 直接返回起始地址
    if (bytes_left >= total_bytes) 
    {
        result = start_free;
        start_free += total_bytes;  // 內(nèi)存池的首地址往后移
        return(result);
    }
    // 內(nèi)存池的內(nèi)存不足以馬上分配那么多內(nèi)存, 但是還能滿足分配一個即以上的大小, 那就按對齊方式全部分配出去
    else if (bytes_left >= size) 
    {
        nobjs = bytes_left/size;
        total_bytes = size * nobjs;
        result = start_free;
        start_free += total_bytes;  // 內(nèi)存池的首地址往后移
        return(result);
    } 
    else 
    { 
        // 如果一個對象的大小都已經(jīng)提供不了了, 那就準備調(diào)用malloc申請兩倍+額外大小的內(nèi)存
        size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
        // Try to make use of the left-over piece.
        // 內(nèi)存池還剩下的零頭內(nèi)存分給給其他能利用的鏈表, 也就是絕不浪費一點.
        if (bytes_left > 0) 
        {
            // 鏈表指向申請內(nèi)存的地址
            obj * __VOLATILE * my_free_list = free_list + FREELIST_INDEX(bytes_left);
            ((obj *)start_free) -> free_list_link = *my_free_list;
            *my_free_list = (obj *)start_free;
        }
        start_free = (char *)malloc(bytes_to_get);
        // 內(nèi)存不足了
        if (0 == start_free) 
        {
            int i;
            obj * __VOLATILE * my_free_list, *p;
            // 充分利用剩余鏈表的內(nèi)存, 通過遞歸來申請
            for (i = size; i <= __MAX_BYTES; i += __ALIGN) 
            {   
                my_free_list = free_list + FREELIST_INDEX(i);
                p = *my_free_list;
                if (0 != p) 
                {
                    *my_free_list = p -> free_list_link;
                    start_free = (char *)p;
                    end_free = start_free + i;
                    return(chunk_alloc(size, nobjs));
                }
            }
            // 如果一點內(nèi)存都沒有了的話, 就只有調(diào)用一級配置器來申請內(nèi)存了, 并且用戶沒有設(shè)置處理例程就拋出異常
            end_free = 0;   // In case of exception.
            start_free = (char *)malloc_alloc::allocate(bytes_to_get);
        }
            // 申請內(nèi)存成功后重新修改內(nèi)存起始地址和結(jié)束地址, 重新調(diào)用chunk_alloc分配內(nèi)存竖幔，此時內(nèi)存池已有空間分配
            heap_size += bytes_to_get;
            end_free = start_free + bytes_to_get;
            return(chunk_alloc(size, nobjs));
    }   
}

上述的 chunk_alloc(）函數(shù)以 end_free - start_free 來判斷內(nèi)存池的水量板乙。如果水量充足，就直接調(diào)出 20 個區(qū)塊返回給 free list拳氢。如果水量不足以提供 20個區(qū)塊募逞，但還足夠供應(yīng)一個以上的區(qū)塊，就撥出這不足 20 個區(qū)塊的空間出去馋评。這時候其 pass by reference 的 nobjs 參數(shù)將被修改為實際能夠供應(yīng)的區(qū)塊數(shù)放接。如果內(nèi)存池連一個區(qū)塊空間都無法供應(yīng),對客端顯然無法交待,此時便需利用 malloc(）從 heap 中配置內(nèi)存，為內(nèi)存池注人活水源頭以應(yīng)付需求留特。新水量的大小為需求量的兩倍纠脾，再加上一個隨著配置次數(shù)增加而愈來愈大的附加量。

內(nèi)存池實際操練結(jié)果：

內(nèi)存池操作

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

前兩個函數(shù)是用于構(gòu)造的construct（）和用于析構(gòu)的destroy（）蜕青，另三個函數(shù)是 uninitialized_copy(),uninitialized_fi11(),uninitialized_fil1_n()10, 分別對應(yīng)于高層次函數(shù)copy（）苟蹈、fi11（）、fi11_n(）——這些都是STL算法右核。

uninitialized_copy函數(shù)

功能 : 從first到last范圍內(nèi)的元素復(fù)制到從 result地址開始的內(nèi)存.

template <class InputIterator, class ForwardIterator>
inline ForwardIterator uninitialized_copy(InputIterator first, InputIterator last,
                     ForwardIterator result) {
  return __uninitialized_copy(first, last, result, value_type(result));
}

uninitialized_copy()使我們能夠?qū)?nèi)存的配置與對象的構(gòu)造行為分離開來慧脱。如果作為輸出目的地的[result，result+(last-first))范圍內(nèi)的每一個迭代器都指向未初始化區(qū)域贺喝，則uninitializead_copy（）會使用copy constructor菱鸥，給身為輸入來源之[first，last)范圍內(nèi)的每一個對象產(chǎn)生一份復(fù)制品躏鱼，放進輸出范圍中氮采。換句話說，針對輸入范圍內(nèi)的每一個迭代器i染苛，該函數(shù)會調(diào)用construct(&*(result+(i-first)),*i),產(chǎn)生*i的復(fù)制品扳抽，放置于輸出范圍的相對位置上。

如果你需要實現(xiàn)一個容器殖侵，uninitialized_copy（）這樣的函數(shù)會為你帶來很大的幫助贸呢，因為容器的全區(qū)間構(gòu)造函數(shù)（range constructor)通常以兩個步驟完成：

配置內(nèi)存區(qū)塊，足以包含范圍內(nèi)的所有元素拢军。
使用uninitialized_copy（)楞陷，在該內(nèi)存區(qū)塊上構(gòu)造元素。

C++標準規(guī)格書要求uninitialized_copy（）具有“commit or rollback”語意茉唉，意思是要么“構(gòu)造出所有必要元素”固蛾，要么（當有任何一個copy constructor失敗時)“不構(gòu)造任何東西”。

其中__uninitialized_copy函數(shù)代碼如下：

template <class InputIterator, class ForwardIterator, class T>
inline ForwardIterator __uninitialized_copy(InputIterator first, InputIterator last,
                     ForwardIterator result, T*) {
  typedef typename __type_traits<T>::is_POD_type is_POD;
  return __uninitialized_copy_aux(first, last, result, is_POD());
}

__uninitialized_copy使用了typename進行萃取, 并且萃取的類型是POD.

優(yōu)化處理

POD意指Plain Old Data度陆，也就是標量型別（scalar types)或傳統(tǒng)的Cstruct型別艾凯。POD型別必然擁有trivial ctor/dtor/copy/assignment函數(shù)茫蛹，因此米间，我們可以對POD型別采用最有效率的復(fù)制手法讲冠，而對non-POD型別采取最保險安全的做法：

__uninitialized_copy_aux優(yōu)化處理

// 如果是POD類型
template <class InputIterator, class ForwardIterator> 
inline ForwardIterator __uninitialized_copy_aux(InputIterator first, InputIterator last,
                         ForwardIterator result,
                         __true_type) {
  return copy(first, last, result);
}

// 如果不是POD類型
template <class InputIterator, class ForwardIterator>
ForwardIterator __uninitialized_copy_aux(InputIterator first, InputIterator last,
                         ForwardIterator result,
                         __false_type) {
  ForwardIterator cur = result;
  __STL_TRY {
    for ( ; first != last; ++first, ++cur)
      construct(&*cur, *first);
    return cur;
  }
  __STL_UNWIND(destroy(result, cur));
}

__uninitialized_copy針對普通類型(int, double)做了特殊的優(yōu)化, 以執(zhí)行更高效的處理, 對類和用戶定義類型做了構(gòu)造處理, 當然用戶自定義的不一定是類, 但是編譯器為了安全性依然會執(zhí)行最慢處理.

uninitialized_copy_n函數(shù)

uninitialized_copy_n也做了跟uninitialized_copy類似的處理, 只是它是采用tratis編程里iterator_category迭代器的類型來選擇最優(yōu)的處理函數(shù).

template <class InputIterator, class Size, class ForwardIterator>
inline pair<InputIterator, ForwardIterator>
uninitialized_copy_n(InputIterator first, Size count,
                     ForwardIterator result) {
  return __uninitialized_copy_n(first, count, result, iterator_category(first)); // 根據(jù)iterator_category選擇最優(yōu)函數(shù)
}

template <class InputIterator, class Size, class ForwardIterator>
pair<InputIterator, ForwardIterator>
__uninitialized_copy_n(InputIterator first, Size count, ForwardIterator result,
                       input_iterator_tag) // input_iterator_tag類型的迭代器
{
  ForwardIterator cur = result;
  __STL_TRY {
    for ( ; count > 0 ; --count, ++first, ++cur) 
      construct(&*cur, *first);
    return pair<InputIterator, ForwardIterator>(first, cur);
  }
  __STL_UNWIND(destroy(result, cur));
}

template <class RandomAccessIterator, class Size, class ForwardIterator>
inline pair<RandomAccessIterator, ForwardIterator>
__uninitialized_copy_n(RandomAccessIterator first, Size count, ForwardIterator result,
                       random_access_iterator_tag) // random_access_iterator_tag類型的迭代器
{
  RandomAccessIterator last = first + count;
  return make_pair(last, uninitialized_copy(first, last, result));
}

uninitialized_copy類似于第一篇分析空間配置器的destory針對const char*和const wchar*單獨做了特例化.

inline char* uninitialized_copy(const char* first, const char* last,
                                char* result) {
  memmove(result, first, last - first);
  return result + (last - first);
}

inline wchar_t* uninitialized_copy(const wchar_t* first, const wchar_t* last,
                                   wchar_t* result) {
  memmove(result, first, sizeof(wchar_t) * (last - first));
  return result + (last - first);
}

直接調(diào)用c++的memmove操作, 畢竟這樣的效率更加的高效.

uninitialized_fill函數(shù)

功能 : 從first到last范圍內(nèi)的都填充為 x 的值.

uninitialized_fill采用了與uninitialized_copy一樣的處理方法選擇最優(yōu)處理函數(shù),

函數(shù)聲明：

template <class ForwardIterator, class T>
void uninitialized_fill(ForwardIterator first, ForwardIterator last, const T& x);

uninitialized_fill()也能夠使我們將內(nèi)存配置與對象的構(gòu)造行為分離開來蹋半。如果[first礁遣，last）范圍內(nèi)的每個迭代器都指向未初始化的內(nèi)存晰奖，那么uninitialized_fill()會在該范圍內(nèi)產(chǎn)生x（上式第三參數(shù)）的復(fù)制品队腐。換句話說坐儿，uninitialized_fill（）會針對操作范圍內(nèi)的每個迭代器i犀斋，調(diào)用construct(&*i贝乎，x），在i所指之處產(chǎn)生x的復(fù)制品叽粹。

與uninitialized_copy（）一樣览效，uninitialized_fill（）必須具備“commitor rollback”語意，換句話說虫几，它要么產(chǎn)生出所有必要元素锤灿，要么不產(chǎn)生任何元素。
如果有任何一個copy constructor 丟出異常(exception)持钉，uninitialized_fill（）衡招，必須能夠?qū)⒁旬a(chǎn)生的所有元素析構(gòu)掉。

相關(guān)代碼如下：

// 函數(shù)封裝
template <class ForwardIterator, class T>
inline void uninitialized_fill(ForwardIterator first, ForwardIterator last, const T& x) 
{
  __uninitialized_fill(first, last, x, value_type(first));
}

// 類型萃取并且調(diào)用重載函數(shù)
template <class ForwardIterator, class T, class T1>
inline void __uninitialized_fill(ForwardIterator first, ForwardIterator last,  const T& x, T1*)
{
  typedef typename __type_traits<T1>::is_POD_type is_POD;
  __uninitialized_fill_aux(first, last, x, is_POD());
                   
}

// 是POD類型
template <class ForwardIterator, class T>
inline void
__uninitialized_fill_aux(ForwardIterator first, ForwardIterator last,  const T& x, __true_type)
{
   fill(first, last, x);    // 調(diào)用STL算法fill()
}

// 不是POD類型
template <class ForwardIterator, class T>
void
__uninitialized_fill_aux(ForwardIterator first, ForwardIterator last, const T& x, __false_type)
{
  ForwardIterator cur = first;
  __STL_TRY {
    for ( ; cur != last; ++cur)
      construct(&*cur, x);  // 必須一個一個元素地構(gòu)造每强，無法批量進行
  }
  __STL_UNWIND(destroy(first, cur));
}

uninitialized_fill_n函數(shù)

功能 : 從first開始n 個元素填充成 x 值.

相關(guān)代碼：

// 函數(shù)封裝
template <class ForwardIterator, class Size, class T>
inline ForwardIterator uninitialized_fill_n(ForwardIterator first, Size n, const T& x) 
{
  return __uninitialized_fill_n(first, n, x, value_type(first));
}

// 萃取并且調(diào)用重載函數(shù)
template <class ForwardIterator, class Size, class T, class T1>
inline ForwardIterator __uninitialized_fill_n(ForwardIterator first, Size n, const T& x, T1*) 
{
  typedef typename __type_traits<T1>::is_POD_type is_POD;
  return __uninitialized_fill_n_aux(first, n, x, is_POD());                                
}

// 假如是POD類型
template <class ForwardIterator, class Size, class T>
inline ForwardIterator __uninitialized_fill_n_aux(ForwardIterator first, Size n, const T& x, __true_type) 
{
  return fill_n(first, n, x);   // 交由高階函數(shù)執(zhí)行
}

// 不是POD類型
template <class ForwardIterator, class Size, class T>
ForwardIterator __uninitialized_fill_n_aux(ForwardIterator first, Size n, const T& x, __false_type) 
{
    ForwardIterator cur = first;
    __STL_TRY 
    {
        for ( ; n > 0; --n, ++cur)
            construct(&*cur, x);    // 必須一個一個調(diào)用拷貝構(gòu)造函數(shù)
        return cur;
    }
    __STL_UNWIND(destroy(first, cur));
}

三個函數(shù)效率的特殊考慮可以總結(jié)為下圖：

函數(shù)效率優(yōu)化

參考地址：

STL源碼分析目錄
《STL源碼分析》- 侯捷