新[]，删除[]复杂度 [英] new [], delete [] complexity
问题描述
我已经知道new[]运算符首先分配内存，然后为每个元素调用构造函数，并且delete[]运算符首先为每个元素调用析构函数，然后释放内存，因此，它们都具有时间复杂度为O(n).
I already know that the new[] operator first allocates memory and then calls the constructor for each element and that the delete[] operator first calls the destructor for each element and then frees memory and, because of that, they both have an O(n) time complexity.
但是，如果我有一个尚未定义任何构造函数/析构函数的类，那么复杂度是否仍为O(n)或仅为O(1)?
But if I have a class, for which I have not defined any constructor/destructor, will the complexity still be O(n), or will it be just O(1)?
例如，如果我有两个班级:
For instance, if I have two classes:
class foo
{
public:
int a;
foo()
{
a = 0;
// more stuff
}
~foo()
{
a = 1;
// some useful stuff here
}
};
class boo
{
public:
int a;
};
我创建了两个这样的数组:
And I create two arrays of them like this:
int n = 1000;
foo* pfoo = new foo[n];
boo* pboo = new boo[n];
我很确定第一个new调用的复杂度为O(n)，但是第二个调用又如何呢? new会只是分配必要的内存，就是这样，还是会为每个元素调用一些默认的构造函数(我不确定这种事情是否真的在C ++中退出了)?
I'm pretty sure the first new call will have an O(n) complexity, but what about the second? Will new just allocate the necessary memory and that's it, or will it call some default constructor (I'm not sure if such thing actually exits in C++) for each element?
与delete相同的问题:
delete [] pfoo;
delete [] pboo;
当我删除第二个数组时，复杂度是否仍为O(n)，或者delete只是以O(1)复杂度重新分配内存?
When I delete the second array will the complexity still be O(n), or will delete just deallocate the memory in O(1) complexity?
推荐答案
不知道时，最好使用程序集输出.例如，假设这是要比较的代码.
When you don't know, it's great idea to use assembly output. For example, let's assume this is the code to compare.
class foo
{
public:
int a;
foo()
{
a = 0;
// more stuff
}
~foo()
{
a = 1;
// some useful stuff here
}
};
class boo
{
public:
int a;
};
void remove_foo(foo* pfoo) {
delete [] pfoo;
}
void remove_boo(boo *pboo) {
delete [] pboo;
}
使用gcc进行优化编译时(Clang提供类似的输出)，您将得到以下结果.
When compiling with optimizations using gcc (Clang gives similar output), you get the following result.
.file "deleter.cpp"
.text
.p2align 4,,15
.globl _Z10remove_fooP3foo
.type _Z10remove_fooP3foo, @function
_Z10remove_fooP3foo:
.LFB6:
.cfi_startproc
testq %rdi, %rdi
je .L1
movq -8(%rdi), %rax
leaq (%rdi,%rax,4), %rax
cmpq %rax, %rdi
je .L4
.p2align 4,,10
.p2align 3
.L6:
subq $4, %rax
movl $1, (%rax)
cmpq %rax, %rdi
jne .L6
.L4:
subq $8, %rdi
jmp _ZdaPv
.p2align 4,,10
.p2align 3
.L1:
rep ret
.cfi_endproc
.LFE6:
.size _Z10remove_fooP3foo, .-_Z10remove_fooP3foo
.p2align 4,,15
.globl _Z10remove_booP3boo
.type _Z10remove_booP3boo, @function
_Z10remove_booP3boo:
.LFB7:
.cfi_startproc
testq %rdi, %rdi
je .L8
jmp _ZdaPv
.p2align 4,,10
.p2align 3
.L8:
rep ret
.cfi_endproc
.LFE7:
.size _Z10remove_booP3boo, .-_Z10remove_booP3boo
.ident "GCC: (SUSE Linux) 4.8.1 20130909 [gcc-4_8-branch revision 202388]"
.section .note.GNU-stack,"",@progbits
很容易说出来，对于foo它调用析构函数，但是对于boo它直接调用delete []函数(名称改写后的_ZdaPv).如果没有优化，也会发生这种情况.代码更长，因为方法实际上是输出的，但是仍然值得注意的是直接为boo调用delete [].
It's easy to tell that for foo it calls destructor, but for boo it directly calls delete [] function (_ZdaPv after name mangling). This also happens without optimizations. The code is longer, because methods are actually output, but it's still noticeable that delete [] is called directly for boo.
.file "deleter.cpp"
.section .text._ZN3fooD2Ev,"axG",@progbits,_ZN3fooD5Ev,comdat
.align 2
.weak _ZN3fooD2Ev
.type _ZN3fooD2Ev, @function
_ZN3fooD2Ev:
.LFB4:
.cfi_startproc
pushq %rbp
.cfi_def_cfa_offset 16
.cfi_offset 6, -16
movq %rsp, %rbp
.cfi_def_cfa_register 6
movq %rdi, -8(%rbp)
movq -8(%rbp), %rax
movl $1, (%rax)
popq %rbp
.cfi_def_cfa 7, 8
ret
.cfi_endproc
.LFE4:
.size _ZN3fooD2Ev, .-_ZN3fooD2Ev
.weak _ZN3fooD1Ev
.set _ZN3fooD1Ev,_ZN3fooD2Ev
.text
.globl _Z10remove_fooP3foo
.type _Z10remove_fooP3foo, @function
_Z10remove_fooP3foo:
.LFB6:
.cfi_startproc
pushq %rbp
.cfi_def_cfa_offset 16
.cfi_offset 6, -16
movq %rsp, %rbp
.cfi_def_cfa_register 6
pushq %rbx
subq $24, %rsp
.cfi_offset 3, -24
movq %rdi, -24(%rbp)
cmpq $0, -24(%rbp)
je .L3
movq -24(%rbp), %rax
subq $8, %rax
movq (%rax), %rax
leaq 0(,%rax,4), %rdx
movq -24(%rbp), %rax
leaq (%rdx,%rax), %rbx
.L6:
cmpq -24(%rbp), %rbx
je .L5
subq $4, %rbx
movq %rbx, %rdi
call _ZN3fooD1Ev
jmp .L6
.L5:
movq -24(%rbp), %rax
subq $8, %rax
movq %rax, %rdi
call _ZdaPv
.L3:
addq $24, %rsp
popq %rbx
popq %rbp
.cfi_def_cfa 7, 8
ret
.cfi_endproc
.LFE6:
.size _Z10remove_fooP3foo, .-_Z10remove_fooP3foo
.globl _Z10remove_booP3boo
.type _Z10remove_booP3boo, @function
_Z10remove_booP3boo:
.LFB7:
.cfi_startproc
pushq %rbp
.cfi_def_cfa_offset 16
.cfi_offset 6, -16
movq %rsp, %rbp
.cfi_def_cfa_register 6
subq $16, %rsp
movq %rdi, -8(%rbp)
cmpq $0, -8(%rbp)
je .L7
movq -8(%rbp), %rax
movq %rax, %rdi
call _ZdaPv
.L7:
leave
.cfi_def_cfa 7, 8
ret
.cfi_endproc
.LFE7:
.size _Z10remove_booP3boo, .-_Z10remove_booP3boo
.ident "GCC: (SUSE Linux) 4.8.1 20130909 [gcc-4_8-branch revision 202388]"
.section .note.GNU-stack,"",@progbits
这也适用于new [].直接调用_Znam，无需构造对象，甚至无需优化.
This also applies to new []. _Znam is called directly, without constructing objects, even without optimizations.
通常，这意味着自定义构造函数或析构函数意味着new []和delete []不会在恒定时间内执行.但是如果没有，编译器将不会尝试为它们调用构造函数或析构函数，它们将是POD数据类型，这意味着构造这些对象就像是简单的类似于malloc的调用.有一些例外情况(涉及各种优化)，但通常假设带有O(1)new []/delete []实现，带有构造函数/析构函数的代码将为O(N)，而没有构造函数的代码将为O(1).
Generally, that means custom constructors or destructors mean that new [] and delete [] won't be executed in constant time. But if there aren't, the compiler doesn't try to call constructors or destructors for these, and they will be POD data types, which means that constructing these objects is simple malloc-like call. There are some exceptions (involving various optimizations), but usually code with constructors/destructors will be O(N), and without will be O(1), assuming O(1) new []/delete [] implementation.
这篇关于新[]，删除[]复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
