首页 > 代码库 > stl分析之allocator
stl分析之allocator
allocator封装了stl标准程序库的内存管理系统，标准库的string，容器，算法和部分iostream都是通过allocator分配和释放内存的。标准库的组件有一个参数指定使用的allocator类，比如vector的原型是：
template<typename _Tp, typename _Alloc = std::allocator<_Tp> >class vector : protected _Vector_base<_Tp, _Alloc>
第二个参数_Alloc指定使用的allocator，默认是std::allocator。我们也可以自己指定allocator
vector<int, __gnu_cxx::malloc_allocator<int> > malloc_vector;
将使用malloc_allocator分配释放内存。
GNU gcc实现了多种allocator，下面简单介绍几种allocator的作用，我的g++版本是4.8。
1. new_allocator
这是g++4.8默认使用的allocator，即 std::allocator使用的allocator，在头文件
/usr/include/c++/4.8/bits/allocator.h中定义了 std::allocator：
template<typename _Tp>class allocator: public __allocator_base<_Tp>
std::allocator使用的接口是由__allocator_base定义的，而后者在/usr/include/i386-linux-gnu/c++/4.8/bits/c++allocator.h定义为new_allocator：
# define __allocator_base __gnu_cxx::new_allocator
new_allocator只是简单地包装::operator new和operator delete，实现在/usr/include/c++/4.8/ext/new_allocator.h
pointer allocate(size_type __n, const void* = 0) { if (__n > this->max_size()) std::__throw_bad_alloc(); return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp))); } void deallocate(pointer __p, size_type) { ::operator delete(__p); }
并没有memory pool，所以现在如果还有程序因为使用了stl而出现内存没有回收的问题，那么一定是libc的cache没有释放，并不是stl的原因。
2. malloc_allocator
malloc_allocator直接包装malloc和free，定义在/usr/include/c++/4.8/ext/malloc_allocator.h头文件中，
pointer allocate(size_type __n, const void* = 0) { if (__n > this->max_size()) std::__throw_bad_alloc(); pointer __ret = static_cast<_Tp*>(std::malloc(__n * sizeof(_Tp))); if (!__ret) std::__throw_bad_alloc(); return __ret; } void deallocate(pointer __p, size_type) { std::free(static_cast<void*>(__p)); }
3. array_allocator
array_allocator并不调用new或者malloc从操作系统申请分配内存，而是直接使用已分配的内存。通过使用该allocator可以重用内存，效率很高。
array_allocator(array_type* __array = 0) _GLIBCXX_USE_NOEXCEPT : _M_array(__array), _M_used(size_type()) { } Pointer allocate(size_type __n, const void* = 0) { if (_M_array == 0 || _M_used + __n > _M_array->size()) std::__throw_bad_alloc(); pointer __ret = _M_array->begin() + _M_used; _M_used += __n; return __ret，_M_used}
_M_array指向已分配的内存块地址，_M_used指向空闲的地址位移，初始值为0，每分配一段内存后就将_M_used后移.当需要的内存量超出空闲内存大小时会抛出bad_alloc异常。
4. debug_allocator
可以包装任意其它的allocator，包括G++自带的或者用户自定义的，分配内存时多分配了一块内存保存申请的内存大小，释放时检查释放的内存大小是否和保存的值一样，不一样则抛出异常。具体的申请释放动作由被包装的allocator执行。
pointer allocate(size_type __n) { pointer __res = _M_allocator.allocate(__n + _M_extra); size_type* __ps = reinterpret_cast<size_type*>(__res); *__ps = __n; return __res + _M_extra; } void deallocate(pointer __p, size_type __n) { if (__p) { pointer __real_p = __p - _M_extra; if (*reinterpret_cast<size_type*>(__real_p) != __n) { throw std::runtime_error("debug_allocator::deallocate wrong size"); } _M_allocator.deallocate(__real_p, __n + _M_extra); } else throw std::runtime_error("debug_allocator::deallocate null pointer"); }
__ps中存储了当前申请分配的内存长度， deallocate时会检测释放的内存大小是否等于该值。debug_allocator可以检测内存是否存在泄露，代价是需要多分配用于debug的空间。
5. __pool_alloc
唯一一个带内存池的allocator，也是G++早期默认使用的allocator,侯捷的《stl源码剖析》第二章详细分析了其代码实现.原理就是为了减少内存碎片，当分配大于128byte的内存时直接调用operator new，而小于128byte的内存则从一个free list里面取，free list中的内存是可以重用的，程序运行期间不会归还给操作系统。过程比较复杂，有兴趣的同学可以参考《stl源码剖析》。
reference：
https://gcc.gnu.org/onlinedocs/gcc-4.9.1/libstdc++/manual/manual/memory.html#std.util.memory.allocato