【STL】空间配置器||分配器（Allocators）

编程入门行业动态更新时间:2024-10-10 01:22:02

【STL】空间配置器||<a href=https://www.elefans.com/category/jswz/34/1752801.html style= 分配器（Allocators）"/>

【STL】空间配置器||分配器（Allocators）

一、概述

分配器主要负责空间配置与管理。从实现的角度来看，配置器是一个实现了动态空间配置、空间管理、空间释放的class template。从使用的角度来讲，它是隐藏在一切组件（容器）的背后，是最不需要了解的，但是STL的实现过程与分配器密切是相关的。

隐藏在这些容器后的内存管理工作是通过STL提供的一个默认的allocator实现的。当然，用户也可以定制自己的allocator，只要实现allocator模板所定义的接口方法即可，然后通过将自定义的allocator作为模板参数传递给STL容器。

但是不建议自己定义，因为大多数情况下，STL默认的allocator的安全性以及效率等就已经足够了。所以我们使用时，一般都会使用默认的配置器。如下：

template <class T, class Alloc = allocator<T> >
class vector {...
};vect<int> vec;	//这里只传入int类型，使用默认的空间配置器

下面的空间配置器是按照SGI 版本的STL进行讲解的，每一个编译器实现方式与手法可能各有不同，但是都是符合STL的标准规格的。

2、SGI中标准的空间配置器

提到内存分配和释放，首先就要谈一下 operator new 和 malloc 。具体可以参考前面整理的C/C++中的new和delete的实现过程。

在SGI中也定义了一个符合部分标准，名为allocator的配置器（在VC和CB编译器中，使用的是这种默认配置器），但很少使用。

主要原因是因为效率不佳，只是单纯的对C++中 ::operator new 和 ::operator delete 进行了简单的包装。

下面SGI的std::allocator的部分实现：

template <class T>
inline T* allocate(ptrdiff_t size, T*) {set_new_handler(0);T* tmp = (T*)(::operator new((size_t)(size * sizeof(T))));    //简单的调用 ::operator newif (tmp == 0) {cerr << "out of memory" << endl; exit(1);}return tmp;
}
template <class T>
inline void deallocate(T* buffer) {::operator delete(buffer);     //简单的调用 ::operator delete 
}
template <class T>
class allocator {
public:typedef T value_type;....pointer allocate(size_type n) { return ::allocate((difference_type)n, (pointer)0);}void deallocate(pointer p) { ::deallocate(p); }....
};

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

一般来说，我们所熟知的C++内存配置操作和释放操作是这样的：

class Foo {...};
Foo* pf = new Foo;	//配置内存，然后构造对象
delete pf;			//将对象析构，然后释放内存

这其中的

new 内含两个阶段操作：（1）调用operator new 配置内存。（2）调用构造函数，构造对象内容
delete也内含两个阶段操作：（1）调用析构函数。（2）调用operator delete 释放内存。

为了精密分工，STL 将这两个阶段操作区分开来。内存配置操作由成员函数 alloccate() 负责，内存释放由 deallcate() 负责；对象构造由 construct() 负责，对象析构则由 destroy() 负责。

SGI STL设计了由两级分配器构成的内存管理器，当申请的内存大小大于128byte时，就启动第一级分配器通过malloc直接向系统的堆空间分配，如果申请的内存大小小于128byte时，就启动第二级分配器，从一个预先分配好的内存池中取一块内存交付给用户，这个内存池由16个不同大小（8的倍数，8~128byte）的空闲列表组成，allocator会根据申请内存的大小（将这个大小round up成8的倍数）从对应的空闲块列表取表头块给用户。

这种做法有两个优点：

小对象的快速分配。小对象是从内存池分配的，这个内存池是系统调用一次malloc分配一块足够大的区域给程序备用，当内存池耗尽时再向系统申请一块新的区域，整个过程类似于批发和零售，起先是由allocator向总经商批发一定量的货物，然后零售给用户，与每次都向总经商要一个货物再零售给用户的过程相比，显然是快捷了。当然，这里的一个问题时，内存池会带来一些内存的浪费，比如当只需分配一个小对象时，为了这个小对象可能要申请一大块的内存池，但这个浪费还是值得的，况且这种情况在实际应用中也并不多见。
避免了内存碎片的生成。程序中的小对象的分配极易造成内存碎片，给操作系统的内存管理带来了很大压力，系统中碎片的增多不但会影响内存分配的速度，而且会极大地降低内存的利用率。以内存池组织小对象的内存，从系统的角度看，只是一大块内存池，看不到小对象内存的分配和释放。

4、第一级配置器

流程图如下：

SGI的第一级配置器以 malloc(), free(), realloc() 等C函数执行实际的内存配置、释放、重配置操作。当 malloc 或者 realloc 调用不成功后，改调用 oom_malloc() 和 oom_realloc() 。后两者都有内循环，不断调用“内存不足处理例程”，期望在某次调用之后，获得足够的内存。但如果“内存不足处理例程”未被客户端设定，则直接抛出 bad_alloc 异常，或者终止程序。

5、第二级配置器

二级配置器每次配置一大块内存，并维护一个自由链表（free-list）。下次如有相同大小的内存需求，就从 free-list 中拨出。欲释放区块，则由free-list进行回收。

为了方便管理，它是用一个16个元素的自由链表（free_list）来管理的，每个位置的内存大小都是8的倍数，分别为：8、16、24、32、40、48、56、64、72、80、88、96、104、112、120、128。

free-list节点结构：

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

其中，由于使用了union，使得一物两用，减少了维护链表所必须的指针而造成的浪费。

5.1、二级配置器内存分配

主要分为四种情况：

free_list列表中有空余内存。如果申请3个字节的内存，则所需空间大小提升为8的倍数，然后去 free_list 中查找相应的链表，如果 free_list[i] 不为空，则返回第一个元素，然后把头指针往后移。
free_list列表中没有空余，但内存池不为空。首先检验内存池中的大小是不是比申请的内存大，比如申请20*8的内存，如果足够，通过refill()，准备为free list 重新填充空间。新的空间将取自内存池。将其中一个分配给用户使用，其它的挂在相应的free_list 中。如果内存池不够大，只够几个内存分配，则就分配这几个，把相应的数据返回。如果连一个都不够则执行第三中情况。
free_list列表中没有空余，内存池也不够。调用malloc重新分配内存，分配时会多分配一倍的内存，把相应的内存挂到free_list下，剩余的放到内存池中。
free_list列表中没有空余，内存池也不够，malloc也失败。则调用一级空间配置器，里面会有循环处理，或者抛出异常。