首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >delete[]算子的时间复杂度

问delete[]算子的时间复杂度
EN

Stack Overflow用户
提问于 2014-01-12 16:27:15
回答 2查看 5.3K关注 0票数 42

delete[]算子的时间复杂度是多少?

我的意思是它是如何实现的-它是否迭代数组中的所有元素并为每个元素调用析构函数?

这个运算符对原语类型(int等)也是这样吗?以及用户定义的类型?

EN

回答 2

Stack Overflow用户

发布于 2014-01-12 16:34:26

delete和delete[]的实现分为两个阶段:

  1. 递归调用析构函数(如果有的话)
  2. 已删除对象的内存释放

更不用说对析构函数的调用链了,因为析构函数的复杂性本质上是由您控制的,我们留给我们的是如何释放内存来考虑的。

第二点不在C++规范的范围之内。因此,任何编译器套件/操作系统都可以自由地采用自己的策略。

一种常见的内存分配/去分配策略是在需要时从操作系统分配整个内存页,然后在每个new/new[]上返回适当大小的块,然后将其长度和属性作为页眉/页脚存储在页面中。对应的delete/delete[]可以简单地将相同的块标记为“空闲”,这显然是O(1)。

如果内存解分配的复杂性为O(1),则delete 的复杂性本质上取决于对析构函数的调用。默认实现(几乎)什么也不做,它是单个调用的O(1),因此是一个整体的O(n),其中n是调用的toal数(例如,如果被解构的对象有两个字段,其析构函数被调用,然后是n = 1 (object) + 2 (o. fields) = 3)。

将所有的部分组合在一起:您可以通过在析构函数中执行操作(可以由您编写)来任意增加复杂性,但是不能比O (n ) (上一段中定义的n)“执行得更好”。在形式上正确的说法是:“delete 的复杂性是一个Omega(n)"。

请允许我在这一点上有点非正式。

票数 11
EN

Stack Overflow用户

发布于 2014-01-12 16:37:59

对于类类型,理论复杂性是O(n)。为每个元素调用析构函数。当然,这取决于实现是否坚持可观察的行为,因此如果析构函数是无操作的,或者行为与只将整个块标记为已释放的行为相同,那么复杂性可能就是O(1)。

对于原始类型,编译器很可能一次只释放整个内存块,因此复杂性O(1)。

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/21077140

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档