Dynamic 2 Dimensional Array

This is a discussion on Dynamic 2 Dimensional Array within the C Programming forums, part of the General Programming Boards category; Originally Posted by C_ntua There is a "nicer" way to allocate a 2d, 3d etc array. It has also the ...

  1. #16
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    Quote Originally Posted by C_ntua View Post
    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.
    (Note: you should have had "int *array" instead of "int *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 . . . .
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  2. #17
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,717
    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);
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #18
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    D'oh! I tried "(int *[Y])", but of course that's not right.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  4. #19
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    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

  5. #20
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,604
    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.]
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  6. #21
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,717
    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.

    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #22
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    Quote Originally Posted by Elysia View Post
    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

  8. #23
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,604
    Quote Originally Posted by C_ntua View Post
    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.

    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);
    Last edited by Elysia; 06-21-2008 at 07:00 AM.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  9. #24
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    Quote Originally Posted by Elysia View Post
    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!

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Dynamic Array Allocation function
    By P4R4N01D in forum C++ Programming
    Replies: 6
    Last Post: 05-15-2009, 02:04 AM
  2. Replies: 2
    Last Post: 07-11-2008, 07:39 AM
  3. Dynamic Mutli dimensional Array question.
    By fatdunky in forum C Programming
    Replies: 6
    Last Post: 02-22-2006, 06:07 PM
  4. Dynamic 2 dimensional array with new?
    By Quantum1024 in forum C++ Programming
    Replies: 10
    Last Post: 11-19-2005, 01:46 PM
  5. total size of dynamic memory allocated array
    By trekker in forum C Programming
    Replies: 10
    Last Post: 03-10-2002, 11:59 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21