How does C allocate space for a 2D (3D…) array whe

Question

I am having a problem understanding how C allocates space for a 2D (or more dimensional) array, especially when we use malloc and the like. Take the program in this question for example.

A one-dimensional array of pointers is first defined, then pointers to arrays of 1D data (in this case strings) are put in each one of boxes of the first 1D array. So there is no guarantee that the whole 2D array is contiguous (the last cell of the previous row is followed by the first cell of the next row). Each 1D array of data can be very distant, only their pointers are contiguous. Am I correct or am I missing something? I would really appreciate if you could help me clarify this.

Answer 1

I think you are right. But if you really want the array to be contiguous, you can malloc an 1D-array and use it like a 2D one, like

int* oneDArray = (int*)malloc(sizeof(int)*10*10);
int a = oneDArray[i*10+j];     //which equals to twoDArray[i][j]

Answer 2

There are various ways of doing it, depending on how you're going to access it. You can ensure that the main body of the array is contiguous, or you can avoid that. For arrays of strings, you often don't bother with making the body of the array contiguous. For 2D (etc) arrays of integers or doubles, you usually do make the body of the array contiguous.

In the examples, the data type of the array is the generic type T, assumed to be numeric so the array elements can be assigned 0. The examples do not error check the memory allocations; they should in production code.

Array access with computed indexes — contiguous array body

int n1 = 5;
int n2 = 6;

T *a = malloc(n1 * n2 * sizeof(T));

for (int i = 0; i < n1; i++)
    for (int j = 0; j < n2; j++)
        a[i * n2 + j] = 0;

free(a);

Array access with double subscripts — contiguous array body

int n1 = 5;
int n2 = 6;

T **a = malloc(n1 * sizeof(T*));
T  *b = malloc(n1 * n2 * sizeof(T));

for (int i = 0; i < n1; i++)
    a[i] = &b[i * n2];

for (int i = 0; i < n1; i++)
    for (int j = 0; j < n2; j++)
        a[i][j] = 0;

free(b);
free(a);

Array access with double subscripts — discontiguous array body

int n1 = 5;
int n2 = 6;

T **a = malloc(n1 * sizeof(T*));

for (int i = 0; i < n1; i++)
    a[i] = malloc(n2 * sizeof(T));

for (int i = 0; i < n1; i++)
    for (int j = 0; j < n2; j++)
        a[i][j] = 0;

for (int i = 0; i < n1; i++)
    free(a[i]);
free(a);

Answer 3

Method 1 (pointers to buffers, non contiguous)

You are correct, there is no guarantee the data will contiguous and in fact it most likely will not be. The top level array (rows) is simply a 1D array of pointers (each element is it's own pointer). These pointers each point to their own 1D array of actual objects. These buffers are only connected through pointers.

/* allocation */
int** array = malloc(sizeof(int*) * height)
for (int y = 0; y < height; y ++)
{
   array[i] = malloc(sizeof(int) * width);
}
/* indexing */
int item = array[y][x];

Method 2 (single buffer, contiguous)

Another way to allocate 2D arrays is with a single buffer and then indexing it based on 2D coordinates. e.g. 8 * 8 = 64. Allocate a single 64 byte buffer and index = x + y * 8. This method stores data contiguously and it is much easier to allocate and deallocate than method 1.

/* allocation */
int* array = malloc(sizeof(int) * width * height)
/* indexing */
int item = array[x + y * width];