+ Reply to Thread
Results 1 to 6 of 6

Thread: Multi-dimensional arrays

  1. #1
    Super Moderator WingedPanther has much to be proud of WingedPanther has much to be proud of WingedPanther has much to be proud of WingedPanther has much to be proud of WingedPanther has much to be proud of WingedPanther has much to be proud of WingedPanther has much to be proud of WingedPanther has much to be proud of WingedPanther has much to be proud of WingedPanther's Avatar
    Join Date
    Jul 2006
    Age
    37
    Posts
    13,155
    Blog Entries
    59

    Multi-dimensional arrays

    Earlier,I talked about 1-dimensional arrays, arrays with one index. There is nothing that says an array has to be limited to 1 dimension. In fact, you can have an arbitrary number of dimensions in an array. 2 dimensional arrays are quite common, especially for storing things like screen coordinates or tables of data. Higher dimensions are used when you have more aspects that are required to specify a unique item (3-D coordinates, for example).

    An important thing to understand about arrays is this: technically, there is no such thing as a multi-dimensional array. All arrays are 1-dimensional, but some of them contain arrays, or arrays of arrays. What this means is that when you see
    Code:
    int multiarray[4][2]
    you are probably thinking of it as a grid of integers like this:
    Code:
       0       1
    0 [0][0]  [0][1]
    1 [1][0]  [1][1]
    2 [2][0]  [2][1]
    3 [3][0]  [3][1]
    In reality, the computer cannot store a “grid”, because memory is one long line of addresses. C++ treats each row as a 2 element array, which is a single element of a 4 element array. In other words, multiarray has 4 elements. Each element is an array, which contains 2 elements. So multiarray[0] is an array of 2 elements, multiarray[1] is an array of 2 elements, etc. That also means that multiarray[0] is a pointer! The type of multiarray[0] is int*. Since multiarray is a pointer to multiarray[0], that means multiarray has type int (*)[2]!!!

    If you think this is getting messy, you're right. If you think there's a lot of room for errors in code based on this, you're very right. Let's add to the mess. I said that the array cannot be stored as a grid, so let's look at how it is store. multiarray has three elements, so it looks something like this:
    Code:
    |  whatever's in 0 || whatever's in 1 || whatever's in 2 || whatever's in 3 |
        multiarray[0]      multiarray[1]      multiarray[2]      multiarray[3]
    Since each element of multiarray is an array of five ints, that means the “whatever's in..” is five consecutive ints, like this:
    Code:
    memory:     |[int0] [int1]||[int0] [int1]||[int0] [int1]||[int0] [int1]|
    multiarray:       [0]            [1]            [2]            [3]
    multiarray:  [0][0] [0][1]  [1][0] [1][1]  [2][0] [2][1]  [3][0] [3][1]
    What this means is that you have two ways to deal with multiarray: either as an array of 2 element arrays, or as a single array with 8 elements.

    Let's look at the two ways we can access this array with functions.
    Code:
    #include <iostream>
    
    void setarray(int ma[][2],int size)
    {
      for (int i=0;i<size;i++)
        for (int j=0;j<2;j++)
          ma[i][j] = 10*i+j;
    }
    
    void printarray(int* ma,int dim1, int dim2)
    {
      for (int i=0;i<dim1;i++)
      {
        for (int j=0;j<dim2;j++)
          std::cout<<*(ma+(i*dim2+j))<<" ";
        std::cout<<"\n";
      }
    }
    
    int main()
    {
      int multiarray[4][2];
      setarray(multiarray,4);
      printarray(&multiarray[0][0],4,2);
    }
    In function setarray(), the size of the subarray is hardcoded. but we can do the familiar easy call. The problem is that it is NOT flexible. On the other hand, printarray() is a lot more complicated to work with, but more flexible. Notice that that printarray simply takes the address of the first element and exploits the linear layout we've been talking about. I encourage you to step through the code and see how it produces this output:
    Code:
    0 1 
    10 11 
    20 21 
    30 31
    Needless to say, 3, 4, or higher dimensional arrays deal with either 1) increasingly less flexible function headers, or 2) increasingly nasty arithmetic. To think, some people think there's no math in programming !
    CodeCall Blog | CodeCall Wiki
    Programming is a branch of mathematics.
    My CodeCall Blog | My Personal Blog

  2. #2
    MeTh0Dz is a name known to all MeTh0Dz is a name known to all MeTh0Dz is a name known to all MeTh0Dz is a name known to all MeTh0Dz is a name known to all MeTh0Dz is a name known to all
    Join Date
    May 2008
    Posts
    2,129

    Re: Multi-dimensional arrays

    Some things that you may consider adding to this tutorial or a part two (Maybe I should write a tutorial, I always get half way done and say **** it).

    Explain that the way multidimensional arrays are stored in memory changes on a language to language basis. In the case of C/C++ they use row major ordering. Which you give an example above. However other languages use column major ordering which is a bit different (go down the columns listing the data and then return to the top of the next column).

    Another thing, Bjarne explicitly says that multidimensional arrays above 2 dimensions should be avoided whenever possible.

  3. #3
    Administrator Jordan is a name known to all Jordan is a name known to all Jordan is a name known to all Jordan is a name known to all Jordan is a name known to all Jordan is a name known to all Jordan's Avatar
    Join Date
    Nov 2005
    Location
    Hendersonville, NC
    Posts
    24,750
    Blog Entries
    97

    Re: Multi-dimensional arrays

    Excellent read, I read it while waiting on my wife at the mall.



    Posted via CodeCall Mobile

  4. #4
    Super Moderator WingedPanther has much to be proud of WingedPanther has much to be proud of WingedPanther has much to be proud of WingedPanther has much to be proud of WingedPanther has much to be proud of WingedPanther has much to be proud of WingedPanther has much to be proud of WingedPanther has much to be proud of WingedPanther has much to be proud of WingedPanther's Avatar
    Join Date
    Jul 2006
    Age
    37
    Posts
    13,155
    Blog Entries
    59

    Re: Multi-dimensional arrays

    @Methodz, you're right that implementation of arrays is language specific. Using 3+ dimensional arrays is generally a sign that you're doing something wrong. One problem is the rate at which memory is consumed. int[100] uses 100 ints, int[100][100] uses 10,000 ints, int[100][100][100] uses 1,000,000 ints. In general, you're looking at 100^n, where n is the number of dimensions. That can very quickly consume ridiculous amounts of memory.

    The only time I can think of to legitimately use a 3-dimensional array is for a board game like 3D chess (8x8x3) or something similar.

    I'd love to see you write some tutorials.
    CodeCall Blog | CodeCall Wiki
    Programming is a branch of mathematics.
    My CodeCall Blog | My Personal Blog

  5. #5
    Code Slinger chili5 has a reputation beyond repute chili5 has a reputation beyond repute chili5 has a reputation beyond repute chili5 has a reputation beyond repute chili5 has a reputation beyond repute chili5 has a reputation beyond repute chili5 has a reputation beyond repute chili5 has a reputation beyond repute chili5 has a reputation beyond repute chili5 has a reputation beyond repute chili5 has a reputation beyond repute chili5's Avatar
    Join Date
    Mar 2008
    Posts
    7,042

    Re: Multi-dimensional arrays

    There are some programming contest questions that require using 3D arrays but it is not common. Like you are in a 3D maze and you want to know the shortest way through the 3D maze.

    With that, very nice. +rep for you.

    You know how you create an array like this:

    Code:
    int arnNums[15][30];
    What if you want to create a 2d array based on input from a file. Like the user specifies the size of the array, what would you do then?

    I suppose you could do this:

    Code:
    while(in>>n>>m) {
          int a[n][m];
    }
    but is there a way around that in C++? In Java you can do this:

    Code:
    arnNums = new int[n][m];
    but I can't seem to get that to work in C++. Thoughts?
    "Whenever you remember, I'll be there/
    Remember how we reached that dream together" - Carrie Underwood

  6. #6
    Code Warrior BlaineSch is a name known to all BlaineSch is a name known to all BlaineSch is a name known to all BlaineSch is a name known to all BlaineSch is a name known to all BlaineSch is a name known to all BlaineSch's Avatar
    Join Date
    Apr 2009
    Location
    Trapped in my own little world.
    Age
    20
    Posts
    2,289
    Blog Entries
    8

    Re: Multi-dimensional arrays

    The thread is alive!

    You might try typecasting and seeing if that works. I know if it's just a variable you can initialize it with that, I don't see that as an issue with C++.

+ Reply to Thread

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

     

Similar Threads

  1. Two dimensional array
    By bar707 in forum C# Programming
    Replies: 2
    Last Post: 07-21-2010, 08:38 PM
  2. Replies: 1
    Last Post: 06-28-2010, 05:34 PM
  3. Creating a Two Dimensional Vector
    By whitey6993 in forum C Tutorials
    Replies: 1
    Last Post: 04-04-2010, 11:19 AM
  4. Replies: 6
    Last Post: 10-12-2009, 07:56 PM
  5. 3-Dimensional Cube
    By Paradox in forum Java Tutorials
    Replies: 0
    Last Post: 07-16-2008, 06:10 PM