allocator::value_type

    allocator::pointer

    allocator::const_pointer

    allocator::reference

    allocator::const_reference

    allocator::size_type

    allocator::difference_type

const_pointer allocator::address(const_reference x) const

    2.1.1 设计一个简单的空间配置器

    //file: 2jjalloc.h

    #ifndef _JJALLOC_

    #define _JJALLOC_

    #include <cstddef>    //for ptrdiff_t,size_t

    namespace JJ

    {

        template <class T>

        inline T* _allocate(ptrdiff_t  size,T*)

        {

            set_new_handle(0);//当new失败时，呼叫该函数所设的参数

            T* tmp=(T*)(::operator new((size_t)(size*sizeof(T))));

        if (tmp==0)

            {

                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);

        }

        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);}

        pointer address(reference x) {return (pointer)&x;}

       const_pointer const_address(const_reference x) {return (const_pointer)&x;}

        size_type max_size() const

            {return size_type(UINT_MAX/sizeof(T));}

        }

    }

2.2 具备次配置能力（sub allocation）的SGI空间配置器

     SGI STL的配置器与众不同，与标准规范不同，其名称为alloc，而非allocator，并且不接收任何引数（所谓引数，即是template<T>中的T）,换句话说，既不能使用标准写法：

        vector<int,std::allocator<int>>iv;        //in VC

    必须这么写：

        vector<int,std::alloc> iv;

     2.2.1 SGI标准的空间配置器，std::allocator

        虽然SGI也定义了一个符合部分标准的allocator,但SGI从未用过它，也不主张我们使用。

         其实现和我们上面所列的code类似

    2.2.2 SGI特殊的空间配置器，std::alloc

    2.2.3 建模和解构的基本工具：construct()和destroy()

typename语法

#ifndef __SGI_STL_INTERNAL_CONSTRUCT_H#define __SGI_STL_INTERNAL_CONSTRUCT_H#include <new.h>__STL_BEGIN_NAMESPACEtemplate <class T>inline void destroy(T* pointer) {    pointer->~T();}template <class T1, class T2>inline void construct(T1* p, const T2& value) {new (p) T1(value);}template <class ForwardIterator>inline void__destroy_aux(ForwardIterator first, ForwardIterator last, __false_type) {    for ( ; first < last; ++first)    destroy(&*first);}template <class ForwardIterator> inline void __destroy_aux(ForwardIterator, ForwardIterator, __true_type) {}template <class ForwardIterator, class T>inline void __destroy(ForwardIterator first, ForwardIterator last, T*) {typedef typename __type_traits<T>::has_trivial_destructor trivial_destructor;__destroy_aux(first, last, trivial_destructor());}template <class ForwardIterator>inline void destroy(ForwardIterator first, ForwardIterator last) {__destroy(first, last, value_type(first));}inline void destroy(char*, char*) {}inline void destroy(wchar_t*, wchar_t*) {}__STL_END_NAMESPACE#endif

    之所以需要增加trivial_destructor的特化是因为如果该类别的析构无关痛痒,反复的循环调用是很耗费效率的.

    特化后,如为true_type，则什么都不做

    2.2.4 空间的配置与释放，std::alloc

    2.2.5 第一级配置器 __malloc_alloc_template剖析

template <int inst>class __malloc_alloc_template {private:    //以下为几个函数指针        static void *oom_malloc(size_t);    //OOM=out of memory    static void *oom_realloc(void *, size_t);    #ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG       static void (* __malloc_alloc_oom_handler)();    #endifpublic://SGI STL并没有使用Set_new_hanlde的机制，因为它并没有使用new的方法，而是把两步分解开来执行。    static void * allocate(size_t n)    {        void *result = malloc(n);        if (0 == result) result = oom_malloc(n);        return result;    }    static void deallocate(void *p, size_t /* n */)    {        free(p);    }    static void * reallocate(void *p, size_t /* old_sz */, size_t new_sz)    {        void * result = realloc(p, new_sz);        if (0 == result) result = 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_BUGtemplate <int inst>    void (* __malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = 0;#endiftemplate <int inst>void * __malloc_alloc_template<inst>::oom_malloc(size_t n){    void (* my_malloc_handler)();    void *result;

 //不断的循环尝试释放，分配，期望在一次中得到正确处理    for (;;)

  {        my_malloc_handler = __malloc_alloc_oom_handler;        if (0 == my_malloc_handler) { __THROW_BAD_ALLOC; }        (*my_malloc_handler)();        result = malloc(n);        if (result) return(result);    }}template <int inst>void * __malloc_alloc_template<inst>::oom_realloc(void *p, size_t n){    void (* my_malloc_handler)();    void *result;    for (;;) {        my_malloc_handler = __malloc_alloc_oom_handler;        if (0 == my_malloc_handler) { __THROW_BAD_ALLOC; }        (*my_malloc_handler)();        result = realloc(p, n);        if (result) return(result);    }}typedef __malloc_alloc_template<0> malloc_alloc;

    Reference:

    1.Effective C++ 2nd   条款7：为内存不足的状况预做准备 025                    Be prepared for out-of-memory conditions.

    2.Memory Pool(内存池)

    2.2.6 第二级配置器 __default_alloc_template剖析

        我们知道，如果反复的分配一小块内存，然后释放，会造成很多的碎片。

         因此，第二级配置器对此做出了调整，如果分配的区块够大（大于128byte）,这直接移交第一级配置器处理。

            如果小于，则使用内存池（memory pool，又称记忆池）管理，此法也称为次层配置（sub-allocation）。

            其方法为：

            1.每次配置一大块记忆体，并维护与之对应的free-lists(自由串列)。

            2.若下次，再有相同大小的内存分配需求，则直接再此free-lists上分配。

            3.如果客户端释放，则由配置器回收到free-lists中.---别忘了，配置器不光负责分配，而且负责回收

            4.为了方便管理，SGI第二级分配器要求每次分配的为8的倍数

template <bool threads, int inst>class __default_alloc_template { private:    enum {__ALIGN = 8};    //小型区块的最小边界    enum {__MAX_BYTES = 128};    //小型区块的上限    enum {__NFREELISTS = __MAX_BYTES/__ALIGN};//free-lists个数    

    static size_t ROUND_UP(size_t bytes) 

    {return (((bytes) + __ALIGN-1) & ~(__ALIGN - 1));    //好的方法，比(bytes+_ALIGN-1)*_ALIGN/_ALIGN 效率高}

PRIVATE:    union obj

   {        union obj * free_list_link;            char client_data[1]; /* The client sees this. */    };        //妙哉！为了维护串列，需要额外开销指针的空间。

       //但使用Union就可以做到节省空间的一物两用private:    static obj * __VOLATILE free_list[]; 

    static size_t FREELIST_INDEX(size_t bytes) //根据区块的大小，决定使用第几个free-lists    {        return (((bytes) + __ALIGN-1)/__ALIGN - 1);    }    // Returns an object of size n, and optionally adds to size n free list.    static void *refill(size_t n);

    // Allocates a chunk for nobjs of size "size". nobjs may be reduced    // if it is inconvenient to allocate the requested number.    static char *chunk_alloc(size_t size, int &nobjs);    // Chunk allocation state.    static char *start_free;//记忆池起始位置，只在chunk_alloc中变化    static char *end_free;//记忆池结束位置，只在chunk_alloc中变化    static size_t heap_size;

public:

    static void * allocate(size_t n);

    static void deallocate(void *p, size_t n);

    static void * reallocate(void *p, size_t old_sz, size_t new_sz);

}

//以下几个static变量的定义

template <bool threads, int inst>char *__default_alloc_template<threads, inst>::start_free = 0;template <bool threads, int inst>char *__default_alloc_template<threads, inst>::end_free = 0;template <bool threads, int inst>size_t __default_alloc_template<threads, inst>::heap_size = 0;template <bool threads, int inst>__default_alloc_template<threads, inst>::obj * __VOLATILE        __default_alloc_template<threads, inst> ::free_list[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };

    2.2.7 空间配置函数allocate()

如果大于128,扔给第一级分配器

/* n must be > 0 */static void * allocate(size_t n){    obj * __VOLATILE * my_free_list;    obj * __RESTRICT result;    if (n > (size_t) __MAX_BYTES) 

  {        return(malloc_alloc::allocate(n));    }    my_free_list = free_list + FREELIST_INDEX(n);

  result = *my_free_list;    if (result == 0)

   {        void *r = refill(ROUND_UP(n));        return r;    }    *my_free_list = result -> free_list_link;    return (result);};

    2.2.8 空间释放函数deallocate()

如果大于128,扔给第一级分配器

 /* p may not be 0 */static void deallocate(void *p, size_t n){    obj *q = (obj *)p;    obj * __VOLATILE * my_free_list;    if (n > (size_t) __MAX_BYTES) 

  {        malloc_alloc::deallocate(p, n);        return;    }    my_free_list = free_list + FREELIST_INDEX(n);    q -> free_list_link = *my_free_list;    *my_free_list = q;}

    2.2.9 重新填充free-lists

        使用chunk_alloc分配空间，默认分配20个。如记忆体空间不足，可能个数比这个少。

/* 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 <bool threads, int inst>void* __default_alloc_template<threads, inst>::refill(size_t n){    int nobjs = 20;    char * chunk = chunk_alloc(n, nobjs);    obj * __VOLATILE * my_free_list;    obj * result;    obj * current_obj, * next_obj;    int i;    if (1 == nobjs) return(chunk);   //如果只分配了一个，可以直接返回    my_free_list = free_list + FREELIST_INDEX(n);    /* Build free list in chunk */    result = (obj *)chunk;    *my_free_list = next_obj = (obj *)(chunk + n);    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);}

    2.2.10 记忆池（memory pool）

        虽然S

/* 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. */

//注意nobjs为Reference型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;    //需要分配的大小    size_t bytes_left = end_free - start_free; //目前遗留的大小    if (bytes_left >= total_bytes) //如果能够满足，直接分配，返回

    {        result = start_free;        start_free += total_bytes;        return(result);    } 

  else if (bytes_left >= size) //如果大于一个的大小，则能分配几个，就分配几个

  {        nobjs = bytes_left/size;        total_bytes = size * nobjs;        result = start_free;        start_free += total_bytes;        return(result);    } 

  else //如果一个都不够了

  {

        // Try to make use of the left-over piece.        if (bytes_left > 0) //如果原有的还有一些剩余的空间，先把它分配出去

    {            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;        }

     //准备重新分配20+n的大小，n的大小取决于不断变化的heap_size        size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);//这句话，原文放在if(bytes_left>0)之前        start_free = (char *)malloc(bytes_to_get);//调用malloc分配20+n的空间

        if (0 == start_free) //如果非常的不幸，分配失败了，内存空间不够

    {            int i;            obj * __VOLATILE * my_free_list, *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 <= __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;//start_free,end_free，抓一个大小。                    end_free = start_free + i;                    return(chunk_alloc(size, nobjs));//重新调用分配                    // Any leftover piece will eventually make it to the                    // right free list.                }            }

        //苍天呀，大地啊！一个都没有了，山穷水尽。呼叫第一层的alllocate，

     //它和直接呼叫allocate的做法唯一的不同在于拥有exception的处理

     //期望着Exception能够解决我们的问题            end_free = 0; // In case of exception.            start_free = (char *)malloc_alloc::allocate(bytes_to_get);            // This should either throw an            // exception or remedy the situation. Thus we assume it            // succeeded.        }        heap_size += bytes_to_get;    //重新设定堆的大小        end_free = start_free + bytes_to_get;//设定分配空间的大小        return(chunk_alloc(size, nobjs));//根据设定过的值，重新呼叫自身    }}

实例操作，第一次chunk_alloc(32,20),分配了40+n个，一个返回。19个给free_list[3]控制，剩下的20+n给记忆池

第二次chunk_alloc(64,20),此时不够20个，分配给其10个，然后返回一个，9个由free_list[7]控制。记忆池空了

第三次chunk_alloc(96,20),呼叫重新分配新空间

2.3 记忆体基本处理工具

    作用于非初始化空间上的函数，除了以上介绍过的construct()和destroy()，下面介绍的是另外的三个。

    分别对应于STL的算法copy(),fill(),fill_n()

    三者都是Commit or Roll-back，意即如果成功就全部分配，否则一个都不成功

    2.3.1 uninitialized_copy

template <class InputIterator, class ForwardIterator>inline ForwardIterator __uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator result)

   2.3.2 uninitialized_fill

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

   2.3.3 uninitialize_fill_n

template <class ForwardIterator, class Size, class T>inline ForwardIterator uninitialized_fill_n(ForwardIterator first, Size n,const T& x)

　（1）uninitialize_fill_n实做

        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));//利用value_type，取出first的所指型别                }

                        |

                        |

                        //

        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型别            }

        所谓POD型别，plain old data.也就是指纯量型别（scalar types）或传统的C struct型别。

     POD型别，必然拥有trival ctor/dtor/copy/assignment函数。

     因此，我们可以对POD类型采取最有效的初值填写方法

     而对non-POD类型需采取最安全的做法

                        |

                        |

                        //

// Valid if copy construction is equivalent to assignment, and if the// destructor is trivial.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);}

template <class ForwardIterator, class Size, class T>ForwardIterator __uninitialized_fill_n_aux(ForwardIterator first, Size n,const T& x, __false_type) 

{    ForwardIterator cur = first;    for ( ; n > 0; --n, ++cur)         construct(&*cur, x);//调用constuct，初始化cur中的内容为x    return cur;}

  （2）uninitialized_copy实做

    template <class InputIterator, class ForwardIterator>        inline ForwardIterator uninitialized_copy(InputIterator first, InputIterator last,ForwardIterator result) 

    {            return __uninitialized_copy(first, last, result, value_type(result));        }

    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());        }

template <class InputIterator, class ForwardIterator>inline ForwardIterator  __uninitialized_copy_aux(InputIterator first, InputIterator last,ForwardIterator result,__true_type) 

{    return copy(first, last, result);}template <class InputIterator, class ForwardIterator>ForwardIterator __uninitialized_copy_aux(InputIterator first, InputIterator last,ForwardIterator result,__false_type) 

{    ForwardIterator cur = result;   for ( ; first != last; ++first, ++cur)       construct(&*cur, *first);    return cur;}

对于char*和wchar_t*，可以使用最有效的memmove办法

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);}

   (3)uninitialized_fill实做

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

    {            __uninitialized_fill(first, last, x, value_type(first));        }

     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());        }    

        template <class ForwardIterator, class T>        inline void __uninitialized_fill_aux(ForwardIterator first, ForwardIterator last, const T& x, __true_type)        {            fill(first, last, x);        }

    template <class ForwardIterator, class T>       void __uninitialized_fill_aux(ForwardIterator first, ForwardIterator last, const T& x, __false_type)     {        ForwardIterator cur = first;        for ( ; cur != last; ++cur)            construct(&*cur, x);     }

    所有的Non-Pod函数的false_type都是非inline的

一、MSDN:C++ Specific —>

typename identifier;

Use this keyword only in template definitions. This keyword tells the compiler that an unknown identifier is a type. For example:

This keyword can also be used in place of class in template parameter lists. For example, the following statements are identical:

二、