C99/C11 dynamic array that mimics C++'s std::vector
Posted on January 6, 2017 by Paul
Recently, I’ve worked on a large C library used to store items from a database. The idea was to get all records that matched a particular criteria and store these in a C data structure for further processing. The original author of the library used a linked list to store the records which probably was a sensible idea 20 years ago. However, today’s computers perform better if you use a cache friendly data structure like an array. Basically, I wanted a dynamic array that automatically increases his size if needed, something like C++'s std::vector.
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.
Let’s start with a simplified problem - say that we want a C dynamic array that stores integers, something like this:
In the above structure, size represents the number of elements from data and capacity the memory allocated for data. Following the C++ std::vector model, every time size is equal to capacity we will increase the available memory by a factor of twice the number of elements currently stored.
First, we need two helper functions to create/destroy an Array:
For simplicity we didn’t check if calloc was successful, don’t take shortcuts in production code!
Using the above functions we can, for example, create two arrays:
Please note that arr is initially empty, has zero elements, while arr2 can store 100 elements. We can iterate over the data stored in an Array with:
What if we want to add some data to an Array ? Again, following the C++ std::vector model, we can implement a push_back function that will insert numbers to the end of our array, resizing the data buffer if necessary:
At this point, we have a working, albeit simplified, C dynamic array that can store an arbitrary number of integers. Here is an example of how we can use Array:
I will leave as an exercise for the reader the implementation of a shrink_to_fit function. Hint, use realloc to resize the data buffer in order to have size equal to capacity.
What if we want to be able to store more than integers in our dynamic array ? A classical C pattern is to use a void pointer, something like:
No change is necessary for the array_free function. However, array_create must be modified to account for the size of the data type we want to store in data:
The array_push_back function also needs to be refactored in order to account for the size and type of what we store in the data buffer. A possible approach is to use a macro, instead of the original function:
Assuming that we have all of the Array functions and macros defined in a file named Array.h, let’s see an example of how we can store arbitrary types in an Array.
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.
If you want to learn more about C99/C11 I would recommend reading 21st Century C: C Tips from the New School by Ben Klemens:
or the classic C Bible, The C Programming Language by B.W. Kernighan, D.M. Ritchie: