学步园

由于std::set，std::multiset，std::map，std::multimap四种容器的插入删除操作性能高并且自动排序，在很多时候比如需要动态操作时往往会使用它们，然后由于容器内部使用的是节点，每次的插入或删除都要调用new或delete，往往容易造成碎片和性能下降，于是自定义的allocator出现了。

这篇文章的目的就是详细讲解std::allocator的内部结构，为实现自定义的allocator奠基。

贴出STL源码，通过增加注释讲解

// xmemory internal header (from <memory>)<br /> #pragma once<br /> #ifndef _XMEMORY_<br /> #define _XMEMORY_<br /> #ifndef RC_INVOKED<br /> #include <cstdlib><br /> #include <new><br /> #include <xutility></p> <p>// 说明：std::allocator将内存分配与释放、对象的构造与销毁独立出来，<br /> // 分别为内存分配、对象构造、对象销毁、内存释放。</p> <p> #pragma pack(push,_CRT_PACKING)<br /> #pragma warning(push,3)</p> <p> #define _ALLOCATOR allocator</p> <p>// 由于下方使用了operator new函数，因此需要先取消new的宏定义<br /> #pragma push_macro("new")<br /> #undef new</p> <p> #pragma warning(disable: 4100)</p> <p>#ifndef _FARQ /* specify standard memory model */<br /> #define _FARQ<br /> #define _PDFT ptrdiff_t<br /> #define _SIZT size_t<br /> #endif /* _FARQ */</p> <p>_STD_BEGIN<br /> // 这里是内存分配<br /> // TEMPLATE FUNCTION _Allocate<br /> template<class _Ty> inline<br /> _Ty _FARQ *_Allocate(_SIZT _Count, _Ty _FARQ *)<br /> { // allocate storage for _Count elements of type _Ty<br /> void *_Ptr = 0;</p> <p> if (_Count <= 0)<br /> _Count = 0;<br /> else if (((_SIZT)(-1) / sizeof (_Ty) < _Count)<br /> || (_Ptr = ::operator new(_Count * sizeof (_Ty))) == 0)<br /> _THROW_NCEE(bad_alloc, 0);</p> <p> return ((_Ty _FARQ *)_Ptr);<br /> }</p> <p> // 使用 placement new 进行对象的拷贝构造放置<br /> // TEMPLATE FUNCTION _Construct<br /> template<class _Ty1,<br /> class _Ty2> inline<br /> void _Construct(_Ty1 _FARQ *_Ptr, _Ty2&& _Val)<br /> { // construct object at _Ptr with value _Val<br /> void _FARQ *_Vptr = _Ptr;<br /> ::new (_Vptr) _Ty1(_STD forward<_Ty2>(_Val));<br /> }</p> <p> // 使用 placement new 进行对象的默认构造放置<br /> template<class _Ty1> inline<br /> void _Construct(_Ty1 _FARQ *_Ptr)<br /> { // construct object at _Ptr with default value<br /> void _FARQ *_Vptr = _Ptr;</p> <p> ::new (_Vptr) _Ty1();<br /> }</p> <p> // 对象销毁（析构函数）<br /> // TEMPLATE FUNCTION _Destroy<br /> template<class _Ty> inline<br /> void _Destroy(_Ty _FARQ *_Ptr)<br /> { // destroy object at _Ptr<br /> _Ptr->~_Ty();<br /> }</p> <p> // 内嵌字符串类型不用析构，特化版本供优化使用<br /> template<> inline<br /> void _Destroy(char _FARQ *)<br /> { // destroy a char (do nothing)<br /> }</p> <p>template<> inline<br /> void _Destroy(wchar_t _FARQ *)<br /> { // destroy a wchar_t (do nothing)<br /> }</p> <p> #ifdef _NATIVE_WCHAR_T_DEFINED<br /> template<> inline<br /> void _Destroy(unsigned short _FARQ *)<br /> { // destroy a unsigned short (do nothing)<br /> }<br /> #endif /* _NATIVE_WCHAR_T_DEFINED */</p> <p> // 根据指针类型选择是否为 POD 数据类型<br /> // TEMPLATE FUNCTION _Destroy_range<br /> template<class _Alloc> inline<br /> void _Destroy_range(typename _Alloc::pointer _First,<br /> typename _Alloc::pointer _Last, _Alloc& _Al)<br /> { // destroy [_First, _Last)<br /> _Destroy_range(_First, _Last, _Al, _Ptr_cat(_First, _Last));<br /> }</p> <p> // 非 POD 数据类型需要显示调用析构函数<br /> template<class _Alloc> inline<br /> void _Destroy_range(typename _Alloc::pointer _First,<br /> typename _Alloc::pointer _Last, _Alloc& _Al,<br /> _Nonscalar_ptr_iterator_tag)<br /> { // destroy [_First, _Last), arbitrary type<br /> for (; _First != _Last; ++_First)<br /> _Dest_val(_Al, _First);<br /> }</p> <p> // POD 数据类型不需要调用析构函数<br /> template<class _Alloc> inline<br /> void _Destroy_range(typename _Alloc::pointer _First,<br /> typename _Alloc::pointer _Last, _Alloc& _Al,<br /> _Scalar_ptr_iterator_tag)<br /> { // destroy [_First, _Last), scalar type (do nothing)<br /> }</p> <p> // TEMPLATE FUNCTION addressof<br /> template<class _Ty> inline<br /> _Ty * addressof(_Ty& _Val)<br /> { // return address of _Val<br /> return ((_Ty *) &(char&)_Val);<br /> }</p> <p> // TEMPLATE CLASS _Allocator_base<br /> template<class _Ty><br /> struct _Allocator_base<br /> { // base class for generic allocators<br /> typedef _Ty value_type;<br /> };</p> <p> // 偏特化，去除 const 属性<br /> // TEMPLATE CLASS _Allocator_base<const _Ty><br /> template<class _Ty><br /> struct _Allocator_base<const _Ty><br /> { // base class for generic allocators for const _Ty<br /> typedef _Ty value_type;<br /> };</p> <p> // TEMPLATE CLASS _ALLOCATOR<br /> template<class _Ty><br /> class _ALLOCATOR<br /> : public _Allocator_base<_Ty><br /> { // generic allocator for objects of class _Ty<br /> public:<br /> typedef _Allocator_base<_Ty> _Mybase;<br /> typedef typename _Mybase::value_type value_type;</p> <p> typedef value_type _FARQ *pointer;<br /> typedef value_type _FARQ& reference;<br /> typedef const value_type _FARQ *const_pointer;<br /> typedef const value_type _FARQ& const_reference;</p> <p> typedef _SIZT size_type;<br /> typedef _PDFT difference_type;</p> <p> // 由于在STL容器中allocator是以模板参数传入的，而对于节点型容器，<br /> // 如list, set, map，需要重新绑定数据结构，因而 rebind 便会用到<br /> template<class _Other><br /> struct rebind<br /> { // convert this type to _ALLOCATOR<_Other><br /> typedef _ALLOCATOR<_Other> other;<br /> };</p> <p> pointer address(reference _Val) const<br /> { // return address of mutable _Val<br /> return ((pointer) &(char&)_Val);<br /> }</p> <p> const_pointer address(const_reference _Val) const<br /> { // return address of nonmutable _Val<br /> return ((const_pointer) &(char&)_Val);<br /> }</p> <p> _ALLOCATOR() _THROW0()<br /> { // construct default allocator (do nothing)<br /> }</p> <p> _ALLOCATOR(const _ALLOCATOR<_Ty>&) _THROW0()<br /> { // construct by copying (do nothing)<br /> }</p> <p> // 这里使用了 Coercion by Member Template 惯用法<br /> template<class _Other><br /> _ALLOCATOR(const _ALLOCATOR<_Other>&) _THROW0()<br /> { // construct from a related allocator (do nothing)<br /> }</p> <p> // 这里使用了 Coercion by Member Template 惯用法<br /> template<class _Other><br /> _ALLOCATOR<_Ty>& operator=(const _ALLOCATOR<_Other>&)<br /> { // assign from a related allocator (do nothing)<br /> return (*this);<br /> }</p> <p> // 内存释放<br /> void deallocate(pointer _Ptr, size_type)<br /> { // deallocate object at _Ptr, ignore size<br /> ::operator delete(_Ptr);<br /> }</p> <p> // 内存分配<br /> pointer allocate(size_type _Count)<br /> { // allocate array of _Count elements<br /> return (_Allocate(_Count, (pointer)0));<br /> }</p> <p> pointer allocate(size_type _Count, const void _FARQ *)<br /> { // allocate array of _Count elements, ignore hint<br /> return (allocate(_Count));<br /> }</p> <p> void construct(pointer _Ptr, const _Ty& _Val)<br /> { // construct object at _Ptr with value _Val<br /> _Construct(_Ptr, _Val);<br /> }</p> <p> // placement new<br /> void construct(pointer _Ptr, _Ty&& _Val)<br /> { // construct object at _Ptr with value _Val<br /> ::new ((void _FARQ *)_Ptr) _Ty(_STD forward<_Ty>(_Val));<br /> }</p> <p> template<class _Other><br /> void construct(pointer _Ptr, _Other&& _Val)<br /> { // construct object at _Ptr with value _Val<br /> ::new ((void _FARQ *)_Ptr) _Ty(_STD forward<_Other>(_Val));<br /> }</p> <p> // 对象销毁<br /> void destroy(pointer _Ptr)<br /> { // destroy object at _Ptr<br /> _Destroy(_Ptr);<br /> }</p> <p> _SIZT max_size() const _THROW0()<br /> { // estimate maximum array size<br /> _SIZT _Count = (_SIZT)(-1) / sizeof (_Ty);<br /> return (0 < _Count ? _Count : 1);<br /> }<br /> };</p> <p> // 特化版本，void 类型通常是无意义的<br /> // CLASS _ALLOCATOR<void><br /> template<> class _ALLOCATOR<void><br /> { // generic _ALLOCATOR for type void<br /> public:<br /> typedef void _Ty;<br /> typedef _Ty _FARQ *pointer;<br /> typedef const _Ty _FARQ *const_pointer;<br /> typedef _Ty value_type;</p> <p> // rebind 必须重定义<br /> template<class _Other><br /> struct rebind<br /> { // convert this type to an _ALLOCATOR<_Other><br /> typedef _ALLOCATOR<_Other> other;<br /> };</p> <p> _ALLOCATOR() _THROW0()<br /> { // construct default allocator (do nothing)<br /> }</p> <p> _ALLOCATOR(const _ALLOCATOR<_Ty>&) _THROW0()<br /> { // construct by copying (do nothing)<br /> }</p> <p> template<class _Other><br /> _ALLOCATOR(const _ALLOCATOR<_Other>&) _THROW0()<br /> { // construct from related allocator (do nothing)<br /> }</p> <p> template<class _Other><br /> _ALLOCATOR<_Ty>& operator=(const _ALLOCATOR<_Other>&)<br /> { // assign from a related allocator (do nothing)<br /> return (*this);<br /> }<br /> };</p> <p>// allocator内部由于没有数据，因而总是相同的功能<br /> template<class _Ty,<br /> class _Other> inline<br /> bool operator==(const allocator<_Ty>&,<br /> const allocator<_Other>&) _THROW0()<br /> { // test for allocator equality<br /> return (true);<br /> }</p> <p>template<class _Ty,<br /> class _Other> inline<br /> bool operator!=(const allocator<_Ty>& _Left,<br /> const allocator<_Other>& _Right) _THROW0()<br /> { // test for allocator inequality<br /> return (!(_Left == _Right));<br /> }</p> <p> // TEMPLATE FUNCTIONS _Cons_val AND _Dest_val<br /> template<class _Alloc,<br /> class _Ty1,<br /> class _Ty2><br /> void _Cons_val(_Alloc& _Alval, _Ty1 *_Pdest, _Ty2&& _Src)<br /> { // construct using allocator<br /> _Alval.construct(_Pdest, _STD forward<_Ty2>(_Src));<br /> }</p> <p>template<class _Alloc,<br /> class _Ty1><br /> void _Dest_val(_Alloc& _Alval, _Ty1 *_Pdest)<br /> { // destroy using allocator<br /> _Alval.destroy(_Pdest);<br /> }<br /> _STD_END</p> <p> #pragma pop_macro("new")</p> <p> #pragma warning(pop)<br /> #pragma pack(pop)</p> <p>#endif /* RC_INVOKED */<br /> #endif /* _XMEMORY_ */</p> <p>/*<br /> * This file is derived from software bearing the following<br /> * restrictions:<br /> *<br /> * Copyright (c) 1994<br /> * Hewlett-Packard Company<br /> *<br /> * Permission to use, copy, modify, distribute and sell this<br /> * software and its documentation for any purpose is hereby<br /> * granted without fee, provided that the above copyright notice<br /> * appear in all copies and that both that copyright notice and<br /> * this permission notice appear in supporting documentation.<br /> * Hewlett-Packard Company makes no representations about the<br /> * suitability of this software for any purpose. It is provided<br /> * "as is" without express or implied warranty.<br /> */</p> <p>/*<br /> * Copyright (c) 1992-2009 by P.J. Plauger. ALL RIGHTS RESERVED.<br /> * Consult your license regarding permissions and restrictions.<br /> V5.20:0009 */<br />

附注：

（1）注意 rebind 结构的使用和作用

（2）Coercion by Member Template 惯用法的使用和作用