整个STL的操作对象(所有的数值)都存放在容器之内,而容器一定需要配置空间以置放资料。不先掌握空间配置器的原理,难免在阅读其它STL组件的实现时处处遇到挡路石。空间不一定是内存,空间也可以是磁盘或其它辅助存储介质。allocator可以写一个直接向硬盘取空间。
根据STL的规范,以下是 allocator的必要接口
allocator:: value_type
allocator:: pointer
allocator:: const pointer
allocator:: reference
allocator: const_reference
allocator::size_type
allocator: difference_type
allocator: rebind
在STL中，容器的定义中都带有一个模板参数，
template <class T, class Alloc=alloc> //默认使用alloc空间配置器class vector{…}
具备次配置力(sub- b-allocation)的SGI空间配置器
SGI STL的配置器与众不同,也与标准规范不同,其名称是 alloc而非allocator,而且不接受任何参数。换句话说,如果你要在程序中明白采用SGI配置器,则不能采用标准写法:
vector<int,std:: allocator>iv;// in VC or CB
必须这么写:
vector<int,std:: alloc>iv;// in GCC
SGI标准空间配置器， std::allocator
SGI中定义了一个符合部分标准、名为allocator的配置器，但从不从不使用它。主要效率不佳，只是简单包装了下::operator new 和 ::operator delete
STL标准规格告诉我们,配置器定义于之中, SGI的memory内含以下两个文件:
#include <stlalloc. h>//负责内存空间的配置与释放
#include <stl_construct. h>//负责对象内容的构造与析构
内存空间的配置/释放与对象内容的构造/析构,分别着落在这两个文件身上。
其中< construct.h>定义有两个基本函数:构造用的 construct()和析构用的 destroy()。
template <class T1, class T2>
inline void construct(T1* p, const T2& value){
new (p) T1(value); //placement new; 调用T1::T1(value);
}
// 第一个版本，接受一个指针
template <class T>
inline void destory(T* pointer){
pointer->~T();
}
// 第二个版本，接受了个迭代器， 根据元素的类型进行删除
template <class ForwardIterator, class T>
inline void destory(ForwardIterator first, ForwardIterator last, T*){
_destory_aux(first, last, value_type(first));
}
//数值类型有non-trivial destructor
template<class ForwardIterator>
inline void _destroy_aux(ForwardIterator first, ForwardIterator last, __false_type){
for(; first<last; ++first)
destroy(&*first);
}
//数值类型有trival destructor
template<class ForwardIterator>
inline void _destroy_aux(ForwardIterator first, ForwardIterator last, __true_type){
// 针对迭代器为char*和wchar*的特化版
inline void destroy(char*, char*){}
inline void destroy(wchar_t*, wchar_t*){}
}
空间配置与释放
设计理念
1. 向system heap要求空间
2. 考虑多线程多状态
3. 考虑内存不足的应对措施
4. 考虑过多“小型区块”可能造成的内存碎片问题
5. alloc定义了两级的空间配置器
第一级是对malloc/free简单的封装。 C++内存配置基本操作::operator new ,::operator delete相当于C的malloc()和free(),SGI正是使用malloc()和free()完成空间配置的。
而为了解决小型区块可能造成的内存破碎问题，alloc采用了第二级空间配置器。第二级空间配置器在分配大块内存(大于128bytes)时，会直接调用第一级空间配置器，而分配小于128bytes的内存时，则使用内存池跟free_list进行内存分配/管理。
空间配置函数 allocate()
身为一个配置器, default_alloc_template拥有配置器的标准接口函数 allocate()。此函数首先判断区块大小,大于128 8 bytes就调用第一级配置器,小于128 8 bytes就检查对应的 free_list.如果 free list之内有可用的区块,就直接拿来用,如果没有可用区块,就将区块大小上调至8倍数边界,然后调用refi11(),准备为 free_list重新填充空间。
空间释deallocate放函数(),身为一个配置器, default_alloc_template拥有配置器标准接口函数 deallocate()。该函数首先判断区块大小,大于128 8 bytes就调用第一级配置器,小于12 88 bytes就找出对应的 free list,将区块回收。
重新填充 free_lists
allocate()：当它发现 free_list中没有可用区块了时,就调用 refill(),准备为 free_list重新填充空间新的空间将取自内存池(经由 chunk_ alloc()完成)。缺省取得20个新节点(新区块),但万一内存池空间不足,获得的节点数(区块数)可能小于20；
STL定义五个全局函数作用于未初始化空间上，构造用的 construct()和析构用的 destroy()。其中uninitialized_fill( ), uninitialized_ copy, uninitialized_fill_n()使我们能够将内存的配置与对象的构造行为分离开来.具有“commit or rollback”语意:要么产生所有必要的元素,否则就不产生任何元素。
uninitialized_ copy (Input Iterator first, Inputiterator last, ForwardIterator result)
uninitialized_copy():如果作为输出目的地的[result, result+last–first))范围内的每一个选代器都指向未初始化区域,则 uninitialized copy()会使用 copy constructor给身为输入来源之first,last)范围内的每一个对象产生一份复制品,放进输出范围中。换句话说,针对输入范围内的每一个迭代器i,该函数会调用 construct(&*(result+(i-first-)),*i),产生的复制品,放置于输出范围的相对位置上。
uninitialized_fill( ):如果[first,last)范围内的每个迭代器都指向未初始化的内存,那么 uninitialized_fill( )会在该范围内产生x(式第三参数)的复制品。换句话说, uninitialized_fill_n( )会针对操作范围内的每个迭代器i,调用 construct(&*i,x),在i所指之处产生×的复制品。
uninitialized_fill_n():它会为指定范围内的所有元素设定相同的初值如果[first, first+n)]范围内的每一个迭代器都指向未初始化的内存,那么 uninitialized_fill_n()会调用 copy constructor,在该范围内产生(上式第三参数)的复制品。也就是说,面对first, first+n)范围内的每个迭代器i, uninitialized_fill_n()会调用 construct(&*i,x),在对应位置处产生的复制品。
来源：《STL源码剖析》