空间配置器

在C++中所有STL容器的空间分配其实都是使用的 std::allocator，它是可以感知类型的空间分配器，并将空间的申请与对象的构建分离开来。其实单个对象使用new的时候，空间的申请与对象的构造好像是没有连在一起的，也是分开的（可以回顾new表达式的工作步骤），另外对于容器vector而言，其有个函数叫做reserve函数，先申请空间，然后在在该空间上构建对象。

那么为什么要将空间的申请与对象的构建分开呢？

因为STL中的容器的申请都是批量的，那么对于批量元素而言，肯定不是申请一个空间，然后在该空间构建对象，然后再申请一个空间，接着再构建对象，那么空间的申请就非常频繁，就有可能出现内存碎片问题以及效率问题。

将内存的申请与对象的构建分开的例子，比如：自己实现一个 自定义Vector

参考资料

• cppreference-allocator
• cppreference-allocator_traits

类模板声明

#include <memory>

template <class T>
struct allocator;

template <>
struct allocator<void>;

四个函数

// 空间的申请,申请的是原始的，未初始化的空间
pointer allocate(size_type n, const void *hint = 0);
T *allocate(std::size_t n, const void *hint);
T *allocate(std::size_t n);

// 空间的释放
void deallocate(T *p, std::size_t n);

// 对象的构建，在指定的未初始化的空间上构建对象，使用的是定位new表达式
void construct(pointer p, const_reference val);

// 对象的销毁
void destroy(pointer p);

动手实现

template <typename T>
class Allocator {
public:
    // 负责申请内存
    T* allocate(int size) {
        // return (T*)malloc(sizeof(T) * size);
        return (T*)operator new(sizeof(T) * size);
    }

    // 负责释放内存
    void deallocate(void* p) {
        if (p == nullptr) {
            return;
        }

        // free(p);
        operator delete(p);
        p = nullptr;
    }

    // 负责构造对象
    template <typename U>
    void construct(T* p, U&& value) {
        new (p) T(std::forward<U>(value)); // 定位 new
    }

    // 负责析构对象
    void destory(T* p) {
        p->~T();
    }
};

申请释放空间

• 申请空间的函数——allocate，负责分配未初始化的存储空间。
• 释放空间的函数——deallocate，负责回收不在使用的存储空间。

在施磊老师的课程_{夯实基础类模板部分}中是使用 malloc/free 实现的，在我实现的过程中测试 operator new()/operator delete() 函数也可以正常运作，具体待后续深入。

参考资料 cppreference-分配器 (Allocator)

构造析构对象

• 构造对象的函数——construct，负责在分配的存储中构造对象。
• 析构对象的函数——destroy，负责析构储存于已分配存储中的对象。

构造对象时可能要牵扯到对象的优化问题，比如有时我们需要接收一个左值引用（调用拷贝构造函数）；有时我们需要接收一个右值引用（调用移动构造函数）。因此，实现时可以使用 万能引用 + 完美转发 来满足不同的要求。

析构对象时，直接调用该类的析构函数即可。

空间配置器的原理（重难点）

查看源码，我们知道空间配置器会分为两级，即：两级空间配置器，第一级空间配置器使用类模板malloc_alloc_template ，其底层使用的是malloc/free进行空间的申请与释放，二级空间配置器使用类模板，default_alloc_template，其底层根据申请空间大小又分为两个分支，第一分支是当申请的空间大于128字节的时候，还是走malloc_alloc_template ，当申请的空间小于128字节的使用，使用内存池+16个自由链表的结构进行。也就是由一个16维的数组组成，每一维会按照8的整数倍申请空间，比如：下标为3，也就是会按照32字节为基本单位申请空间，每次申请空间的大小都是32字节，而且每次申请的时候一次申请很大一片空间，然后按照32字节为一个等分，分成多个等分，然后挂接在下标为3的下面，形成链表形式，这样以后需要32字节的时候，直接在下标为3的下面取出一个节点，就是32字节即可。其他下标的处理方式完全一致。

为什么要分成两部分呢？

• 向系统堆要求空间
• 考虑多续状态(multi-threads)
• 考虑内存不足时的应变措施
• 考虑过多小块内存造成的内存碎片（重点）

内存碎片

• 内部碎片：页式管理、段式管理、段页式管理(局部性原理)，无法避免，但是通过算法可以优化。
• 外部碎片：申请堆内存之间的片段空隙，这个是可以合理使用的。

分成两部分的总结

• 一级空间配置器：使用malloc/free系统调用，缺点：频繁的用户态到内核态的切换，开销大(brk,mmap)
• 二级空间配置器：内存池+16个自由链表，优点：以空间换时间，缺点：内存占用比较大，如果内存有限，内存不可控，这也是早期STL提出时候不被重用的原因，那时间内存较小。

源码解析

以《STL源码剖析》这本书的例子进行研究，先申请32字节空间（此时内存充足），然后申请64字节空间（此时内存充足），接着申请96字节空间（此时内存充足），最后申请72字节(假设此时内存池耗尽、堆空间没有大于72字节的连续空间)，按照这个思路去解读源码。搞清楚这几个函数的含义、字节、调用关系。

释放内存的deallocate

对应一级空间配置器，直接使用free将内存回收到堆空间。

对应二级空间配置器，直接将用完后的空间链回到相应的链表下面，使用头插法进行连接。

定位new表达式

定位new表达式接受指向未构造内存的指针，并在该空间中初始化一个对象或者数组。不分配内存，它只在特定的，预分配的内存地址构造一个对象。

template <class _T1, class _T2>
inline void construct(_T1 *__p, const _T2 &__value) {
    _Construct(__p, __value);
}

template <class _T1, class _T2>
inline void _Construct(_T1 *__p, const _T2 &__value) {
    new ((void *)__p) _T1(__value); 
    // 定位new表达式，在执行空间__p上构建对象，例如
    // int a = 10;
    // new (&a) int(5);
}

template <class _Tp>
inline void destroy(_Tp *__pointer) {
    _Destroy(__pointer);
}

template <class _Tp>
inline void _Destroy(_Tp *__pointer) {
    __pointer->~_Tp();
}