STL allocator是做什么用？

在學(xué)習(xí)STL中containers會(huì)發(fā)現(xiàn)C++ STL里定義了很多的容器（containers），每一個(gè)容器的第二個(gè)模板參數(shù)都是allocator類型，而且默認(rèn)參數(shù)都是allocator。但是allocator到底是什么？有什么作用呢？

有關(guān)allocator的最重要的事實(shí)是它們只是為了一個(gè)目的：封裝STL容器在內(nèi)存管理上的低層細(xì)節(jié)。你不應(yīng)該在自己的代碼中直接調(diào)用 allocator 的成員函數(shù)，除非正在寫(xiě)一個(gè)自己的STL容器。你不應(yīng)該試圖使用allocator來(lái)實(shí)現(xiàn)operator new[]；這不是allocator該做的。 如果你不確定是否需要使用allocator，那就不要用。

基本上很少有人會(huì)自定義一個(gè)allocator。一來(lái)，默認(rèn)的allocator已經(jīng)夠用了；二來(lái)，確實(shí)不知道該怎么用。一般來(lái)說(shuō)，我們沒(méi)有必要重新定義一個(gè)allocator。自定義的方式主要是為了提高內(nèi)存分配相關(guān)操作的性能。而STL提供的方式性能已經(jīng)足夠好了。

淺析STL allocator

一般而言，我們習(xí)慣的 C++ 內(nèi)存配置操作和釋放操作是這樣的：

class FOO{};
FOO *pf = new FOO;    
delete pf;

我們看其中第二行和第三行，雖然都是只有一句，但是都完成了兩個(gè)動(dòng)作。但你 new 一個(gè)對(duì)象的時(shí)候兩個(gè)動(dòng)作是：先調(diào)用::operator new 分配一個(gè)對(duì)象大小的內(nèi)存，然后在這個(gè)內(nèi)存上調(diào)用FOO::FOO()構(gòu)造對(duì)象。同樣，當(dāng)你 delete 一個(gè)對(duì)象的時(shí)候兩個(gè)動(dòng)作是：先調(diào)用FOO::~FOO() 析構(gòu)掉對(duì)象，再調(diào)用::operator delete將對(duì)象所處的內(nèi)存釋放。為了精密分工，STL 將allocator決定將這兩個(gè)階段分開(kāi)。分別用 4 個(gè)函數(shù)來(lái)實(shí)現(xiàn)：

1.內(nèi)存的配置：alloc::allocate();

2.對(duì)象的構(gòu)造：::construct();

3.對(duì)象的析構(gòu)：::destroy();

4.內(nèi)存的釋放：alloc::deallocate();

stl_alloc.h中代碼設(shè)計(jì)的原則如下：

1.向 system heap 要求空間

2.考慮多線程狀態(tài)

3.考慮內(nèi)存不足時(shí)的應(yīng)變措施

4.考慮過(guò)多“小型區(qū)塊”可能造成的內(nèi)存碎片問(wèn)題。

stl_alloc.h中的代碼相當(dāng)復(fù)雜，我們今天只看其中的配置器的工作原理：

考慮到小型區(qū)塊可能造成內(nèi)存破碎問(wèn)題(即形成內(nèi)存碎片)，SGI STL 設(shè)計(jì)了雙層級(jí)配置器。第一層配置器直接使用malloc() 和 free()。第二層配置器則視情況采用不同的策略：當(dāng)配置區(qū)塊超過(guò) 128 bytes時(shí)，調(diào)用第一級(jí)配置器。當(dāng)配置區(qū)塊小于 128 bytes時(shí)，采用復(fù)雜的 memory pool 方式，需要小的堆在小的存儲(chǔ)塊的鏈表上取，需要大的堆在大的存儲(chǔ)塊的鏈表上取，某個(gè)大小存儲(chǔ)塊鏈表預(yù)留個(gè)數(shù)用完后從系統(tǒng)繼續(xù)申請(qǐng)。

圖1 memory pool配置方式

STL 簡(jiǎn)單 allocator 的實(shí)現(xiàn)

其中用到的小知識(shí)：

1.ptrdirr_t：

ptrdiff_t是C/C++標(biāo)準(zhǔn)庫(kù)中定義的一個(gè)與機(jī)器相關(guān)的數(shù)據(jù)類型。ptrdiff_t類型變量通常用來(lái)保存兩個(gè)指針減法操作的結(jié)果。ptrdiff_t定義在stddef.h（cstddef）這個(gè)文件內(nèi)。ptrdiff_t通常被定義為long int類型。

2.non-trivial constructor/destructor：

意思是“非默認(rèn)構(gòu)造函數(shù)/析構(gòu)函數(shù)”，這里的non-trivial指不是編譯器自動(dòng)生成的（函數(shù)）維基百科

我認(rèn)為trivial更深層次的含義是構(gòu)造和析構(gòu)的東西都是在棧上分配的，其內(nèi)存可以被棧自動(dòng)回收，所以SGI STL的空間配置器std::alloc在做destroy時(shí)會(huì)先判斷析構(gòu)對(duì)像是不是trivial，如果對(duì)象是trivial，證明對(duì)象的所有成員分配在棧上，那么為了節(jié)省效率，可以不調(diào)用析構(gòu)函數(shù)，由棧來(lái)自動(dòng)回收內(nèi)存。如果對(duì)象是non-trivial則需要調(diào)用每個(gè)對(duì)象的析構(gòu)函數(shù)，釋放堆上分配的內(nèi)存。

3.operator new()：

指對(duì)new的重載形式，它是一個(gè)函數(shù)，并不是運(yùn)算符。對(duì)于operator new來(lái)說(shuō)，分為全局重載和類重載，全局重載是void* ::operator new(size_t size)，在類中重載形式 void* A::operator new(size_t size)。還要注意的是這里的operator new()完成的操作一般只是分配內(nèi)存，事實(shí)上系統(tǒng)默認(rèn)的全局::operator new(size_t size)也只是調(diào)用malloc分配內(nèi)存，并且返回一個(gè)void*指針。而構(gòu)造函數(shù)的調(diào)用(如果需要)是在new運(yùn)算符中完成的。

4.由第三點(diǎn)可知，在空間配置器的new操作分為兩步：allocate()函數(shù)分配內(nèi)存，construct()函數(shù)把分配的內(nèi)存初始化為一個(gè)個(gè)的模板類對(duì)象。

侯捷老師的書(shū)中介紹了空間配置器基本的接口（p43~44）。以下是一個(gè)簡(jiǎn)單的空間配置器實(shí)現(xiàn)。

cghAlloc.h：

#ifndef _CGH_ALLOC
#define _CGH_ALLOC
#include <new>
#include <cstddef>
#include <cstdlib>
#include <climits>
#include <iostream>
using namespace std;

namespace CGH {
template<class T>
inline T* _allocate(ptrdiff_t size, T*) {
    set_new_handler(0);
    T* tmp = (T*) (::operator new((size_t) (size * sizeof(T)))); // size：待分配的元素量，sizeof(T)每個(gè)元素的大小
    if (tmp == 0) {
        cout << "out of memory" << endl;
        exit(1);
    }
    return tmp;
}
template<class T>
inline void _deallocate(T* buffer) {
    ::operator delete(buffer);
}
template<class T1, class T2>
inline void _construct(T1* p, const T2& value) {
    new (p) T1(value); // 調(diào)用placement new，在指定的內(nèi)存位置p處初始化T1對(duì)象，初始化T1對(duì)象時(shí)調(diào)用T1的復(fù)制構(gòu)造函數(shù)
}
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;
    };
    pointer allocate(size_type n, const void* hint = 0) {
        return _allocate((difference_type) n, (pointer) 0);
    }
    void deallocate(pointer p, size_type n) {
        _deallocate(p);
    }
    void construct(pointer p, const T& value) {
        _construct(p, value);
    }
    void destroy(pointer p) {
        _destroy(p);
    }
};
}

#endif

測(cè)試空間配置器，allocator.cpp：

// allocator.cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。
//
#include "stdafx.h"
#include "cghAlloc.h"
#include <vector>
#include <iostream>
using namespace::std;

int _tmain(int argc, _TCHAR* argv[])
{
    int arr[5] = { 0, 1, 2, 3, 4 };
    //unsigned int i;
    CGH::allocator<int> test;
    CGH::allocator<int> test1;
    vector<int, CGH::allocator<int>>iv(arr, arr + 5);
    for (int i = 0; i < iv.size(); i++){
        cout << iv[i] << ' ';
    }
    cout << endl;
    system("pause");
    return 0;
}