A dynamic array implementation in C++

Somewhere in Medium, I found Google Interview University (Give it a look!) and decided to follow some of the advices given; starting by creating my own implementation of basic data structures.

What is a dynamic array?

In layman’s terms, a dynamic array is similar to an array, but with the difference that its size can be dynamically modified at runtime.

The elements of an array occupy a contiguous block of memory, and once created, its size cannot be changed. A dynamic array can, once the array is filled, allocate a bigger chunk of memory, copy the contents from the original array to this new space, and continue to fill the available slots.

In the backend, dynamic arrays allocate a predetermined amount of memory on creation, which then grows by a certain factor when needed. These parameters, initial size and growth factor are central in terms of performance. If the initial size and growth factor are small, you’ll end up reallocating memory often, which isn’t good; on the other hand, if they have a higher value, you’ll probably have a lot of unused memory, and the resize operation could take longer. The tradeoff is obvious here.

Examples of dynamic arrays in common languages are ArrayList in Java and C#, Vector in C++, List<> in .NET, Python’s list, among others.

The implementation

I started writing a dynamic array of integers in C. While doing so, I noticed that it would be better to write a class Array that managed the data structure, so I switched to C++. And, since we are already on C++, I decided to create a template class, so that we could manage a dynamic array of any type :).

That’s my Array class; the important methods here are Array (constructor), push, pop, set, get and resize. The attributes used are m_size, the current size of the array, m_capacity, the current capacity of the array, andm_data, a pointer to the data of the array. I also declared some utilitary methods, like size(), capacity() & print().

Constructor

Sets up size and capacity. Here, I used a predetermined value for the initial capacity. Size is zero, since on creation there`s no data on the array. Also, space for the array is allocated.

Destructor

Frees the allocated memory, m_data.

Push

Pushes a value to te top of the array. Must ensure that there’s space available in the array before pushing! Failing on doing so, could cause a segmentation fault.

Pop

Returns the value at the top of the array, and removes it from the array, by diminishing the size of it by one.

Set

Sets a value in the array for the given index. If the index is greater than the current capacity, the array is resized and filled with zeros until the index is reached.

Resize

As the name tells, it resizes the array, making it grow by a given factor. To do this, I used the realloc function. You could use malloc/memcpy too. If realloc succeeds, m_data points to the auxiliary pointer tmp.

Testing

This is a little example on how to use the data structure, creating and manipulating an array of integers.

And the result…

Code

I’ll leave the full implementation in my Github, feel free to comment or suggest changes if you see something wrong :)