网站建设电销,批量入侵wordpress,西安网站seo技术厂家,南宁网页制作设计营销一、什么是空间配置器 空间配置器 #xff0c;顾名思义就是为各个容器高效的管理空间#xff08;空间的申请与回收#xff09;的#xff0c;在默默地工作。虽然在常规使用 STL 时#xff0c;可能用不到它#xff0c;但站在学习研究的角度#xff0c;学习它的实现原理对…一、什么是空间配置器 空间配置器 顾名思义就是为各个容器高效的管理空间空间的申请与回收的在默默地工作。虽然在常规使用 STL 时可能用不到它但站在学习研究的角度学习它的实现原理对我们有很大的帮助。 二、为什么需要空间配置器 前面在模拟实现 vector、list、map、unordered_map 等容器时所有需要空间的地方都是通过 new 申请的虽然代码可以正常运行但是有以下不足之处 空间申请与释放需要用户自己管理容易造成内存泄漏。频繁向系统申请小块内存块容易造成内存碎片。频繁向系统申请小块内存影响程序运行效率。直接使用 malloc 与 new 进行申请每块空间前有额外空间浪费。申请空间失败怎么应对。代码结构比较混乱代码复用率不高。未考虑线程安全问题。 因此需要设计一块高效的内存管理机制。 三、SGI-STL空间配置器实现原理 以上提到的几点不足之处最主要还是频繁向系统申请小块内存造成的。那什么才算是小块内 存SGI-STL 以 128 作为小块内存与大块内存的分界线将空间配置器其分为两级结构一级空间 配置器处理大块内存二级空间配置器处理小块内存。 1、一级空间配置器 一级空间配置器原理非常简单直接对 malloc 与 free 进行了封装并增加了 C 中 set_new_handle 思想。 template int inst
class __malloc_alloc_template
{
private:static void *oom_malloc(size_t);
public:
// 对malloc的封装static void * allocate(size_t n){// 申请空间成功直接返回失败交由oom_malloc处理void *result malloc(n);if (0 result) result oom_malloc(n);return result;}// 对free的封装static void deallocate(void *p, size_t /* n */){ free(p);}// 模拟set_new_handle// 该函数的参数为函数指针返回值类型也为函数指针// void (* set_malloc_handler( void (*f)() ) )()static void (* set_malloc_handler(void (*f)()))(){void (* old)() __malloc_alloc_oom_handler;__malloc_alloc_oom_handler f;return(old);}
};// malloc申请空间失败时代用该函数
template int inst
void * __malloc_alloc_templateinst::oom_malloc(size_t n)
{void (* my_malloc_handler)();void *result;for (;;) {// 检测用户是否设置空间不足应对措施如果没有设置抛异常模式new的方式my_malloc_handler __malloc_alloc_oom_handler;if (0 my_malloc_handler){__THROW_BAD_ALLOC;}// 如果设置执行用户提供的空间不足应对措施(*my_malloc_handler)();// 继续申请空间可能就会申请成功result malloc(n);if (result)return(result);}
}typedef __malloc_alloc_template0 malloc_alloc; 2、二级空间配置器 二级空间配置器 专门负责处理 小于 128 字节 的小块内存。如何才能提升小块内存的申请与释放的 方式呢 SGI-STL 采用了内存池的技术来提高申请空间的速度以及减少额外空间的浪费采用 哈希桶 的方式来提高用户获取空间的速度与高效管理。 1内存池 内存池 就是先申请一块比较大的内存块已做备用当需要内存时直接到内存池中去当池中空间不够时再向内存中去取当用户不用时直接还回内存池即可。避免了频繁向系统申请小块内存所造成的效率低、内存碎片以及额外浪费的问题。 【思考】
当用户需要空间时能否直接从内存池中大块空间中直接截取为什么 对用户归还的空间能否直接拼接在大块内存前 对用户归还的空间如何进行管理 不断切割会有什么后果 2SGI-STL中二级空间配置器设计 SGI-STL中的二级空间配置器使用了内存池技术但没有采用链表的方式对用户已经归还的空间进 行管理因为用户申请空间时在查找合适的小块内存时效率比较低而是采用了哈希桶的方式进行 管理。那是否需要 128 桶个空间来管理用户已经归还的内存块呢 答案是不需要因为用户申请 的空间基本都是 4 的整数倍其他大小的空间几乎很少用到。因此SGI-STL 将用户申请的内存块 向上对齐到了 8 的整数倍请思考为什么是 8 的整数倍而不是 4。 3SGI-STL二级空间配置器之空间申请 a. 前期的准备 // 去掉代码中繁琐的部分
template int inst
class __default_alloc_template
{
private:enum {__ALIGN 8}; // 如果用户所需内存不是8的整数倍向上对齐到8的整数倍enum {__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:static obj * free_list[__NFREELISTS]; // 哈希函数根据用户提供字节数找到对应的桶号static size_t FREELIST_INDEX(size_t bytes){return (((bytes) __ALIGN-1)/__ALIGN - 1);}// start_free与end_free用来标记内存池中大块内存的起始与末尾位置static char *start_free;static char *end_free;// 用来记录该空间配置器已经想系统索要了多少的内存块static size_t heap_size;// ...
}; b. 申请空间 // 函数功能向空间配置器索要空间
// 参数n: 用户所需空间字节数
// 返回值返回空间的首地址
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);
}; c. 填充内存块 // 函数功能向哈希桶中补充空间
// 参数n小块内存字节数
// 返回值首个小块内存的首地址
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);
} d. 向内存池中索要空间 template int inst
char* __default_alloc_templateinst::chunk_alloc(size_t size, int
nobjs)
{// 计算nobjs个size字节内存块的总大小以及内存池中剩余空间总大小char * result;size_t total_bytes size * nobjs;size_t bytes_left end_free - start_free;// 如果内存池可以提供total_bytes字节返回if (bytes_left total_bytes) {result start_free;start_free total_bytes;return(result);} else if (bytes_left size){// nobjs块无法提供但是至少可以提供1块size字节内存块提供后返回nobjs bytes_left/size;total_bytes size * nobjs;result start_free;start_free total_bytes;return(result);} else{// 内存池空间不足连一块小块村内都不能提供// 向系统堆求助往内存池中补充空间// 计算向内存中补充空间大小本次空间总大小两倍 向系统申请总大小/16size_t bytes_to_get 2 * total_bytes ROUND_UP(heap_size 4);// 如果内存池有剩余空间(该空间一定是8的整数倍)将该空间挂到对应哈希桶中if (bytes_left 0) {// 找对用哈希桶将剩余空间挂在其上obj ** my_free_list free_list FREELIST_INDEX(bytes_left);((obj *)start_free) - free_list_link *my_free_list;*my_ree_list (obj *)start_free;}// 通过系统堆向内存池补充空间如果补充成功递归继续分配start_free (char *)malloc(bytes_to_get);if (0 start_free) {// 通过系统堆补充空间失败在哈希桶中找是否有没有使用的较大的内存块int i;obj ** my_free_list, *p;for (i size; i __MAX_BYTES; i __ALIGN){my_free_list free_list FREELIST_INDEX(i);p *my_free_list;// 如果有将该内存块补充进内存池递归继续分配if (0 ! p){*my_free_list p - free_list_link;start_free (char *)p;end_free start_free i;return(chunk_alloc(size, nobjs));}}// 山穷水尽只能向一级空间配置器求助// 注意此处一定要将end_free置空因为一级空间配置器一旦抛异常就会出问题end_free 0;start_free (char *)malloc_alloc::allocate(bytes_to_get);}// 通过系统堆向内存池补充空间成功更新信息并继续分配heap_size bytes_to_get;end_free start_free bytes_to_get;return(chunk_alloc(size, nobjs));}
} 4SGI-STL二级空间配置器之空间回收 // 函数功能用户将空间归还给空间配置器
// 参数p空间首地址 n空间总大小
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;
} 3、空间配置器的默认选择 SGI-STL 默认使用一级还是二级空间配置器通过 USE_MALLOC 宏进行控制 #ifdef __USE_MALLOCtypedef malloc_alloc alloc;
typedef malloc_alloc single_client_alloc;#else// 二级空间配置器定义#endif 在 SGI_STL 中该宏没有定义因此默认情况下 SGI_STL 使用二级空间配置器。 4、空间配置器的再次封装 在 C 中用户所需空间可能是任意类型的有单个对象空间有连续空间每次让用户自己计算所需空间总大小不是很友好因此 SGI-STL 将空间配置器重新再封装了一层 // T: 元素类型
// Alloc: 空间配置器
// 注意该类只负责申请与归还对象的空间不否则空间中对象的构造与析构
templateclass T, class Alloc
class simple_alloc
{
public:// 申请n个T类型对象大小的空间static T *allocate(size_t n){ return 0 n? 0 : (T*) Alloc::allocate(n * sizeof (T)); }// 申请一个T类型对象大小的空间static T *allocate(void){ return (T*) Alloc::allocate(sizeof (T));}// 释放n个T类型对象大小的空间static void deallocate(T *p, size_t n){ if (0 ! n) Alloc::deallocate(p, n * sizeof (T));}// 释放一个T类型对象大小的空间static void deallocate(T *p){ Alloc::deallocate(p, sizeof (T)); }
}; 5、对象的构造与释放 一切为了效率考虑SGI-STL 决定将空间申请释放和对象的构造析构两个过程分离开因为有些对 象的构造不需要调用析构函数销毁时不需要调用析构函数将该过程分离开可以提高程序的性 能 // 归还空间时先先调用该函数将对象中资源清理掉
template class T
inline void destroy(T* pointer)
{pointer-~T();
}// 空间申请好后调用该函数利用placement-new完成对象的构造
template class T1, class T2
inline void construct(T1* p, const T2 value)
{new (p) T1(value);
} 注意 在释放对象时需要根据对象的类型确定是否调用析构函数类型萃取。对象的类型可以通过迭代器获萃取到。 以上两步在实现时稍微有点复杂感兴趣可参考 STL 源码。 四、与容器结合 本例子给出 list 与空间配置器是如何结合的大家参考可给出 vector 的实现。 template class T, class Alloc alloc
class list
{// ...// 实例化空间配置器typedef simple_alloclist_node, Alloc list_node_allocator;// ...protected:link_type get_node(){// 调用空间配置器接口先申请节点的空间return list_node_allocator::allocate(); }// 将节点归还给空间配置器void put_node(link_type p) {list_node_allocator::deallocate(p);}// 创建节点1. 申请空间 2. 完成节点构造link_type create_node(const T x){link_type p get_node();construct(p-data, x);return p;}// 销毁节点 1. 调用析构函数清理节点中资源 2. 将节点空间归还给空间配置器void destroy_node(link_type p){destroy(p-data);put_node(p);}// ...iterator insert(iterator position, const T x){link_type tmp create_node(x);tmp-next position.node;tmp-prev position.node-prev;(link_type(position.node-prev))-next tmp;position.node-prev tmp;return tmp;}iterator erase(iterator position) {link_type next_node link_type(position.node-next);link_type prev_node link_type(position.node-prev);prev_node-next next_node;next_node-prev prev_node;destroy_node(position.node);return iterator(next_node);}// ...
};
