安徽网站设计费用,在线观看网址最新电影,2022年装修效果图大全,成都设计院有哪些空间配置器是STL六大组件之一#xff0c;它和其他五个组件相互配合#xff0c;起着很关键的作用。
容器#xff1a;各种数据结构、如vector、list、stack、deque、queue、set、map、unordered_map等等算法#xff1a;各种算法#xff0c;如sort、serach、copy、erase 提供…空间配置器是STL六大组件之一它和其他五个组件相互配合起着很关键的作用。
容器各种数据结构、如vector、list、stack、deque、queue、set、map、unordered_map等等算法各种算法如sort、serach、copy、erase 提供了对容器的增删查改等等迭代器迭代器通常用于遍历容器元素的时候扮演者容器和算法之间的胶合剂它封装了底层实现的细节、给用户提供了统一的接口去调用极大的降低了成本。适配器stack/queue/priority_queue中就有涉及到适配器它们的默认配接的就是deque像map和list中的反向迭代器也是适配器仿函数是实现了operator()的类这个类对象可以像函数一样去使用空间配置器顾名思义空间配置器就是给各个容器高效的管理空间的。
其实看源码的时候其中alloc就是空间配置器有了它就可以解决一下几个问题
频繁的像系统申请小块的内存这样容易造成内存碎片如果直接使用malloc new内存就可能有浪费申请空间失败在多线程中线程不安全的问题... SGI-STL空间配置器中主要是解决了频繁的像系统申请小块内存 在SGI版本中是以128为小块空间的边界将大于128的称之为一级空间配置器小于128的称为二级空间配置器 一级空间配置器__malloc_alloc_template
一级空间配置器其实就是对malloc和free的封装并增加了C中set_new_handle思想 如果申请成功了就直接返回失败就交给oom_malloc处理其中for里面就是检测用户是否设置了空间不足的应对措施如果没有设置抛异常模式为new方式
deallocate就是对free的封装 二级空间配置器__default_alloc_template
二级空间配置器专门负载处理小于128字节的小内存块在SGI版本中采用了内存池的方式去申请空间和释放空间。 其中有以下四个成员函数之所以定义为static是因为所有容器都是向同一块内存池中申请和释放的所以是共享的同一块空间。
可以发现SGI采用了哈希桶的方式提高用户获取空间的速度与高校管理。
内存池会先申请一块大的内存作为备用当需要的内存小于128的时候就会直接向哈希桶里面申请内存和释放内存这样就避免了频繁的向系统申请小内存所造成的内存效率低内存碎片的问题 SGI版本中内存池技术其实并没有以链表的方式对用户已经归还的空间进行管理因为用户申请内存的时候在查找方面其效率比较低所以采用了哈希桶的方式。在查找方面平均就做到了O1。但其实SGI中并没有用到128个桶它用到的是8 16 24...8的倍数。 那么这时候就有一个疑问
用户申请的空间通常是4的倍数为什么要内存对齐到8呢
我们设想这样一个场景如果我们申请40字节的空间但是二级空间配置器没有了malloc也失败了那么它就会像下一个有空间的内存比如64字节来用将64字节分为40和24分别挂到哈希桶中。 这也是为什么要对齐到8的一个优势 template bool threads, int inst
class __default_alloc_template {private:enum {__ALIGN 8}; //如果用户需要的内存不是8对齐到8enum {__MAX_BYTES 128}; //内存块的边界enum {__NFREELISTS __MAX_BYTES/__ALIGN}; //采用哈希桶保存小块内存映射时桶的个数//如果用户所需要的每次块不是8的倍数对齐到8的倍数static size_t ROUND_UP(size_t bytes) {return (((bytes) __ALIGN-1) ~(__ALIGN - 1));}
__PRIVATE://这里遵循了好的习惯要知道如果用宏对调试等都不方便而且联合体可以对空间利用到极致union obj {union obj * free_list_link;char client_data[1]; /* The client sees this. */};
private:
# ifdef __SUNPRO_CCstatic obj * __VOLATILE free_list[]; static obj * __VOLATILE free_list[__NFREELISTS]; //哈希函数根据用户提供的字节数找到对应的桶号static size_t FREELIST_INDEX(size_t bytes) {return (((bytes) __ALIGN-1)/__ALIGN - 1);}static void *refill(size_t n);static char *chunk_alloc(size_t size, int nobjs);//start_free和end_free用来标记内存池中大块内存的起始和末尾static char *start_free;static char *end_free;//用来记录该空间配置器已经向系统索要了多少的内存static size_t heap_size; 二级空间配置器的逻辑如下 可以看到耳机空间配置器申请空间的时候会根据空间是否大于128来进行划分如果小于128字节那么就会根据申请字节找到对应的哈希桶中去申请内存如果没有就向内存池中申请内存。
static void * allocate(size_t n)
{obj * __VOLATILE * my_free_list;obj * __RESTRICT result;// 检测用户所需空间释放超过128(即是否为小块内存)if (n (size_t) __MAX_BYTES) {// 不是小块内存交由一级空间配置器处理return (malloc_alloc::allocate(n));}// 根据用户所需字节找到对应的桶号my_free_list free_list FREELIST_INDEX(n);result *my_free_list;// 如果该桶中没有内存块时向该桶中补充空间if (result 0){// 将n向上对齐到8的整数被保证向桶中补充内存块时内存块一定是8的整数倍void *r refill(ROUND_UP(n));return r;}// 维护桶中剩余内存块的链式关系*my_free_list result - free_list_link;return (result);
}; 可以看到refill函数中当哈希桶中没有了内存块的时候这时候就需要向哈希桶中补充内存。我们会向内存池中一次性申请20个n字节的小内存这时有两个策略
1、如果我们只要了一块那么我们就直接给用户。
2、剩余的内存挂到哈希桶中 template int inst
void* __default_alloc_templateinst::refill(size_t n)
{// 一次性向内存池索要20个n字节的小块内存int nobjs 20;char * chunk chunk_alloc(n, nobjs);obj ** my_free_list;obj *result;obj *current_obj, *next_obj;int i;// 如果只要了一块直接返回给用户使用if (1 nobjs) return(chunk);// 找到对应的桶号my_free_list free_list FREELIST_INDEX(n);// 将第一块返回值用户其他块连接在对应的桶中result (obj *)chunk;*my_free_list next_obj (obj *)(chunk n);for (i 1; ; i) {current_obj next_obj;next_obj (obj *)((char *)next_obj n);if (nobjs - 1 i) {current_obj - free_list_link 0;break;} else{current_obj - free_list_link next_obj;}}return(result);
} 二级空间配置器的回收 可以看到如果空间没有大于128那么就会去找到对应的哈希桶中将内存挂到对应的下标中。 static void deallocate(void *p, size_t n)
{
obj *q (obj *)p;
obj ** my_free_list;
// 如果空间不是小块内存交给一级空间配置器回收
if (n (size_t) __MAX_BYTES){malloc_alloc::deallocate(p, n);return;}
// 找到对应的哈希桶将内存挂在哈希桶中
my_free_list free_list FREELIST_INDEX(n);
q - free_list_link *my_free_list;
*my_free_list q;
} 最后空间配置器是将容器结合起来的所有STL中的容器共用一份空间配置器都可以采用这样的方式来申请内存所以也可以理解为什么空间配置器都是静态的。
