CODEWITHSUNDEEP
carrayspointerslinked-listmalloc
drh0use
drh0use

Reputation: 89

Memory allocation for just one element of array

I can't determine the array size in run time, because it will have dependencies. So I need to do memory allocation for an element. Just like linked-lists I can say.

How can I do that in integer arrays ?

Upvotes: 1

Views: 1089

Answers (1)

Persixty
Persixty

Reputation: 8589

I think you're saying you want to 'grow' an array one element at a time.

realloc() is an option in C for an array of integers(*).

size_t n=0;//Length of array.
int* arr=NULL;

//Some code...

//Now we want to grow our array
//This is probably in a loop or called in a function from a loop (not shown).
++n;
int* temp=realloc(arr,n*sizeof(int));
if(temp==NULL){
    free(arr);
    return 1;//Error...
}
arr=temp;

//More code....

//Now we're done with arr.
free(arr);

In the first pass arr is NULL and realloc(NULL,..) just acts like malloc(). But in subsequent passes when arr is not NULL then realloc attempts to grow the array 'in place' (if memory is available at the end of it). If not, it attempts to allocate space elsewhere and then copies over the existing data and frees the old location. If it can't reallocate, it does nothing and returns NULL so you are responsible for then freeing that space (free(arr)).

NB: Always allocate the return of realloc() to a temporary variable (i.e. not the first argument). Otherwise if allocation fails you have leaked the existing memory.

realloc is a quick trick to reduce the amount of allocating and copying required to grow an array - the alternative.

If that's not effective enough the normal model is to keep track of 'capacity' and 'length' something like this.

 const size_t chunk=10;
 size_t cap=0;
 size_t n=0;
 int* arr=NULL;

 ++n;
 if(n>cap){
     cap+=chunk;
     int* temp=realloc(arr,cap);
     if(temp==NULL){
         free(arr);
         return 1;//Error
     }
 }

 //Later...
 free(arr);

That has the advantage of you being able to tune how much 'spare' overhead you have to tune how often reallocation occurs. Another strategy is cap=cap*2; though obviously space tends to grow exponentially! A book could be written on strategies for this classic. It's often possible to allocate enough for most realistic cases in one hit but still handle exceptional cases.

You also have the option allocate back down to recover free space if you know the array is now full-sized.

In case it's not obvious, if the array is moved, any pointers to it or into it will have to be redirected. That's an argument for only indexing into it with [.]. You will need to keep hold of the old location until you do the redirection. ptr=temp+(ptr-arr) makes ptr point to the new location of the element ptr pointed to.

This is standard approach found in Java ArrayList and most implementations of std::vector<>. It's an engineering compromise. The benefits of an array (O(1) random access by index) and a linked list (O(1) growth).

It's asymptotically still linear but in practical cases provides great benefit. Computer Science is concerned with asymptotic rates and engineering with actual values in finite real cases.

(*) The copy is a raw copy of memory. That's fine for int but complex structures 'struct' may not be copyable by what amounts to memmove or take further effort.

Upvotes: 2

Related Questions