What exactly happens when accessing a 2D array

Question

I've been coding for quite a while, but just realized that my interperation of a very elementary operation may be confused.

int array[10][10];

array[1][1] = 0;

This is sample enough - address of array + (10 * 1 + 1) * sizeof(int) is assigned 0.

But what about when doing dynamic arrays?

int **array;

// malloc/new the base array of pointers - say 10 as above.
array = malloc(10 * sizeof(int *));

// through pointers and alloc each with ints - again 10 per row as above.
for(int i=0; i<10; i++) 
    array[i] = malloc(10 * sizeof(int);

array[1][1] = 0;

In this example, the compiler has to reference an array on the first layer of the array to get to the second pointer to get to memory. Again, this process is straight forward.

My question here is: How does the compiler know that memory is contiguous and therefore it can just do simple math instead of a reference in the first example, but not the second?

If the answer is: because the compiler knows the size of the array beforehand, so be it, but is there a way to tell the compiler that the dynamic array is a single allocation and therefore it can do the simpler math instead of the extra deref and extra memory fragmenting allocations? Or does this require VLA support to get right as per this post which goes like:

double (*A)[n] = malloc(sizeof(double[n][n]));

Another website listed this as a possibility as well:

int r=3, c=4;
int **arr;

arr  = (int **)malloc(sizeof(int *) * r);
arr[0] = (int *)malloc(sizeof(int) * c * r);

Which really got me wondering about how the compiler is figuring things out, or if this is just another way of using VLA support.

For C++, there is boost and nested vectors, but they are even heavier than the above so again, I would avoid those if possible.

---

Update

Honestly, what I should do here is just compile my above examples and take a gander at the assembler output. That would answer all my questions in no time at all. My misconception was that I assumed that all n-dim array access was done just by doing math similiar to how it is done with compile time known arrays. I did not realize that [][] was doing double duty as **array with appropriate indexing between each dereference for dynamic allocs, while doing [i*dim+j] for compile time known types. Dynamic 2+ Dimension arrays is just not something I ever have had to do.

Answer 1

The types int ** and int[10][10] are not the same.

The type int ** doesn't contain any information about how many elements there are, because it is not an array type, it is a pointer type (specifically a pointer to an int *). int[10][10] contains all the information the compiler needs to know how many elements there are.

You'll notice this if you try using sizeof on a pointer vs an array. The following program demonstrates this:

#include <stdio.h>                                                             

int main ( int argc, char * argv[] ) { 

    printf( "Size of int[10][10]: %lu\n", sizeof(int[10][10]) );
    printf( "Size of int**: %lu\n", sizeof(int**) );

    return 0;
}

Dynamic memory isn't allocated at compile time, it is compiled at run-time, so a compiler changing the way the dynamic memory is created, could end up modifying the behaviour of your program, (IE. by allocating more than is available in a contiguous block, and having malloc return null).

You can get a contiguous block of memory yourself of course, by allocating enough memory for 100 ints, and then doing the arithmatic yourself:

int * mem = malloc( 10 * 10 * sizeof( int ) );

Now mem is a contiguous block of 100 ints

int * array[10];
for ( int i = 0; i < 10; i++ )
    array[i] = &mem[10*i];

Now you have an array of 10 int *s that can be used to index into mem, just like before (this array is allocated statically, but if you wanted to return it from this function you would want to allocate it dynamically instead).

Answer 2

Because the types are completely different.

In the first case, the type in an array with two dimensions, and the length of each dimension is known, so the address can be computed directly, and referenced once.

In the second case, the type is completely different, the type is a double pointer. A pointer to an array of pointers to some type, in your case, an int.

All that the compiler knows is that array is a pointer to an array, of some unknown size, of pointers to int. array is a

int **array;

And array[x] is a pointer to an int. Note that it's just a pointer to an int. It says nothing about how many ints it's pointing to.

It can just be a single int, or it may not. And each pointer to an int could point to a different number of int's.

For example, array[0] may point to ten ints. array[1] may point to twenty ints. There's nothing that requires array[x] to point to the same number of ints as array[y].

That job belongs to you, the programmer. The compiler doesn't know anything. It is up to you to properly allocate each pointer to an int, to the right number of ints, for each such pointer, and then allocate the right number of pointers to ints in the first place. The compiler doesn't know how many of each there are, it's your job to keep track of that, in some form or fashion, in order to write bug-free code.

Welcome to C++.