How do I declare an array of undefined or no initial size?

Question

I know it could be done using malloc, but I do not know how to use it yet.

For example, I wanted the user to input several numbers using an infinite loop with a sentinel to put a stop into it (i.e. -1), but since I do not know yet how many he/she will input, I have to declare an array with no initial size, but I'm also aware that it won't work like this int arr[]; at compile time since it has to have a definite number of elements.

Declaring it with an exaggerated size like int arr[1000]; would work but it feels dumb (and waste memory since it would allocate that 1000 integer bytes into the memory) and I would like to know a more elegant way to do this.

Answer 1

This can be done by using a pointer, and allocating memory on the heap using malloc. Note that there is no way to later ask how big that memory block is. You have to keep track of the array size yourself.

#include <stdio.h> #include <stdlib.h> #include <string.h>  int main(int argc, char** argv) {   /* declare a pointer do an integer */   int *data;    /* we also have to keep track of how big our array is - I use 50 as an example*/   const int datacount = 50;   data = malloc(sizeof(int) * datacount); /* allocate memory for 50 int's */   if (!data) { /* If data == 0 after the call to malloc, allocation failed for some reason */     perror("Error allocating memory");     abort();   }   /* at this point, we know that data points to a valid block of memory.      Remember, however, that this memory is not initialized in any way -- it contains garbage.      Let's start by clearing it. */   memset(data, 0, sizeof(int)*datacount);   /* now our array contains all zeroes. */   data[0] = 1;   data[2] = 15;   data[49] = 66; /* the last element in our array, since we start counting from 0 */   /* Loop through the array, printing out the values (mostly zeroes, but even so) */   for(int i = 0; i < datacount; ++i) {     printf("Element %d: %d\n", i, data[i]);   } } 

That's it. What follows is a more involved explanation of why this works :)

I don't know how well you know C pointers, but array access in C (like array[2]) is actually a shorthand for accessing memory via a pointer. To access the memory pointed to by data, you write *data. This is known as dereferencing the pointer. Since data is of type int *, then *data is of type int. Now to an important piece of information: (data + 2) means "add the byte size of 2 ints to the adress pointed to by data".

An array in C is just a sequence of values in adjacent memory. array[1] is just next to array[0]. So when we allocate a big block of memory and want to use it as an array, we need an easy way of getting the direct adress to every element inside. Luckily, C lets us use the array notation on pointers as well. data[0] means the same thing as *(data+0), namely "access the memory pointed to by data". data[2] means *(data+2), and accesses the third int in the memory block.

Answer 2

The way it's often done is as follows:

• allocate an array of some initial (fairly small) size;
• read into this array, keeping track of how many elements you've read;
• once the array is full, reallocate it, doubling the size and preserving (i.e. copying) the contents;
• repeat until done.

I find that this pattern comes up pretty frequently.

What's interesting about this method is that it allows one to insert N elements into an empty array one-by-one in amortized O(N) time without knowing N in advance.