126.STL 之 空间配置器（allocator）

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

SGI也定义了一个符合部分标准，名为allocator的配置器，但是它自己不使用，也不建议我们使用，主要原因是效率不佳。

它只是把C++的操作符::operator new和::operator delete做了一层简单的封装而已。

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

由于SGI 标准的空间配置器只是把C++的操作符::operator new和::operator delete做了一层简单的封装，没有考虑到任何效率上的强化。

所以 SGI 出现了一个特殊的空间配置器，供 STL标准模板库使用。

通常，C++中用new操作符来分配内存都包括两个阶段：

（1）调用::operator new配置内存

（2）调用构造函数来构造对象内容

同理，delete操作也包括两个阶段：

（1）调用析构函数将对象析构

（2）调用::operator delete释放内存

为了精密分工，SGI STL allocator将两个阶段分开：

内存配置操作由alloc:allocate负责，内存释放由alloc:deallocate负责；对象构造操作由::contructor()负责，对象析构由::destroy()负责。

配置器定义在头文件<memory>中，它里面又包括两个文件：

#include <stl_alloc.h>        // 负责内存空间的配置和器释放  
#include <stl_construct.h>        // 负责对象的构造和析构  

3.STL 空间配置器：

3.1STL 空间配置器解决的问题

1.内存碎片问题（外碎片）

内碎片：操作系统在分配给申请者未被利用的部分。产生原因：内存对齐（效率高）；

外碎片：内存充足时但分配不出大块内存。产生原因：由于多次分配小块内存，将大块内存分割成小块；

2.频繁系统分配，释放小块内存，调用 malloc，delete 系统调用产生性能问题；

STL 空间配置器的实现机制：

3.2双层级的配置器

注：

当需要开辟的空间大于 128 bytes 时，视为“足够大”，调用一级配置器，直接调用 malloc，free；

当需要开辟的空间小于 128 bytes 时，视为“过小”，为了降低额外负担，调用二级空间配置器

A.一级空间配置器

//以下是第第一级配置器
template <int inst>
class __malloc_alloc_template 
{

private:
    //以下函数用来处理内存不足的情况
    static void* oom_malloc(size_t);
    static void* oom_realloc(void*, size_t);
    static void (*__malloc_alloc_oom_handler)();

public:

    static void* allocate(size_t n)
    {
        void* result = malloc(n);                    //第一级配置器，直接使用malloc()
        //如果内存不足，则调用内存不足处理函数oom_alloc()来申请内存
        if (0 == result) result = oom_malloc(n);
        return result;
    }

    static void deallocate(void* p, size_t /* n */)
    {
        free(p);            //第一级配置器直接使用 free()
    }

    static void* reallocate(void* p, size_t /* old_sz */, size_t new_sz)
    {
        void* result = realloc(p, new_sz);            //第一级配置器直接使用realloc()
        //当内存不足时，则调用内存不足处理函数oom_realloc()来申请内存
        if (0 == result) result = oom_realloc(p, new_sz);
        return result;
    }

    //设置自定义的out-of-memory handle就像set_new_handle()函数
    static void (*set_malloc_handler(void (*f)()))()
    {
        void (*old)() = __malloc_alloc_oom_handler;
        __malloc_alloc_oom_handler = f;
        return(old);
    }
};

template <int inst>
void (*__malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = 0;　　//内存处理函数指针为空，等待客户端赋值

template <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;            //设定自己的oom(out of memory)处理函数
        if (0 == my_malloc_handler) { __THROW_BAD_ALLOC; }         //如果没有设定自己的oom处理函数，毫不客气的抛出异常
        (*my_malloc_handler)();                                    //设定了就调用oom处理函数
        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; }    //如果自己没有定义oom处理函数，则编译器毫不客气的抛出异常
        (*my_malloc_handler)();                                //执行自定义的oom处理函数
        result = realloc(p, n);                                //重新分配空间
        if (result) return(result);                            //如果分配到了，返回指向内存的指针
    }
}

上面代码看似繁杂，其实流程是这样的：

1.我们通过allocate()申请内存，通过deallocate()来释放内存，通过reallocate()重新分配内存。

2.当allocate()或reallocate()分配内存不足时会调用oom_malloc()或oom_remalloc()来处理。

3.当oom_malloc() 或 oom_remalloc()还是没能分配到申请的内存时，会转如下两步中的一步：

(a)调用用户自定义的内存分配不足处理函数(这个函数通过set_malloc_handler() 来设定)，然后继续申请内存！

(b)如果用户未定义内存分配不足处理函数，程序就会抛出bad_alloc异常或利用exit(1)终止程序。

看完这个流程，再看看上面的代码就会容易理解多了！

B.二级配置器 _ _default_alloc_template

第二级配置器的代码很多，这里我们只贴出其中的 allocate() 和 dellocate()函数的实现和工作流程(参考侯捷先生的《STL源码剖析》)，而在看函数实现代码之前，我大致的描述一下第二层配置器配置内存的机制。

我们之前说过，当申请的内存大于 128 bytes时就调用第一层配置器。当申请的内存小于 128bytes时才会调用第二层配置器。第二层配置器如何维护128bytes一下内存的配置呢？ SGI 第二层配置器定义了一个 free-lists，这个free-list是一个数组，如下图：

这数组的元素都是指针，用来指向16个链表的表头。这16个链表上面挂的都是可以用的内存块。只是不同链表中元素的内存块大小不一样，16个链表上分别挂着大小为8,16,24,32,40,48,56,64,72,80,88,96,104,112,120,128 bytes的小额区块，图如下：

就是这样，现在我们来看allocate()代码：

static void* allocate(size_t n)
{
    obj* __VOLATILE* my_free_list;
    obj* __RESTRICT result;

    //要申请的空间大于128bytes就调用第一级配置
    if (n > (size_t)__MAX_BYTES) 
    {
        return(malloc_alloc::allocate(n));
    }
    //寻找 16 个free lists中恰当的一个
    my_free_list = free_list + FREELIST_INDEX(n);
    result = *my_free_list;
    if (result == 0)
    {
        //没找到可用的free list，准备新填充free list
        void* r = refill(ROUND_UP(n));
        return r;
    }
    *my_free_list = result->free_list_link;
    return (result);
};

其中有两个函数我来提一下，一个是ROUND_UP()，这个是将要申请的内存字节数上调为8的倍数。因为我们free-lists中挂的内存块大小都是8的倍数嘛，这样才知道应该去找哪一个链表。另一个就是refill()。这个是在没找到可用的free list的时候调用，准备填充free lists。意思是：参考上图，假设我现在要申请大小为 56bytes 的内存空间，那么就会到free lists 的第 7 个元素所指的链表上去找。如果此时 #6元素所指的链表为空怎么办？这个时候就要调用refill()函数向内存池申请N(一般为20个)个大小为56bytes的内存区块，然后挂到 #6 所指的链表上。这样，申请者就可以得到内存块了。当然，这里为了避免复杂，误导读者我就不讨论refill()函数了。allocate()过程图如下：

学过链表的操作的人不难理解上图，我就不再讲解。下面看deallocate()，代码如下：

static void deallocate(void* p, size_t n)
{
    obj* q = (obj*)p;
    obj* __VOLATILE* my_free_list;

    //如果要释放的字节数大于128，则调第一级配置器
    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;
}

deallocate()函数释放内存的步骤如下图：

其实这就是一个链表的插入操作，也很简单。不再赘述！上面忘了给链表结点的结构体定义了，如下：

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

4.标准库allocator类及其算法

#include <iostream>
#include <memory>

using namespace std;

class Example
{
public:
    Example() 
    {
        cout << "Example default constructor..." << endl;
    }
    Example(int x) : a(x) 
    {
        cout << "Example constructor..." << endl;
    }
    ~Example() 
    {
        cout << "Example destructor..." << endl;
    }
    int a = 0;
};

int main() 
{
    allocator<Example> alloc;

    // 使用allocate函数分配一块能够存放5个Example对象的内存空间
    Example* p = alloc.allocate(5);

    // 使用construct函数在第一个位置构造一个Example对象
    alloc.construct(p, 1);

    // 使用construct函数在第二个位置构造一个Example对象
    alloc.construct(p + 1, 2);

    // 使用destroy函数销毁第一个位置的Example对象
    alloc.destroy(p);

    // 使用deallocate函数释放分配的内存空间
    alloc.deallocate(p, 5);

    return 0;
}

输出：

Example constructor...
Example constructor...
Example destructor...

在这个例子中，我们首先创建了一个名为alloc的allocator对象，用于分配Example对象所需的内存。

然后，我们使用alloc.allocate(5)函数分配了一块能够存放5个Example对象的内存空间，并将返回的指针赋值给指针变量p。

接下来，我们使用alloc.construct()函数在刚刚分配的内存空间中构造了两个Example对象。第一个对象使用带参数的构造函数进行构造，并将参数值设置为1；第二个对象也使用带参数的构造函数进行构造，并将参数值设置为2。

然后，我们使用alloc.destroy()函数销毁了第一个位置的Example对象。最后，我们使用alloc.deallocate()函数释放了分配的内存空间。

需要注意的是，在使用allocator类进行内存分配和对象构造时，必须使用alloc.construct()函数来显式地调用构造函数进行对象的构造，并使用alloc.destroy()函数来显式地调用析构函数进行对象的销毁。

参考：STL 之 空间配置器（allocator）

浅析STL allocator

本栏目推荐文章
• 【C语言】动态内存申请，堆空间与栈空间差异
• String 类和 STL (Standard Template Library)
• PostgreSQL从小白到高手教程 - 第41讲：postgres表空间备份与恢复
• ROS2 删除一个工作空间文件夹，source后终端出现not found ...... local_setup.bash解决
• 1虚拟地址空间与堆栈调用
• XAML x 名称空间的介绍
• 【五期李伟平】CCF-A（MobiCom'18 Session EdgeTech'18）A Game-Theoretic Approach to Multi-Objective Resource Sharing and Allocation in Mobile Edge Clouds
• R语言用LOESS(局部加权回归)季节趋势分解（STL）进行时间序列异常检测
• 磁盘空间不足|删除文件后空间不释放
• docker磁盘空间清理

allocator 空间 126 STLallocator空间126 stl 分配器allocator stl 元素vector空间stl 126 126c 126e 126d 126f 客户端 邮箱 客户126 affine 126f sort arc