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

Question

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?

Answer 1

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.

Answer 2

x[i][j] is always exactly equivalent to *(*(x+i)+j) ... but you have to keep in mind that pointer arithmetic takes into account the size of the type pointed to. In

double ary[NROWS][NCOLS];

the size of ary[i] (i.e., *(ary+i)) is NCOLS*sizeof(double). In

double** ptr;

the size of ptr[i] (i.e., *(ptr+i)) is sizeof(double*).

In both cases, ary[i][j] or ptr[i][j], the correct element is fetched.

Answer 3

Yes. You are going right way but the declaration

double grid[5][5]

and

double **grid; 

are different. First is declaring a 2D array of 25 elements of double type while second is declaring a pointer to pointer to a double type. Both are different. Note that arrays are not pointers.

In first case memory allocation is on stack and it is continuous and hence compiler optimizes grid[i][j] to *(*(grid + i) + j) which is further optimized to *(*grid + (i*5 + j)).

In second case memory is allocated on heap and malloc won't create contiguous memory. In this case compiler optimizes grid[i][j] to *(*(grid + i) + j) but it doesn't further optimized it to *(*grid + (i*5 + j)).

Answer 4

Yes, the address A[i][j] refers to does depend on how A is declared.

The pointer arithmetic used to evaluate array_variable[i][j] depends on the number of columns (on the second dimension): This is because all the elements for each row (first dimension) are stored together, and the number of columns impacts where the data for the second, third, ETC. row is stored.

This URL states that if you have a 2-dimensional array, declared as:

int [NUMBER_OF_ROWS][NUMBER_OF_COLUMNS]

Then:

x = y[a][b]

is equivalent to:

x = *((int *)y + a * NUMBER_OF_COLUMNS + b);

URL: How to use pointer expressions to access elements of a two-dimensional array in C?

This URL states that elements of (a 2 dimensional array) are stored in row-major order: E.G. all the elements of row 1 are stored first.

http://www.cse.msu.edu/~cse251/lecture11.pdf

This URL has a similar calculation, dependent on the size of the second dimension:

http://www.cs.umd.edu/class/sum2003/cmsc311/Notes/BitOp/pointer.html

addr( & arr[ row ][ col ] ) = addr( arr ) + [ sizeof( int ) * COLS * row ]
                                          + [ sizeof( int ) * col ]

Answer 5

Additionally to other answers:

when grid is declared, a contiguous block of memory is allocated for 5*5 doubles, no more no less;

It's not totally true (the part with less will always be true), but sometimes you will find, that even though you are accessing memory after the end of an array the program seems to work (does not segfault instantly). This means that sometimes malloc can allocate more memory than you are asking. Of course it does not mean, that you should access this excessive memory.

Answer 6

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

A No, it does not.

If you have,

int a[3][3] = {1, 2, 3, 4, 5, 6, 7, 8, 9};

then, a[i] is evaluated as *(a+i).

If you have

int ** create2DArray(int d1, int d2)
{
   int i = 0;
   int ** a = malloc(sizeof(*a)*d1);
   for ( ; i != d1; ++i )
   {
      a[i] = malloc(sizeof(int)*d2);
   }
   return a;
}

int **a = create2DArray(3, 3);

then, a[i] is still evaluated as *(a+i).

No matter how they are declared, a[i][j] is evaluated as *(a[i] + j).

You can still call a function like:

void func(int* p, int size)
{
   int i = 0;
   for ( ; i != size; ++i )
   {
      printf("%d ", p[i]);
   }
   printf("\n");
}

using

func(a[i]);

no matter how a was defined.

The main difference between the first definition of a and the second definition of a is how memory is allocated for it. In the first case, memory is allocated on the stack, and it is contiguous. In the second case, memory is allocated on the heap, and it is most likely not contiguous. However, how you use it and how the compiler treats it are exactly same.