Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

In C, does the meaning of A[i][j] depend on how A is declared?

Suppose I have a two-dimensional array grid declared as double grid[5][5]. It is my understanding that the following statements are true:

  • when grid is declared, a contiguous block of memory is allocated for 5*5 doubles, no more no less;
  • when an element of the array is accessed with the notation grid[i][j], this piece of code is actually interpreted as *(grid+(i*5+j)).

On the other hand, I know I can also store the same matrix as an array of pointers, by writing something like:

double ** grid;
grid = (double**)malloc(sizeof(double*)*5);
for (i=0; i<5; i++)
   grid[i] = (double*)malloc(sizeof(double)*5);

and I actually have a code which does that. The problem is that it then proceeds to access the elements of grid just like before, with the double subscript notation. Is this case different? In this case, is grid[i][j] converted to *(*(grid+i)+j), i.e. to a double dereferenciation? That's the only way I can see it happen correctly.

(This question probably stems from my (lack of) understanding of the relationship between pointer and array types in C...)

EDIT:

Ok, let's see if I got this straight:

  • grid[i][j] is always converted to *(*(grid+i)+j);
  • this expression is indeed calculated differently in the two cases, because, as Jim states in his answer, pointer arithmetic takes into account the size of the type pointed to; nevertheless, the correct element is fetched in both cases;
  • if and only if "grid" is a 2D array, this expression is further optimized to *( (double*)grid + (i*5+j) ), which is possible because the compiler knows that any grid[i] is actually an array starting at location grid+i*5.

But this leaves me with an inescapable conclusion: for a 2D array, if I set i=j=0, then I have that **grid == *((double*)grid). Is this correct?

like image 242
sp00n Avatar asked Mar 27 '14 18:03

sp00n


1 Answers

when an element of the array is accessed woth the notation grid[i][j], this piece of code is actually interpreted as *(grid+(i*5+j)).

No. (Not sure why so many answers said yes to this). *(grid+(i*5+j)) is the same as grid[i*5+j], which is an out-of-bounds access for some values of i and j. Also, this specifies an array, not an int.

The following two expressions are exactly equivalent in all cases: A[i][j] *(*(grid+i)+j).

You never "gain" anything by converting between the two different dereferencing notations. It is just two equivalent forms of syntax for an lvalue expression which designates a particular object.

For the rest of my answer I will use the [ ] syntax as I find it clearer.

Perhaps you meant to ask something like "with int A[5][5];, then is A[i][j] equivalent to offsetting by i+5*j from the start of A?"

The other answers muddle around a bit because the term "offsetting by N" is ambiguous. N bytes, or N ints, or N arrays of int?

If you imagine in your head that A were a 1-D array of length 25 (let's call this B), then A[i][j] designates the same object as B[i*5+j].

To express this in code, you would write: int *B = (int *)&A. This aliases the 2-D array of int as a 1-D array.

NB. It would be wrong to write int *B = (int *)A, because A decays to &A[0] which only has five ints in it, so B[6] is still an out-of-bounds access (undefined behaviour). If you've not got bounds-checking turned on in your compiler it's likely you'll not notice anything though.

like image 50
M.M Avatar answered Oct 19 '22 23:10

M.M