new[],delete[]复杂性

我已经知道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) 复杂度释放内存？

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

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 [] and delete []不会在恒定时间内执行。但如果没有，编译器不会尝试调用这些对象的构造函数或析构函数，它们将是 POD 数据类型，这意味着构造这些对象是简单的类似 malloc 的调用。有一些例外（涉及各种优化），但通常带有构造函数/析构函数的代码将是 O(N)，而没有构造函数/析构函数的代码将是 O(1)，假设 O(1)new []/delete []执行。