Thread: Dynamic 2 Dimensional Array

To get straight everything about arrays.
array[x] means *(array+x). This is clear.
What does array[x][y] mean? It could be
*(*(array+x)+y) which makes sense. Or it could be
*(array+x + y * MAX_X) which is more efficient

If the second is true you could cast a one dimensional array to a two dimensional array as you said. If not then you couldn't. This is why:

With the first method the system would have to save:
1) pointer to pointers of int (array)
2) x pointers to int (array[x])
3) x*y spaces of memory (array[x][y])
You malloc three things so that should be correct

With the second method:
1) pointer to int (array)
2) x*y spaces of memory (array(x, y))
You malloc two things so this should be correct

Originally Posted by Elysia

The formula is: x * y + x.
A 2D array is not int**, it's int[x][y] or (int* [y]) [as laserlight kindly pointed out.]

So, just to get things straight. Lets say about a 3d array, since that was my example.
If you do:
char str[X][Y][Z]
from what you say the OS will give you a continuous space and figure out the indexes as it wants. Right?

If you do:

Code:

char ***array;
for(i=0; i < X; i++)
   array[i] = malloc(Y * sizeof(char *));
for (i=0; i < X; i++)
   for (j=0; j < Y; j++)
      array[i][j] = malloc(Z * sizeof(char));

then you, considering that char* is 4 bytes, you ll allocate 4Y bytes of continuous memory. For the pointers. Then you will allocate for each pointer Z bytes of memory. The point is that when you call a malloc get a continuous space of memory. Lets say you get a memory with adressses from 1000 to 1000+Z-1. Why should the next malloc give you the memory spaces from 1000+Z to 2000+2*Z-1? Wouldn't it give you whatever the OS decides? In that case it wouldn't be a continuous memory space.
Plus, totaly won't you dynamically allocate:
4*Y+X*Y*Z bytes? Instead of X*Y*Z bytes that you would expect.

Or for a 2d dimensional array think of the following code:

Code:

char **array;
for (i=0; i < X; i++)
   if (i !=3)
       array[i] = malloc(Y * sizeof(char));
array[3] = malloc(10000 * sizeof(char));
//consider Y < 10000

Now you cannot have a continuous space. If Y == 10000 in the above example then you could have a continuous space if for whatever strange reason the system guessed what you are doing. One malloc() doesn't know what the other malloc() did.

Ofc, GCC might optimize your code and give you a continuous space if you didn't have the !=3 as above. The system may try to optimize malloc() to give you continuous space. Maybe it doesn't in a 4d array though.
But in any case (IF IF I am correct) a 2d array in C isn't the same as a 1d array. There is no 2d, 3d array in C, you just get that impression because of the indexes. At least that is what I understand until now.

At least do we know for sure that str[x][y][z] will be a continuous space?

Of course if you wanted you could do:

Code:

char *temp= malloc(X*Y*sizeof(char));
char **array;
for (i=0; i < X; i++)
   array[i] = temp[i*X];
temp = NULL;

Now for sure you ll have a 2d array of continuous space, since you call only ONE malloc.

That is my point. That to be sure don't rely on optimizations, just do your job correctly

Originally Posted by Elysia

However, you must understand that any dynamically allocated 2D array is not guaranteed to be contiguous at all. This is because subsequent malloc calls are not guaranteed to allocate memory next to the previous malloc call. So therefore, only a 1D array is guaranteed to be be contiguous.
The compiler cannot, and I repeat, it cannot, optimize this and place it in a contiguous space because it has no control over malloc.
Malloc is a function that calls OS API, which the compiler has no control over.

Although, if you want, it's quite possible to create a contiguous 3/+D array:

Code:

	int (*p)[10][10] = malloc(10 * 10 * 10); /* malloc(x * y * z); */
	p[9][9][9] = 0;
	free(p);

Yeah, that was my point!
As for the code... I feel a bit stupid not thinking about it
I needed such a code a few months ago. But I had the problem of contiguous memory. So I found 2 solutions. The #define one and one more complex with pointers. Noone had posted something like yours. Your code would clearly had been the best!