如何为数组和向量进行内存分配？

Question

我知道数组的大小无法调整，而向量是一个可选项。

我很想了解它们两者的内存分配方式。

- pa1pal

---

对于Java而言：它管理一个数组，并在需要扩展时调整大小并复制它。 - jmj

请注意，数组的大小在某些情况下是可以调整的，即通过C库的realloc和/或系统特定的手段。但是，请注意，首先，realloc不能保证调整大小，其次，std::vector的要求（据我所知）是它不能在内部使用realloc。即使这通常会显著加快速度。 - Cheers and hth. - Alf

Answer 1

对于Vector，它管理一个内部数组，并在需要时分配更大尺寸的新数组，并将现有数据复制到新数组中。需要时。

- jmj

---

问题目前标记为C++，没有提到Java。 - crashmstr

@crash 它被标记为Java，我认为它是关于数据结构的一般性问题。 - jmj

顺便说一句，我不是给你点踩的那个人。奇怪的是我看不到任何编辑历史，但我怀疑可能有标签切换。 - crashmstr

Answer 2

向量具有一定的容量，这对应着可以在不重新调整大小的情况下存储多少元素 - 这是“底层”数组的实际大小。

达到容量后，将创建一个更大长度的新数组（增量数量可能会有所变化，并且可以进行配置），并将所有元素复制到新数组中。在没有自动垃圾回收的语言中，旧数组应该被删除。

这种操作的算法复杂度为O(n)。

这些结构的实现在所有编程语言中几乎都是相同的，至少从算法角度来看是这样的。Wiki链接here。

说到Java - Vector类的实现是开源的，通常与JDK一起提供源代码。但是如果您没有源代码，可以在互联网上找到它，例如在这里：Vector

- dzirtbry

Answer 3

"既然你在谈论固定大小的数组，我就假设你想要比较类似于..."

int my_array[10];

使用

vector<int> my_vector;

在第一种情况下，程序将请求所需的内存空间，并将该空间视为您的代码所跟随的连续int数。

至于向量，它是一个管理一些内部内存位置的类，因此，当您从它请求某个值时，它会寻找它在哪里并给出结果。

向量不会无限地分配内存，因此，如果它已经为十个整数分配了内存，然后您添加了第十一个整数，它将自动收集更多的内存空间并找到保留实际值的方法。

它如何做取决于实现方式。我使用的是每次需要更多内存时将内存空间加倍并将先前的值复制到新位置。

一些程序员喜欢编写自己的向量类，并使其每次请求固定大小的内存，或将空间乘以特定常数。

---

一些推理：

为什么向量没有通用规则？

很抱歉我无法给出非常通用的“向量工作原理”，但这正是向量的基本思想，它们完成工作，你不必担心 =）每个实现都有自己的哲学。Java的我不知道，但我知道C++的应该类似。

为什么要将大小加倍？或者为什么要请求一个恒定的大小？

假设你需要存储一千个整数。

每次需要更多空间时，请求10个int的向量将分配10个空间，然后再加上10个，然后再加上10个，然后......一百次分配。

每次加倍大小的向量将请求1、2、4、8、16、32、64、128、256、512、1024的空间。只需要十次分配。

一些程序员不想要末尾的24个空位，或者只想要一个分配（直接分配一千个），所以他们制作了一个向量类，分配他们认为好的一些固定内存大小。

C++向量有特定的函数来处理这些问题，例如resize()，它将要求向量具有特定的大小，或者reserve()，它将要求向量在内存中保留特定的空间。

---

"而且，至少，这个网站是金子般的："

http://www.cplusplus.com/reference/vector/vector/

这是关于C++实现的，但是思想是通用的。而且阅读是有益的 =)

- Kahler

Answer 4

正如Jigar所提到的，它在内部管理数组，以下是如何增加大小的实现（我是用Java说的）：

//This ensures size of Vector
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    //elementData is array of type Object
    elementData = Arrays.copyOf(elementData, newCapacity); //Copies the specified array with specified capacity for array
}

上述方法是在向Vector添加任何数据时调用的，它确保新创建的Vector的大小。

- Vishrant

Answer 5

如果动态分配了数组，就可以调整它的大小。例如在C语言中，通过malloc()函数动态分配内存。您可以通过realloc()重新分配该内存空间，并更改其大小。

如果您以这种方式在C / C ++中分配数组：

int array[5];

它将被分配在您声明的函数的堆栈帧中。相反，向量是一个高级对象，在堆内存段上动态分配。

- Dante