delete[]操作符的时间复杂度是多少?
我的意思是它是如何实现的 - 是否迭代遍历数组中的所有元素并为每个元素调用析构函数?
这个操作符对于基本类型(例如int
)和用户定义的类型是否执行相同的操作?
delete[]操作符的时间复杂度是多少?
我的意思是它是如何实现的 - 是否迭代遍历数组中的所有元素并为每个元素调用析构函数?
这个操作符对于基本类型(例如int
)和用户定义的类型是否执行相同的操作?
::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所评论的那样)。
delete
和 delete[]
的实现由两个阶段组成:
new
/new[]
时返回一个适当大小的块,其长度和属性然后作为页头/页脚存储在页面中。相应的 delete
/delete[]
可以简单地将同一块标记为“空闲”,这显然是O(1)。
如果内存释放的复杂度为 O(1),那么 delete
的复杂度基本上由析构函数调用决定。默认实现几乎不做任何事情,对于单个调用来说它是 O(1),因此总体上是 O(n),其中 n 是调用总数(例如,如果被销毁的对象有两个字段其析构函数将被调用,则 n = 1(对象)+ 2(字段)= 3
)。
将所有部分整合起来:通过在析构函数中执行操作,您可以任意增加复杂度,但您无法“表现得更好”¹ ,即 O(n) 是上限 (n在前面的段落中定义)。正确陈述这一点的正式方式是:“delete
的复杂度是 Omega(n)”。
O(n)
。对于每个元素都会调用析构函数。当然,实现取决于可观察行为是否遵循,所以如果析构函数为no-op或行为与标记整个块已释放相同,则复杂度可以为O(1)
。O(1)
。free
的复杂性取决于实现方式(块压缩?线程缓存?),因此很难将释放内存块解释为O(1)
,除非明确说明我们正在计算什么... - Matthieu M.
delete[]
运算符的时间复杂度是多少?
所需的时间量当然是由实现定义的。但是,该运算符仅适用于指向一维数组的指针,因此它的时间复杂度为O(1)。(原文有误,已更正)
我的意思是它是如何实现的 - 它是否遍历数组中的所有元素并为每个元素调用析构函数?
是的。
前提是它只在分配使用new[]
创建的内存的确切指针上调用。对于基本类型,没有用户定义的析构函数。
这个运算符对于基本类型(int等)和用户定义类型是否执行相同的操作?
比较是不公平的,因为基本类型没有用户定义的析构函数,也不能是多态的。
例如,对多态类进行delete[]操作是未定义行为。
Base* p1 = new Derived, *p2 = new Derived[2];
delete p1; // ok
delete[] p2; // bad