Dynamic Allocation of Memory for Multi Dimensional Arrays

The traditional solution is to allocate an array [footnote] of pointers to pointers, and then initialize each pointer to a dynamically-allocated ``row.'' Here is a two-dimensional example:

	#include <stdlib.h>

	int **array1 = malloc(nrows * sizeof(int *));
	for(i = 0; i < nrows; i++)
		array1[i] = malloc(ncolumns * sizeof(int));

(In real code, of course, all of malloc's return values would be checked. You can also use sizeof(*array1) and sizeof(**array1) instead of sizeof(int *) and sizeof(int); see [footnote] .)

You can keep the array's contents contiguous, at the cost of making later reallocation of individual rows more difficult, with a bit of explicit pointer arithmetic:

	int **array2 = malloc(nrows * sizeof(int *));
	array2[0] = malloc(nrows * ncolumns * sizeof(int));
	for(i = 1; i < nrows; i++)
		array2[i] = array2[0] + i * ncolumns;

In either case (i.e for array1 or array2), the elements of the dynamic array can be accessed with normal-looking array subscripts: arrayx[i][j] (for 0 <= i < nrows and 0 <= j < ncolumns). Here is a schematic illustration of the layout of array1 andarray2:

If the double indirection implied by the above schemes is for some reason unacceptable,[footnote] you can simulate a two-dimensional array with a single, dynamically-allocated one-dimensional array:

	int *array3 = malloc(nrows * ncolumns * sizeof(int));

However, you must now perform subscript calculations manually, accessing the i,jth element with the expression

array3[i * ncolumns + j]

and this array cannot necessarily be passed to functions which expect multidimensional arrays. (A macro such as

	#define Arrayaccess(a, i, j) ((a)[(i) * ncolumns + (j)])

could hide the explicit calculation, but invoking it would require parentheses and commas which wouldn't look exactly like conventional C multidimensional array syntax, and the macro would need access to at least one of the dimensions, as well. See also question 6.19.)

Yet another option is to use pointers to arrays:

	int (*array4)[NCOLUMNS] = malloc(nrows * sizeof(*array4));

or even

	int (*array5)[NROWS][NCOLUMNS] = malloc(sizeof(*array5));

but the syntax starts getting horrific (accesses to array5 look like (*array5)[i][j]), and at most one dimension may be specified at run time.

With all of these techniques, you may of course need to remember to free the arrays when they are no longer needed; in the case of array1 and array2 this takes several steps (see also question 7.23):

	for(i = 0; i < nrows; i++)
		free((void *)array1[i]);
	free((void *)array1);

	free((void *)array2[0]);
	free((void *)array2);

Also, you cannot necessarily intermix dynamically-allocated arrays with conventional, statically-allocated ones (see question 6.20, and also question 6.18).

Finally, in C99 you can use a variable-length array.

All of these techniques can also be extended to three or more dimensions. Here is a three-dimensional version of the first technique (which, like the rest of the fragments presented here, requires error-checking before being used in a real program):

	int ***a3d = (int ***)malloc(xdim * sizeof(int **));
	for(i = 0; i < xdim; i++) {
		a3d[i] = (int **)malloc(ydim * sizeof(int *));
		for(j = 0; j < ydim; j++)
			a3d[i][j] = (int *)malloc(zdim * sizeof(int));
	}

Dynamic 2d array method 1:

This one works if you know the the number of columns at compile time.

#define CCOLS 200

int (*m)[CCOLS] = malloc(cRows * sizeof(*m));
m[iRow][iCol] = n; // sets the item at iRow*CCOLS + iCol

...

free(m);

This works because m is declared as a pointer to an array of CCOLS ints. The compiler knows its size and does the math for you. m[iRow] = an array of CCOLS ints.

You can only pass this to functions with this signature:

foo(int (*m)[CCOLS]) { ... }

and maybe this signature, depending upon your compiler and the switches you use:

foo(int m[][CCOLS]) { ... }

not this signature:

foo(int **m) { ... }

Since the memory layouts and sizes are different.

int m[][CCOLS] looks like this:

+---------+---------+---------+---------+     
| m[0][0] | m[0][1] | m[0][2] | m[0][3] |     
+---------+---------+---------+---------+     
| m[1][0] | m[1][1] | m[1][2] | m[1][3] |     
+---------+---------+---------+---------+     
| m[2][0] | m[2][1] | m[2][2] | m[2][3] |     
+---------+---------+---------+---------+     
| m[3][0] | m[3][1] | m[3][2] | m[3][3] |     
+---------+---------+---------+---------+     

int **m looks like this:

+----+        +----+----+----+----+----+      
|m[0]|  --->  |    |    |    |    |    |      
+----+        +----+----+----+----+----+      
|m[1]|  --->  |    |    |    |    |    |      
+----+        +----+----+----+----+----+      
|m[2]|  --->  |    |    |    |    |    |      
+----+        +----+----+----+----+----+      
|m[3]|  --->  |    |    |    |    |    |      
+----+        +----+----+----+----+----+      

Dynamic 2d array method 2 (C99 which is not supported by all compilers):

This one is the same as the previous but you don't need to know dimensions at compile time.

int cCols, cRows, iCol, iRow;
... set cRows, cCols somehow, they could be passed in as parameters also ...
int (*m)[cCols] = malloc(cRows * sizeof(*m));
m[iRow][iCol] = n; // sets the item at iRow*cCols + iCol

...

free(m);

You can only pass this to functions with this signature:

foo(int cCols, m[][cCols])  {}

or this one

foo(int cRows, int cCols, m[cRows][cCols])  {}

If you use gcc, here is more info.

Dynamic 2d array method 3 using the STACK! (C99 which is not supported by all compilers):

This lets you avoid malloc entirely if you are ok with your 2d array on the stack.

int cRows, cCols;
... set cRows, cCols somehow ...
int m[cRows][cCols];
m[iRow][iCol] = n; 

I assume you could declare a global variable this way too.

You pass this to functions the same way as method 2.

Dynamic 2d array method 4:

This is the array of pointers method that a lot of people use.

You use one malloc to allocate to be efficient. And of course you then only use one free. Only if you have HUGE arrays where contiguous memory becomes and issue, would you want to malloc each row individually.

int cCols = 10, cRows = 100, iRow;

// allocate:
// cCols*cRows*sizeof(int) = space for the data
// cRows*sizeof(int*) = space for the row ptrs
int **m = malloc(cCols*cRows*sizeof(int) + cRows*sizeof(int*));

// Now wire up the row pointers.  They take the first cRows*sizeof(int*) 
// part of the mem becasue that is what m[row] expects.
// we want each row pointer to have its own cCols sized array of ints.
// We will use the space after the row pointers for this.
// One way to calc where the space after the row pointers lies is to
// take the address of the nth + 1 element: &m[cRows].
// To get a row ptr, cast &m[cRows] as an int*, and add iRow*cCols to that.
for (iRow = 0; iRow < cRows; ++iRow)
    m[iRow] = (int*)&m[cRows] + iRow*cCols; 

// or 
for (p=(int*)&m[cRows] ; iRow = 0; iRow < cRows; ++iRow, p+=cCols)
    m[iRow] = p; 

// use it:
...
m[iRow][iCol] = 10;
...

// free it
free(m);

END