STL内存管理

1. 概述

STL Allocator是STL的内存管理器，也是最低调的部分之一，你可能使用了3年stl，但却不知其为何物。

STL标准如下介绍Allocator

the STL includes some low-level mechanisms for allocating and deallocating memory. Allocators are very specialized, and you can safely ignore them for almost all purposes. Allocators encapsulate allocation and deallocation of memory. They provide a low-level interface that permits efficient allocation of many small objects;different allocator types represent different schemes for memory management.

<STL 源码剖析>将其描述为空间配置器，理由是allocator可以将其它存储介质（例如硬盘）做为stl 容器的存储空间。由于内存是allocator管理的主要部分，因此，本文以STL内存管理为出发点介绍allocator。

Allocator就在我们身边，通常使用STL的方式：
#include <vector>
std::vector<int> Array(100);

本质上，调用的是：

#include <vector>
std::vector<int, std::allocator> Array(100);

std::allocator就是一个简单的Allocator

2. 为什么需要了解Allocator

项目中遇到的两个case
1）memory高位

线上使用vector保存待处理的数据，在停服务追数据的过程中，由于vector::clear并不释放内存，造成内存始终处于高位。
参考：http://blog.csdn.net/yfkiss/article/details/6537234

2）多线程使用vector、map

使用map保存状态，在多线程环境下，出现性能问题

在实际使用STL的过程中，会遇到很多问题，需要了解STL Allocator

3. 使用

针对不同的应用场合，STL中实现了不同的Allocator，如下（gcc-3.4：http://www.cs.huji.ac.il/~etsman/Docs/gcc-3.4-base/libstdc++/html/20_util/allocator.html）:

__gnu_cxx::new_allocator<T> Simply wraps ::operator new and ::operator delete.
__gnu_cxx::malloc_allocator<T> Simply wraps malloc and free. There is also a hook for an out-of-memory handler
__gnu_cxx::debug_allocator<T> A wrapper around an arbitrary allocator A. It passes on slightly increased size requests to A, and uses the extra memory to store size information.
__gnu_cxx::__pool_alloc<bool, int> A high-performance, single pool allocator. The reusable memory is shared among identical instantiations of this type.
__gnu_cxx::__mt_alloc<T> A high-performance fixed-size allocatorthat was initially developed specifically to suit the needs of multi threaded applications
__gnu_cxx::bitmap_allocato A high-performance allocator that uses a bit-map to keep track of the used and unused memory locations

例如，在多线程环境下，可以使用：

[html] view plain copy

#include <vector>
#include <mt_allocator.h>
std::vector<int, __gnu_cxx::__mt_alloc<int>> Array(100);

4.一个简单的Allocator实现
我们可以实现自己的allocator

[cpp] view plain copy

#include <memory>
template<class T>
class my_allocator : public std::allocator<T>
{
public:
typedef std::allocator<T> base_type;
// 必须要重新定义
template<class Other>
struct rebind
{
typedef my_allocator<Other> other;
};
// 内存的分配与释放可以实现为自定义的算法
pointer allocate(size_type count)
{
return (base_type::allocate(count));
}
void deallocate(pointer ptr, size_type count)
{
base_type::deallocate(ptr, count);
}
// 构造函数
my_allocator()
{}
my_allocator(my_allocator<T> const&)
{}
my_allocator<T>& operator=(my_allocator<T> const&)
{
return (*this);
}
template<class Other>
my_allocator(my_allocator<Other> const&)
{}
template<class Other>
my_allocator<T>& operator=(my_allocator<Other> const&)
{
return (*this); }
};

5. 参考文献

STL源码剖析
http://gcc.gnu.org/onlinedocs/libstdc++/manual/ext_allocators.html
http://www.codeguru.com/cpp/cpp/cpp_mfc/stl/article.php/c4079
http://blog.163.com/dengminwen@126/blog/static/870226720097189486788/

STL中诸多容器和算法都要涉及到向系统申请和释放内存，所以先读读C++的内存管理----C++称其为allocator

1, default allocator

SGI STL 的头文件defalloc.h中有一个符合标准的名为allocator的内存分配器，它只是简单地将::operator new 和::operator delete做了一层薄薄的封装。在SGI STL的容器和算法部分从来没有用到这个内存分配器。在此略过。

2， STL 的内存分配策略

首先简要介绍一下STL中对内存分配的规划

当用户用new构造一个对象的时候，其实内含两种操作：1）调用::operator new申请内存；2）调用该对象的构造函数构造此对象的内容

当用户用delete销毁一个对象时，其实内含两种操作：1）调用该对象的析构函数析构该对象的内容；2）调用::operator delete释放内存

SGI STL中对象的构造和析构由::construct()和::destroy()负责；内存的申请和释放由alloc:allocate()和alloc:deallocate()负责；此外，SGI STL还提供了一些全局函数，用来对大块内存数据进行操作。

　　上一段提到的三大模块分别由stl_construct.h stl_alloc.h stl_uninitialized.h 负责

　　下面的各小节分别分析这三大模块的主要内容

3，对象的构造和析构工具(stl_construct.h)

　　　stl_construct.h中提供了两种对象的构造方法，默认构造和赋值构造：

1 template <class _T1, class _T2>
2 inline void _Construct(_T1* __p, const _T2& __value) {
3   new ((void*) __p) _T1(__value);
4 }
5 
6 template <class _T1>
7 inline void _Construct(_T1* __p) {
8   new ((void*) __p) _T1();
9 }

　　上面两个函数的作用是构造一个类型为T1的对象，并由作为参数的指针p返回。

其中的new (_p) _T1(_value); 中使用了placement new算子，它的作用是通过拷贝的方式在内存地址_p处构造一个_T1对象。（placement new能实现在指定的内存地址上用指定类型的构造函数来构造一个对象）。

在对象的销毁方面，stl_construct.h也提供了两种析构方法：

1 template <class _Tp>
2 inline void _Destroy(_Tp* __pointer) {
3   __pointer->~_Tp();
4 }
5 
6 template <class _ForwardIterator>
7 inline void _Destroy(_ForwardIterator __first, _ForwardIterator __last) {
8   __destroy(__first, __last, __VALUE_TYPE(__first));
9 }

　　第一个版本的析构函数接受一个指针，将该指针所指的对象析构掉；第二个版本的析构函数接受first和last两个迭代器，将这两个迭代器范围内的对象析构掉。

　　在第二个版本的destroy函数里面，运用了STL中惯用的traits技法，traits会得到当前对象的一些特性，再根据特性的不同分别对不同特性的对象调用相应的方法。在stl_construct.h中的destroy中，STL会分析迭代器所指对象的has_trivial_destructor特性的类型（只有两种：true_type和false_type），如果是true_type，STL就什么都不做；如果是false_type，就会调用每个对象的析构函数来销毁这组对象。

　　除此之外，stl_construct还为一些基本类型的对象提供了特化版本的destroy函数，这些基本类型分别是char, int, float, double, long。当destroy的参数为这些基本类型时，destroy什么都不做。

4，内存空间管理工具alloc

我想以自底向下的顺序介绍一下STL的allocator。首先说说STL内建的两种分配器，然后介绍STL如何封装这两种分配器对外提供统一的接口，最后用一个vector的例子看看容器如何使用这个allocator。

4.1 两种内存分配器

4.1.1 __malloc_alloc_template分配器

该分配器是对malloc、realloc以及free的封装：

 1   static void* allocate(size_t __n)
 2   {
 3     void* __result = malloc(__n);
 4     if (0 == __result) __result = _S_oom_malloc(__n);
 5     return __result;
 6   }
 7 
 8   static void deallocate(void* __p, size_t /* __n */)
 9   {
10     free(__p);
11   }
12 
13   static void* reallocate(void* __p, size_t /* old_sz */, size_t __new_sz)
14   {
15     void* __result = realloc(__p, __new_sz);
16     if (0 == __result) __result = _S_oom_realloc(__p, __new_sz);
17     return __result;
18   }

　　当调用malloc和realloc申请不到内存空间的时候，会改调用oom_malloc()和oom_realloc()，这两个函数会反复调用用户传递过来的out of memory handler处理函数，直到能用malloc或者realloc申请到内存为止。如果用户没有传递__malloc_alloc_oom_handler，__malloc_alloc_template会抛出__THROW_BAD_ALLOC异常。

　　所以，内存不足的处理任务就交给类客户去完成。

　　4.1.2 __default_alloc_template分配器

　　这个分配器采用了内存池的思想，有效地避免了内碎片的问题（顺便一句话介绍一下内碎片和外碎片：内碎片是已被分配出去但是用不到的内存空间，外碎片是由于大小太小而无法分配出去的空闲块）。

　　如果申请的内存块大于128bytes，就将申请的操作移交__malloc_alloc_template分配器去处理；如果申请的区块大小小于128bytes时，就从本分配器维护的内存池中分配内存。

　　分配器用空闲链表的方式维护内存池中的空闲空间，空闲链表大概类似于下面的形状：

如图所示，s_free_list是这些空闲分区链的起始地址组成的数组，大小为16。这16个链表中每个链表中的空闲空间的大小都是固定的，第一个链表的空闲块大小是8bytes, 依次是16, 24, 32, 40, 48, 56, 64, 72, 80, 88, 96, 104, 112, 120, 128bytes。

　　另外还有三个指针s_start_free, s_end_free, s_heap_size。它们分别指向整个内存池的起始地址，结束地址和可用空间大小。

分配内存过程：

　　1）如果申请的内存空间大于128bytes, 则交由第一个分配器处理

　　2）分配器首先将申请内存的大小上调至8的倍数n，并根据n找出其对应的空闲链表地址__my_free_list

　　3）如果该空闲链表中有可用的空闲块，则将此空闲块返回并更新__my_free_list，否则转到4）

　　4）到这一步，说明__my_free_list中没有空闲块可用了，分配器会按照下面的步骤处理：

　　　　a) 试着调用_s_chunk_alloc()申请大小为n*20的内存空间，注意的是，此时不一定能申请到n*20大小的内存空间

b) 如果只申请到大小为n的内存空间，则返回给用户，否则到c)

c) 将申请到的n*x(a中说了，不一定是n*20)内存块取出一个返回给用户，其余的内存块链到空闲链表__my_free_list中

_s_chunk_alloc()的具体过程为：

1)如果_s_start_free和_s_end_free之间的空间足够分配n*20大小的内存空间，则从这个空间中取出n*20大小的内存空间，更新_s_start_free并返回申请到的内存空间的起始地址，否则转到2)

2) 如果_s_start_free和_s_end_free之间的空间足够分配大于n的内存空间，则分配整数倍于n的内存空间，更新_s_start_free，由nobj返回这个整数，并返回申请到的内存空间的起始地址；否则转到3）

　　3) 到这一步，说明内存池中连一块大小为n的内存都没有了，此时如果内存池中还有一些内存（这些内存大小肯定小于n），则将这些内存插入到其对应大小的空闲分区链中

　　4) 调用malloc向运行时库申请大小为（2*n*20 + 附加量）的内存空间，如果申请成功，更新_s_start_free, _s_end_free和_s_heap_size，并重新调用_s_chunk_alloc()，否则转到5)

　　5) 到这一步，说明4)中调用malloc失败，这时分配器依次遍历16个空闲分区链，只要有一个空闲链，就释放该链中的一个节点，重新调用_s_chunk_alloc()

　　内存释放过程：

　　内存的释放过程比较简单，它接受两个参数，一个是指向要释放的内存块的指针p，另外一个表示要释放的内存块的大小n。分配器首先判断n，如果n>128bytes，则交由第一个分配器去处理；否则将该内存块加到相应的空闲链表中。

4.2 对外提供的分配器接口

SGI STL 为了方便用户访问，为上面提到的两种分配器包装了一个接口，该接口如下：

 1 template<class _Tp, class _Alloc>
 2 class simple_alloc {
 3 
 4 public:
 5     static _Tp* allocate(size_t __n)
 6       { return 0 == __n ? 0 : (_Tp*) _Alloc::allocate(__n * sizeof (_Tp)); }
 7     static _Tp* allocate(void)
 8       { return (_Tp*) _Alloc::allocate(sizeof (_Tp)); }
 9     static void deallocate(_Tp* __p, size_t __n)
10       { if (0 != __n) _Alloc::deallocate(__p, __n * sizeof (_Tp)); }
11     static void deallocate(_Tp* __p)
12       { _Alloc::deallocate(__p, sizeof (_Tp)); }
13 };

用户调用分配器的时候，为simple_alloc的第二个模板参数传递要使用的分配器。

4.3 用户使用分配器的方式

下面是vector使用STL分配器的代码

 1 template <class _Tp, class _Alloc>

　　//cobbliu 注：STL vector 的基类 
 2 class _Vector_base {　　
 3 public:
 4   typedef _Alloc allocator_type;
 5   allocator_type get_allocator() const { return allocator_type(); }
 6 
 7   _Vector_base(const _Alloc&)
 8     : _M_start(0), _M_finish(0), _M_end_of_storage(0) {}
 9   _Vector_base(size_t __n, const _Alloc&)
10     : _M_start(0), _M_finish(0), _M_end_of_storage(0) 
11   {
12     _M_start = _M_allocate(__n);
13     _M_finish = _M_start;
14     _M_end_of_storage = _M_start + __n;
15   }
16 
17   ~_Vector_base() { _M_deallocate(_M_start, _M_end_of_storage - _M_start); }
18 
19 protected:
20   _Tp* _M_start;
21   _Tp* _M_finish;
22   _Tp* _M_end_of_storage;
23 
24   typedef simple_alloc<_Tp, _Alloc> _M_data_allocator;
25   _Tp* _M_allocate(size_t __n)
26     { return _M_data_allocator::allocate(__n); }
27   void _M_deallocate(_Tp* __p, size_t __n) 
28     { _M_data_allocator::deallocate(__p, __n); }
29 };

　　我们可以看到vector的基类调用simple_alloc作为其分配器

5，基本内存处理工具

除了上面的内存分配器之外，STL还提供了三类内存处理工具：uninitialized_copy(), uninitialized_fill()和uninitialized_fill_n()。这三类函数的实现代码在头文件stl_uninitialized.h中。

uninitialized_copy()像下面的样子：

1 template <class _InputIter, class _ForwardIter>
2 inline _ForwardIter
3   uninitialized_copy(_InputIter __first, _InputIter __last,
4                      _ForwardIter __result)
5 {
6   return __uninitialized_copy(__first, __last, __result,
7                               __VALUE_TYPE(__result));
8 }

uninitialized_copy()会将迭代器_first和_last之间的对象拷贝到迭代器_result开始的地方。它调用的__uninitialized_copy(__first, __last, __result,__VALUE_TYPE(__result))会判断迭代器_result所指的对象是否是POD类型（POD类型是指拥有constructor, deconstructor, copy, assignment函数的类），如果是POD类型，则调用算法库的copy实现；否则遍历迭代器_first~_last之间的元素，在_result起始地址处一一构造新的元素。

uninitialized_fill()像下面的样子：

1 template <class _ForwardIter, class _Tp>
2 inline void uninitialized_fill(_ForwardIter __first,
3                                _ForwardIter __last, 
4                                const _Tp& __x)
5 {
6   __uninitialized_fill(__first, __last, __x, __VALUE_TYPE(__first));
7 }

uninitialized_fill()会将迭代器_first和_last范围内的所有元素初始化为x。它调用的__uninitialized_fill(__first, __last, __x, __VALUE_TYPE(__first))会判断迭代器_first所指的对象是否是POD类型的，如果是POD类型，则调用算法库的fill实现；否则一一构造。

　　uninitialized_fill_n()像下面这个样子：

1 template <class _ForwardIter, class _Size, class _Tp>
2 inline _ForwardIter 
3 uninitialized_fill_n(_ForwardIter __first, _Size __n, const _Tp& __x)
4 {
5   return __uninitialized_fill_n(__first, __n, __x, __VALUE_TYPE(__first));
6 }

uninitialized_fill_n()会将迭代器_first开始处的n个元素初始化为x。它调用的__uninitialized_fill_n(__first, __n, __x, __VALUE_TYPE(__first))会判断迭代器_first所指对象是否是POD类型，如果是，则调用算法库的fill_n实现；否则一一构造。

6，总结

   STL的内存分配和迭代器是理解一切容器实现细节的基础，本文主要粗略地介绍了一下STL中两种内存分配器的分配机制，没有涉及很多alloc_traits的内容，关于这部分的内容会在迭代器部分详细介绍。

7，参考文献

   1）《STL源码剖析》第二章：空间配置器

   2）sgi-stl-3.3 源代码

声明：本文系作者原创，如转载请注明出处http://www.cnblogs.com/cobbliu/archive/2012/04/05/2431804.html

STL的设计非常巧妙，组件间互取短长，形成了一个世界，这是这个世界里的组件：
1. containers（容器）：所谓容器，是指存放数据的地方，将数据以一定的方法组织存放。根据不同的组织方式，可以把容器分为顺序容器，如vector、deque、list，关联容器，如set、map。Container是一种class template。
2. algorithm（算法）：各种常用不常用的算法如sort、copy、search等等。algorithm是一种function template。
3. iterator（迭代器）：迭代器是算法和容器之前的胶合剂，算法作用于容器之上，但算法以迭代器作为形参。从实现上看，迭代器是一种将operator*，operator++，operator--，operator->等指针相关操作予以重载的class template。所以容器都带有自己的迭代器，因为只有容器设计者才知道如何遍历自己的元素。
4. functors（仿函数）：行为类似函数，可作为算法的某种策略。从实现的角度来看，仿函数是一种重载了operator()的class或class template，它常常是算法的一个输入，类似于一种策略。
5. adapters（适配器）：用来形容容器、迭代器或仿函数接口的东西，有时候上面那些组件的行为可能跟我们想要的约束不大一样，于是给它们包装一下，使它们遵守一定的行为。
6. allocator（配置器）：负责空间配置与管理。从实现的角度来看，配置器是一种实现了动态空间配置、管理、空间释放的class template。

STL中的空间配置器，使用了两层架构，一层用于分类大块内存，一层用于管理小块内存。大块内存基本上是用完了就返回给操作系统，而小块内存则由内存池管理。另外，我们知道当我们new一个对象的时候，不仅仅是给了它内存，同时还可能调用了构造函数对这块内存进行了初始化（假如它是用户自定义类型），当我们delete一个对象的时候，同样，也可能是先调用了析构函数，然后再把内存还回去。调用构造、析构函数是要付出代价的，可是对于基本类型如int、long这种Plain-Old-Data，根本就不存在这样的构造/析构函数，便没有必要为它花费这种心思了。因此，为了便于分开处理这两种情况，STL把new/delete的执行过程分开成了两部分，一部分放在<stl_construct>里，用于在必要的时候调用构造、析构函数，一部分放在<stl_alloc>里，用于策略性地分配内存，跟内存分配管理相关的，还有一个<stl_uninitialized>，针对多个对象的初始化、复制做了一定的优化（当然也是以是否为POD来区分）。

<stl_construct>里定义了一个construct和两个destroy，construct基本上就是一个placement new，在指定内存上调用构造函数，而destroy有两个版本，一个是只析构单独一个对象的，直接调用了对应的~T()版本，另一个版本用于析构一段范围内的对象，这样的话如果对象是POD类型的，还for[i,j)地去执行，就是一种无谓的浪费了，因此，这个destroy将根据数据类型，决定调用特定版本的__destroy，如果是POD类型，则什么都不做，如果不是POD类型，则for[i,j)地去调用~T()。这些类型判断都是在编译时就确定的（通过__type_traits<T>::has_trivial_destructor），因此并不影响运行时效率。另外你肯定会想，为什么针对destroy这番考虑，针对construct却没有呢？反正当时我就是这么想的，后来发现原来这些事情交给uninitialized_fill、uninitialized_copy和unintialized_fill_n去做了，因为对象的初始化可能是经由constructor，也可能是经由copy constructor去执行呀。这里面，**_copy可能在必要的时候直接使用memmove来执行。

然后就是那个大头，空间分配器了。<stl_alloc.h>内定义了两个template，一个是__malloc_alloc_template，这是sgi stl的一级配置器，它的allocate()直接使用malloc()而deallocate()直接使用free()，同时，它模拟C++的set_new_handler()处理内存不足的状况。第二个是__default_alloc_template，它维护了16个free list，每个list上集合着大小分别为8，16，24，...128大小的内存块。内存池以malloc()配置而得，如果内存不足，转调用第一级配置器，因为那里设置了内存不足的处理程序。如果请求的内存块大小大于128bytes，就转调用第一级配置器。另外定义了两个alloc，一个是debug_alloc，每次配置一块内存时，都会配置比需求多8byte的空间以存储空间大小，通过assert语句来检查会不会内存溢出。另一个是simple_alloc，定义了两个版本的allocate和deallocate，它们都只是单纯的转调用。sgi stl容器全都使用simple_alloc接口。free-list的节点巧妙地使用了一个union结构来管理链表：

Cpp代码

union obj{
union obj* free_list_link; //当作为自由链表的一个结点时，存储其下一个节点的地址
char client_date[1]; //当其作为返回值时，返回的正好是分配内存的首地址
}

每次配置器需要向系统要内存的时候，都不是按客户需求向系统申请的，而是一次性向系统要了比需求更多的内存，放在内存池里，有一个free_start和free_end指示剩余的空间（也就是说内存池剩余的空间都是连续的，因此每次重新向system heap要空间的时候，都会把原先内存池里没用完的空间分配给合适的free list。）当free-list中没有可用区块了的时候，会首先从内存池里要内存，同样，也不是以按客户需求要多少块的，而是一次可能会要上20块，如果内存池内空间允许的话，可能会得到20个特定大小的内存，如果内存池给不了那么多，那么就只好尽力给出；如果连一个都给不出，那么就要开始向系统即system heap要空间了。换算的标准是bytes_to_get=2*total_bytes+ROUND_UP(heap_size>>4)。这个时候使用的是malloc，如果没成功，就尝试着从大块一点的freelist那里要一个来还给内存池，如果还是不行，那么会调用第一级空间配置器的malloc::allocate，看看out-of-memory机制能做点什么不。

总结起来整个过程大概是这样的，假设我们向系统要x大小的内存，
（1）x大于128byte，用第一级配置器直接向系统malloc，至于不成功的处理，过程仿照new，通过set_new_handler来处理，直到成功返回相应大小的内存或者是抛出异常或者是干脆结束运行；
（2）x小于128byte，用第二级配置器向内存池相应的free_list要内存，如果该freelist上面没有空闲块了，
（2.1）从内存池里面要内存，差不多要的是<=20个相应freelist大小的块，如果要不到：
（2.2）从系统的heap里面要内存给到内存池，换算的标准是bytes_to_get=2*total_bytes+ROUND_UP(heap_size>>4)，这时使用的是系统的malloc，如果要不到：
（2.3）从比较大的freelist那里要内存到内存池，如果还是要不到：
（2.4）从系统的heap里面要内存给到内存池，换算标准跟2.2一样，但是这时候使用的是第一级配置器的allocate，主要是看看能不能通过out_of_memory机制得到一点内存。所以，freelist总是从内存池里要内存的，而内存池可能从freelist也可能从系统heap那里要内存。
sgi stl的alloc的主要开销就在于管理这些小内存，管理这些小内存的主要开销就在于，每次freelist上的内存块用完了，需要重新要空间，然后建立起这个list来。freelist上的内存，会一直保留着直到程序退出才还给系统。但这不会产生内存泄漏，一来是管理的都是小内存，二来是，占用的内存只会是整个程序运行过程中小内存占用量最大的那一刻所占用的内存。

SGI STL的alloc是一种内存管理机制，用于管理小内存块的分配，以减少内存碎片。后来我又看了另外一些内存管理机制（利用对象管理资源），包括智能指针的RAII，用于复杂但可能过程不是很久的算法内存管理AutoFreeAlloc，ScopeAlloc，以及boost中的pool跟object_pool。总的来说，内存管理的基本要求就是：不重不漏，既不重复delete，也不漏掉delete。
首先是智能指针，智能指针的基本思想是利用编译器在对象离开作用范围后自动调用析构函数来实现内存的自动释放，即通过对象来管理资源，把指针封装成一个对象，在其构造、析构、赋值函数中，实现对内存的管理。最简单的是auto_ptr，你把指针给了它，它就在析构的时候把指针指向的内存释放掉。可是我要把指针赋值给其他人怎么办？它说，哦，那没办法，被赋值的那个人接管了你的内存，你就退休指向NULL吧。这显然给指针的应用带来了相当大的不便，想想，在用裸指针时，用temp = head, head = head->next这样的状况是多么常见，用容器存放指针也是常有的事（存放到容器是一种赋值行为）。那就使用share_ptr吧。share_ptr中记录了一块内存的reference_count，在构造时其为一，在复制构造、赋值时修改reference_count，在析构时reference_count--，如果reference_count为0，那么就把内存给释放了。在多线程中，reference_count便成了一个竞争资源，因此可能会成为瓶颈。另外，所谓的这个“把内存给释放了”，其实也可能只是一种指定的操作，例如把它放到freelist去啊之类的，是可以自定义的。

接下来的内容我基本是从许式伟的博客（http://blog.csdn.net/xushiweizh/article/category/265099）看到的，因为AutoFreeAlloc和ScopeAlloc是他们团队做的内存管理库中的一部分。AutoFreeAlloc的基本思想可以用下图表示：

因此在一般情况下，使用AutoFreeAlloc为底层的NEW的开销就是对m_end的移动，或者重新开辟一块大内存进行管理，而这种NEW不需要DELETE，当算法结束的时候通过clear把AutoFreeAlloc管理的内存链表释放掉。

情况一：

情况二：

情况三：

ScopeAlloc跟AutoFreeAlloc的区别主要在于，AutoFreeAlloc是直接从系统申请的内存，用的是malloc/free，而ScopeAlloc是从内存池里申请的内存，用的是使用的内存池ProxyBlockPool::allocate/deallocate。

Cpp代码

typedef AutoFreeAllocT<ProxyBlockPool> ScopeAlloc;
typedef AutoFreeAllocT<DefaultStaticAlloc> AutoFreeAlloc;

内存池
经典的内存池技术是一种用于分配大小相同的小对象的技术，它通常涉及两个常量：MemBlockSize和ItemSize，就是说，每次申请的内存大小固定为ItemSize，当池中没有空间的ItemSize块时，从系统heap中申请MemBlockSize大小的内存块，跟原先池中的大小块串在一起，而MemBlockSize的块中也要相应建立起一条freelist，因此，内存池还涉及另外两个指针变量：pFreeNodeHeader，指向freelist的头部，当需要一个对象时，从pFreeNodeHeader取下一个，当然，如果pFreeNodeHeader为空，说明没有空闲的块了；另一个为pMemBlockHeader，最后要把所有的内存释放时，从pMemBlockHeader处开始释放。
boost::pool对经典内存池的改进：
（1）MemBlockSize不再是固定的，而是采用了预测模型，第一次申请时，MemBlockSize=ItemSize*32，第二次为ItemSize*64等等，就像std::vector的增长模型。
（2）增加了ordered_free(void* p)。ordered_free与free的差别在于，free的时候，只是简单地把这个item放回freelist的头部，而ordered_free假设这些item是有一定的顺序的，因此返回item的时候会找到一个合适的位置放置item（指的是在链表中的位置）。
boost::object_pool支持手工释放内存和自动回收内存（并自动执行析构函数），从而保证当它离开作用范围后不会产生内存泄漏，为了判断block中的节点是否为free，要求其在获取、释放内存的时候必须使用ordered_malloc和ordered_free。这样子，当object_pool离开作用范围而调用析构函数~object_pool时，它遍历所有的内存块MemBlock，并遍历其中所有结点，如果该结点不出现在free_list中，那么它就是未被释放的，因此要执行该结点的析构函数，如果free跟malloc是有序的，我们就能在线性时间内完成自动释放。

STL中给我印象比较深的就是这个allocator，因此也才会额外去看了这么些内存管理的技术。其他的，印象比较深的就是里面一些精简的算法了。

1. 好多废话

在分析完nginx的内存池之后，也想了解一下C++的内存管理，于是就很自然得想到STL。

STL是一个重量级的作品，据说当时的出现，完全可以说得上是一个划时代意义的作品。

泛型、数据结构和算法的分离、底耦合、高复用… 啊，废话不多说了，再说下去让人感觉像

王婆卖瓜了。

啊，还忘了得加上两位STL大师的名字来聊表我的敬意了。泛型大牛Alexander Stepanov

和 Meng Lee（李梦--让人浮想的名字啊）。

2. SLT 内存的分配

以一个简单的例子开始。

我们想知道的时候，当vec声明的时候和push_back的时候，是怎么分配的。

其实对于一个标准的STL 容器，当Vetor<int> vec 的真实语句应该是 vetor<int, allocator<int>>vec，

allocator是一个标准的配置器，其作用就是为各个容器管理内存。这里需要注意的是在SGI STL中，有两个

配置器：allocator(标准的)和alloc(自己实现的，非常经典，这篇文章的主要目的就是为了分析它)。

3. 一个标准的配置器

要写一个配置器并不是很难，最重要的问题是如何分配和回收内存。下面看下一个标准（也许只能称为典型）

的配置器的实现：

注：代码有比较大的改动，因为主要是为了理解。

在使用的时候，只需这样vector<int, SLD::allocator<int>>vec; 即可。

vetor便会自动调用我们的配置器分配内存了。

要自己写个配置器完全可以以这个类为模板。而需要做的工作便是写下自己的 allocate和deallocate即可。

其实SGI的allocator 就是这样直接调用operator new 和::operator delete实现的，不过这样做的话效率就很

差了。

4. SGI STL中的alloc

4.1 SGI 中的内存管理

SGI STL默认的适配器是alloc，所以我们在声明一个vector的时候实际上是这样的

vetor<int, alloc<int>>vec. 这个配置器写得非常经典，下面就来慢慢分析它。

在我们敲下如下代码：

CSld* sld = new CSld;

的时候其实干了两件事情：（1）调用::operator new 申请一块内存（就是malloc了）

（2）调用了CSld::CSld();

而在SGI中，其内存分配把这两步独立出了两个函数：allocate 申请内存， construct 调用构造函数。

他们分别在<stl_alloc.h>, <stl_construct.h> 中。

SGI的内存管理比上面所说的更复杂一些，首先看一些SGI内存管理的几个主要文件，如下图所示：

<图1. SGI 内存管理>

在stl_construct.h中定义了两个全局函数construct()和destroy()来管理构造和析构。

在stl_allo.h中定义了5个配置器，我们现在关心的是malloc_alloc_template(一级)

和default_alloc_template(二级)。在SGI中，如果用了一级配置器，便是直接使用了

malloc()和free()函数，而如果使用了二级适配器，则如果所申请的内存区域大于128b,

直接使用一级适配器，否则，使用二级适配器。

而stl_uninitialized.h中，则定义了一下全局函数来进行大块内存的申请和复制。

是不是和nginx中的内存池很相似啊，不过复杂多了。

4.2一级配置器：__malloc_alloc_template

上面说过， SGI STL中，如果申请的内存区域大于128B的时候，就会调用一级适配器，

而一级适配器的调用也是非常简单的，直接用malloc申请内存，用free释放内存。

可也看下如下的代码：

好了，很简单把，只是对malloc，free, realloc简单的封装。

4.3 二级配置器：__default_alloc_template

按上文所说的，SGI的 __default_alloc_template 就是一个内存池了。

我们首先来看一下它的代码：

我们最关心的有三点：1. 内存池的创建。2.内存的分配。 3. 内存的释放。

4.3.1 SGI内存池的结构

在分析内存池的创建之前我们首先需要看下SGI内存池的结构。

在__default_alloc_template 内部，维护着这样一个结构体：

static _Obj*  _S_free_list[]; //我就是这样用的

其实一个free_list 就是一个链表，如下图所示：

<图2. free_list的链表表示>

这里需要注意的有两点：

一：SGI 内部其实维护着16个free-list，对应管理的大小为8,16,32……128.

二：_Obj是一个union而不是sturct, 我们知道，union中的所有成员的引用在内存中的位置都是

相同的。这里我们用union就可以把每一个节点需要的额外的指针的负担消除掉。

4.3.2 二级配置器的内存分配：allocate

比如现在我要申请一块30B的空间，我要怎么申请呢？

首先会呼叫二级配置器，调用 allocate，在allocate函数之内，从对应的32B的链表中拿出空间。

如果对应的链表空间不足，就会先用填充至32B，然后用refill()冲洗填充该链表。

相应的代码如下：

下面画了一张图来帮助理解：

<图3. GetMemory>

4.3.3 二级配置器的内存释放：allocate

有内存的分配，当然得要释放了，下面就来看看是如何释放的：

4.3.4 二级配置器的内存池：chunk_alloc

前面说过，在分配内存时候如果空间不足会调用_S_refill函数，重新填充空间（ps:如果这是第一个的话，

就是创建了）。而_S_refill最终调用的又是chunk_alloc函数从内存池中提取内存空间。

首先我们看一下它的源代码：

区间[_S_start_free, _S_end_free)便是内存池的总空间（参考类：__default_alloc_template的定义）。

当申请一块内存时候，如果内存池总内存量充足，直接分配，不然就各有各的处理方法了。

下面举一个例子来简单得说明一下：

1. 当第一次调用chunk_alloc(32,10)的时候，表示我要申请10块__Obje(free_list)，每块大小32B，

此时，内存池大小为0，从堆空间申请32*20的大小的内存，把其中32*10大小的分给free_list[3]（参考图3）。

2. 我再次申请64*5大小的空间，此时free_list[7]为0，它要从内存池提取内存，而此时内存池剩下320B，

刚好填充给free_list[7]，内存池此时大小为0。

3. 我第三次神奇一耳光72*10大小的空间，此时free_list[8]为0，它要从内存池提取内存，此时内存池空间

不足，再次从堆空间申请72*20大小的空间，分72*10给free_list用。

整一个SGI内存分配的大体流程就是这样了。