UPDATE: Thanks for all the great comments! Apparently I’m the #1 result for “C dynamic array” on Google. Pretty cool. 
It’s certainly taken me a while to get around to it, but I’ve updated this tutorial and sample code to incorporate some of your suggestions and comments. Thanks a bunch, especially to bbulkow and tinkertim!
For the purposes of education and the prospect of writing a new game, I’ve been doing some poking around in C. I’ve certainly learned a few things (and expect to learn more in the future) Prior to this, I’ve only had experience with C++, which some would argue is a completely different beast altogether. However, this post is not intended to discuss the differences between C and C++.
Anyways, I figured I might share a few snippets and wisdom that I’ve picked up along the way, so here’s a quick (?) rundown of how to use structs and pointers to create “dynamic” arrays that will resize as you need them.
Right, so let’s suppose you’ve got a struct built that you’ll use to hold some data…
typedef struct {
char *name;
int number;
} DATA;
And we’ll also need to set up an array, along with some variables to track how many items are in the array and how large the array is…
DATA *the_array = NULL; int num_elements = 0; // Keeps track of the number of elements used int num_allocated = 0; // This is essentially how large the array is
What’s this? I’m not using []’s to define the size of the array? That’s right; At this point, the array is just a pointer. We’ll need to allocate memory for each entry into the array.
So next, we need a way to add items to our array that will be mindful of the fact that it is dynamic. What is needed is a function that will do three things:
Keeping that in mind, let’s take a look at the realloc function’s prototype:
void * realloc ( void * ptr, size_t size );
The purpose of this function is to re-allocate memory to a pointer that already has memory allocated to it. Of course, you’ll only want to use it to make memory allocations larger, otherwise you’ll risk losing data. The size parameter is the amount of memory that you want to allocate. And the other parameter, ptr, is where you’d like to allocate it to. In this case, it’ll be the TheArray pointer that we’ve defined above. What is great about realloc is that if the ptr is NULL, the function will act just like malloc. This will allow us to use this one call for both initializing and resizing the array. Check this realloc reference page for more information.
Here is my AddToArray function …
int AddToArray (DATA item)
{
if(num_elements == num_allocated) // Are more refs required?
{
// Feel free to change the initial number of refs
// and the rate at which refs are allocated.
if (num_allocated == 0)
num_allocated = 3; // Start off with 3 refs
else
num_allocated *= 2; // Double the number
// of refs allocated
// Make the reallocation transactional
// by using a temporary variable first
void *_tmp = realloc(the_array, (num_allocated * sizeof(DATA)));
// If the reallocation didn't go so well,
// inform the user and bail out
if (!_tmp)
{
fprintf(stderr, "ERROR: Couldn't realloc memory!\n");
return(-1);
}
// Things are looking good so far
the_array = (DATA*)_tmp;
}
the_array[num_elements] = item;
num_elements++;
return num_elements;
}
You can see that it performs all three requirements listed above.
You may ask, ‘why is the allocation size doubling each time a resize is needed?’. This is done mainly because realloc() can be an expensive call, and if you spend a lot of time resizing your array, it could slow down the execution of your application. This way, it’s only done once in a while. Of course, feel free to fiddle with the initial allocation as well.
Also, be careful when using realloc(), as you’ll need to remember to use the free() function later on to free the memory that you’ve allocated to your program. You’ll want to run this code when you’re done using the array …
// Deallocate! free(TheArray);
I’ve got a little example available right here:
Download Example – (arrays.c – 2kb)
It compiles and runs just fine using GCC, but I haven’t tried it with anything else, so your mileage may vary. Also, a huge special thanks to DrPetter and X-0ut for their help on this subject!
As always, comments are welcome!
Sorry if this is a dumb question but why would “TheArray” ever be NULL?
if (TheArray == NULL)
{
fprintf(stdout, “ERROR: Couldn’t realloc memory!”);
exit(2);
}
Sorry for not adding this into my first reply, but how do you deallocate each item in the array if you do not know the size of the array?
Hi Anthony! Thanks for the comments.
I probably should have elaborated a little more in the article, but if there is insufficient memory available, the realloc() call will return NULL. Since you don’t have any control over how much free memory the user will have available, it’s a good idea to check to ensure the allocation succeeded.
As for your second question, in my example I’ve created two variables that will track the number of elements in the array, as well as the number of elements allocated in the array. You actually don’t even need those variables for deallocation, as just passing the array to the free() function will automatically deallocate the entire array.
Hope that helps!
thx for the tutorial it helped alot.
amazing!
I’ve learned about realloc.
@7
Your code has two flaws, and since you’re the number one Google entry under ‘C dynamic array’, I feel moved to comment.
First,
When ‘realloc’ returns NULL, the input data is not freed. Thus, you’ve written a memory leak (at least, you would if the error case wasn’t ‘exit()’). It’s more common to use a metaphor like this:
void *_tmp = realloc(TheArray, newsize);
if (!_tmp) { fprintf(stderr,”whoa, dude, no memory\n”); return(-1); }
TheArray = _tmp;
thus your structure contains the data before the failed add, thus can be used if the addition isn’t fatal, and a ‘free’ of the object is uncomplicated.
Second, TheArray is uninitialized. If you’re programming in Linux, ‘valgrind’ is a huge tool here, other analysis tools like Purify are available for other platforms.
Hi this tutorial is highly helpful and very lucid
I would have made AddToArray() a signed int type that returned:
– The number of elements currently in the array on success
– 0 on a non-fatal error (i.e., DATA is in tact)
– -1 on a fatal error (i.e. , don’t use DATA anymore and don’t try to free it)
I also suggest the comment made by bbulkow which in essence makes realloc() (and by extension AddToArray() ) transactional.
Beyond that … ThisIsNotJava(Its_C);
I know .. I know .. everyone’s a ^@*&^ critic
This kind of dynamic array only stores elements of type “DATA”, which are structs with two fields – a string and an integer. What if you want to make a dynamic array structure that supports any type of element?
I’ve been trying to do it and ran into some weird trouble… I have another kind of field in my dynamic array for this purpose, element size, which is assigned to the array with a special initialization function. It is then used in all subsequent reallocations.
For some reason, at some point realloc messes up my data and then outputs some memory access error (realloc?? how is that possible?)… Anyone have some sugguestions?
Actually, never mind that, I got the dynamic array of variable element type to work. Anyone interested in the source can post a request here.
great tutorial! this really helped me a lot! wow!
Hi,
this is really a great post, and solved a part of my project.. I have very
little knowledge of C, and this was useful. Sometimes I love C++ more
over C.
@Gregory: Hey mate, can ya help me with your generic version. your help
is much appreciated.
Regards,
This is an excellent implementation of vector like structure in c. It really works for me.
@Gregory,
I’m working on something quite similar and would love to see the source code.
thanks for posting this. saved me some time.
Man thanks a million!
I was struggling with dynamic structure array since last three days!
This tutorial has helped me like anything.
Thanks Thanks Thanks Thanks.