浅谈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可以被重载：

1. 重载时，返回类型必须声明为void*；
2. 重载时，第一个参数类型必须为分配空间的大小（字节），类型为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; }};    

那对new operator和delete operator拆分为两部分功能有什么好处呢？使用new表达式在分配内存时，需要在堆中查找足够大的剩余空间，显然这个操作速度是很慢的，而且有可能出现无法分配内存的异常（空间不够）。

placement new就可以解决这个问题。在一个预先准备好了的内存缓冲区上进行构造函数，不需要查找内存，内存分配的时间是常数。而且不会出现在程序运行中途出现内存不足的异常。所以，placement new非常适合那些对时间要求比较高，长时间运行不希望被打断的应用程序。

总之，new造成的反复分配内存很浪费，所以placement new直接固定内存，在这个固定内存上反复构造和析构，但不再反复分配内存和释放内存。

note：如果采用placement new，可别忘记在operator delete前调用析构函数！除非元素的析构函数是无关紧要的。

allocator

STL的allocator负责对容器的分配内存、释放内存、调用元素的构造函数、调用元素的析构函数。

其实理解了上面的内容，STL的allocator也就很简单。

对外提供四大方法：

• allocator方法：即调用operator new
• construct方法：即调用placement new
• deallocator方法：即调用operator delete
• destroy方法：即调用~T()

note：不是所有类都需要调用destroy，当类的析构函数是无关紧要的时候，我们可以不进行析构，那么什么样的是无关紧要的?可以用std::is_trivially_destructible类模板判断。具体来说：

1. 使用隐式定义的析构函数，即没有定义自己析构函数
2. 析构函数不是虚函数
3. 其基类与非静态成员也是可trivially析构

其实会发现basic_string在释放内存前没有调用析构函数，正是因为basic_string严格要求元素类的析构函数是无关紧要的。而vector等则需要在释放内存前调用析构函数。

第二层内存分配器

先申请一大块内存，然后切割成小块，由单向链表串起来，内存池包括十六条链表，分别负责不同大小的内存大小，比如第7个负责256字节的区块，以8的倍速增长。

至于STL内存池设计的好坏也颇有争议：C++ 标准库中的allocator是多余的，allocator作为模板参数这就导致不同allocator是不同的type。