Why does it work to access a dynamically allocated 2D array element with a[i][j]?

Question

Let's say we have declared: int array[10][6]. As far as I understand, when you say array[i][j], it translates to *(((int *)array)+i*6+j). But, why does it work if array would be dynamically allocated because to access an element this would be needed: *(*(array+i)+j)? I don't understand why a[i][j] would work now if it is automatically translated like in the first case. Thanks.

check this one http://stackoverflow.com/questions/917783/how-do-i-work-with-dynamic-multi-dimensional-arrays-in-c. A 2D dynamic array, is an array of pointers in the 1st dimension and a simple type in the 2nd. — ViNi89, Jan 24 '16 at 17:42
Your first case is an array of arrays, the second is an array of pointers, so it's natural that they're accessed differently. Arrays are not pointers, pointers are not arrays. — molbdnilo, Jan 24 '16 at 17:43
@molbdnilo well... that's the idea... Why does it work to acces a double pointer with a[i][j]? — Toma Radu-Petrescu, Jan 24 '16 at 17:43
@rptoma The compiler knows whether things are arrays or pointers and adjusts things accordingly. It is not automatically translated like in the first case. — molbdnilo, Jan 24 '16 at 17:52
@molbdnilo hmm, ok. I thought that it translates it like in the first case. It's pretty weird for a newbie, haha. — Toma Radu-Petrescu, Jan 24 '16 at 17:54

haccks · Accepted Answer · 2016-01-24T18:40:52.043

Why does it work to access a dynamically allocated 2D array element with a[i][j]?

That's because pointer arithmetic and array indexing are same. Theexpression

array[i][j]

is equivalent to *(*(array + i) + j)). In this expression array converts to pointer to its first element and hence becomes of type int(*)[6], i.e. pointer to an array of 6 int. Adding i to array will increment it to i*sizeof(int[i]) bytes. Therefore, saying array[i][j] is translated to *(((int *)array)+i*6+j) is wrong.
So, dereferencing array + i will give an array of 6 int which further will decay to pointer to its first element array[i][0] having type int *. Therefore, array[i][j] is equivalent to *(&array[i][0] + j))

When array is allocated dynamically

int **array =  malloc(sizeof(int*)*10);  
for(int i =0; i < 10; i++)
    array[i] = malloc(sizeof(int)*6);

then its element can also be accessed using array[i][j]. This expression is also equivalent to *(*(array + i) + j)). But, the difference here is array is of type int ** and adding i to it will increment it by i*sizeof(int*). Dereferencing array + i will give array[i] which is of type int * and hence array[i][j] is equivalent to *(&array[i][0] + j)).

That said, in both cases array + i increment it to its next element (which can either be of type int[6] or int *) and finally arithmetic is between int * (&array[i][j]) and int (j).

score 0 · Answer 2 · answered Jan 24 '16 at 18:03

If you have a two-dimensional array like this

int a[M][N];

then in expressions arrays are implicitly converted to pointers to their first element.

So this expression

has type int ( * )[N] and points to the first "row" (element) of the two-dimensional array.

Expression

a + i

where i some intager in the range 0 - M - 1 point to i-th row of the array

Expression

*( i + i )

gives the row that is i-th element of the array.

You can write for example

printf( "%zu\n", sizeof( a[i] ) );

and the statement outputs a value that is equal to N * sizeof( int )

On the other hand if this expression

*( i + i )

is used in other context then as an operand of the sizeof operator then it in turn (as it is an array) is converted to pointer to its first element.

Thus expression

*( i + i )

is implicitly converted to pointer of type int * that points to the first element of the i-th row of the original array.

Expression

*( i + i ) + j

points to th j-th element of the i-th row of the array

As result expression

*( *( i + i ) + j )

is equivalent to

a[i][j]

If you dynamically allocated a two dimensional array the following way

int ( *a )[N] = malloc( sizeof( int[N][M] );

then you at once got the pointer of the same type and having the same value as the expression shown above for the two-dimensional array

So when you have initially a pointer then the step that implicitly converts a two-dimensional array to a pointer is simply skipped. But the net result will be the same.

If you allocated dynamically an array of pointers the following way

int **a = malloc( M * sizeof( int * ) );
for ( size_t i = 0; i < M; i++ ) a[i] = malloc( N * sizeof( int ) );

then a points to the first element of the dynamically alllocated first array.

a + i

gives the pointer to the i-th element of the array.

Expression

*( a + i )

gives the value stored in this element. This value is the address of the i-th allocated array in the loop aboth. It has type int *.

So

*( a + i ) + j

gives the pointer to the j-th element and at last

*( *( a + i ) + j )

is the unteger value stored in this element.

Why does it work to access a dynamically allocated 2D array element with a[i][j]?

2 Answers2