stl六大组件简介

我们知道，stl有容器，空间配置器，适配器，迭代器，仿函数以及算法这6个组件，它们六者关系大概如下：容器通过配置器取得数据存储空间,算法通过迭代器获取容器内容,仿函数可以协助算法完成不同的策略变化,配接器可以修饰或套界仿函数。

侯捷在《STL源码剖析》一书讲到：

因此我们需要先去学习空间配置器。

---

预备知识

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

class A {};
A* pa = new A;
//...执行其他操作
delete pa;

这里面隐含几个操作，对于new，我们都是先配置内存，然后调用对应的构造函数；而delete则是先调用对应的析构函数，然后释放内存。

在这里，我们先不去看对象的构造和释放，而将注意力放在内存的配置和释放，也就是alloc这个文件上，去研究它的代码。

在SGI版本的STL中，空间的配置释放都由< stl_alloc.h > 负责。它的设计思想如下：

• 向system heap要求空间
• 考虑多线程
• 考虑内存不足的应变措施
• 考虑内存碎片的问题

PS：关于内存碎片，下图可以解释：

---

SGI两层配置器

由于以上的问题，SGI设计了两层的配置器，也就是第一级配置器和第二级配置器。同时为了自由选择，STL又规定了 __USE_MALLOC 宏，如果它存在则直接调用第一级配置器，不然则直接调用第二级配置器。SGI未定义该宏，也就是说默认使用第二级配置器

需要注意的是，SGI版STL提供了一层更高级的封装，定义了一个simple _ alloc类，无论是用哪一级都以模板参数alloc传给simple _ alloc，这样对外体现都是只是simple _ alloc

而它的代码实现比较简单，仅仅是调用一级或者二级配置器的接口

template<class T, class Alloc = AllocToUse>
class SimpleAlloc
{
public:
    static T* Allocate()
    {
        return (T*)Alloc::Allocate(sizeof(T));
    }

    static T* Allocate(size_t n)
    {
        return n == 0 ? 0 : (T*)Alloc::Allocate(n * sizeof(T));
    }

    static void Deallocate(T* p)
    {
        if (p != NULL)
            return Alloc::Deallocate(p, sizeof(T));
    }

    static void Deallocate(T* p, size_t n)
    {
        return Alloc::Deallocate(p, n * sizeof(T));
    }

};

第一级配置器

直接调用malloc和free来配置释放内存，简单明了。

template<int Inst>
class __MallocAllocTemplate //一级空间配置器
{
    typedef void (*OOM_HANDLER)();
private:
    //these funs below are used for "OOM" situations
    //OOM = out of memory
    static void* OOM_Malloc(size_t n); //function
    static void* OOM_Realloc(void *p, size_t newSZ); //function
    static OOM_HANDLER OOM_Handler; //function pointer

public:
    static void* Allocate(size_t n)
    {
        void* ret = malloc(n);
        if (ret == NULL)
            ret = OOM_Malloc(n);
        return ret;
    }

    static void Deallocate(void* p, size_t n)
    {
        free(p);
    }

    static void* Reallocate(void* p, size_t oldSZ, size_t newSZ)
    {
        void* ret = realloc(p, newSZ);
        if (ret == NULL)
            ret = OOM_Realloc(p, newSZ);
        return ret;
    }
    //static void (* set_malloc_handler(void (*f)()))()
    //参数和返回值都是函数指针void (*)()
    static OOM_HANDLER SetMallocHandler(OOM_HANDLER f)
    {
        OOM_HANDLER old = OOM_Handler;
        OOM_Handler = f;
        return old;
    }
};

//让函数指针为空
template<int Inst>
void (*__MallocAllocTemplate<Inst>::OOM_Handler)() = NULL;

template<int Inst>
void* __MallocAllocTemplate<Inst>::OOM_Malloc(size_t n)
{
    void* ret = NULL;
    void(*myHandler)() = NULL;
    for (;;)
    {
        myHandler = OOM_Handler;
        if (myHandler == NULL)
            throw bad_alloc();
        (*myHandler)();
        ret = malloc(n);
        if (ret != NULL)
            return ret;
    }
}

template<int Inst>
void* __MallocAllocTemplate<Inst>::OOM_Realloc(void* p, size_t newSZ)
{
    void* ret = NULL;
    void(*myHandler)() = NULL;
    for (;;)
    {
        myHandler = OOM_Handler;
        if (myHandler == NULL)
            throw bad_alloc();
        (*myHandler)();
        ret = realloc(p, newSZ);
        if (ret != NULL)
            return ret;
    }
}


typedef __MallocAllocTemplate<0> MallocAlloc; //一级空间配置重命名

第二级配置器

根据情况来判定，如果配置区块大于128bytes，说明“足够大”，调用第一级配置器，而小于等于128bytes，则采用复杂内存池（memory pool）来管理。

图示如下：

第二级空间配置器的过程，我们重点可以看allocate和deallocate这两个函数的实现

static void* Allocate(size_t n)
{
    if (n > (size_t)__MAX_BYTES) // 字节数大于128，调用一级空间配置器
        return MallocAlloc::Allocate(n);
    //不然到freelist去找
    Obj* volatile* myFreeList = FreeList + FreeListIndex(n); //定位下标
    Obj* ret = *myFreeList;
    if (ret == NULL)
    {
        void* r = Refill(RoundUP(n));//没有可用free list 准备装填
    }
    *myFreeList = ret->freeListLink;
    return ret; 
}

可以看出来：

1. 如果用户需要的区块大于128，则直接调用第一级空间配置器
2. 如果用户需要的区块大于128，则到自由链表中去找
   
   • 如果自由链表有，则直接去取走
   • 不然则需要装填自由链表（Refill）

static void Deallocate(void* p, size_t n)
{
    if (n > (size_t)__MAX_BYTES) //区块大于128， 则直接由第一级空间配置器收回
        MallocAlloc::Deallocate(p, n);
    Obj* volatile* myFreeList = FreeList + FreeListIndex(n);
    Obj* q = (Obj*)p;
    q->freeListLink = *myFreeList;
    *myFreeList = q;
}

释放操作和上面有点类似：

1. 如果区块大于128， 则直接由第一级空间配置器收回
2. 如果区块小于等于128， 则有自由链表收回

我们在上面重点分析了整体思路，也就是二级配置器如何配置和是否内存，他们和一级配置器一样都提供Allocate和Deallocate的接口（其实还有个Reallocate也是用于分配内存，类似于C语言中realloc函数），我们都提到了一点自由链表，那么自由链表是个什么？

如上图所示，自由链表是一个指针数组，有点类似与hash桶，它的数组大小为16，每个数组元素代表所挂的区块大小，比如free _ list[0]代表下面挂的是8bytes的区块，free _ list[1]代表下面挂的是16bytes的区块…….依次类推，直到free _ list[15]代表下面挂的是128bytes的区块

同时我们还有一个被称为内存池地方，以start _ free和 end _ free记录其大小，用于保存未被挂在自由链表的区块，它和自由链表构成了伙伴系统。

我们之前讲了，如果用户申请小于等于128的区块，就到自由链表中取，但是如果自由链表对应的位置没了怎么办？？？这下子我们的内存池就发挥作用了！

下面我们来重点讲一讲如果自由链表对应的位置没有所需的内存块该怎么办，也就是Refill函数的实现。

static void* Allocate(size_t n)
{
//...
    if (ret == NULL)
    {
        void* r = Refill(RoundUP(n));//没有可用free list 准备装填
    }
//...
}

//freelist没有可用区块，将要填充，此时新的空间取自内存池
static void* Refill(size_t n)
{
    size_t nobjs = 20;
    char* chunk = (char*)ChunkAlloc(n, nobjs); //默认获得20的新节点，但是也可能小于20，可能会改变nobjs
    if (nobjs == 1) //如果只有一块直接返回调用者，此时freelist无结点
        return chunk;
    //有多块，返回一块给调用者，其他挂在自由链表中
    Obj* ret = (Obj*)chunk;
    Obj* cur = (Obj*)(chunk + n);
    Obj* next = cur;
    Obj* volatile *myFreeList = FreeList + FreeListIndex(n);
    *myFreeList = cur;
    for (size_t i = 1; i < nobjs; ++i)
    {       
        next = (Obj*)((char*)cur + n);
        cur->freeListLink = next;
        cur = next;
    }
    cur->freeListLink = NULL;
    return ret;

}

这里面的重点函数为ChunkAlloc，它的逻辑相对复杂，代码如下：

static char* ChunkAlloc(size_t size, size_t& nobjs)
{
    size_t bytesLeft = endFree - startFree; //内存池剩余空间
    size_t totalBytes = size * nobjs;
    char* ret = NULL;
    if (bytesLeft >= totalBytes) // 内存池大小足够分配nobjs个对象大小
    {
        ret = startFree;
        startFree += totalBytes;
        return ret;
    }
    else if (bytesLeft >= size) // 内存池大小不够分配nobjs，但是至少分配一个
    {
        size_t nobjs = bytesLeft / size;
        totalBytes = size * nobjs;
        ret = startFree;
        startFree += totalBytes;
        return ret;
    }
    else // 内存池一个都分配不了
    {
        //让内存池剩余的那么点挂在freelist上
        if (bytesLeft > 0)
        {
            size_t index = FreeListIndex(bytesLeft);
            ((Obj*)startFree)->freeListLink = FreeList[index];
            FreeList[index] = (Obj*)startFree;
        }

        size_t bytesToGet = 2 * totalBytes + RoundUP(heapSize >> 4);
        startFree = (char*)malloc(bytesToGet);
        if (startFree == NULL)
        {
            //申请失败，此时试着在自由链表中找
            for (size_t i = size; i <= __MAX_BYTES; i += __ALIGN)
            {
                size_t index = FreeListIndex(i);
                Obj* volatile* myFreeList = FreeList + index;
                Obj* p = *myFreeList;
                if (FreeList[index] != NULL)
                {
                    FreeList[index] = p->freeListLink;
                    startFree = (char*)p;
                    endFree = startFree + i;
                    return ChunkAlloc(size, nobjs);
                }
            }
            endFree = NULL;
            //试着调用一级空间配置器
            startFree = (char*)MallocAlloc::Allocate(bytesToGet);
        }

        heapSize += bytesToGet;
        endFree = startFree + bytesToGet;
        return ChunkAlloc(size, nobjs);
    }

}

观擦上面的代码，我们知道当自由链表中没有对应的内存块，系统会执行以下策略：

如果用户需要是一块n字节的区块，且n <= 128（调用第二级配置器），此时Refill填充是这样的：（需要注意的是：系统会自动将n字节扩展到8的倍数也就是RoundUP（n），再将RoundUP（n）传给Refill）。用户需要n块，且自由链表中没有，因此系统会向内存池申请nobjs * n大小的内存块，默认nobjs=20

• 如果内存池大于 nobjs * n，那么直接从内存池中取出
• 如果内存池小于nobjs * n，但是比一块大小n要大，那么此时将内存最大可分配的块数给自由链表，并且更新nobjs为最大分配块数x （x < nobjs）
• 如果内存池连一个区块的大小n都无法提供，那么首先先将内存池残余的零头给挂在自由链表上，然后向系统heap申请空间，申请成功则返回，申请失败则到自己的自由链表中看看还有没有可用区块返回，如果连自由链表都没了最后会调用一级配置器

这就是ChunkAlloc所执行的操作，在执行完ChunkAlloc函数后会获得内存（失败就抛出异常），此时也就是这段代码：

if (nobjs == 1) //如果只有一块直接返回调用者，此时freelist无结点
        return chunk;
    //有多块，返回一块给调用者，其他挂在自由链表中
    Obj* ret = (Obj*)chunk;
    Obj* cur = (Obj*)(chunk + n);
    Obj* next = cur;
    Obj* volatile *myFreeList = FreeList + FreeListIndex(n);
    *myFreeList = cur;
    for (size_t i = 1; i < nobjs; ++i)
    {       
        next = (Obj*)((char*)cur + n);
        cur->freeListLink = next;
        cur = next;
    }
    cur->freeListLink = NULL;

如果只有一块返回给调用者，有多块，返回给调用者一块，剩下的挂在对应的位置。

这样一个空间配置的比较关键思路就有了，剩余的可以参看stl源码剖析。

关于完整代码可见 我的github

最后

也就是STL可能存在的问题，通俗的讲就是优缺点吧

我们知道，引入相对的复杂的空间配置器，主要源自两点：

1. 频繁使用malloc，free开辟释放小块内存带来的性能效率的低下
2. 内存碎片问题，导致不连续内存不可用的浪费

引入两层配置器帮我们解决以上的问题，但是也带来一些问题：

1. 内碎片的问题，自由链表所挂区块都是8的整数倍，因此当我们需要非8倍数的区块，往往会导致浪费，比如我只要1字节的大小，但是自由链表最低分配8块，也就是浪费了7字节，我以为这也就是通常的以空间换时间的做法，这一点在计算机科学中很常见。
2. 我们发现似乎没有释放自由链表所挂区块的函数？确实是的，由于配置器的所有方法，成员都是静态的，那么他们就是存放在静态区。释放时机就是程序结束，这样子会导致自由链表一直占用内存，自己进程可以用，其他进程却用不了。