关于STL 中allocator的接口与实现,C++标准有比较清楚的定义:
http://en.wikipedia.org/wiki/Allocator_(C%2B%2B)
关于STL的allocator的标准接口阐述,可阅读另外一篇转载文章:allocator
-
SGI STL版本的allocator并没有遵守C++标准。它只提供simple_alloc类共container使用,设计的allocator名字叫做alloc,有二级配置器。第一级配置采用malloc/free来实现allocate/deallocate,第二级配置器采用针对申请的内存有特别处理,如果大小大于128字节,则转调用第一级配置来分配和释放内存,否则采用memory pool的方式来分配这些小额的内存。在SGI STL中,默认采用第二级内存分配器。具体的可以阅读侯捷的《STL源码剖析》第二章。
-
GNU C++的STL内部借鉴SGI STL的实现,不过它对外的的STL allocator严格遵守C++的标准:
看一下它的代码:(定义在bits/allocator.h文件中)
1 namespace std
2 {
3 template<typename _Tp>
4 class allocator;
5
6 template<>
7 class allocator<void>
8 {
9 public:
10 typedef size_t size_type;
11 typedef ptrdiff_t difference_type;
12 typedef void* pointer;
13 typedef const void* const_pointer;
14 typedef void value_type;
15
16 template<typename _Tp1>
17 struct rebind
18 { typedef allocator<_Tp1> other; };
19 };
20
21 /**
22 * @brief The "standard" allocator, as per [20.4].
23 *
24 * (See @link Allocators allocators info @endlink for more.)
25 */
26 template<typename _Tp>
27 class allocator: public ___glibcxx_base_allocator<_Tp>
28 {
29 public:
30 typedef size_t size_type;
31 typedef ptrdiff_t difference_type;
32 typedef _Tp* pointer;
33 typedef const _Tp* const_pointer;
34 typedef _Tp& reference;
35 typedef const _Tp& const_reference;
36
37 typedef _Tp value_type;
38
39 template<typename _Tp1>
40 struct rebind
41 { typedef allocator<_Tp1> other; };
42
43 allocator() throw() { }
44
45 allocator(const allocator& a) throw()
46 : ___glibcxx_base_allocator<_Tp>(a) { }
47
48 template<typename _Tp1>
49 allocator(const allocator<_Tp1>&) throw() { }
50
51 ~allocator() throw() { }
52
53 // Inherit everything else.
54 };
55
56 template<typename _T1, typename _T2>
57 inline bool
58 operator==(const allocator<_T1>&, const allocator<_T2>&)
59 { return true; }
60
61 template<typename _T1, typename _T2>
62 inline bool
63 operator!=(const allocator<_T1>&, const allocator<_T2>&)
64 { return false; }
65
66 // Inhibit implicit instantiations for required instantiations,
67 // which are defined via explicit instantiations elsewhere.
68 // NB: This syntax is a GNU extension.
69 #if _GLIBCXX_EXTERN_TEMPLATE
70 extern template class allocator<char>;
71
72 extern template class allocator<wchar_t>;
73 #endif
74
75 // Undefine.
76 #undef ___glibcxx_base_allocator
77 } // namespace std
template 类___glibcxx_base_allocator 定义在具体的平台相关的头文件中,例如i386-redhat-linux/bits/c++allocator.h:
1 // Define new_allocator as the base class to std::allocator.
2 #include <ext/new_allocator.h>
3 #define ___glibcxx_base_allocator __gnu_cxx::new_allocator
根据GCC/libstdc++的DOC: http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt04ch11.html, 知道
The current default choice for allocator
is __gnu_cxx::new_allocator
.
可以看出GNU c++的allocator其实采用的是new/delete-based allocation.
1 namespace __gnu_cxx
2 {
3 /**
4 * @brief An allocator that uses global new, as per [20.4].
5 *
6 * This is precisely the allocator defined in the C++ Standard.
7 * - all allocation calls operator new
8 * - all deallocation calls operator delete
9 *
10 * (See @link Allocators allocators info @endlink for more.)
11 */
12 template<typename _Tp>
13 class new_allocator
14 {
15 public:
16 typedef size_t size_type;
17 typedef ptrdiff_t difference_type;
18 typedef _Tp* pointer;
19 typedef const _Tp* const_pointer;
20 typedef _Tp& reference;
21 typedef const _Tp& const_reference;
22 typedef _Tp value_type;
23
24 template<typename _Tp1>
25 struct rebind
26 { typedef new_allocator<_Tp1> other; };
27
28 new_allocator() throw() { }
29
30 new_allocator(const new_allocator&) throw() { }
31
32 template<typename _Tp1>
33 new_allocator(const new_allocator<_Tp1>&) throw() { }
34
35 ~new_allocator() throw() { }
36
37
38 pointer
39 address(reference __x) const { return &__x; }
40
41 const_pointer
42 address(const_reference __x) const { return &__x; }
43
44 // NB: __n is permitted to be 0. The C++ standard says nothing
45 // about what the return value is when __n == 0.
46 pointer
47 allocate(size_type __n, const void* = 0)
48 { return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp))); }
49
50 // __p is not permitted to be a null pointer.
51 void
52 deallocate(pointer __p, size_type)
53 { ::operator delete(__p); }
54
55 size_type
56 max_size() const throw()
57 { return size_t(-1) / sizeof(_Tp); }
58
59 // _GLIBCXX_RESOLVE_LIB_DEFECTS
60 // 402. wrong new expression in [some_] allocator::construct
61 void
62 construct(pointer __p, const _Tp& __val)
63 { ::new(__p) _Tp(__val); }
64
65 void
66 destroy(pointer __p) { __p->~_Tp(); }
67 };
68
69 template<typename _Tp>
70 inline bool
71 operator==(const new_allocator<_Tp>&, const new_allocator<_Tp>&)
72 { return true; }
73
74
75 template<typename _Tp>
76 inline bool
77 operator!=(const new_allocator<_Tp>&, const new_allocator<_Tp>&)
78 { return false; }
79 } // namespace __gnu_cxx
80
不过GNU GCC提供了更多很有意思的定制allocator:__gnu_cxx::malloc_allocator(malloc_allocator.h), __gnu_cxx::bitmap_allocator (bitmap_allocator.h)
, __gnu_cxx::pool_allocator(pool_allocator.h)
, and __gnu_cxx::__mt_alloc(mt_allocator.h)
可通过--enable-libstdcxx-allocator 选项来开启其它的allocator,或者在定义一个container时,显式的描述模板参数表示用哪一个allocator:
std::vector <int, __gnu_cxx::malloc_allocator<int> > malloc_vector;
- MSVC的STL采用了P.J. Plauger的版本:allocator类定义在了include/xmemory文件中(以VS2008为例):
// TEMPLATE FUNCTION _Allocate
template<class _Ty> inline
_Ty _FARQ *_Allocate(_SIZT _Count, _Ty _FARQ *)
{ // check for integer overflow
if (_Count <= 0)
_Count = 0;
else if (((_SIZT)(-1) / _Count) < sizeof (_Ty))
_THROW_NCEE(std::bad_alloc, NULL);
// allocate storage for _Count elements of type _Ty
return ((_Ty _FARQ *)::operator new(_Count * sizeof (_Ty)));
}
// TEMPLATE FUNCTION _Construct
template<class _T1,
class _T2> inline
void _Construct(_T1 _FARQ *_Ptr, const _T2& _Val)
{ // construct object at _Ptr with value _Val
void _FARQ *_Vptr = _Ptr;
::new (_Vptr) _T1(_Val);
}
// TEMPLATE FUNCTION _Destroy
template<class _Ty> inline
void _Destroy(_Ty _FARQ *_Ptr)
{ // destroy object at _Ptr
_DESTRUCTOR(_Ty, _Ptr);
}
template<> inline
void _Destroy(char _FARQ *)
{ // destroy a char (do nothing)
}
template<> inline
void _Destroy(wchar_t _FARQ *)
{ // destroy a wchar_t (do nothing)
}
它的_Allocate模板函数直接采用全局的operator new来分配内存。
// TEMPLATE CLASS _Allocator_base
template<class _Ty>
struct _Allocator_base
{ // base class for generic allocators
typedef _Ty value_type;
};
// TEMPLATE CLASS _Allocator_base<const _Ty>
template<class _Ty>
struct _Allocator_base<const _Ty>
{ // base class for generic allocators for const _Ty
typedef _Ty value_type;
};
// TEMPLATE CLASS allocator
template<class _Ty>
class allocator
: public _Allocator_base<_Ty>
{ // generic allocator for objects of class _Ty
public:
typedef _Allocator_base<_Ty> _Mybase;
typedef typename _Mybase::value_type value_type;
typedef value_type _FARQ *pointer;
typedef value_type _FARQ& reference;
typedef const value_type _FARQ *const_pointer;
typedef const value_type _FARQ& const_reference;
typedef _SIZT size_type;
typedef _PDFT difference_type;
template<class _Other>
struct rebind
{ // convert an allocator<_Ty> to an allocator <_Other>
typedef allocator<_Other> other;
};
pointer address(reference _Val) const
{ // return address of mutable _Val
return (&_Val);
}
const_pointer address(const_reference _Val) const
{ // return address of nonmutable _Val
return (&_Val);
}
allocator() _THROW0()
{ // construct default allocator (do nothing)
}
allocator(const allocator<_Ty>&) _THROW0()
{ // construct by copying (do nothing)
}
template<class _Other>
allocator(const allocator<_Other>&) _THROW0()
{ // construct from a related allocator (do nothing)
}
template<class _Other>
allocator<_Ty>& operator=(const allocator<_Other>&)
{ // assign from a related allocator (do nothing)
return (*this);
}
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 _FARQ *)
{ // allocate array of _Count elements, ignore hint
return (allocate(_Count));
}
void construct(pointer _Ptr, const _Ty& _Val)
{ // construct object at _Ptr with value _Val
_Construct(_Ptr, _Val);
}
void destroy(pointer _Ptr)
{ // destroy object at _Ptr
_Destroy(_Ptr);
}
_SIZT max_size() const _THROW0()
{ // estimate maximum array size
_SIZT _Count = (_SIZT)(-1) / sizeof (_Ty);
return (0 < _Count ? _Count : 1);
}
};
// allocator TEMPLATE OPERATORS
template<class _Ty,
class _Other> inline
bool operator==(const allocator<_Ty>&, const allocator<_Other>&) _THROW0()
{ // test for allocator equality (always true)
return (true);
}
template<class _Ty,
class _Other> inline
bool operator!=(const allocator<_Ty>&, const allocator<_Other>&) _THROW0()
{ // test for allocator inequality (always false)
return (false);
}
// CLASS allocator<void>
template<> class _CRTIMP2_PURE allocator<void>
{ // generic allocator for type void
public:
typedef void _Ty;
typedef _Ty _FARQ *pointer;
typedef const _Ty _FARQ *const_pointer;
typedef _Ty value_type;
template<class _Other>
struct rebind
{ // convert an allocator<void> to an allocator <_Other>
typedef allocator<_Other> other;
};
allocator() _THROW0()
{ // construct default allocator (do nothing)
}
allocator(const allocator<_Ty>&) _THROW0()
{ // construct by copying (do nothing)
}
template<class _Other>
allocator(const allocator<_Other>&) _THROW0()
{ // construct from related allocator (do nothing)
}
template<class _Other>
allocator<_Ty>& operator=(const allocator<_Other>&)
{ // assign from a related allocator (do nothing)
return (*this);
}
};
参考:
STL allocator:1) wiki: http://en.wikipedia.org/wiki/Allocator_(C%2B%2B)2) stl allocator的介绍和基于malloc/free的allocator的实现:http://www.drdobbs.com/cpp/184403759?pgno=13. GNU GCChttp://gcc.gnu.org/libstdc++/http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/a01328_source.html4. LLVM 项目中的STL:http://libcxx.llvm.org/5. codeguru上的一篇文章:http://www.codeguru.com/cpp/cpp/cpp_mfc/stl/article.php/c4079/Allocators-STL.htm6. SGI STL的allocator的design:http://www.sgi.com/tech/stl/alloc.html7. 侯捷的池内春秋:池内春秋-侯捷.pdf原文链接: https://www.cnblogs.com/zerolee/archive/2012/06/17/2552457.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/52934
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!