C++非连续分配数组

Question

让我们将这段 C++ 代码视为一个粗略的示例。

int *A = new int [5];
int *B = new int [5];
int *C = new int [5];
delete []A;
delete []C;
int *D = new int [10];

显然，任何机器都可以处理这种情况，而不会出现缓冲区溢出或内存泄漏的任何问题。然而，让我们想象长度乘以一百万甚至更大的数字。据我所知，所有数组元素的地址(至少是虚拟地址)都是连续的。所以每当我创建一个数组时，我可以确定它们是虚拟内存中的连续 block ，如果我有指向第一个元素的指针，我可以执行指针算术来访问第 n 个元素。下图说明了我的问题(为简单起见，忽略了表示数组末尾的寄存器)。

在堆中分配 A、B、C 后，我们释放 A 和 C 并获得两个长度为 5 的空闲内存块(用绿点标记)。当我想分配一个长度为 10 的数组时会发生什么？我认为有3种可能的情况。

• 我会因为没有连续的 10 长内存块而得到 bad_alloc 异常。

• 程序会自动将数组 B 重新分配到堆的开头，并将其余未使用的内存连接在一起。

• 数组 D 将被分成 2 部分，并且不连续存储，导致数组的第 n 个元素的访问时间不恒定(如果分割的数量多于 2 则它开始类似于链表而不是一个数组)。

  其中哪一个是最可能的答案，还是我没有考虑其他可能的情况？

Answer 1

I will get bad_alloc exception for not having contiguous 10 length memory chunk.

这可能发生。

The program will automatically reallocate array B to the beginning of the heap and join together the rest of the unused memory.

这不可能发生。在 C++ 中无法将对象移动到不同的地址，因为这会使现有指针无效。

The array D will be split into 2 parts and stored not contiguously causing not constant access time for n-th element of the array (if there are much more than 2 splits it starts to resemble a linked list rather than an array).

这也不可能发生。在 C++ 中，数组元素是连续存储的，因此可以进行指针运算。

但实际上还有更多的可能性。要理解它们，我们必须考虑到内存可以是虚拟的这一事实。这意味着可用地址空间可能大于实际存在的内存量。可以为一 block 物理内存分配可用地址空间中的任何地址。

例如，假设一台具有 8GB(2^33 字节)内存的机器在 64 位 CPU 上运行 64 位操作系统。分配给程序的地址不都小于 8GB；它可以在地址 0x00000000ffff0000 处接收一个兆字节的内存块，在地址 0x0000ffffffff0000 处接收另一个兆字节的 block 。分配给程序的内存总量不能超过 2^33 字节，但每个 block 可以位于 2^64 空间中的任何位置。 (实际上这有点复杂，但与我描述的差不多)。

在你的图片中，你有 15 个小方 block 代表内存 block 。假设它是物理内存。虚拟内存是 15,000 个小方 block ，您可以在任何给定时间使用其中的 15 个任意。

因此，考虑到这一事实，以下情况也是可能的。

• 一 block 虚拟地址空间被分配给程序，它没有真正的物理内存支持。当程序尝试访问该空间时，操作系统将尝试分配物理内存并将其映射到相应的地址，以便程序可以继续运行。如果此尝试失败，则该程序可能会被操作系统杀死。新释放的内存现在可供其他可能需要它的程序使用。
• 两个短的内存块被映射到新的虚拟地址，这样它们在虚拟内存空间中形成一个长的连续 block 。请记住，通常虚拟内存地址比物理内存多得多，并且通常很容易找到未分配的范围。通常，这种情况只有在所讨论的内存块很大时才会实现。