STL - 内存分配器

标准内存分配器

定义STL容器时有一个可选参数allocator，缺省情况下使用STL自带的默认allocator类进行内存分配。allocator类在VS2013下由头文件xmemory0定义，间接由memory头文件引用。类声明节选如下：

//基类
template<typename _Ty>
struct _Allocator_base
{
	typedef _Ty value_type;
}

//allocator类
template<typename _Ty>
class allocator:public _Allocator_base<_Ty>
{
public:
	//STL标准需要的类型定义
	typedef allocator<_Ty> other;
	typedef _Allocator_base<_Ty> _Mybase;
	typedef typename _Mybase::value_type value_type;
	typedef value_type *pointer;
	typedef const value_type *const_pointer;
	typedef void *void_pointer;
	typedef const void *const_void_pointer;
	typedef value_type& reference;
	typedef const value_type& const_reference;
	typedef size_t size_type;
	typedef ptrdiff_t difference_type;
	
	//三个空构造函数
	allocator() {}
	allocator(const allocator<_Ty>&) {}
	template<typename _Other>
	allocator(const allocator<_Other>&) {}
	
	//rebind
	template<typename _Other>
	struct rebind
	{
		typedef allocator<_Other> other;
	}

	//其它成员函数
}

其中略难理解的是rebind结构，rebind只有一个other成员用来代表allocator<_Other>，这一步貌似有点多余，何不在需要的时候直接声明一个allocator<_Other>类型的分配器呢。STL的allocator是为容器服务的，要弄清楚设计者的目的，需要联系容器的实现。作为普通容器如vector和array等，它们的元素是直接存储的，而list等容器有一个中间存储结构node，且node与元素类型是有关的。在分配内存时需要为节点类型node<T>和元素类型T传入对应的allocator，而声明list时只传入了元素类型T，因此需要某种方法根据allocator<T>得到allocator<node<T>>，这时rebind的作用就体现出来了。附VS2013的部分list实现代码：

template<class _Ty,class _Alloc0>
	struct _List_base_types
	{
	typedef _Alloc0 _Alloc;
	typedef _List_base_types<_Ty, _Alloc> _Myt;

	typedef _Wrap_alloc<_Alloc> _Alty0;

	//向底层元素的rebind
	typedef typename _Alty0::template rebind<_Ty>::other _Alty;

	typedef typename _Get_voidptr<_Alty, typename _Alty::pointer>::type
		_Voidptr;
	typedef _List_node<typename _Alty::value_type,
		_Voidptr> _Node;
	
	//向节点类型的rebind
	typedef typename _Alty::template rebind<_Node>::other _Alnod_type;
	typedef typename _Alnod_type::pointer _Nodeptr;
	typedef _Nodeptr& _Nodepref;
	};

rebind算是一种比较巧妙的方法，在元素与中间结构之间创建某种联系，从而达到只需要一个模板参数即可创建多级内存分配器的目的。

STL标准要求的其它函数接口实现如下：

void deallocate(pointer _Ptr, size_type)
		{	// deallocate object at _Ptr, ignore size
		::operator delete(_Ptr);
		}

pointer allocate(size_type _Count)
		{	// allocate array of _Count elements
		return (_Allocate(_Count, (pointer)0));
		}

pointer allocate(size_type _Count, const void *)
		{	// allocate array of _Count elements, ignore hint
		return (allocate(_Count));
		}

void construct(_Ty *_Ptr)
		{	// default construct object at _Ptr
		::new ((void *)_Ptr) _Ty();
		}

void construct(_Ty *_Ptr, const _Ty& _Val)
		{	// construct object at _Ptr with value _Val
		::new ((void *)_Ptr) _Ty(_Val);
		}

template<class _Objty,
		class... _Types>
		void construct(_Objty *_Ptr, _Types&&... _Args)
		{	// construct _Objty(_Types...) at _Ptr
		::new ((void *)_Ptr) _Objty(_STD forward<_Types>(_Args)...);
		}

template<class _Uty>
		void destroy(_Uty *_Ptr)
		{	// destroy object at _Ptr
		_Ptr->~_Uty();
		}

与SGI的二级分配器实现相比更简单，直接调用全局的operator new和delete，没有额外的内存优化。