首页 > 代码库 > 浅谈C++容器动态内存管理的优化
浅谈C++容器动态内存管理的优化
在信息学竞赛中,C++的容器的用途非常广泛,但经常因常数过大而超时。怎样才能提高它们的效率呢?
我们知道,容器是存储同一类对象的对象,既然“对象”我们无法改变,那么我们只能从“存储”入手,不难想到,不同容器在实现上的根本区别是它们对应着不同的内存组织方式,内存管理无疑是这种实现的核心,所以优化内存管理是加快容器效率的最好途径之一。
一、内存分配器简介
怎样才能优化内存管理呢?很简单,C++为我们提供了这样的接口,我们可以通过自定义容器模板中的最后一个allocator内存分配器来提高容器效率,在默认情况下,alloc为allocator<T>,allocator<T>是C++的用于泛型化内存分配的模板,它在申请小空间时通常很快(比new运算符快一些),又因为自定义一般化的内存分配器(可自行查询“内存池”的资料)需要较大的代码量,而且效率未必高,所以本文我们只讨论某些特殊情况下的内存分配。
二、编写内存分配模板
下面我们来编写一个简单的内存分配器,为了简单起见,我们继承C++的allocator<T>:
template<typename T>
struct myalloc:allocator<T>
构造函数是必不可少的:
myalloc(){}
template<typename T2>//别忘记写模板,下同
myalloc(const myalloc<T2> &a){}
template<typename T2>
myalloc<T>& operator=(const myalloc<T2> &a)
{
return *this;
}
由于继承了allocator<T>,所以一定要把rebind覆盖掉,否则other分配器将是allocator<T>,而不是myalloc:
template<typename T2>
struct rebind
{
typedef myalloc<T2> other;
};
接下来我们将讨论一下:如何实现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<int,myalloc<int> > L;
for(int i=0;i<800000;++i)
{
L.push_back(500);
L.pop_back();
}
cout << "myalloc:" << (double)(clock()-start)/CLOCKS_PER_SEC << endl;
start=clock();
list<int> L2;
for(int i=0;i<800000;++i)
{
L2.push_back(500);
L2.pop_back();
}
cout << "allocator:" << (double)(clock()-start)/CLOCKS_PER_SEC << endl;
笔者测试结果:
myalloc:0.063
allocator:0.203
我们的myalloc比默认的allocator快了近三倍!
那么它在实际应用中的效果如何呢?笔者用NOIP2012提高组的drive测试了一下,其中用到了一个list,最后4个点会超时,最慢的一个用时1.33秒,用刚刚介绍的定长内存分配器优化,最慢的一个点仅用时0.62秒。
六、注意事项
上文介绍的内存分配器缺少对内存上限的处理,因为有时我们并不清楚要开多大的space才够,所以当内存不足时通常要进行额外处理,用allocator来分配内存以防止内存泄露是个不错的选择,请读者自己完善代码。
另外有些C++容器允许通过reserve成员函数预留内存,避免不必要的重复申请操作,这也是一个很有效的优化方法。