问标准如何保证数据结构使用连续内存？

EN

您的问题似乎是关于如何从初学者的角度理解内存分配的概念。让我试着以一种非常简单的方式来解释正在发生的事情。作为一个例子，我们可以考虑向std::vector添加大量元素的C++程序。

当程序启动时，C++运行时将调用操作系统来分配一些内存。这块内存称为堆，在C++程序需要动态内存时使用。最初，堆大部分是未使用的，但对new和malloc的调用将在堆上划分出内存块。在内部，堆使用一些记账信息来跟踪堆的已用区域和空闲区域。

std::vector在内部的具体行为取决于实现，但通常它会为堆上的向量元素分配一个缓冲区。这个缓冲区足够大，可以容纳向量中的所有元素，但大多数情况下，它的末尾有一些空闲空间。这是一个存储5个元素的缓冲区，有足够的空间容纳8个元素。缓冲区位于堆上的地址1000处。

1000: X X X X X _ _ _

std::vector跟踪向量(5)中元素的数量以及缓冲区的大小(8)和位置(1000)。

下面是调用push_back向向量添加新元素后的缓冲区：

1000: X X X X X X _ _

这可以再做两次，直到缓冲区中的所有空间都用完为止。

1000: X X X X X X X X

但是如果再次调用push_back会发生什么呢？向量必须增加缓冲区的大小。缓冲区是在堆上分配的，如果缓冲区后面的区域未被使用，则实际上可以简单地增加缓冲区。然而，在大多数情况下，内存已经被分配给了其他对象。这是堆跟踪的东西。为了使向量能够增长缓冲区，它必须分配一个大小增加的全新缓冲区。许多实现都会简单地将缓冲区的大小加倍。下面是新的buffer，它现在存储了9个元素，并有16个元素的空间。新的缓冲区被分配到堆上的地址2000：

2000: X X X X X X X X X _ _ _ _ _ _ _

旧缓冲区的内容被复制到新缓冲区，如果缓冲区很大，则此操作的开销可能会很大。

如果您想知道，当程序运行时，堆也可能增长，就像在堆上分配的单个块可能增长一样。这将增加程序的内存消耗。随着越来越多的元素被添加到向量中，堆将不得不增长，直到操作系统拒绝增加堆的大小。当发生这种情况时，程序将失败，并出现内存不足的情况。

总结一下：

• 操作系统为堆提供内存，该内存的大小可以增长，直到达到操作系统的限制为止。
• C++中的内存分配例程可以分配和释放堆上固定大小的块。
• std::vector将预分配一个缓冲区以允许向量增长，但如果向量增长超过缓冲区的大小，它将分配一个新缓冲区并将向量的全部内容复制到这个新缓冲区。

标准可能要求符合标准的实现以某种方式运行--它们只能“保证”符合标准的实现以这种方式运行，因为根据定义，违反标准中要求的实现是不符合的。

std::vector的典型实现如何符合连续内存需求:它分配一定数量的空间(“容量”)，如果当前大小赶上容量，它会重新分配空间(这相当于进行全新的分配，通常是当前容量的固定倍数，将当前内容复制到新空间，然后释放先前获得的空间)。

要记住的一件事是，所有现代操作系统都有一种叫做Virtual Memory的东西。这使得任何程序都能够假定它能够完全访问该体系结构的最大可能内存量，而不管其他进程，甚至计算机中的物理RAM的大小。因此，在编译时，编译器可以在堆栈上自动分配足够的空间(如果在编译时知道所需的大小)，或者它可以编写程序集在堆上动态分配内存，就好像整个内存空间都是可用的一样。这是一个抽象的层次，让事情变得非常简单。

操作系统所做的就是在各种正在运行的程序需要这些页时，负责将这些页交换到物理内存和从物理内存中交换出来。这样，没有程序需要担心其他程序，但您仍然可以同时运行程序。

当然，我正在极大地简化实际发生的事情，但我认为这至少回答了您的问题，即编译器如何判断哪些内存是空闲的；因为它可以假设所有内存都是空的。