浅谈C++容器动态内存管理的优化
2020-11-16 18:13
标签：size tar art strong type 不同的 start 管理 ble c++ har 在信息学竞赛中，C++的容器的用途非常广泛，但经常因常数过大而超时。怎样才能提高它们的效率呢？ 我们知道，容器是存储同一类对象的对象，既然“对象”我们无法改变，那么我们只能从“存储”入手，不难想到，不同容器在实现上的根本区别是它们对应着不同的内存组织方式，内存管理无疑是这种实现的核心，所以优化内存管理是加快容器效率的最好途径之一。 一、内存分配器简介 怎样才能优化内存管理呢？很简单，C++为我们提供了这样的接口，我们可以通过自定义容器模板中的最后一个allocator内存分配器来提高容器效率，在默认情况下，alloc为allocator 二、编写内存分配模板 下面我们来编写一个简单的内存分配器，为了简单起见，我们继承C++的allocator template 构造函数是必不可少的： myalloc(){} template myalloc(const myalloc template myalloc { return *this; } 由于继承了allocator template struct rebind { typedef myalloc }; 接下来我们将讨论一下：如何实现T* allocate(size_t n)和void deallocate(T* p,size_t
n)成员函数。我们只研究内存分配的最简单情况：不回收内存分配和定长内存分配。 三、不回收内存分配 回想一下链表的写法，在竞赛中最常见的实现往往是用数组模拟链表，存储链表的空间是从一个足够大的数组中得到的，这样编写快、效率也高。于是我们得到了主要思想：化动为静！我们一次性预留足够大的“线性”空间，申请内存时从“线”的开头截掉一部分，记录开头的位置即可。思路很直观，实现也很简单。 开一个足够大的数组space，用space_len记录已经分配到的空间大小，注意space必须是全局变量，如果写在类里的话，那么这个类每次实例化都会重复占用空间，很可能超过内存限制。 char space[10000000]; int space_len=0; 可以写allocate函数了，n表示需要的空间大小，函数返回申请到的空间首地址： T* allocate(size_t n) { T *result=(T*)(space+space_len); space_len+=n*sizeof(T); return result; } 然后把void deallocate(T* p,size_t n){}留空，短短几行代码就完成了一个不回收的内存分配器。 四、定长内存分配 在要申请的内存长度确定的情况下，我们可以完成内存释放函数以节省内存空间。内存释放的根本目的是将释放的内存用于下一次申请，由于我们要的内存是定长的，所以保存一下刚刚释放掉的内存地址，下次申请时直接返回这个地址不就可以了？我们用栈来保存地址： int stack[10000000],stack_len=0; 释放很简单： void deallocate(T* p,size_t n) { stack[stack_len++]=(int)p; } 再修改一下申请函数： T* allocate(size_t n) { if(stack_len!=0) return (T*)stack[--stack_len]; else { T *result=(T*)(space+space_len); space_len+=n*sizeof(T); return result; } } 五、效率对比 大功告成！分配效率如何呢？这里用list进行效率测试： int start=clock(); list for(int i=0;i
{ L.push_back(500); L.pop_back(); } cout
start=clock(); list for(int i=0;i
{ L2.push_back(500); L2.pop_back(); } cout
笔者测试结果： myalloc:0.063 allocator:0.203 我们的myalloc比默认的allocator快了近三倍！ 那么它在实际应用中的效果如何呢？笔者用NOIP2012提高组的drive测试了一下，其中用到了一个list，最后4个点会超时，最慢的一个用时1.33秒，用刚刚介绍的定长内存分配器优化，最慢的一个点仅用时0.62秒。 六、注意事项 上文介绍的内存分配器缺少对内存上限的处理，因为有时我们并不清楚要开多大的space才够，所以当内存不足时通常要进行额外处理，用allocator来分配内存以防止内存泄露是个不错的选择，请读者自己完善代码。 另外有些C++容器允许通过reserve成员函数预留内存，避免不必要的重复申请操作，这也是一个很有效的优化方法。 浅谈C++容器动态内存管理的优化,搜素材,soscw.com 浅谈C++容器动态内存管理的优化 标签：size tar art strong type 不同的 start 管理 ble c++ har 原文地址：http://www.cnblogs.com/phar/p/3695080.html
struct myalloc:allocator