SGI設計了雙層級配置器，第一級配置器直接使用malloc()和free()，第二級配置器則視情況采用不同的策略：當配置區塊超過128bytes時，視之為“足夠大”，便調用第一級配置器；當配置區小於128bytes時，視之為“過小”，為了降低額外負擔，便采用復雜的memory pool 整理方式，而不再求助於第一級配置器。整個設計究竟只開放第一級配置器，取決於_USE_MALLOC是否被定義：
1 #ifdef __USE_MALLOC 2 ... 3 typedef __malloc_alloc_template<0> malloc_alloc ; 4 typedef malloc_alloc alloc ; //令alloc為第一級配置器 5 #else 6 //令alloc為第二級配置器 7 typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS,0> alloc ; 8 #endif /*! __USE_MALLOC*/
SGI STL 第一級配置器
template<int inst>
class __malloc_alloc_template {…} ;
注釋：
1.allocate()直接使用malloc()，deallocate()直接使用free()。
2.模擬C++的set_new_handler()以處理內存不足的狀況。第一級配置器以malloc()，free()，realloc()等C函數執行實際的內存配置、釋放、重配置操作。
SGI STL 第二級配置器
template<bool threads,int inst>
class __default_alloc_template {…} ;
注釋：
1.維護16個自由鏈表(free lists)，負責16種小型區塊的次配置能力。內存池(memory pool)以malloc()配置而得。如果內存不足，轉調用第一級配置器。
2.如果需求區塊大於128byte，就轉調用第一級配置器。
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什麼都不做。
內存空間管理工具alloc
我想以自底向下的順序介紹一下STL的allocator。首先說說STL內建的兩種分配器，然後介紹STL如何封裝這兩種分配器對外提供統一的接口，最後用一個vector的例子看看容器如何使用這個allocator。
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異常。所以，內存不足的處理任務就交給類客戶去完成。
2 __default_alloc_template分配器
這個分配器采用了內存池的思想，有效地避免了內碎片的問題（順便一句話介紹一下內碎片和外碎片：內碎片是已被分配出去但是用不到的內存空間，外碎片是由於大小太小而無法分配出去的空閒塊）。如果申請的內存塊大於128bytes，就將申請的操作移交__malloc_alloc_template分配器去處理；如果申請的區塊大小小於128bytes時，就從本分配器維護的內存池中分配內存。分配器用空閒鏈表的方式維護內存池中的空閒空間，空閒鏈表大概類似於下面的形狀：
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的第二個模板參數傳遞要使用的分配器。
vector(用戶方式)使用STL分配器的代碼，可以看到vector的基類調用simple_alloc作為其分配器：
1 template <class _Tp, class _Alloc>
2 //cobbliu 注：STL vector 的基類
3 class _Vector_base {
4 public:
5 typedef _Alloc allocator_type;
6 allocator_type get_allocator() const { return allocator_type(); }
7
8 _Vector_base(const _Alloc&)
9 : _M_start(0), _M_finish(0), _M_end_of_storage(0) {}
10 _Vector_base(size_t __n, const _Alloc&)
11 : _M_start(0), _M_finish(0), _M_end_of_storage(0)
12 {
13 _M_start = _M_allocate(__n);
14 _M_finish = _M_start;
15 _M_end_of_storage = _M_start + __n;
16 }
17
18 ~_Vector_base() { _M_deallocate(_M_start, _M_end_of_storage - _M_start); }
19
20 protected:
21 _Tp* _M_start;
22 _Tp* _M_finish;
23 _Tp* _M_end_of_storage;
24
25 typedef simple_alloc<_Tp, _Alloc> _M_data_allocator;
26 _Tp* _M_allocate(size_t __n)
27 { return _M_data_allocator::allocate(__n); }
28 void _M_deallocate(_Tp* __p, size_t __n)
29 { _M_data_allocator::deallocate(__p, __n); }
30 };
基本內存處理工具
除了上面的內存分配器之外，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實現；否則一一構造。
