stl中空间配置器简介

最近作死，在看sgi-stl（以后均称stl），给自己的理由，美其名曰为了更好的理(zhuang)解(bi)。。。

这一篇文章就先简单介绍下，stl当中的空间配置器。

一般而言，我们平时最常用的空间配置器应该就是new和delete了如下：

class A{…};
A *pa = new A;
delete pa;

在这之中，new和delete分别包含了两个阶段，

new：1. 分配内存；2. 构造对象内容；

delete：1.析构对象；2. 释放内存。

在stl当中，allocator将这四个部分分别拆开，分别对应于alloc::allocate(), ::construct(), ::destroy(), alloc::deallocate(),

先说跟这篇文章关系不太大的两个部分，::construct()和::destroy()，前者不用多说，每次都要调用生命类型的构造函数；但是::destroy()的话，就有些地方可以优化一下了，stl里面在调用destroy的时候，会判断指针所指类型是否有trivial destructor， 如果有，啥也不做，等待其自动销毁；如果没有，就调用其类型的析构函数进行析构。在这里，如何做到判断指针类型是否拥有trivial destructor，stl使用的是一个叫trait<>的东西，具体实现下次再说，这里只需要记住可以判断指针所指类型有无trivial destructor 就好了。

之后就轮到今天的重点了：空间的配置与释放

stl为了提高效率，在空间的配置上设置了双层配置器，第一级就是使用传统的malloc()和free()， 第二级配置器则视情况采用不同的策略：当申请空间超过128bytes时，调用第一级配置器；当申请空间小于128bytes时，采用memory pool整理方式，而不是一味的求助于第一级配置器，其中，memory pool由malloc()配置而得。具体如下图所示：

先说第一级：第一条没啥好说的，大家应该都看得懂；这里简单说下第二条（因为我对这个是真的没有印象了。。。），C++的set_new_handler()是指可以在内存配置需求无法满足时，要求调用一个指定函数；若没有设置，就乖乖抛出bad_alloc异常信息了。

接下来介绍第二级配置器

之所以有第二级配置器，是考虑到了如果仅仅只有第一层配置器的话，会造成太多内存碎片。在第二级配置的过程中，每次会配置一大块内存，并维护对应的自由链表，若下次再有相同大小的内存需求，就直接从free-list中拨出；如果释放小额区块，则收到对应的free-list当中去，（注，分配小区块时，会自动调至8的倍数，这是一种折中的消除内存碎片化的做法）

free-list结构如下图：

为了省事，只画出了简单的几个下标对应的链表，实际上每个下标下面都有对应的一条链表的。

当分配空间的时候，查找到free-list对应的下标，接下来就是链表删除的操作了

当返还空间的时候，查到free-list对应的下标，接下来就是链表的插入操作了

当allocate()发现free-list当中没有可用区块时，就调用refill()为其填充空间，新的空间来自内存池，默认获取20个新节点；若空间不足，获取节点个数可能会小于20；若内存池中剩余空间不足所1个申请的区块的大小，则先将剩余空间（若有）编入对应free-list，之后配置heap空间，申请40个对应区块大小+round_up(heap_size>>4)字节的内存，作为内存池容量。若分配失败，则有如下几种选择：1. 查看free-list中足够大的区块是否有尚未使用的空间；2. 调用第一级配置器，抛出异常。。。

stl的空间配置器就先介绍到这里啦，欢迎拍砖~