4

所以我一直在寻找动态数组通常是如何工作的。我发现是两个不同的概念。

在 C++ 中

在 C++ 中，动态数组一般由向量实现。向量将容量设置为 0，增加插入新元素的计数，然后将新插入的容量大小加倍。

矢量.h

/*
 * Implementation notes: Vector constructor and destructor
 * -------------------------------------------------------
 * The constructor allocates storage for the dynamic array and initializes
 * the other fields of the object.  The destructor frees the memory used
 * for the array.
 */

template <typename ValueType>
Vector<ValueType>::Vector() {
   count = capacity = 0;
   elements = NULL;
}

用于扩展矢量大小

/*
 * Implementation notes: expandCapacity
 * ------------------------------------
 * This function doubles the array capacity, copies the old elements into
 * the new array, and then frees the old one.
 */

template <typename ValueType>
void Vector<ValueType>::expandCapacity() {
   capacity = max(1, capacity * 2);
   ValueType *array = new ValueType[capacity];
   for (int i = 0; i < count; i++) {
      array[i] = elements[i];
   }
   if (elements != NULL) delete[] elements;
   elements = array;
}

在 Java 中

在 java 中，动态数组是使用 arrayList 实现的，它们将容量设置为 10（基于 JVM），一旦容量已满，它们就会将容量增加一些。将容量设置为 10 的原因是您不必为每次新插入频繁地初始化内存。一旦容量已满，请增加容量大小。

好奇心

为什么vector.h中的实现将默认值设置为0？将容量设置为某个较小的值（比如说 10）而不是将其设置为 0，可以节省每次用户插入某个元素时初始化内存的开销。

因为是动态数组，所以设置vector的小容量是没有坏处的，因为动态数组的大小一般都在10以上。

编辑：我的问题是为什么默认 0 ？默认情况下它可以是任何小的值，因为无论如何向量都会扩展到某个特定的大小，这就是首先使用向量的目的。

4

3 回答 3

6

默认情况下容量为零的优点是默认构造 anstd::vector根本不进行任何动态内存分配（您不需要为不需要的东西付费）。如果您知道需要约 10 个元素，则可以通过调用显式设置容量std::vector::reserve：

std::vector<int> vec;
vec.reserve(10);

我只能推测，为什么 Java 做的事情不同，但是 afaik，Java 中的动态内存分配比 C++ 更便宜，而且这两种语言在性能/低级控制与简单性方面也遵循不同的理念。

于 2017-08-08T20:47:28.017 回答
3

我使用了一个实现，它为每个向量保留 32 个元素的默认值。它是本机 Sun C++ STL 实现。那是一场灾难。我有一个完全合理的程序，它本质上必须有大约数十万个这些向量。它内存不足。它应该运行良好，因为在这数十万个元素中，只有一小部分的向量是非空的。

所以从个人经验来看，0 是最好的默认向量大小。

于 2017-08-08T21:15:45.173 回答
3

为什么默认为 0？

实际上，默认情况下它不是 0。也就是说，C++ 语言标准没有定义（AFAIK）默认构造向量的初始容量应该是多少。

在实践中，大多数/所有实现默认为 0 容量。我想说的原因在于 C++ 语言的设计原则之一是：

你不用的东西，你不用付钱。

（参见：B. Stroustrup：C++ 的设计和演变。Addison Wesley，ISBN 0-201-54330-3。1994 年 3 月）

这不仅仅是一个琐碎的重言式 - 这是一个设计考虑的倾斜。

因此，在 C++ 中，我们宁愿不为没有插入任何元素的向量支付任何费用，然后通过进行初始“牺牲”来节省潜在的大小增加。

然而，正如@yurikilocheck 指出的那样，std::vector该类确实为您提供了一种reserve()方法，因此您可以自己设置初始容量 - 由于默认构造函数不分配任何内容，因此您无需为两次分配支付“额外”费用 -就一次。同样，您支付（基本上）尽可能低的费用。

编辑：另一方面，std::vector在达到其容量时分配比实际需要更多的空间部分打破了这一原则。但至少它不是一个多余的分配调用。

于 2017-08-08T20:51:54.630 回答