參考 STL原始碼剖析

空間配置器

從STL的角度看，空間配置器是一個很常見的東西，他以預設的形式隱藏在一切組件中，默默無聞，為各個容器高效的管理空間(空間的申請與回收)

• vector
  
• list
  
• unordered_map
  

等等，我們平常用的時候，通常都是向記憶體申請空間，但是既然STL中叫做空間配置器，那么一定不單單只能申請記憶體空間，因為空間不一定都是記憶體，也可以是磁盤或者其他輔助存盤的介質，

一個簡單的空間配置器

所需要包含的頭檔案，new，exit，size_t，ptrdiff_t （兩個指標之間的距離），UINT_MAX，cerr（標準錯誤），才知道居然都在這里，，，，，，

ptrdiff_t型別變數通常用來保存兩個指標減法操作的結果

對于一個簡單的空間配接器來說，需要有申請空間，釋放空間的操作（簡單實作，只使用operator new/operator delete，placement new）

new/delete 與 operator new/operator delete ，placement new

• new operator和new delete

new operator和new delete 就是 new 和 delete 運算子，當我們在程式中使用new或者delete時，會先呼叫我們運算子多載的operator new/operator delete 函式來申請空間，之后就呼叫物件的構造和解構式去初始化和析構空間中的資料，

他和sizeof一樣是語言內置的，他總是做兩件事

1. 為物件申請記憶體
2. 呼叫建構式初始化物件

我們是不能對這個功能進行改變的，也就是不能多載，但是我們可以多載operator new/operator delete

• operator new/operator delete

operator new/operator delete的本質是一個函式，他所實作的功能僅僅就是申請空間和釋放空間，并不會呼叫相關的建構式進行初始化作業，

當無法滿足所要求分配的空間時，則

1. 如果有new_handler，則呼叫new_handler

2. 如果沒要求不拋出例外（以nothrow引數表達），則執行bad_alloc例外，否則回傳0

operator new就像operator ++一樣，是可以多載的，但是如果類中沒有多載operator new，那么呼叫的就是全域的::operator new來完成堆的分配

• placement new

當我們使用operator new來申請到堆中的空間時，這個時候所申請的空間中的資料型別就是我們申請時的指定資料型別，

但是如果我們想要把這個已經申請的空間，變成存盤另外一種資料型別的時候，就需要使用placement new，來對這個空間的資料型別進行重新分配，他允許我們在一個已經分配好的記憶體中（堆疊或者堆中）構造一個新的物件，

void *operator new( size_t, void * p ) throw() { return p; }

原型中void* p實際上就是指向一個已經分配好的記憶體緩沖區的的首地址.

placement new只是operator new多載的一個版本，它并不分配記憶體，只是回傳指向已經分配好的某段記憶體的一個指標，對這片空間我們還是需要進行手動析構的，否則就會造成記憶體泄漏

源程式

#include <new>      // placement new
#include <cstddef>  // ptrdiff_t size_t
#include <cstdlib>  // exit
#include <climits>  // UINT_MAX
#include <iostream> // cerr

namespace dcl
{
    // 分配記憶體
    template<class T>
    inline T* _allocate(ptrdiff_t size, T*) {
        std::set_new_handler(0);
        T* tmp = (T*)(::operator new((size_t)(size * sizeof(T))));
        if(tmp == 0) {
            std::cout<< "out of memory " << std::endl;
            exit(1);
        }
        return tmp;
    }

    // 釋放記憶體
    template<class T>
    inline void _deallocate(T* buffer) {
        ::operator delete(buffer);
    }

    // 以申請的記憶體中重新構造 T1物件
    template<class T1,class T2>
    inline void _construct(T1* p, const T2& value) {
        new(p) T1(value);
    }

    // placement new 物件的析構
    template<class T>
    inline void _destroy(T* ptr) {
        ptr->~T();
    }

    template <class T>
    class allocator {
    public:
        typedef     T           value_type;
        typedef     T*          pointer;
        typedef     const T*    const_pointer;
        typedef     T&          reference;
        typedef     const T&    const_reference;
        typedef     size_t      size_type;
        typedef     ptrdiff_t   difference_type;

        template <class U>
        struct rebind {
            typedef allocator<U>    other;
        };

        // 申請 n 個 pointer型別的空間
        pointer allocate(size_type n,const void* hint = 0) {
            return _allocate((difference_type)n, (pointer)0);
        }

        // new 空間的析構
        void deallocate(pointer ptr, size_type n) {
            _deallocate(ptr);
        }

        // 已經new 的空間重新分配
        void construct(pointer ptr, const T& value) {
            _construct(ptr, value);
        }

        // 銷毀重新分配的空間
        void destory(pointer p) {
            _destroy(p);
        }

        // 得到指標變數
        pointer address(reference x) {
            return (pointer)&x;
        }
        
        // const 指標變數
        const_pointer const_address(reference x) {
            return (const_pointer)&x;
        }

        // 得到最大可以開辟的空間數
        size_type max_size() const {
            return size_type(UINT_MAX / sizeof(T));
        }
    };
}

測驗結果：

但是在STL原始碼剖析中，有這個空間配置器只能有限的搭配PJ STL和RW STL，而完全無法應用于SGI STL

首先最大的一個不同之處就在于寫法的不同，我們的空間配置器中，對于vector容器的第二個引數是這樣描述的

vector<int, std::allocator<int> >

但是，SGI STL中必須這樣來

vector<int, std::alloc>

std::alloc

class Foo { ... };
Foo* pf = new Foo;		// 配置記憶體，然后析構物件
delete pf;				// 析構物件，然后釋放記憶體

STL中為了分工明確，將這兩個階段的操作區分開，所以將記憶體的配置交給了alloc::allocate()，記憶體的釋放交給了alloc::deallocate()，物件的構造交給了::construct()，物件的析構操作由::destory()負責

而這兩種操作所對應的頭檔案也不同：

#include <stl_alloc.h>		// 空間的配置和釋放
#include <stl_construct>	// 物件內容的構造和析構

空間的構造和析構

空間的構造與析構的基本工具便是construct()和destory()

對于建構式，STL中直接使用placement new，分工明確，只是對已經分配好的空間，進行重新構造

但是對于解構式，實際上除了一個指標變數的引數外，還有其他的函式多載，對于一些特殊的情況，進行了特化

進行特化的原因

如果我們申請了一塊特別大的空間，但是空間中物件的解構式都是trivial destructor，也就是無關痛癢的解構式，那么不停的呼叫每個物件的解構式就會浪費很大的性能，所以說就需要進行特化判斷

trivial destructor 與 non-trivial destructor

如果用戶不定義解構式，而是用系統自帶的，則說明，解構式基本沒有什么用（但默認會被呼叫）我們稱之為trivial destructor，
反之，如果特定定義了解構式，則說明需要在釋放空間之前做一些事情，則這個解構式稱為non-trivial destructor，
如果某個類中只有基本型別的話是沒有必要呼叫解構式的，delelte p的時候基本不會產生析構代碼

而如何判斷一個物件，是否定義了解構式，則使用了一種萃取的機制，主要就是利用了函式模板的思想，在定義型別的同時得到想要的型別，

在這一步中，首先利用value_type()獲得迭代器所指物件的型別，再利用__type_traits<T>來判斷解構式是否無關痛癢，如果是，那就什么也不干；不是，則需要回圈呼叫來完成物件的析構作業，

然后在分別呼叫對應的操作，

空間的配置與釋放

SGI對于物件的析構，還有這么一套設計哲學，，，

1. 向system heap 申請空間，（堆中申請空間）
2. 考慮多執行緒狀態
3. 考慮記憶體不足時的應變措施
4. 考慮小型區塊造成的記憶體碎片問題

而在C++中，我們一般對記憶體的操作便是：::operator new() 和 ::operator delete()，相當于在C語言中的malloc()和free()，

對此，由于考慮到了記憶體破碎的問題，SGI設定了雙層級配置器，

但是我們在使用的程序中，好像vector容器的第二個默認的預設值只是alloc，并沒有具體說明是哪一級的配置器，使用的是哪一級的配置器我們是感受不到的，但是實際是這樣的

這分別為第一級配接器與第二級配接器，所以說，alloc是不接受任何引數的，這也是為什么我們之前的簡單的配置器完全不支持SGI的原因