Data Structures: dynamic arrays in C

mgcadmin 29-09-2021

How to implement vector style dynamic arrays in C.

Dynamic Arrays

Most programming languages today offer some implementation of dynamic arrays in their standard libraries. Dynamically typed languages such as Perl, Swift, and PHP use dynamic arrays as their default. C++ offers std::vector via the Standard Template Library. I could continue, but you get the point.

Once you've become accustomed to the simplicity of dynamic arrays - vectors - the thought of using their static older brother makes one groan inside. Don't get me wrong: static arrays have their place, particularly in embedded devices where memory resources are at a premium.

What about C?

In the minimalist tradition, C does not include a vector type in its standard library, but it DOES give you everything you need to implement them yourself, as C always does. The concept behind a vector is simple: You allocate a static array in the normal way, when that array runs out of space, you allocate another array with twice as much space, copy all your data offer to this new array, rinse, repeat. By using realloc() C handles the reallocation and copying of data for us.

Implementation

The first step in creating a vector is to define a struct that will contain an array to hold our data, an integer to hold the current number of elements in the array, and an integer to hold the maximum size of our array. These values are needed for resizing our array.

typedef struct {
  int *arr;
  int max_size;
  int current_size;
} vector;

Next we need a function to handle the allocation and initialization our vector:

vector* newVector(int n)
{
  vector* v = malloc(sizeof(vector));
  v->arr = malloc(n + sizeof(int));
  v->max_size = n;
  v->current_size = 0;
  return v;
}

The next function is the important part. We could, if we wanted, assign values to our array by interacting with our vector array by treating it as a static array, but that would defeat the whole purpose. Instead, we will implement a push_back() function which will add an item to the end of our array, while simultaneously handling the resizing if necessary:

void vector_push_back(vector* v, int n)
{
 if (v->current_size == v->max_size)
 {
  v->max_size *= 2;
  void* temp = realloc(v->arr, v->max_size * sizeof(v->arr));
  if (!temp) {
   return; //realloc failed
  }
  v->arr = temp;
 }
 v->arr[v->current_size++] = n;
}

and with that, we now have an array that grows in size as needed. Another function that makes sense to implement is a shrink_to_size() function. If we know that we wont need be adding any more data to our vector, we can realloc() again, this time shrinking it to hold the current number of elements, thus freeing up memory for use by other resources:

void vector_shrink_to_size(vector* v)
{
 void* temp = realloc(v->arr, (v->current_size + 1) * sizeof(v->arr));
 if (!temp) {
  return;
 }
 v->arr = temp;
}

And of course since we are allocating and using heap memory, we must always remember to free that memory when we are done using it to avoid memory leaks:

void destroyVector(vector* v)
{
  free(v->arr);
  free(v);
}

And with that, we have added this simple, but incredibly useful data structure to our C programming tool box. Lets take it for a spin to test it out in action:

#include <stdio.h>
#include <stdlib.h>

#include "vector.h"

int main(int argc, char *argv[])
{
  vector* myVec = newVector(5); /* create a vector with an initial size of 5 */
  for (int i = 1; i <= 30; i++)
  {
    vector_push_back(myVec, i);
  }
  for (int i = 0; i < myVec->current_size; i++)
  {
    printf("%d ", myVec->arr[i]);
  }
  return 0;
}

Output:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Source code of the examples shown in this article is available via my github at:

https://github.com/maxgoren/examples/blob/main/vector.h

---