Arrays in C are fixed in size. In order to use a Dynamic Array in C one has to allocate memory manually and later free it to prevent memory leaks. Furthermore Arrays cannot be passed by reference to functions.
In C++ there is a Dynamic Array Class called std::array which is part of the STL in C+ as std::array<T>, where T stands for the type you want the collection to be of.
In C there is nothing like this so we have to implement it for ourselves. We will rely on some concepts from my article on how to implement Classes in C, so read it first if you are interested.
If you need an overview of different containers and their advantages and disadvantages you can find them in my article here.
In this Article...
How an Array works
An Array is a simple list of a given datatype. The number of elements is known at construction time, it is also fixed over the lifetime of an Array. This means that memory is allocated once and never changes until destruction. The contents of an array are addressed by an Index which is a whole number.
Array Memory Allocation
The memory is allocated and then only freed if the Array is destroyed. This makes Access performant because the size is known and the memory is reserved adjancantly.
Dynamic Array vs. Vector
Dynamic Arrays are good when you know how many elements you will (maximal) need at compile time. If you need a more flexible container then a Vector may be the better choice because it is dynamically sizeable.
A Note on Multi-Dimensional Arrays
A Multi-Dimensional Array (i.e. Matrix) is an Array with more that one Dimension. An example would be a simple 2×2 Matrix, storing 2 rows and 2 columns. In C this would look like this:
int my_matrix[2][2];
my_matrix[0][0] = 1; /* Set first column in first row to 1 */
my_matrix[1][1] = 2; /* Set second column in second row to 2 */We will not describe or use Multi-Dimensional Arrays in this article.
Goals of the Dynamic Array Implementation in C
We will implement a Dynamic Array Class in C that is capable of the following features:
- Initialization of Array (and clean up!)
- Adding Elements to Array
- Accessing Elements in Array
- Removing Elements from Array
We will only implement a Dynamic Array for the Integer (int) type. The C language is missing the <template> stuff that C++ provides so you have to make an implementation for every type that you need. (You maybe could use void-Pointers but that is a rabbit whole of it’s own…)
Dynamic Vector Initialization in C
We will need three files for our implementation:
- array.h – here we define the Interface for our Array
- array.c – the actual Array implementation
- main.c – here we write a little program to test our Array
The header file serves as an interface for our Dynamic Array “Class”. The struct is only declared but not defined yet because we will treat it as if they were private members of a class. The functions are for creating and destroying the array.
In contrast to our Vector Class we can specify the initial size of the Array ourselves with the help of the size argument in the Constructor array_ctr(…).
#pragma once
typedef struct array_t array_t;
array_t* array_new();
void array_ctr(array_t* obj, const int size);
void array_dtr(array_t* obj);Our struct is now defined an contains the elements and a member for storing the current size. In the constructor we set the size and allocate enough memory for it. Be aware that we don’t check against negative numbers here, maybe you come up with a solution for this.
The destructor makes sure that all allocated memory is freed and thus no memory leak is created.
#include "array.h"
#include <stdlib.h>
typedef struct array_t {
int* elements;
int size;
} array_t;
array_t* array_new()
{
return (array_t*) malloc(sizeof(array_t));
}
void array_ctr(array_t* obj, const int size)
{
obj->elements = calloc(size, sizeof(array_t));
obj->size = size;
}
void array_dtr(array_t* obj)
{
if(NULL != obj) {
if(NULL != obj->elements) {
free(obj->elements);
}
free(obj);
}
}The Test Program for this is quite simple and doesn’t do that much. It only creates an array with space for two elements and immediatly gets destroyed. There is no output yet.
#include "array.h"
int main(int argc, char** argv)
{
array_t* my_array = array_new();
array_ctr(my_array, 2);
array_dtr(my_array);
return 0;
}Adding an Element to a Dynamic Array in C
You cannot really add new Elements in an Array. The size of the array is fixed and this is why you have to pass it as a parameter to the constructor. Then you set the values within the Array.
If you need a container with Array behaviour but flexible in size, you should take a look at my Implementation of the Vector Container Class in C.
Getting Information about the Array
The STL Container Classes all have empty() and size() functions, Array also has max_size().
However, an Implementation of empty() is not needed for our class, because the size of the Array is fixed and if you create an empty Array you could never use it for anything.
The return values of the functions size() and max_size() should always be equal, so we will only have to implement the size() function and then simply forward max_size() to it. The header declaration then looks like this:
...
int array_size(array_t* obj);
int array_max_size(array_t* obj);
...In the Implementation of size() we simply return the size of the Array. Although I said that we will forward max_size() to size() I decided to copy the Implementation. This way we save one function call in exchange for duplicate code. It’s a matter of preference and if size() would be more than this one line just returning a value then I would definitly opt for the forwarding.
...
int array_size(array_t* obj)
{
return obj->size;
}
int array_max_size(array_t* obj)
{
return obj->size;
/*return array_size(obj); => Forward if size() would be more complicated */
}
...We add two output statements to our test program to show that both functions return the same value.
#include "array.h"
#include <stdio.h>
int main(int argc, char** argv)
{
array_t* my_array = array_new();
array_ctr(my_array, 2);
printf("Array Size: %d\n", array_size(my_array));
printf("Array Max-Size: %d\n", array_max_size(my_array));
array_dtr(my_array);
return 0;
}We see that although we did not set any values, the size of the array is 2 and that max_size() equals size().
Array Size: 2
Array Max-Size: 2Accessing Dynamic Array Elements in C
There are several possibilities to access elements in an Array, both for reading and writing. The most intuitive, however, is not available because of language restrictions.
(Not) Accessing Elements with []
Unfortunatly, the C Language does not support operator overloading. If you create a standard C Array you access Elements with this syntax:
int classic_array[2];
classic_array[0] = 1;However, we cannot do this with our “Class” because we cannot overload the brackets operator. We use a pointer to a struct and cannot set a value to the elements within the struct directly. This means that we cannot create the syntax from above.
Or can we? Maybe there is a way using MACROS and/or Pointer Magic but I leave this as an exercise to you
Accessing Elements with at()
Like in a Vector, we access our Elements with the at(…) function. The function takes the index of the Element you want to access as a parameter.
In order to write to an index, we create the array_set(..) function which additionally takes the value to set as a third parameter.
...
int array_at(array_t* obj, const int index);
void array_set(array_t* obj, const int index, const int value);
...In the definition of at(…) we return the element at the given index. Beforehand we have to check if there are any elements in the array and that the index does not access an invalid index.
In the array_set(..) function we have the same guard clause and then simply set the value at the given index of elements.
...
int array_at(array_t* obj, const int index)
{
if(obj->size <= 0 || index >= obj->size || index < 0) {
return 0;
}
return obj->elements[index];
}
void array_set(array_t* obj, const int index, const int value)
{
if(obj->size <= 0 || index >= obj->size || index < 0) {
return;
}
obj->elements[index] = value;
}
...In our test program we first check the initial value of our first Element. Then we set the first value of our Array and immediatly print it to the Console again.
...
int main(int argc, char** argv)
{
array_t* my_array = array_new();
array_ctr(my_array, 2);
printf("First Element (inital): %d\n", array_at(my_array, 0));
array_set(my_array, 0, 1);
printf("First Element (after set): %d\n", array_at(my_array, 0));
array_dtr(my_array);
return 0;
}This leads to the following output:
First Element (inital): 0
First Element (after set): 1Accessing Elements with front() and back()
These functions give us the values of the first and the last element of an Array. The header declaration is simple indeed.
...
int array_front(array_t* obj);
int array_back(array_t* obj);
...The implementation is almost as simple. We only check if the size is positive and then return the first or the the last element of the array.
...
int array_front(array_t* obj)
{
if(obj->size <= 0) {
return 0;
}
return obj->elements[0];
}
int array_back(array_t* obj)
{
if(obj->size <= 0) {
return 0;
}
return obj->elements[obj->size-1];
}
...For our test program we create another array with 5 elements. Then we set all elements in correlation to its index and do some math for fun. Then we ask for the front() and the back() of the Array.
...
int main(int argc, char** argv)
{
array_t* another_array = array_new();
array_ctr(another_array, 5);
for(int i=0;i<5;i++) {
array_set(another_array, i, (i+1)*2);
}
printf("First Element (front): %d\n", array_front(another_array));
printf("Last Element (back): %d\n", array_back(another_array));
array_dtr(another_array);
return 0;
}
...The output shows that our functions work. The first element is (i+1)*2=(0+1)*2=2 and the last element is (i+1)*2=(4+1)*2 = 10.
First Element (front): 2
Last Element (back): 10Removing Dynamic Array Elements in C
As with adding Elements to an Array it is the same with removing. You cannot change the size of an array so the best thing you could do is to set the value to 0 which is not really what you want.
Reducing the size of your container is an option if you use my Implementation of the Vector Class in C.
Swapping and Filling Dynamic Arrays in C
We have two more functions to cover that both of which affect the Array as a whole. The fill(…) function takes a given value and sets every value within the array to this. The swap(..) function completely swaps the contents (including size) of two arrays.
...
void array_fill(array_t* obj, const int filler);
void array_swap(array_t** source, array_t** target);
...The fill(…) function does not need a guard clause because if it is empty then nothing will be filled. Otherwise is every element set to the given value.
The swap(…) function checks if both given Arrays are not NULL and then swaps the contents.
...
void array_fill(array_t* obj, const int filler)
{
for(int i=0; i<obj->size;i++) {
obj->elements[i] = filler;
}
}
void array_swap(array_t** source, array_t** target)
{
if(NULL == source || NULL == target) {
return;
}
array_t* temp = *source;
*source = *target;
*target = temp;
}
...Our last test program uses both functions. It creates two arrays with different sizes and fills both with different values. Then the arrays are swapped and we check if everything is fine by console output.
...
int main(int argc, char** argv)
{
array_t* int_values = array_new();
array_ctr(int_values, 2);
array_t* tni_values = array_new();
array_ctr(tni_values, 3);
array_fill(int_values, 1);
array_fill(tni_values, 5);
array_swap(&int_values, &tni_values);
printf("Array Size INT_VALUES: %d\n", array_size(int_values));
printf("First Element (front) INT_VALUES: %d\n", array_front(int_values));
printf("Array Size TNI_VALUES: %d\n", array_size(tni_values));
printf("First Element (front) TNI_VALUES: %d\n", array_front(tni_values));
array_dtr(int_values);
array_dtr(tni_values);
return 0;
}The output shows that everything worked as intended.
Array Size INT_VALUES: 3
First Element (front) INT_VALUES: 5
Array Size TNI_VALUES: 2
First Element (front) TNI_VALUES: 1Summary & Further Ideas
This is the implementation of the Dynamic Array Class in C. Feel free to use and optimize it for your own needs.
I personally think that the Vector Class may be more useful because it is flexible in size and if you really need a fixed array (for memory and/or performance reasons) you may use a “normal” one. Having said that, I also think that is safer to use this Dynamic Array Class because of the encapsulation we built around it.
In any case it is a good exercise to implement this class. You could maybe even try to implement it using Unit Testing in C.
Another good exercise for you may be extending this Class to make it possible that a Multi-Dimensional Array can be created.
