Arbitrary length multi-dimensional arrays

Discussion in 'C Programming' started by kd, Jun 26, 2006.

  1. kd

    kd Guest

    Newbie question here. It's been a while since I've done C programming,
    and I hit a wall last night.

    Let's say I have a three dimensional array, like so:

    int p[2][3][3] =
    {{{0,0,0},
    {1,1,1},
    {0,1,0}},

    {{0,1,0},
    {1,1,0},
    {0,1,0}}};

    I also have a number of other three dimensional arrays, generated with
    a code generating script. The size of each dimension varies with each
    one. Some are [5][3][3], some are [2][5][5], etc...

    How would I declare a variable that could hold any of these
    3-dimensional arrays? I'm tripping over the pointer syntax.

    I'd like to be able to do something like:
    int ***val = p; //The variable p from the last example.

    I'm pretty sure that ***val is the wrong way to go about it.

    Thanks for your help!

    -kd
     
    kd, Jun 26, 2006
    #1
    1. Advertising

  2. kd

    Tom St Denis Guest

    kd wrote:
    > Newbie question here. It's been a while since I've done C programming,
    > and I hit a wall last night.
    >
    > Let's say I have a three dimensional array, like so:
    >
    > int p[2][3][3] =
    > {{{0,0,0},
    > {1,1,1},
    > {0,1,0}},
    >
    > {{0,1,0},
    > {1,1,0},
    > {0,1,0}}};
    >
    > I also have a number of other three dimensional arrays, generated with
    > a code generating script. The size of each dimension varies with each
    > one. Some are [5][3][3], some are [2][5][5], etc...
    >
    > How would I declare a variable that could hold any of these
    > 3-dimensional arrays? I'm tripping over the pointer syntax.
    >
    > I'd like to be able to do something like:
    > int ***val = p; //The variable p from the last example.
    >
    > I'm pretty sure that ***val is the wrong way to go about it.


    No you'd need three levels of indirection. A smart way though is to
    just have a single pointer and compute the address yourself, especially
    if you're dealing with a *variable* number of dimensions.

    Tom
     
    Tom St Denis, Jun 26, 2006
    #2
    1. Advertising

  3. kd posted:

    > Newbie question here. It's been a while since I've done C programming,
    > and I hit a wall last night.
    >
    > Let's say I have a three dimensional array, like so:
    >
    > int p[2][3][3] =
    > {{{0,0,0},
    > {1,1,1},
    > {0,1,0}},
    >
    > {{0,1,0},
    > {1,1,0},
    > {0,1,0}}};
    >
    > I also have a number of other three dimensional arrays, generated with
    > a code generating script. The size of each dimension varies with each
    > one. Some are [5][3][3], some are [2][5][5], etc...
    >
    > How would I declare a variable that could hold any of these
    > 3-dimensional arrays? I'm tripping over the pointer syntax.



    Do you want a pointer to the first element of the array?

    int array1[2][3][3];
    int array2[5][3][3];
    int array3[2][5][5];


    int *p;

    p = ***array1;
    p = ***array2;
    p = ***array3;


    Writing:

    array[0]

    is the same as writing:

    *array


    Therefore:

    ***array

    (which can also be written as):

    *(*(*array))

    becomes:

    ((array[0])[0])[0]


    which, because of C operator precedence rules, is simply:

    array[0][0][0]


    --

    Frederick Gotham
     
    Frederick Gotham, Jun 26, 2006
    #3
  4. On 2006-06-26, kd <> wrote:
    > Newbie question here. It's been a while since I've done C programming,
    > and I hit a wall last night.
    >
    > Let's say I have a three dimensional array, like so:
    >
    > int p[2][3][3] =
    > {{{0,0,0},
    > {1,1,1},
    > {0,1,0}},
    >
    > {{0,1,0},
    > {1,1,0},
    > {0,1,0}}};
    >
    > I also have a number of other three dimensional arrays, generated with
    > a code generating script. The size of each dimension varies with each
    > one. Some are [5][3][3], some are [2][5][5], etc...
    >
    > How would I declare a variable that could hold any of these
    > 3-dimensional arrays? I'm tripping over the pointer syntax.
    >
    > I'd like to be able to do something like:
    > int ***val = p; //The variable p from the last example.
    >
    > I'm pretty sure that ***val is the wrong way to go about it.
    >


    No, ***p will do it. You'll be able to go through the array with p++,
    (*p)++, and (**p)++, depending on which dimension you are moving
    through. Indeed, it is pretty complicated.

    Why are you doing this?

    --
    Andrew Poelstra < http://www.wpsoftware.net/blog >
    To email me, use "apoelstra" at the above address.
    I know that area of town like the back of my head.
     
    Andrew Poelstra, Jun 26, 2006
    #4
  5. kd

    Ben C Guest

    On 2006-06-26, kd <> wrote:
    > Newbie question here. It's been a while since I've done C programming,
    > and I hit a wall last night.
    >
    > Let's say I have a three dimensional array, like so:
    >
    > int p[2][3][3] =
    > {{{0,0,0},
    > {1,1,1},
    > {0,1,0}},
    >
    > {{0,1,0},
    > {1,1,0},
    > {0,1,0}}};
    >
    > I also have a number of other three dimensional arrays, generated with
    > a code generating script. The size of each dimension varies with each
    > one. Some are [5][3][3], some are [2][5][5], etc...
    >
    > How would I declare a variable that could hold any of these
    > 3-dimensional arrays?


    You can't really. The thing to think about is how does the compiler
    interpret an expression like:

    p[j][k]

    Suppose p is declared int p[2][3][4]. To find its way to element i,j,k,
    the compiler needs to work out the offset from the start of where p is
    stored to this element. This amounts to something like:

    4*3*i*n + 3*j*n + k*n

    where n is sizeof (int). The point is the compiler needs to know the 3
    and the 4, which it determined by looking at the type of p.

    You can make a pointer to p like this:

    int (*pp)[2][3][4] = &p;

    or even like this:

    int (*pp)[][3][4] = &p;

    since the compiler needs to know the 3 and the 4, but not the 2.

    But you should get an "initialization from incompatible pointer type" or
    similar warning if you try to make pp point to an array that was
    declared int q[2][5][5]. If you force the initialization with a cast,
    you will get the wrong results when you use pp because the compiler will
    be working with the wrong dimensions for q.
     
    Ben C, Jun 26, 2006
    #5
  6. kd

    Michael Mair Guest

    Frederick Gotham schrieb:
    <snip>
    > Do you want a pointer to the first element of the array?
    >
    > int array1[2][3][3];

    <snip>
    >
    > int *p;
    >
    > p = ***array1;


    You are assigning an int value to a pointer.
    Bad idea.

    Cheers
    Michael
    --
    E-Mail: Mine is an /at/ gmx /dot/ de address.
     
    Michael Mair, Jun 26, 2006
    #6
  7. Michael Mair posted:

    > Frederick Gotham schrieb:
    ><snip>
    >> Do you want a pointer to the first element of the array?
    >>
    >> int array1[2][3][3];

    ><snip>
    >>
    >> int *p;
    >>
    >> p = ***array1;

    >
    > You are assigning an int value to a pointer.
    > Bad idea.
    >
    > Cheers
    > Michael



    Wups.


    p = **array1;



    --

    Frederick Gotham
     
    Frederick Gotham, Jun 26, 2006
    #7
  8. kd

    Michael Mair Guest

    kd schrieb:
    > Newbie question here. It's been a while since I've done C programming,
    > and I hit a wall last night.
    >
    > Let's say I have a three dimensional array, like so:
    >
    > int p[2][3][3] =
    > {{{0,0,0},
    > {1,1,1},
    > {0,1,0}},
    >
    > {{0,1,0},
    > {1,1,0},
    > {0,1,0}}};
    >
    > I also have a number of other three dimensional arrays, generated with
    > a code generating script. The size of each dimension varies with each
    > one. Some are [5][3][3], some are [2][5][5], etc...
    >
    > How would I declare a variable that could hold any of these
    > 3-dimensional arrays? I'm tripping over the pointer syntax.
    >
    > I'd like to be able to do something like:
    > int ***val = p; //The variable p from the last example.
    >
    > I'm pretty sure that ***val is the wrong way to go about it.


    It is the wrong way.
    int (*val)[3][3] = p;
    is the right way to deal with arbitrary amounts of "3 by 3" matrices.
    If you want to be able to deal with "arbitrary amounts of arbitrary
    row by arbitrary column number matrices", you need three levels of
    indirection. For every level but the last you need "index arrays".

    Now, there are two ways of representing your "3D array" in memory
    which _can_ make things easier:
    1) Condensed. I.e. the last column of the first row of the
    first matrix is immediately followed by the first column of the
    second row of the first matrix and the last column of the last
    row of the first matrix is immediately followed by the first
    column of the first row of the second matrix.
    This means that you could do with one array of int and could
    access everything "matrixlike" via
    #define INDEX(i, j, k, num_j, num_k) \
    (((i) * (max_j) + (j)) * (max_k) + (k))
    and
    int *array = malloc(sizeof p);
    if (NULL == array) {
    /* error handling and abort */
    }
    memcpy(array, p, sizeof p);
    for (mat = 0; mat < num_mat; ++mat)
    for (row = 0; row < num_row; ++row)
    for (col = 0; col < num_col; ++col) {
    do_something(array[INDEX(mat,row,col, num_row,num_col)]);
    }

    If you really insist on
    int ***val;
    you need the following steps:
    num_mat = sizeof p/sizeof p[0];
    val = malloc(num_mat * sizeof *val);
    if (NULL == val) {
    /* error handling and abort */
    }
    num_row = sizeof p[0] / sizeof p[0][0];
    *val = malloc(num_mat*num_row * sizeof **val);
    if (NULL == *val) {
    /* error handling and abort */
    }
    for (mat = 1; mat < num_mat; ++mat) {
    val[mat] = val[0] + mat*num_row;
    }
    /* 1 */
    for (mat = 0; mat < num_mat; ++mat)
    for (row = 0; row < num_row; ++row)
    val[mat][row] = p[mat][row];
    /* 2 */
    in order to use
    for (mat = 0; mat < num_mat; ++mat)
    for (row = 0; row < num_row; ++row)
    for (col = 0; col < num_col; ++col) {
    do_something(val[mat][row][col]);
    }
    Note that this operates on the original array p.
    If you want to have val as a "copy of p", you have to replace
    /* 1 */ to /* 2 */ by
    num_col = sizeof p[0][0] / sizeof p[0][0][0];
    **val = malloc(num_mat*num_row*num_col * sizeof ***val); /*3*/
    if (NULL == **val) {
    /* error handling and abort */
    }
    memcpy(val, p, sizeof p);
    for (mat = 0; mat < num_mat; ++mat)
    for (row = 0; row < num_row; ++row)
    val[mat][row] = val[0][0] + (mat*num_row + row)*num_col;

    2) Maximum array: Say you know that the largest possible array
    dimensions are MAX_MAT, MAX_ROW, MAX_COL and
    MAX_MAT*MAX_ROW*MAX_COL is not too large. Then declare your
    "intermediate" matrix as
    int val[MAX_MAT][MAX_ROW][MAX_COL];
    and copy the values:
    for (mat = 0; mat < num_mat; ++mat)
    for (row = 0; row < num_row; ++row)
    for (col = 0; col < num_col; ++col) {
    val[mat][row][col] = p[mat][row][col];
    }


    Merits: 1) makes it possible to just memcpy() the array but
    can mean resizing of "array" or "**val", "*val", and "val",
    respectively. 2) means no resizing but potentially increased
    cost for copying -- and much memory consumption.

    If you allocate each row separately instead of at once (/*3*/),
    you can "resize" the matrix in an easier manner but have
    more allocations to take care of.

    It depends on your application whether 1) or 2) or a mixed
    form or something completely different is best for your...


    Cheers
    Michael
    --
    E-Mail: Mine is an /at/ gmx /dot/ de address.
     
    Michael Mair, Jun 26, 2006
    #8
  9. kd

    Guest

    Andrew Poelstra wrote:

    > Why are you doing this?


    Tetris! :) Every budding game developer's first game!

    It's the sequence of rotations for different pieces!
     
    , Jun 27, 2006
    #9
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Alf P. Steinbach
    Replies:
    0
    Views:
    436
    Alf P. Steinbach
    Aug 18, 2003
  2. John Harrison
    Replies:
    4
    Views:
    6,927
    Default User
    Aug 19, 2003
  3. Icosahedron
    Replies:
    8
    Views:
    656
    Vivek
    Aug 21, 2003
  4. Honestmath
    Replies:
    5
    Views:
    559
    Honestmath
    Dec 13, 2004
  5. Wirianto Djunaidi
    Replies:
    2
    Views:
    203
    Wirianto Djunaidi
    Apr 29, 2008
Loading...

Share This Page