为什么阵列不能扩展?

这个问题没有提到语言,所以我将选择基于C的数组作为我的答案。

数组被分配为单个内存块。增加一个数组是有问题的,因为正确地增加数组的唯一方法是在最后增加数组。对于大小n的增长,在下一个分配的地址之前,数组末尾必须至少有n个可用字节。

支持这种类型的分配需要将分配分布在虚拟地址空间中。这两者都消除了内存分配彼此更接近的好处,并有助于增加碎片。大多数内存管理器都试图将内存打包在一起并减少碎片,这一点就迎刃而解了。

在内存中有足够空间的地方分配一个新的数组,并复制该数组,这根本没有一个通用的解决方案。原因是,使用者可以通过指针看到数组的前一个位置。

int* array = malloc(int*someSize);
int* pointer1 = &(arr[2]);
growArray(&array, 12);  // Can't move because pointer1 knows the address of the array

一个数组的根是一个连续的“数组”内存。其他数据可以在这个内存区域之前和之后占用数据,因此,如果不分配一个新的、不同的、适合新的、更大大小的内存区域,就无法动态调整其大小。

取决于您的语言,但通常数组在内存中排列为一系列连续空间。这样就不必为数组中的每个点存储内存位置,只需存储一个内存位置(数组的开头),然后添加一个偏移量(偏移量将是每个条目的大小乘以所需索引),以确定特定条目在内存中的位置。

这也是数组通常只包含一种类型的原因,否则无法进行如此简单的计算。允许存储多个类型的语言实际上是创建一个普通数组,并将指针放在数组中的每个条目上——所有指针的大小通常都相同。这种间接的代价,这就是为什么“更容易”的语言会慢一点的原因。

无论如何,当你分配更多的内存时,你想把新的内存放在数组的末尾——否则你会用一个洞来分割你的内存——为什么要这样做?

所以你不能只在不移动阵列的情况下扩展它。

计算机已经这样做多年了,所以大多数语言都有一些方法来分配一个新的内存块,然后告诉CPU将所有的条目复制到新的块,并改变指针以反映这一点,但是通常(C,Java,…)它们留给程序员以特定的命令来复制数组而不是为YO做它。u(可能只是让您知道扩展数组不是“免费的”

可以在数组末尾添加一个指针,以跳转到要添加到数组末尾的新内存块,但现在数组查找速度变慢了相当大的一部分。

许多语言只是将数组包装为允许这种功能的集合。例如,Java向量/ARARYLIST会自动为您重新分配内存。链接列表实际上每次只分配一个元素,并带有指向下一个元素的指针。增加元素的速度非常快,但是进入元素5000的速度非常慢(你必须读取每个元素,而对于数组,读取元素1的速度和元素5000的速度一样快)

这取决于语言。

在C(和类似Java的类似语言)中,当你声明一个数组时 int ary[10] ,系统会留出足够的内存来连续存放十个整数。扩展它并不容易,因为系统没有留出任何额外的空间(因为它不知道您是想扩展它还是要扩展多少空间),并且数组之后的内存可能正被其他东西使用。因此,获得更大数组的唯一方法是留出一个新的内存块来保存扩展的数组,然后复制旧内容并添加新项。

你说得对,这可能很慢。解决这个问题的一种方法是声明您的数组比需要的数组大,以便为您提供增长空间。尤其是在旧电脑上,这可能会导致一个程序占用了它从未使用过的大量内存。

另一种解决方法是使用具有可扩展数组的高级语言。例如,Ruby允许您在数组中添加更多的项,而不必声明内存或复制数组内容。

一般来说,编程语言在某个地方具有分配 存储器的固定部分 . 然后,从这个抽象中,可以创建其他抽象来隐藏内存管理的复杂性,可能通过移动/复制数据来实现。

大多数时候, array 是固定的——某种程度上是低级抽象——和 lists 或 collections 是 建立在阵列之上 知道如何动态调整自己的大小。

拥有如此低级别的抽象来实现是很方便的 高效算法/优化 有时。但在大多数代码中,您可以使用列表和集合,而不必太担心性能。

是否可以更改数组的大小取决于所使用的语言。在那些不能增加数组大小的语言中,原因是数组被放在内存中连续的位置上,而编译器不能保证数组末尾后面的位置可以添加到数组中。许多编程语言支持可扩展的数组类型,但这些类型只是为您处理底层内存的重新分配和复制。

例如,在curl编程语言中,有一个fastarray类型,它具有大小和最大大小。最大大小指定数组的最大大小,并确定将为数组分配多少内存。有一种更通用的数组类型,它使用FastArray作为其底层实现,并且如果需要将数组扩展到底层FastArray的最大大小之外,它将替换FastArray实例。

在汇编语言中,必须声明变量所需的内存空间。这是数据段(DS)注册表中的保留内存。

所以,大致看起来是这样(BorlandTurbo组装器):

.DATA
    myStringVariable   DB   "Hello world!", 13, 10
    myArrayVariable    DW   "                    " 'Reserving 20 bytes in memory (in a row)

.CODE

    MOV AX, @DATA
    MOV DS, AX
    ' ...

然后,一旦对.data段进行了分隔,就不能更改它,因为.code段(cs)将以几个字节开始。

因此,如果一个数组是可扩展的,比如集合在.NET中,那么数据就会覆盖代码,导致程序崩溃等。

C/C++(3)、Pascal(7)、QBASIC、PowerBasic和COM调试程序都是基于这种体系结构的,可以比汇编程序所允许的更好。

今天,由于技术更加灵活,我想我们现在可以根据需要动态地分配内存地址,并且只使用一个变量来保持对它们的引用,因此数组可以通过集合进行扩展。但在某些情况下,您需要考虑精确的字节量,例如网络数据包等,例如,在这些情况下,数组仍然有用。另一个例子是在数据库中存储图像。您完全知道mow large in bytes是一个图像,因此可以将其存储在字节数组(byte[])中。

也许我在这里遗漏了一些精确性,我是为我所记得的我最喜欢的编程语言而写的。也许有些人可以提出一些更详细的东西。

希望这有帮助!=)