为什么C++和Java中的动态数组具有不同的初始容量？

所以我一直在寻找实际上动态数组的工作原理。我发现的是两个不同的概念。为什么C++和Java中的动态数组具有不同的初始容量？

在C++

在C++中，动态阵列通常通过载体实现。向量将容量设置为0，增加计数以插入新元素，然后将新插入的容量大小加倍。

vector.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可以节省初始化内存的开销。

由于它是一个动态数组，矢量不会有害设置容量小，因为动态数组的大小一般超出10

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

来源

2017-08-08 secretgenes

@juanchopanza [这个问题]（https://stackoverflow.com/questions/23414302/c-vector-initial-capacity）说所有着名的实现默认为0. – Barmar

@Barmar RIght，我的错误。 – juanchopanza

矢量也随着某些因素增长，它不需要是2倍。 –

默认情况下容量为零具有的优点是，默认构建一个std::vector根本不会执行任何动态内存分配（您不支付您不需要的东西）。如果你知道你需要〜10个元素，你可以明确地通过调用std::vector::reserve设置容量：

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

我只能推测，为什么Java那样的事情不同，但据我所知，动态内存分配是Java比便宜C++和两种语言也遵循不同的哲学，当涉及到性能/低级别控制与简单性。

来源

2017-08-08 20:47:28 MikeMB

我会摆脱afaik评论。它增加了很少，并会吸引巨魔。剩下的看起来是正确的，特别是不同意识形态在“不需要，不付钱”和“让程序员很难搞砸”的思想上。 – user4581301

但是，这并不能加倍容量！ – SergeyA

或者（如果你需要10个元素），你可以使用向量ctor给你。 –

为什么默认为0？

实际上，默认情况下它不是0。那就是the C++ language standard does not define (AFAIK) what the initial capacity of a default-constructed vector should be。

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

你不使用，你不支付。

_{（参见：B. Stroustrup的：The Design and Evolution of C++艾迪生韦斯利，ISBN 0-201-54330-3 1994年3月。）}

而且这不只是一个简单的同义反复 - 这是设计的斜面注意事项。因此，在C++中，我们宁愿不支付任何东西对于没有插入任何元素的向量，然后通过做出初始“牺牲”来节省潜在的大小增加。

由于@yurikilocheck指出，然而，std::vector类并为您提供reserve()方法，这样你就可以设置一个初始容量自己 - 既然默认构造函数不分配任何东西，你就不会支付“额外'，两次分配 - 只需一次。再次，您支付（基本上）尽可能最低。

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

来源

2017-08-08 20:51:54 einpoklum

加倍容量失败不使用，不支付。 – SergeyA

@SergeyA：这是一个很好的观点。 – einpoklum

@SergeyA它有一种，因为它只涉及一个分配。大部分时间比分配所需容量便宜。 – juanchopanza

我已经使用了一个实现，每个向量保留32个元素的默认值。这是本机Sun C++ STL实现。那是一场灾难。我有一个完全合理的计划，因为它的本性必须有几十万的那些媒介。它的内存不足了。它应该已经运行良好，因为那些成千上万的元素只有很小的百分比，这些矢量非空。

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

来源

2017-08-08 21:15:45 SergeyA

为什么C++和Java中的动态数组具有不同的初始容量？

回答

相关问题