What is array reallocation?

Arrays in C (and C++) have fixed size. Applications that can't predict their array sizes in advance must therefore simulate dynamic array growth when the arrays fill using a three-step procedure: (1) allocate a new, larger array; (2) copy the contents of the old array into the new array; (3) free the old array. This procedure, called array reallocation, typically looks something like this.

   #include <malloc.h>
   

       int i,size,newsize;
       int *q, *ip, *iq;
       int index;
       ...
       int* p = (int*)malloc(size*sizeof(int));
       ...
       if(index>=size){
           newsize = index < 2*size ? 2*size : index+100;
           q = (int*)malloc(newsize*sizeof(int));
           ip=p;
           iq=q;
   

           for(i=0;i<size;i++)*iq++ = *ip++;
           free(p);
           p=q;
           size=newsize;
       }
       p[index] = 10;

By the way, there's an error here. The programmer forgot to check for heap exhaustion.

In C++, the new and delete operators simplify the statements involving malloc (and make them typesafe).

           int* q = new int[newsize];
           ...
           delete p;

The overall complexity of the code is barely diminished, however. The problem is compounded when array reallocation code is scattered throughout an application.

Some programmers may wish that arrays had automatic reallocation: when a reference is made to an out-of-bounds index, this feature would cause the array to be reallocated automatically in such a way that the index became valid. For technical reasons that are deeply rooted in the C language, such an operation is impossible to implement correctly. There is also an efficiency reason why automatic reallocation would not be desirable: programmers generally want more control over (1) when reallocation occurs and (2) how much excess memory to acquire during reallocation.