So when we want to use an array without knowing the size then the common procedure is to start small and then keep doubling the size and reallocating it as we go along right?
And then I assume once we are done we will want to realloc once more to free up the excess memory that was malloced and we did not use?
#include <stdio.h>
#include <stdlib.h>
int main()
{
// unknown = an unknown amount of work we need to do
int unknown = 1234;
// size = the current allocated memory
int size = 10;
// counter = the final size of the array
int counter = 0;
// first we allocate a small amount for our array
int *array = (int *) malloc(size * sizeof(int));
// and then start working
for(int i = 0; i < unknown; i++)
{
// work
array[i] = i; counter++;
// check the size of the array to see if we need to realloc
if (counter == size)
{
size *= 2;
array = (int *) realloc(array, sizeof(size));
}
}
// when all of the work is done we then shorten it to the exact size
array = (int *) realloc(array, sizeof(counter));
printf("%d", counter);
}
Question 1: Is this the most performant way of tackling this problem?
Question 2: Since we need to keep track of the size of the array do most people create a struct for this?
typedef struct list
{
int size;
int *array;
} list;
the common procedure is to start small and then keep doubling the size and reallocating it as we go along right?
I'd say the most common approach is to start reasonably and then indeed keep doubling the size. Usually to a multiple of the CPU word alignment.
And then I assume once we are done we will want to realloc once more to free up the excess memory
No. Pre-allocating and doubling the size is an execution speed over memory optimization, since realloc calls are expensive. If you are using that approach, you have already decided that execution speed matters and memory use is less important.
Question 1: Is this the most performant way of tackling this problem?
You wouldn't check for sizes in the middle of iteration, but before it. Also repeated if checks in a loop are to be avoided if possible since that creates extra branching.
Instead check if new size fits in the allocated chunk, if not realloc, and then start the loop doing stuff on the data. From a program design perspective, allocation and algorithm should ideally not get mixed together in a tight-coupled mess, if that can be avoided.
And as mentioned, you wouldn't do a final realloc call either.
Question 2: Since we need to keep track of the size of the array do most people create a struct for this?
Yes and keep that struct private through the "opaque type" design pattern, hiding details about allocation away from the caller.