C99/C11 dynamic array that mimics C++'s std::vector - API improvements
Posted on January 8, 2017 by Paul
In my last article I wrote a portable C dynamic array, auto-resizable and theoretically capable to store any C representable data type. While the original implementation works, it is a bit cumbersome to use in practice. A better approach is to create a dynamic array that looks like a normal C array, but it is capable to automatically adjust its size as needed. I took from Sean Barrett’s stb libraries the idea that you can store the size information of an array at the beginning of the array, while publicly exposing a pointer to where the array data resides in memory. The advantage of this approach is that from a user point of view a dynamic array can be used like a C array, except for the creation and destruction phases.
It goes without saying that this article is written for C programmers or people that use a C compiler. If you are using C++, you usually don’t need to implement a vector type, you already have one in the STL, use it.
It will be easier to understand how the general case works if we start with an explicit implementation for a dynamic array of integers. Conceptually, our code has three phases
In phase 1, we will start by initializing the array:
The do while loop that runs only once, is currently used to hide the raw pointer initialization. The user can access directly only the arr pointer that, after the initialization phase, points to the first address, after the size and capacity information. Later, we will move the do while loop in a macro that will abstract the initialization phase.
Next, let’s put some data in our array:
Please note the pattern that we use to access the raw pointer that points to the beginning of our array. After that, we resize the array if necessary and copy the data to the array buffer. At this point, the user can use a simple for loop to iterate over the content of the array. In order to do this we could implement a macro functions that will get the size of the array:
It is interesting to observe how the array is resized: after 1 insertion the array will have a capacity of 1, after 2 insertions the capacity will be 2, after 3 insertions the capacity will be 4 and so on. The array is not resized after every insertion but only when it is necessary.
And here is an example of how you can loop over the array and modify the data:
In order to destroy the array and free the memory we could use something like this:
Now, we can take most of the above code and create a few macros that could create, push any type of data and destroy the array. I will create a header file, array.h, that will contain the generalized helper macros:
I will leave as an exercise for the reader the implementation of an ARRAY_RESIZE and ARRAY_SHRINK_TO_FIT macros. Hint, in order to implement ARRAY_SHRINK_TO_FIT use realloc to resize the memory buffer in order to have size/raw equal to capacity/raw.
Next, let’s try a more challenging example that will use one array of integers and one array of a user defined data type. We’ll initialize the arrays, add 50 elements to each array and print the content of the arrays. At the end we will release the memory used by our two dynamic arrays:
This is the result of running the above code on my machine:
Please note that all the above code was tested with Clang 3.8, GCC 6.3 and Visual Studio 2017. Normally, it should work with any recent C99/C11 compiler, with the notable exception of Visual Studio, for which parts of the C99 standard were added starting with the 2013 version. If you are using Visual Studio 2017 and up, you should be able to use the full C11 Clang toolchain from Visual Studio instead of the CL compiler.