C++标准对于new/delete运算符复杂度的保证

Question

最近的C++标准中有没有内存分配操作的复杂度保证呢？也就是说，如果我有一个类A，它的默认构造函数和析构函数的运行时间是O(1)，那么"new A[N]"和"delete[] A"的时间复杂度是什么？是否有任何关于"new int[N]"的复杂度保证呢？

- 0kcats

---

在任何真实的机器上，我不认为 new 的时间复杂度会低于 O(N)，因为例如操作系统可能需要在分配给你之前清零内存。 - Nate Eldredge

相关：https://dev59.com/FWAg5IYBdhLWcg3wrMh4 - 463035818_is_not_a_number

还有一个与之相关的问题：https://dev59.com/53VC5IYBdhLWcg3weA8-。我的问题中有“标准”一词。 - 0kcats

数组的初始化为O(N)。然而，内存分配部分不太清楚。因此，我的问题主要是关于分配部分的。 - 0kcats

如果标准保证了STL容器上操作的性能，比如vector::push_back，那么人们可以推断出new和delete的最坏情况性能，但这时它应该明确指定"new"的性能。 - 0kcats

注意：Visual Studio 中与内存分配“malloc/free 剧烈性能下降”相关的问题并非是一个 bug。如果分配的性能符合标准，我们至少可以认为这是一个 bug。详见 https://developercommunity.visualstudio.com/content/problem/552439/mallocfree-dramatic-performance-slowdown.html。 - 0kcats

Answer 1

我找不到任何明确提到“复杂度”的内容。我也相当确定，当涉及新操作符（即内存分配本身）时，任何复杂性问题都是无意义的。

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

然而，如果我们专注于新表达式，将[expr.new/22]与[dcl.init/7]组合起来：

一个创建类型T对象的new-expression初始化该对象如下：(22.1)如果省略了new-initializer，则对象是默认初始化的([dcl.init])。

和[dcl.init/7]：

对于默认初始化类型为T的对象，意味着……(7.2)如果T是一个数组类型，则每个元素都是默认初始化的。

我可以得出这样一个结论：这种操作的复杂度将是O(N)。

- SergeyA

---

请问尊敬的给我点踩的用户能否解释一下您的点踩原因？ - SergeyA

Answer 2

我怀疑是否有任何确切的保证，因为太多取决于平台（想象一下一些非常奇怪的理论平台，没有人会制造但可能存在）。然而，您可以做出某些预测。如果构建和删除需要 O(1) 那么...

delete A[] 的大小为 n，取决于 A 是否是平凡可销毁的或需要非平凡的删除过程，其时间复杂度为 O(1) 或 O(n)。实际上，O(1) 可能很大（不是真正的 O(1)），因为释放一大块连续内存可能需要一点时间，但在更大的范围内仍然微不足道。

对于 new A[n] 也是如此。如果 A 是平凡可构造的（例如 int，即允许垃圾数据），则可能需要约（虚假）O(1)，否则每个元素都需要一些 O(1) 处理，时间复杂度为 O(n)。

通常，您不应忘记当 A 的构建和销毁缓慢时，可能需要大量时间。

- ALX23z

---

我可以想象出一些合理的实现方式，即使A是可平凡析构的，delete A[]的时间复杂度也可能是O(N)。比如系统为了安全起见会清空已释放内存，或者需要更新页表项等等。您是否在断言这种情况违反了标准？ - Nate Eldredge

在第一段中，@NateEldredge声称标准实际上并不关心任何声明。首先，无法控制特定大小的分配/释放所需的时间量。然后只是一般性期望。 - ALX23z