delete[] 操作符的时间复杂度

Question

delete[] 操作符的时间复杂度

c++destructortime-complexitydelete-operator

42

delete[]操作符的时间复杂度是多少？

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

这个操作符对于基本类型（例如int）和用户定义的类型是否执行相同的操作？

- rooster

很棒的问题。喜欢它。 - sircodesalot

1

投票支持重新开放！ 1. 这个问题的赞数比“重复”的多。 2. @BasileStarynkevitch的答案引用了标准文档，比“重复”的答案更可靠（在我看来）。 - πάντα ῥεῖ

1

@πάνταῥεῖ 然后标记以合并答案。重新打开这个并试图关闭另一个太麻烦了。 - Kate Gregory

6

@πάνταῥεῖ，我不同意。很抱歉。投票数或回答的“质量”不会改变规则。根据标准程序，应将回答与重复问题合并。 - Shoe

1

@πάνταῥεῖ：对于其他问题的被接受答案有一个优点，那就是它实际上正确回答了问题，这是Basile的答案所没有的（它提出了一些真实的评论并回避了复杂性）。 - Ben Voigt

显示剩余3条评论

4个回答

11

delete 和 delete[] 的实现由两个阶段组成：

递归调用析构函数（如果有的话）
释放被删除对象的内存

不考虑析构函数调用链的复杂性，它的复杂性本质上由您控制，我们需要考虑的是内存如何被释放。

C++规范未涵盖第二点。因此，任何编译器套件/操作系统都可以采用自己的策略。

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

如果内存释放的复杂度为 O(1)，那么 delete 的复杂度基本上由析构函数调用决定。默认实现几乎不做任何事情，对于单个调用来说它是 O(1)，因此总体上是 O(n)，其中 n 是调用总数（例如，如果被销毁的对象有两个字段其析构函数将被调用，则 n = 1（对象）+ 2（字段）= 3）。

将所有部分整合起来：通过在析构函数中执行操作，您可以任意增加复杂度，但您无法“表现得更好”¹ ，即 O(n) 是上限 (n在前面的段落中定义)。正确陈述这一点的正式方式是：“delete 的复杂度是 Omega(n)”。

¹ 允许我在这个问题上有点不太正式

- Stefano Sanfilippo

1

我相信C++规范确实指出每个元素的析构函数都应该被调用。 - Basile Starynkevitch

@BasileStarynkevitch 但是对于基本类型来说，情况并非如此，这种情况下O(1)很有可能。 - Sebastian Hoffmann

@BasileStarynkevitch 是的，我同意。我更关注用户无法控制的部分。无论如何，我已经修复了答案。 - Stefano Sanfilippo

我认为“析构函数的复杂性因情况而异”是关键，应该得到突出强调。 - Ben Voigt

@BenVoigt 我扩展了答案以涵盖那一点 :) - Stefano Sanfilippo

1

对于类类型，理论复杂度为O(n)。对于每个元素都会调用析构函数。当然，实现取决于可观察行为是否遵循，所以如果析构函数为no-op或行为与标记整个块已释放相同，则复杂度可以为O(1)。

对于基本类型，编译器可能会一次性释放整个内存块，因此复杂度为O(1)。

- Luchian Grigore

1

注意：由于free的复杂性取决于实现方式（块压缩？线程缓存？），因此很难将释放内存块解释为O(1)，除非明确说明我们正在计算什么... - Matthieu M.

我想你是指“带有平凡/非平凡析构函数的类型”，而不是原始/类类型。但是，正如Stefano在他的答案中指出的那样，非平凡析构函数的复杂度可能非常高。 - Ben Voigt

不行。个别析构函数的复杂性或底层堆可能会占主导地位。 - bmargulies

0

delete[]运算符的时间复杂度是多少？

所需的时间量当然是由实现定义的。但是，该运算符仅适用于指向一维数组的指针，因此它的时间复杂度为O(1)。
~~（原文有误，已更正）~~

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

是的。
前提是它只在分配使用new[]创建的内存的确切指针上调用。对于基本类型，没有用户定义的析构函数。

这个运算符对于基本类型（int等）和用户定义类型是否执行相同的操作？

比较是不公平的，因为基本类型没有用户定义的析构函数，也不能是多态的。
例如，对多态类进行delete[]操作是未定义行为。

Base* p1 = new Derived, *p2 = new Derived[2];
delete p1; // ok
delete[] p2;  // bad

- iammilind

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Basile Starynkevitch · Accepted Answer

::operator delete[]在cplusplus.com上有文档介绍(有时会被人诟病)，文档如下:

operator delete[] 可以作为普通函数被显式调用，但在C++中，delete[]是一个带有特殊行为的运算符: 带有 delete[] 运算符的表达式首先会为数组中的每个元素（如果这些元素是类类型）调用相应的析构函数，然后调用函数operator delete[] (即此函数)来释放存储空间。

因此，析构函数会被调用n次(每个元素一次), 然后内存释放"函数"才会被调用一次。

^{请注意，每个析构函数的执行时间(或复杂性)可能都不同。一般来说，大多数销毁操作都很快，并且具有相同的复杂度...但如果每个销毁的元素都是一个复杂的树、节点或图形，那就不是这样了...}

对于像int这样的原始类型，int 的虚构析构函数是一个无操作函数。如果需要，编译器可能会对此进行优化。

您应该查看真正的C++11标准，或者至少查看它的最新n3337工作草案，其中在§5.3.5.6第110页中说明了(感谢Matteo Italia在评论中指出):

如果delete-expression的操作数值不是空指针，delete-expression将调用正在被删除的对象或数组元素的析构函数（如果有的话）。在数组的情况下，元素将按地址递减的顺序销毁（也就是说，按照它们构造完成的相反顺序；参见12.6.2）。
如果您使用并信任足够好的GCC 4.8或更高版本，则可以使用带有-fdump-tree-phiopt或-fdump-tree-all选项的g++编译器（请注意，它们会生成大量文件！），或MELT插件来查询某个示例的中间Gimple表示。或者使用-S -fverbose-asm获取汇编代码。您还需要添加像-O1或-O2这样的优化标志。
注意：IMHO，cppreference.com也是关于C ++的一个有趣的网站，请参见这里，了解更多关于delete的信息（如Cubbi所评论的那样）。