浅谈STL中的分配器

分配器是STL中的六大部件之一，是各大容器能正常运作的关键，但是对于用户而言确是透明的，它似乎更像是一个幕后英雄，永远也不会走到舞台上来，观众几乎看不到它的身影，但是它又如此的重要。作为用户，你几乎不用关心它的底层是怎么实现的，甚至也很少有能使用到它的机会。这里简单聊一下我对它的认识。

正常情况下我们如何取得一块内存？

malloc能够帮你获取一块内存并返回这块内存的首地址；
new operator的底层也是用malloc实现，只是相较于malloc，它不光会给你一块内存，还会帮你自动初始化这块内存，即调用对应对象的构造函数
operator new是C++获取内存的方式，注意：new operator和operator new是两种不同的东西，它也是调用了malloc来实现获取内存，只是封装了一些东西，增加了一些异常机制。
而VC，BC,GNU C等等编译器厂商最初提供的allocate的底层也是通过调用operator new实现的。

所以，你发现没有？殊途同归，大家几乎都是通过调用malloc来实现获取内存这一操作的。而malloc根据机器的不同，去调用操作系统底层提供的api接口去获得真正的内存。

在这里插入图片描述

但是，如果你申请一块10个字节的内存，malloc给你的内存的大小却并不真的是10个字节。这里面你能用的内存有10个字节没错，但是还会有一些额外的开销在里面，它们会在这块内存的两头加上所谓的“cookie”来处理一些其他事情，就比如你买东西收到的其实并不是东西本身，还会有快递盒，快递袋，快递单等额外的东西帮助你自己买的东西到达你的手上。这些东西对你来说可能没用，但确确实实是不可避免的开销。

从这个角度而言，如果一个容器里放的东西很小，但是元素的数量又很多，假如容器里你想放一个2个字节的short类型的元素，而这样的容器的数量有100w个，这样轮到这个容器底层的分配器去帮你开辟内存的时候，由于cookie的存在，申请一个这样的容器你可能会得到10个字节，其中2个字节是你想要的内存，其余8个字节是额外的开销，这样下来100w个容器本来只需要200w个字节，现在你却不得不得到1000w个字节，性能实在是不这么高。

这里并不是说cookie很消耗内存才造成的你的性能不理想，而是存在一个比例问题。如果你的容器里放的元素的内存很大，那么这额外的开销就显得很渺小，完全可以接受；但是更多的情况下，容器里放的元素其实并没有那么大，这也就显得性能不理想。

如何解决这种问题？

SGI STL中给出的一个思路是先放很多的分配器，但是每个分配器只负责某种固定大小的内存的申请，等到容器真的申请内存的时候，对应大小的分配器会去申请一块很大的内存，然而自己将这些内存切割成固定大小的内存，再返回给使用者某一块固定大小的内存的首地址。

使用这种策略，便不再会对额外开销产生困扰，因为真正的申请内存只有刚开始的那次，所以只会得到一次cookie，得到的这块大的内存被切割成固定大小时，每块内存上并不会带cookie，也就不会有额外开销。
在这里插入图片描述

STL提供了两层内存分配器：

当分配大于128KB时，直接采用new operator，也就是一级内存分配器；
当分配小于128KB时，采用二级内存分配器，也就是内存池，具体是通过自由链表实现的。参考文章。

为什么要分两级呢？主要是为了减少内存碎片，减少malloc的次数。所以内存池就相当于应用代码和系统调用申请内存的中间件。

第一层内存分配器

operator new

operator new可以被重载：

重载时，返回类型必须声明为void*；
重载时，第一个参数类型必须为分配空间的大小（字节），类型为size_t，当然也可以带其它参数；

如：

   class Foo
   {
   public:
     static void *operator new (size_t size)
     {
         Foo *p = (Foo*)malloc(size);
         return p;
     }
   
    static void operator delete(void *p, size_t size)
     {
         free(p);
     }
   };

这里只是简单的用malloc和free来实现，后续可以用内存池。

C++还提供了全局的operator new和operator delete，可以通过::operator new和::operator delete来访问全局操作符。

placement new

operator new实现了new表达式的第一步即分配内存，那么谁来调用构造函数呢？就是placement new，它的语法是：

 Object * p = new (address) ClassConstruct(...)

这里要求address是void*，并且placement new被定义在#include<new>头文件中。同样的也可以重载它，也提供了全局下的placement new，通过::访问。

举个例子

 int* ptr = ::operator new(sizeof(int));
 ::new ((void*)ptr) int();

其实本质上placement new也是operator new的一个重载版本！只不过，这个重载版本我们常用来调用构造函数。如：

 class Foo
 {
 public:
     //一般的 operator new 重载
     void* operator new(size_t size)
     { return malloc(size); }
 
     //标准库已经提供的 placement new() 的重载形式
     void* operator new(size_t size, void* start)
     { 
       dosomething;
       return start; 
     }
 };