为什么STL的二级空间配置器在有内存池的情况下要使用自由链表？

Question

据我理解，自由链表中每条链表上的各个结点都是相同大小的，并且它们实际上都是存在于内存池中，只不过是把从内存池中划出来的一整块平均分成了8、16、24...这样的大小，然后每一次需要分配相应大小的区块时，直接从对应的链表中取出第一块返回。内存池用两个位置变量start和end来标明内存池剩余可被划分的空间。

那么我的问题是，为什么要用自由链表？为什么不直接用变量来标明内存池中剩余空间的首地址，不管我是分配1个字节，两个字节，n个字节，直接返回剩余空间的首地址，然后将首地址偏移n个字节后的地址作为新的剩余空间的首地址，下一次分配的时候也如此即可，这样也不需要自由链表了。

我个人觉得，使用自由链表可以让相同大小的待分配区块放在一起，每次分配相应大小的区块时直接取出一块来分配就是了，但是这样感觉并没有带来性能上的什么好处，还不如不管分配多大空间直接从内存池中去取，自由链表还多了一次寻址的开销。

STL不可能没考虑到这些很明显的问题，那么到底是为什么呢？

谢谢！

Answer 1

1) 对齐（alignment）

内存使用是有对齐的要求的。char 也许可以放在任何地址，但是 int 不行。随便放有可能导致程序变慢，也可能导致程序挂掉（跟体系结构有关）。

不够这应该不是主要问题，不能满足对齐的要求，就空几个字节就好了。

2) 释放（free）

如果大家都是申请了不释放，这样分配其实挺好。事实上，在我的某一个工程里，我需要大量的对象，并且我知道他们一定会同时释放，我实际就是这么分配的。释放的时候，直接释放掉整个内存池就好了。

但是，通常的应用里，任何一个已经被分配出去的内存都可能随时被释放，并且不会按照分配的顺序被释放。你这种分配方式，如果在添加一种机制记录哪些内存被释放了，恐怕也不比一个链表来得简单。

而且，内存被释放之后，需要重新被分配出去。此时，分配多少偏移多少的方案就不太好用了。你需要从已被释放的内存的记录里（这也许就是一个链表 ...），找到一块足够大的内存分配出去。同时还得去维护已被释放的内存的记录（因为有些内存被重新使用了）。