# Dynamic 2 Dimensional Array

Show 80 post(s) from this thread on one page
Page 2 of 2 First 12
• 06-20-2008
dwks
Quote:

Originally Posted by C_ntua
There is a "nicer" way to allocate a 2d, 3d etc array. It has also the advantage that is mallocs one space of memory, so it will be more effective. And that it requires two lines of code :)
Code:

```int *array3d = malloc(X * Y * Z * sizeof(int)); #define array3d(x, y, z) array[(x) + (y * X) + (z * X * Y)]```
The only downside is that if you have a function that requires ***int you won't be able to pass array3d.

Why not? A multi-dimensional array is represented exactly like that in memory, so you should be able to do it with a cast. Something like this:
Code:

```#include <stdio.h> #include <stdlib.h> enum { X = 3, Y = 4 }; void print2d(int array[X][Y], int X, int Y) {     int x, y;         for(x = 0; x < X; x ++) {         for(y = 0; y < Y; y ++) {             printf("&#37;2i", array[x][y]);             if(y + 1 < Y) putchar(' ');         }                 putchar('\n');     } } int main() {     int *array = malloc(X * Y * sizeof(*array));     int x;         /* because it's really just a 1D array */     for(x = 0; x < X * Y; x ++) {         array[x] = x;     }         /* ... but now, treat it like a 2D array */     print2d((int **)array, X, Y);     free(array);     return 0; }```
It gives a warning, yes, but that's surely to be expected . . . .
• 06-21-2008
laserlight
Quote:

It gives a warning, yes, but that's surely to be expected . . . .
The warning is because you cast array to an int**, but print2d expects an int(*)[Y]. Consequently, we can avoid the warning by casting to the correct type:
Code:

```/* ... but now, treat it like a 2D array */ print2d((int (*)[Y])array, X, Y);```
• 06-21-2008
dwks
D'oh! I tried "(int *[Y])", but of course that's not right. :)
• 06-21-2008
C_ntua
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
• 06-21-2008
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.]
• 06-21-2008
laserlight
Quote:

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
What it means (or perhaps "what it is") is the former. What actually happens depends on the compiler optimisations.

Quote:

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.
Both are true, because they are effectively the same thing (assuming the computations are correct). Whether interpreted as a 1D or 2D array, the block of memory is still the same, as long as the alignments are correct.
• 06-21-2008
C_ntua
Quote:

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
• 06-21-2008
Elysia
Quote:

Originally Posted by C_ntua
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 it's allocated on the stack, I'd say it's pretty sure.
But the compiler will figure out the indexes.
The OS just gives it x * y * z bytes of space.

Quote:

That is my point. That to be sure don't rely on optimizations, just do your job correctly
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);```
• 06-21-2008
C_ntua
Quote:

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!
Show 80 post(s) from this thread on one page
Page 2 of 2 First 12