标准保证C++新建/删除复杂度

Question

最近的 C++ 标准中的内存分配操作是否有复杂性保证？也就是说，如果我有一个类 A，其默认构造函数和析构函数在 O(1) 中运行，那么“new A[N]”和“delete[] A”的 big-O 是什么？new int[N]有复杂度保证吗？

Answer 1

我找不到任何明确提及复杂性的内容。复杂性。我也非常确定，当涉及到新运算符(即内存分配本身)时，任何复杂性问题都是没有意义的。

存在复杂的 C++ 运行时堆管理结构，构建在操作系统级内存管理之上，其中可能包括应用程序级锁、操作系统级锁、基于文件的交换等。出于这些原因，下面的答案不讨论内存分配本身。

但是，如果我们关注新的表达式，拼接在一起[expr.new/22]:

A new-expression that creates an object of type T initializes that object as follows: (22.1) If the new-initializer is omitted, the object is default-initialized ([dcl.init]).

和[dcl.init/7]:

To default-initialize an object of type T means: .... (7.2) If T is an array type, each element is default-initialized.

我可以得出结论，这种操作的复杂度是 O(N)。