爲什麼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中的動態數組具有不同的初始容量？

回答

相關問題