Why do dynamic arrays in C++ and Java have different initial capacities?

Question

So I've been searching for how actually dynamic array works in general. what i found is two different concepts.

In C++

In C++, dynamic array is generally implemented by vectors. Vectors set the capacity to 0, increases the count to insert new element and then doubles the capacity size for new insertions.

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;
}

For expanding the vector size

/*
 * 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;
}

In Java

In java, dynamic array is implemented using arrayList, They set the capacity to 10 (JVM based) and once the capacity is full they increases the capacity by some factor. Reason being for setting the capacity to 10 is that you don't have to initialize the memory frequently for every new insertion. Once the capacity is full increase the capacity size.

curiosity

Why implementation in vector.h sets the default value to 0?? Setting the capacity to some small value (lets say 10)instead of setting it to 0 may save the overhead of initializing memory every time user inserts some element.

As it is a dynamic array, setting small capacity for vector will do no harm because size of dynamic array generally goes beyond 10.

Edit : My question is why default 0 ? it could be any small value by default , because anyways vector is going to expand to some specific size , that's the purpose of using vector in first place.

Answer 1

Having a capacity of zero by default has the advantage that default constructing an std::vector doesn't do any dynamic memory allocation at all (You don't pay for what you don't need). If you know you need ~10 elements, you can set the capacity explicitly via calling std::vector::reserve:

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

I can only speculate, why Java does things differently, but afaik, dynamic memory allocation is cheaper in Java than in c++ and the two languages also follow different philosophies, when it comes to performance/low level control vs simplicity.

Answer 2

Why default 0?

It's not 0 by default, actually. That is, the C++ language standard does not define (AFAIK) what the initial capacity of a default-constructed vector should be.

In practice, most/all implementations default to 0-capacity. The reason, I would say, lies in one of the design principles of the C++ language is:

What you don't use, you don't pay for.

_{(see: B. Stroustrup: The Design and Evolution of C++. Addison Wesley, ISBN 0-201-54330-3. March 1994)}

And this is not just a trivial tautology - it's a slant of design considerations.

So, in C++, we would rather not pay anything for a vector which does not have any elements inserted into it, then save on potential size increases by making an initial "sacrifice".

As @yurikilocheck points out, however, the std::vector class does provide you with a reserve() method, so you can set an initial capacity yourself - and since the default constructor doesn't allocate anything, you will not have paid 'extra', for two allocations - just once. Again, you pay (essentially) the minimum possible.

Edit: On the other hand, std::vector partially breaks this principle in allocating more space than it actually needs when hitting its capacity. But at least it's not a superfluous allocation call.

Answer 3

I have used an implementation which reserves a default value of 32 elements per vector. It was native Sun C++ STL implementation. It was a disaster. I had a perfectly reasonable program which by it's nature had to have somewhat about hundreds of thousands of those vectors. It was running out of memory. And it should have been runinng fine, since of those hundreds of thousands of elements only small percentage had those vectors non-empty.

So from personal experience, 0 is the best default vector size.