use subscript operator on a second rank pointer

Question

I'm confused with a problem about the pointer and array in C.

Let's see a piece of code first:

//case 1
int **a;
a = (int **)malloc(sizeof(int*)*m);
for(i = 0; i < m; i++)
    a[i] = (int *)malloc(sizeof(int)*n);

//case 2
int b[m][n];

then, we known that, the layout of b in memory is as follow:

b[0][0] b[0][1] ... ... b[m-1][n-1]

and, the layout of a in memory is as follow:

a
 \
 _\|
 a[0]  a[1] ... a[m-1]
  |    |
  |    |
  |   \|/
  |   a[1][0] a[1][a] ... a[1][n-1]
 \|/
a[0][1] a[0][2] ... a[0][n-1]

so, my question is: since a[0..m-1][0..n-1] is stored in memory inconsecutively, why we can use subscript operator [] on a? In other words, why a[i][j] can get the correct element, just as b[i][j] do?

[Please do not cast the result of malloc in C](http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc). — Paul R, Sep 19 '13 at 15:59

score 3 · Answer 1 · answered Sep 19 '13 at 15:50

3

That's because a[i][j] equals to *(*(a+i) + j). Even though a is not consecutively stored (possibly), the pointer *(a+i) will exactly point to the right place (where a[i][0] is stored).

answered Sep 19 '13 at 15:50

score 2 · Answer 2 · answered Sep 19 '13 at 15:48

Because the elements of a are stored consecutively in memory, and the elements of each of a[n] are stored consecutively in memory. Doing int n = a[i][j] is basically equivalent to doing int * p = a[i]; int n = p[j]; It doesn't matter that the both dimensions may not be contiguous in memory for a in the way that they are for b.

shf301 · Answer 3 · 2013-09-22T01:00:31.463

2

They both work because the compiler generates different for each case. While it is true that singly dimentioned arrays and pointers and similar, doubly dimentioned arrays and pointers to pointers have the similarities.

So for the case of b since the compiler knows that b is an array and is a consecutive memory block it generates the the code as:

// int c = b[i][j];
int c = *(b + (i*m+j);

But it generates different code for a since it is a pointer to a pointer and not a consecutive memory block each bracket operator is a dereference operator:

// int c  = a[i][j];
int c = *(*(a+i)+j);

edited Sep 22 '13 at 01:00

answered Sep 19 '13 at 15:54

shf301

31,086
2
52
86

1

"int c = b[i][j];" can also be translated into "int c = *(*(b+i)+j);". – xianyu1337 Sep 19 '13 at 16:05
1

It's `int c = *(*(a + i) + j);` and `int c = *(*(b + i) + j);`. The same thing in both cases. – newacct Sep 20 '13 at 01:46

Eric Postpischil · Accepted Answer · 2013-09-19T16:39:49.660

The compiler processes each part of an expression individually. The primary difference between a[i][j] and b[i][j] is that, since a is a pointer to pointers to int, the address calculation for a[i] counts a number of pointers, but, since b is an array of arrays of int, the address calculation for b[i] counts a number of arrays. C uses the type of each part of the expression to determine how to evaluate it.

The steps for interpreting a[i][j] are:

a is a pointer to a pointer to an int.
a[i] is defined to be *(a + i).
The sum a+i is i elements beyond where a points. Since a points to pointers to int, we count i pointers to int to determine the new address.
Since the sum is a pointer to a pointer to an int, applying * to it yields a pointer to an int.
a[i][j] is defined to be *(a[i] + j). We have already evaluated the a[i] part.
The sum a[i] + j is j elements beyond where a[i] points. Since a[i] points to int objects, we count j int objects to determine the new address.
Since this sum is a pointer to an int, applying * to it yields an int.

The steps for interpreting b[i][j] are:

b is an array of m arrays of n int.
Since b is an array, it is converted to a pointer to its first element, an array of n int.
b[i] is defined to be *(b + i).
The sum b + i is i elements beyond where b points. Since b has been converted to a pointer to arrays of n int, we count i arrays of n int to determine the new address.
Since the sum is a pointer to an array of n int, applying * to it yields an array of n int.
Since this expression is another array, it is converted to a pointer to its first element, an int.
b[i][j] is defined to be *(b[i] + j). We have already evaluated the b[i] part.
The sum b[i] + j is j elements beyond where b[i] points. Since it points to int, we count j int to determine the new address.
Since this sum is a pointer to an int, applying * to it yields an int.

score 0 · Answer 5 · answered Sep 19 '13 at 15:51

For a[i][j]

Basically we say :

We need the i'th pointer pointed to by a, and then we need the j'th int pointed to by that inner pointer.

Using this concept only we are able to write

foo(int **a, int rows, int cols){
//...
//acess a[i][j] ; 0<=i<rows, 0<=j<cols
}

use subscript operator on a second rank pointer

5 Answers5