Regular static allocated array looks like this, and may be accessed using the following formulas:
const int N = 3;
const int M = 3;
int a1[N][M] = { {0,1,2}, {3,4,5}, {6,7,8} };
int x = a1[1][2]; // x = 5
int y = *(a1+2+N*1); // y = 5, this is what [] operator is doing in the background
Array is continuous region of memory. It looks different in case of dynamic array allocation, there is array of pointer to arrays instead:
int** a2 = new int*[N];
for (int i = 0; i < N; i++)
a2[i] = new int[M];
//Assignment of values as in previous example
int x = a2[1][2];
int y = *(*(a2+1))+2); // This is what [] operator is doing in the background, it needs to dereference pointers twice
As we can see, operations done by [] operator are completely different in case of typical continuous array and dynamically allocated array. My questions are now following:
For this declaration of an array
int a1[N][M] = { {0,1,2}, {3,4,5}, {6,7,8} };
these records
int x = a1[1][2];
int y = *(a1+2+N*1);
are not equivalent.
The second one is incorrect. The expression *(a1+2+N*1) has the type int[3] that is implicitly converted to an object of the type int * used as an initializer. So the integer variable y is initialized by a pointer.
The operator a1[1] is evaluated like *( a1 + 1 ) . The result is a one-dimensional array of the type int[3].
So applying the second subscript operator you will get *( *( a1 + 1 ) + 2 ).
The difference between the expressions when used the two-dimensional array and the dynamically allocated array is that the designator of the two-dimensional array in this expression (a1 + 1) is implicitly converted to a pointer to its first element of the type int ( * )[3] while the pointer to the dynamically allocated array of pointers still have the same type int **.
In the first case dereferencing the expression *(a1 + 1 ) you will get lvalue of the type int[3] that in turn used in the expression *( a1 + 1) + 2 is again implicitly converted to a pointer of the type int *.
In the second case the expression *(a1 + 1) yields an object of the type int *.
In the both cases there is used the pointer arithmetic. The difference is that when you are using arrays in the subscript operator then they are implicitly converted to pointers to their first elements.
When you are allocating dynamically arrays when you are already deals with pointers to their first elements.
For example instead of these allocations
int** a2 = new int*[N];
for (int i = 0; i < N; i++)
a2[i] = new int[M];
you could just write
int ( *a2 )[M] = new int[N][M];
Is my understanding of [] operations correct?
int y = *(a1+2+N*1); // y = 5, this is what [] operator is doing in the background
By definition, the way to translate the subscript operators to the corresponding indirection and pointer arithmetic is:
int y = *(*(a1+1)+2)
Which is exactly the same as in the case of int**.
How C/C++ compiler can distinguish which [] operation it should perform
The compiler uses the type system. It knows the types of the expressions and it knows what subscript operation means for each type.
Will it work correctly in C language using malloc instead of new? I don't see any reasons why not actually.
It doesn't matter how an array is created. Subscript operator works the same way with all pointers.
a1 and a2 are different types, and as such, the behavior of operator [] will depend on how that type defines the operator. In this case you're dealing with intrinsic compiler behaviors that conform to the C++ spec, but it could just as well be a std::unique_ptr<>, or MyClass with overloaded operator[]