new [],删除[]复杂性

Question

我已经知道new[]运算符首先分配内存,然后为每个元素调用构造函数,并且delete[]运算符首先为每个元素调用析构函数,然后释放内存,因此,它们都具有O(n)时间复杂度.

但是如果我有一个类,我没有定义任何构造函数/析构函数,复杂性仍然是O(n),还是只是O(1)？

例如,如果我有两个类:

class foo
{
public:
    int a;
    foo()
    {
        a = 0;
        // more stuff
    }
    ~foo()
    {
        a = 1;
        // some useful stuff here
    }
};

class boo
{
public:
    int a;
};

我创建了两个这样的数组:

int n = 1000;
foo* pfoo = new foo[n];
boo* pboo = new boo[n];

我很确定第一个new调用会有O(n)复杂度,但第二个调用呢？将new只分配必要的内存,就是这样,还是会调用一些默认的构造函数(我不知道,如果这样的事情居然在退出C++)每个元素？

同样的问题delete:

delete [] pfoo;
delete [] pboo;

当我删除第二个数组时,复杂性仍然是O(n),还是只会delete以O(1)复杂度释放内存？

Answer 1

当你不知道时,使用汇编输出是个好主意.例如,我们假设这是要比较的代码.

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提供类似输出)进行优化编译时,会得到以下结果.

    .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在名称修改之后).这也是在没有优化的情况下发生 代码更长,因为方法实际上是输出的,但是delete []直接调用它仍然是值得注意的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即使没有优化,也可以直接调用,无需构造对象.

通常,这意味着自定义构造函数或析构函数意味着new []并且delete []不会在恒定时间内执行.但是如果没有,编译器不会尝试为这些调用构造函数或析构函数,它们将是POD数据类型,这意味着构造这些对象是简单的malloc类调用.有一些例外(涉及各种优化),但通常带有构造函数/析构函数的代码将是O(N),并且假设为O(1)new []/ delete []实现,则不会是O(1).