Is the syntax for multi-dimensional arrays counter-intuitive?

Discussion in 'C Programming' started by masood.iqbal@lycos.com, Feb 3, 2005.

  1. Guest

    All this time I was under the illusion that I understand the concept of
    multi-dimensional arrays well ---- however the following code snippet
    belies my understanding.

    I had assumed all along that a declaration like:
    int intArray[3][5]
    means that there is an array of pointers to int with a size of 5, each
    of whose elements is an array of int with a size of 3.

    This definition seemed intuitive to me since a declaration like
    int intVar[5]
    means that there is an array of integers with a size of 5.

    In my "intuitive" thinking, to dynamically create a 2D array with 3
    rows and 5 columns, we would do the following:

    Allocate memory for 5 pointers to int (i.e. pointer array)
    For each entry in the pointer array
    Do
    Allocate memory for 3 ints
    Done

    My code had a bug, which was fixed by switching my logic to something
    like this (as can be seen from the coding example):

    Allocate memory for 3 pointers to int (i.e. pointer array)
    For each entry in the pointer array
    Do
    Allocate memory for 5 ints
    Done

    This indicates to me that the correct interpretation of a declaration
    like:

    int intArray[3][5]

    is that there is an array of pointers to int with a size of 3, each of
    whose elements is an array of int with a size of 5. Is this a correct
    interpretation? This sounds counter intuitive to me (for reasons
    mentioned above) but I have reconciled to this interpretation. I will
    jump off the cliff if I am wrong again!


    Masood


    /*************************************************/
    #include <stdio.h>
    #include <stdlib.h>

    #define MAXROWS 3
    #define MAXCOLS 5

    main()
    {
    int startVal = 5;

    int **tbl;

    tbl = (int **)malloc(MAXROWS*sizeof(int*));
    /* C++ : tbl = new (int*)[MAXROWS]; */

    for(size_t i = 0; i < MAXCOLS; i++)
    tbl = (int *)malloc(MAXCOLS*sizeof(int));
    /* C++: tbl = new (int)[MAXCOLS]; */

    for(size_t row = 0; row < MAXROWS; row++)
    for(size_t col = 0; col < MAXCOLS; col++)
    tbl[row][col] = startVal++;

    for(size_t row = 0; row < MAXROWS; row++)
    for(size_t col = 0; col < MAXCOLS; col++)
    printf("Row: %d, Col: %d => %d\n",
    row, col, tbl[row][col]);
    return 0;
    }
    , Feb 3, 2005
    #1
    1. Advertising

  2. writes:
    > All this time I was under the illusion that I understand the concept of
    > multi-dimensional arrays well ---- however the following code snippet
    > belies my understanding.
    >
    > I had assumed all along that a declaration like:
    > int intArray[3][5]
    > means that there is an array of pointers to int with a size of 5, each
    > of whose elements is an array of int with a size of 3.


    Strictly speaking, C doesn't have multi-dimensional arrays. It does
    have arrays of arrays, though.

    The above declaration declares an array of 3 elements. Each element
    is an array of 5 ints.

    It doesn't create any pointers.

    There's a rule that, in an expression, the name of an array is
    (usually) converted to a pointer to its first element. (This
    conversion doesn't happen if the array name is the operand of a sizeof
    or unary "&" operator.) This rule is the source of the fallacy that
    arrays and pointers are somehow the same thing. They aren't.

    The fact that a parameter declaration
    some_type *param
    can be written as
    some_type param[]
    just adds to the confusion.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
    We must do something. This is something. Therefore, we must do this.
    Keith Thompson, Feb 3, 2005
    #2
    1. Advertising

  3. ["Followup-To:" header set to comp.lang.c.]
    On 2005-02-03, <> wrote:
    > All this time I was under the illusion that I understand the concept of
    > multi-dimensional arrays well ---- however the following code snippet
    > belies my understanding.
    >
    > I had assumed all along that a declaration like:
    > int intArray[3][5]
    > means that there is an array of pointers to int with a size of 5, each
    > of whose elements is an array of int with a size of 3.
    >
    > This definition seemed intuitive to me since a declaration like
    > int intVar[5]
    > means that there is an array of integers with a size of 5.


    In C multi-dimensioned arrays are arrays of arrays. With the above
    declarations, intVar in an expression is treated as pointer to an int.
    Similarily, intArray in an expression is treated as a pointer to an
    array of 5 ints.

    > In my "intuitive" thinking, to dynamically create a 2D array with 3
    > rows and 5 columns, we would do the following:
    >
    > Allocate memory for 5 pointers to int (i.e. pointer array)
    > For each entry in the pointer array
    > Do
    > Allocate memory for 3 ints
    > Done


    In C arrays are stored row-wise; the rightmost subscript varies the
    fastest. If the rightmost dimension is 5, you need to allocte memory
    for 5 ints for each occurrence of the next dimension to the left.

    To the designers of C to dynamically create a 2D array with 3 rows
    and 5 columns, you could use

    int (*intArray_p)[3][5] = malloc(sizeof(*intArray_p));

    to declare and allocate the array and use (*intArray_p)[j] to refer
    to the i-th, j-th element.

    If you know all but the leftmost dimension at compile time, you could
    use

    int (*intArray_p)[][5] = malloc(leftDimCount*sizeof(**intArray_p));

    to declare and allocate the array and use (*intArray_p)[j] to refer
    to the i-th, j-th element.

    If you know neither of the dimensions at compile time, you could
    use

    int *int_p = malloc(leftDimCount*rightDimCount*sizeof(*int_p));

    to declare and allocate the array and use int_p[i*rightDimCount + j]
    to refer to the i-th, j-th element.

    > My code had a bug, which was fixed by switching my logic to something
    > like this (as can be seen from the coding example):
    >
    > Allocate memory for 3 pointers to int (i.e. pointer array)


    You want to allocate memory for 3 pointers arrays of 5 ints. However,
    in most implementations a pointer to int and a pointer to and array of
    5 ints have the same representation.

    > For each entry in the pointer array
    > Do
    > Allocate memory for 5 ints
    > Done
    >
    > This indicates to me that the correct interpretation of a declaration
    > like:
    >
    > int intArray[3][5]
    >
    > is that there is an array of pointers to int with a size of 3, each of
    > whose elements is an array of int with a size of 5. Is this a correct
    > interpretation? This sounds counter intuitive to me (for reasons
    > mentioned above) but I have reconciled to this interpretation. I will
    > jump off the cliff if I am wrong again!


    The correct interpretation is that there is an array of 3 elements, each
    of whose elements is an array of 5 ints. When intArray appears in an
    expression, it is treated as a pointer to its first element, which is
    and array of 5 ints. However, intArray is not stored as an array of
    pointers.
    [snip]
    A. Bolmarcich, Feb 3, 2005
    #3
  4. On Thu, 03 Feb 2005 05:28:55 +0000, A. Bolmarcich wrote:

    > ["Followup-To:" header set to comp.lang.c.]
    > On 2005-02-03, <> wrote:
    >> All this time I was under the illusion that I understand the concept of
    >> multi-dimensional arrays well ---- however the following code snippet
    >> belies my understanding.
    >>
    >> I had assumed all along that a declaration like:
    >> int intArray[3][5]
    >> means that there is an array of pointers to int with a size of 5, each
    >> of whose elements is an array of int with a size of 3.


    There are no pointers here, and pointers don't have elements arrays do.
    Pointers point to OTHER objects and there is only one overall object here.
    intArray would be laid out in memory as 15 contiguous int objects,
    treated as 3 groups of 5 ints. If you output sizeof intArray you'll see it
    is 15*sizeof(int).

    >> This definition seemed intuitive to me since a declaration like
    >> int intVar[5]
    >> means that there is an array of integers with a size of 5.


    That's fine, but it doesn't suggest anything about pointers in arrays of
    arrays. In that case you're just replacing the element type int here with
    a different element type that happens itself to be an array. An equivalent
    way of defining intArray would be:

    typedef int Int5[5];
    Int5 intArray[3];

    > In C multi-dimensioned arrays are arrays of arrays. With the above
    > declarations, intVar in an expression is treated as pointer to an int.
    > Similarily, intArray in an expression is treated as a pointer to an
    > array of 5 ints.
    >
    >> In my "intuitive" thinking, to dynamically create a 2D array with 3
    >> rows and 5 columns, we would do the following:
    >>
    >> Allocate memory for 5 pointers to int (i.e. pointer array)
    >> For each entry in the pointer array
    >> Do
    >> Allocate memory for 3 ints
    >> Done

    >
    > In C arrays are stored row-wise; the rightmost subscript varies the
    > fastest. If the rightmost dimension is 5, you need to allocte memory
    > for 5 ints for each occurrence of the next dimension to the left.
    >
    > To the designers of C to dynamically create a 2D array with 3 rows
    > and 5 columns, you could use
    >
    > int (*intArray_p)[3][5] = malloc(sizeof(*intArray_p));


    But typically you wouldn't, you would use

    int (*intArray_p)[5] = malloc(3 * sizeof *intArray_p);

    > to declare and allocate the array and use (*intArray_p)[j] to refer
    > to the i-th, j-th element.


    And then you can refer to the elements using intArray_p[j]

    > If you know all but the leftmost dimension at compile time, you could
    > use
    >
    > int (*intArray_p)[][5] = malloc(leftDimCount*sizeof(**intArray_p));
    >
    > to declare and allocate the array and use (*intArray_p)[j] to refer
    > to the i-th, j-th element.


    The simpler version works here too.

    > If you know neither of the dimensions at compile time, you could
    > use
    >
    > int *int_p = malloc(leftDimCount*rightDimCount*sizeof(*int_p));
    >
    > to declare and allocate the array and use int_p[i*rightDimCount + j]
    > to refer to the i-th, j-th element.


    This is a case where using an intermediate array of pointers can help. If
    you do that you can still use the int_p[j] syntax for accessing
    elements.

    >> My code had a bug, which was fixed by switching my logic to something
    >> like this (as can be seen from the coding example):
    >>
    >> Allocate memory for 3 pointers to int (i.e. pointer array)

    >
    > You want to allocate memory for 3 pointers arrays of 5 ints. However,
    > in most implementations a pointer to int and a pointer to and array of
    > 5 ints have the same representation.


    3 pointers to int is correct. When you access an array using a pointer you
    use a pointer to the array's element type. So to access an array of 5 ints
    you need a pointer of type pointer to int.

    >> For each entry in the pointer array
    >> Do
    >> Allocate memory for 5 ints
    >> Done
    >>
    >> This indicates to me that the correct interpretation of a declaration
    >> like:
    >>
    >> int intArray[3][5]
    >>
    >> is that there is an array of pointers to int with a size of 3, each of
    >> whose elements is an array of int with a size of 5. Is this a correct
    >> interpretation?


    Again, there are no pointers involved. You simply have a bunch of int
    objects together in memory and the type of intArray supplies the
    information the compiler needs to figure out the address of the correct
    one by direct offset calculation.

    >> This sounds counter intuitive to me (for reasons
    >> mentioned above) but I have reconciled to this interpretation. I will
    >> jump off the cliff if I am wrong again!


    Then make it a very small cliff.

    > The correct interpretation is that there is an array of 3 elements, each
    > of whose elements is an array of 5 ints. When intArray appears in an
    > expression, it is treated as a pointer to its first element, which is
    > and array of 5 ints. However, intArray is not stored as an array of
    > pointers.
    > [snip]


    Yes.

    Lawrence
    Lawrence Kirby, Feb 3, 2005
    #4
  5. axter Guest

    The following is an example function that uses a more efficient method
    for allocating memory on a multi dimensional array.
    This code is for a 3D array, but the logic can easily be modified for
    2D array:

    #include <stdlib.h>
    #include <stdio.h>
    #include <memory.h>

    int ***Allocate3DArray_C( int x, int y, int z)
    {
    int *** pppx = (int ***)malloc(x*sizeof(int**));
    int ** pool_y = (int **)malloc(x*y*sizeof(int*));
    int * pool_z = (int *)malloc(x*y*z*sizeof(int));
    int i_x, i_y;
    for(i_x = 0; i_x < x; ++i_x){
    pppx[i_x] = pool_y;
    pool_y +=y;
    for(i_y = 0;i_y < y;++i_y){
    pppx[i_x][i_y] = pool_z;
    pool_z +=z;
    }
    }
    return pppx;
    }

    void Free3DArray_C(int*** Array)
    {
    free(**Array);
    free(*Array);
    free(Array);
    }

    void Test3DArray(int *** Array, int x, int y, int z)
    {
    int ix, iy, iz;
    for(ix = 0;ix < x;++ix)
    {
    for(iy = 0;iy < y;++iy)
    {
    for(iz=0;iz<z;++iz)
    {
    printf("%03i\n", Array[ix][iy][iz]);
    }
    }
    }
    }



    int main()
    {
    int x = 2;
    int y = 3;
    int z = 5;
    int ix, iy, iz;
    int *** d = Allocate3DArray_C(x, y, z);
    for(ix = 0;ix < x;++ix)
    {
    for(iy = 0;iy < y;++iy)
    {
    for(iz=0;iz<z;++iz)
    {
    d[ix][iy][iz] = ix*100 + iy*10 + iz;
    }
    }
    }

    Test3DArray(d, x , y , z);

    Free3DArray_C(d);

    system("pause");
    return 0;
    }

    Check out following link for more information on 2D arrays.
    http://www.tek-tips.com/faqs.cfm?fid=5575
    axter, Feb 4, 2005
    #5
  6. infobahn Guest

    axter wrote:
    >
    > The following is an example function that uses a more efficient method
    > for allocating memory on a multi dimensional array.
    > This code is for a 3D array, but the logic can easily be modified for
    > 2D array:
    >
    > #include <stdlib.h>
    > #include <stdio.h>
    > #include <memory.h>
    >
    > int ***Allocate3DArray_C( int x, int y, int z)
    > {
    > int *** pppx = (int ***)malloc(x*sizeof(int**));


    Better: int ***pppx = malloc(x * sizeof *pppx);

    > int ** pool_y = (int **)malloc(x*y*sizeof(int*));


    Better: int **pool_y = malloc(x * y * sizeof *pool_y);

    > int * pool_z = (int *)malloc(x*y*z*sizeof(int));


    Better: int *pool_z = malloc(x * y * z * sizeof *pool_z);

    > int i_x, i_y;
    > for(i_x = 0; i_x < x; ++i_x){
    > pppx[i_x] = pool_y;


    Aren't you assuming something here that needn't be true?

    > pool_y +=y;
    > for(i_y = 0;i_y < y;++i_y){
    > pppx[i_x][i_y] = pool_z;


    And here.

    <snip>

    > system("pause");


    And here.
    infobahn, Feb 4, 2005
    #6
  7. axter Guest

    >>int *** pppx = (int ***)malloc(x*sizeof(int**));
    >>Better: int ***pppx = malloc(x * sizeof *pppx);


    IMHO, not better.
    The example code was type cast so that it could compile in both C and
    C++.
    Including it, doesn't hurt.

    >>Aren't you assuming something here that needn't be true?

    Can you please be more explicit?
    If you have a point to make, please make it.
    axter, Feb 4, 2005
    #7
  8. Michael Mair Guest

    You snipped the attributions and somehow created a problem
    with citation levels.
    Please do not do that.

    axter wrote:
    >>>int *** pppx = (int ***)malloc(x*sizeof(int**));
    >>>Better: int ***pppx = malloc(x * sizeof *pppx);

    >
    > IMHO, not better.
    > The example code was type cast so that it could compile in both C and
    > C++.
    > Including it, doesn't hurt.


    Maybe. Have you looked at the changes to the argument of malloc()?
    These are indeed an improvement.
    Together with the missing cast, you can change the type of
    pppx in one place (at declaration) without having to change
    any cast-expressions. Even without that, sizeof *pppx is
    always the right size.

    >
    >
    >>>Aren't you assuming something here that needn't be true?

    >
    > Can you please be more explicit?
    > If you have a point to make, please make it.


    Unfortunately, you snipped so much that I cannot help you.


    -Michael
    --
    E-Mail: Mine is an /at/ gmx /dot/ de address.
    Michael Mair, Feb 4, 2005
    #8
  9. infobahn Guest

    axter wrote:
    >
    > >>int *** pppx = (int ***)malloc(x*sizeof(int**));
    > >>Better: int ***pppx = malloc(x * sizeof *pppx);

    >
    > IMHO, not better.


    Then I think YHO is based on incomplete data.

    > The example code was type cast so that it could compile in both C and
    > C++.


    With very few exceptions (pjp being the canonical example), this is
    unwise. C and C++ are very different languages.

    > Including it, doesn't hurt.


    It doesn't help, either, in C (we don't discuss C++ in comp.lang.c,
    but you'd normally expect to use new or std::vector in C++ rather
    than malloc).

    Furthermore, including it can indeed hurt if you forget to include
    <stdlib.h> (which on this occasion you did not, although I now
    notice that you also added a <memory.h> - I am not sure why you did
    that).

    The cast makes the code harder to read, too.

    > >>Aren't you assuming something here that needn't be true?

    > Can you please be more explicit?
    > If you have a point to make, please make it.


    When you ask malloc for memory, it's a good idea to check that you
    actually /received/ that memory before you start to use it.
    infobahn, Feb 5, 2005
    #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. Paul Brown
    Replies:
    7
    Views:
    373
    Christian Bau
    Oct 10, 2003
  2. Paul Brown
    Replies:
    4
    Views:
    400
    Randy Howard
    Oct 9, 2003
  3. Paul Brown
    Replies:
    1
    Views:
    311
    Steven G. Johnson
    Oct 7, 2003
  4. Paul Brown
    Replies:
    2
    Views:
    303
    Keith Thompson
    Oct 9, 2003
  5. Wirianto Djunaidi
    Replies:
    2
    Views:
    200
    Wirianto Djunaidi
    Apr 29, 2008
Loading...

Share This Page