RainAir
My OI Blog
RainAir
「优化」内存池

实现

在c++中,我们非常喜欢使用指针。因为指针非常适合人们的思考方式。

所以我们来优化一下指针的速度。

你们想一下:嵌套7,8层数组和一些平等无嵌套的箭头,哪个更容易理解?

~~当然是前者啦~~

指针非常亲和人们的语言和思维习惯,所以被众多OIer所追求。

~~当然你做工程时写指针 throw 出一堆 Error 时当然会绝望~~

所以说,为了获得更好的指针体验,我们现在分析一下,为什么指针比较慢。

我们来回顾一下图的常规写法:

这种方式的缺点在哪里呢?我们发现建边的时候:

会调用1~2次new函数,我们看一看new函数的执行过程:

等价于:

这是在做什么呢?它就是:获得一块内存空间、调用构造函数、返回正确的指针。

是不是很麻烦?我们能不能直接返回呢?

于是,我们手动实现new的过程。

我们这样写:

这样我们在调用的时候只需:

发现了吗?我们其实就是预先定义出了所有要用的边(pool),然后用一个尾指针(frog)来指向。

每次加边时,我们直接另指针后移,然后获取一个新的未被初始化过的Edge变量,对其进行初始化即可。

其他步骤和普通指针一样即可。

所以说,我们在预定义内存池时,我们必须要算好开多少空间。

那么,内存池有什么好处呢?

优点

  1. 速度比new快了不少。
  2. 我们在需要精确定位第$ i $条边时,不需要多定义一个$ num $成员变量,省下了空间和时间。

那么,我们再拿一个线段树的例子来加深理解。

线段树原实现(部分)

我们对new过程进行分析。

每次执行new时,我们相当于初始化一个SegmentTree类型的变量。那么我们可以如此初始化:

那么,现在的实现就需要这样:

好了,相信你学会了内存池,就能抛弃掉毒瘤的数组写法和超级慢的new写法,能够获得更好的指针体验。

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/99
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「优化」内存池
实现 在c++中,我们非常喜欢使用指针。因为指针非常适合人们的思考方式。 所以我们来优化一下指针的速度。 你们想一下:嵌套7,8层数组和一些平等无嵌套的箭头,哪个更容易理解? ~…
扫描二维码继续阅读
2018-07-12
标签
近期评论