SGI STL二级空间配置器重要成员解读

为了。所以对于进行管理。

SGI STL提供了一级空间配置器和二级空间配置器，而SGI STL一级空间配置器也和STL标准模板库的实现是一样的（都是malloc/free）

其中一级空间配置器allocator采用malloc和free来管理内存，和C++标准库中提供的allocator是一样的，如果我们频繁对内存进行申请和释放，每次都使用malloc和free，效率就很低了 但其二级空间配置器allocator采用了基于freelist自由链表原理的 内存池机制 实现内存管理，只管理不大于128字节的小块内存分配

vector的声明

template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class vector : protected _Vector_base<_Tp, _Alloc> 

可以看到，容器的默认空间配置器是__STL_DEFAULT_ALLOCATOR( _Tp)，它是一个宏定义，如下：

# ifndef __STL_DEFAULT_ALLOCATOR
#   ifdef __STL_USE_STD_ALLOCATORS
#     define __STL_DEFAULT_ALLOCATOR(T) allocator< T >
#   else
#     define __STL_DEFAULT_ALLOCATOR(T) alloc
#   endif
# endif

从上面可以看到__STL_DEFAULT_ALLOCATOR通过宏控制有两种实现，一种是allocator< T >，另一种是alloc，这两种分别就是SGI STL的一级空间配置器和二级空间配置器的实现。

template <int __inst>
class __malloc_alloc_template    // 一级空间配置器内存管理类 -- 通过malloc和free管理内
存

template <bool threads, int inst>
class __default_alloc_template {  // 二级空间配置器内存管理类 -- 通过自定义内存池实现内
存管理

一级空间配置器

//stl_alloc.h
//一级空间配置器的实现，类似与c++ STL的空间配置器
template <int __inst>
class __malloc_alloc_template {
    //...
	static void* allocate(size_t __n)
 	{
    	void* __result = malloc(__n);	//底层通过malloc分配内存
    	if (0 == __result) __result = _S_oom_malloc(__n);
    	return __result;
    }
	static void deallocate(void* __p, size_t /* __n */)
	{
        free(__p);	//使用free释放内存
  	}
};

typedef __malloc_alloc_template<0> malloc_alloc;
typedef malloc_alloc alloc;

#ifdef __STL_USE_STD_ALLOCATORS

template <class _Tp>
class allocator {
	typedef alloc _Alloc;          // The underlying allocator.
	//...
    _Tp* allocate(size_type __n, const void* = 0) {
    return __n != 0 ? static_cast<_Tp*>(_Alloc::allocate(__n * sizeof(_Tp))) 
                    : 0;
  	}
	// __p is not permitted to be a null pointer.
    void deallocate(pointer __p, size_type __n)
    { _Alloc::deallocate(__p, __n * sizeof(_Tp)); }
    
	void construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); }
	void destroy(pointer __p) { __p->~_Tp(); }
};

//C++ STL空间配置器
//容器的空间配置器
template <typename T>
struct Allocator
{
	T* allocate(size_t size)//只负责内存开辟
	{
		return (T*)malloc(sizeof(T) * size);
	}
	void deallocate(void *p)//只负责内存释放
	{
		free(p);
	}
	void construct(T *p, const T &val)//已经开辟好的内存上，负责对象构造
	{
		new (p) T(val);//定位new，指定内存上构造val，T(val)拷贝构造
	}
	void destroy(T *p)//只负责对象析构
	{
		p->~T();//~T()代表了T类型的析构函数
	}
};

二级空间配置器

//stl_alloc.h
# define __NODE_ALLOCATOR_THREADS true
template <bool threads, int inst>
class __default_alloc_template {
	//通过内存池的实现管理内存
};

typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;

• __NODE_ALLOCATOR_THREADS 表示节点是否支持线程安全

二级空间配置器重要成员解读


template <bool threads, int inst>
class __default_alloc_template {
	enum {_ALIGN = 8};	//对齐8字节		  
	// 数组对应位置挂的内存池最大的__chunk块的的大小为128B，即freelist有16个元素，如果大于128字节就相当于是大块内存，不通过内存池管理，还是用malloc、free管理
	enum {_MAX_BYTES = 128};	//最大字节数128字节	  
	enum {_NFREELISTS = 16};   // _MAX_BYTES/_ALIGN	自由链表的个数   

     union _Obj {
        union _Obj* _M_free_list_link;//这个可以看成节点的next域，指向下一个空闲chunk块的起始地址
        char _M_client_data[1];    /* The client sees this. */
     };
    
    
    //多线程对于堆上和数据段上的数据一般都加volatile修饰，防止线程对数据缓存，
	//不能及时看到其他线程对共享数据的修改
    //自由链表大小_NFREELISTS = 16，存储类型为_Obj*
    static _Obj* __STL_VOLATILE _S_free_list[_NFREELISTS]; 
    
    
    // 记录内存块的分配状态，Chunk allocation state.
	// 全部会初始化为0
	static char* _S_start_free;
	static char* _S_end_free;
	static size_t _S_heap_size;    // 向OS申请的所有内存大小
    
    //...
};

template <bool __threads, int __inst>
char* __default_alloc_template<__threads, __inst>::_S_start_free = 0;//nullptr

template <bool __threads, int __inst>
char* __default_alloc_template<__threads, __inst>::_S_end_free = 0;//nullptr

template <bool __threads, int __inst>
size_t __default_alloc_template<__threads, __inst>::_S_heap_size = 0;


//静态成员类外初始化，初始化自由链表
template <bool __threads, int __inst>
typename __default_alloc_template<__threads, __inst>::_Obj* __STL_VOLATILE
//free-list的16个元素初始化为0（nullptr）
__default_alloc_template<__threads, __inst> ::_S_free_list[
# if defined(__SUNPRO_CC) || defined(__GNUC__) || defined(__HP_aCC)
    _NFREELISTS
# else
    __default_alloc_template<__threads, __inst>::_NFREELISTS
# endif
] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };
// The 16 zeros are necessary to make version 4.1 of the SunPro
// compiler happy.  Otherwise it appears to allocate too little
// space for the array.

• chunk 块

• 如果_S_start_free和_S_end_free相等，则需要像OS申请内存

• _Obj 的结构，每个chunk块的头信息，会指向下一个空闲chunk块的起始地址 chunk块：就是_S_free_list每个元素下面挂的8、16、24字节的内存块