Multi-dimensional arrays

[WingedPanther]

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

int multiarray[4][2]

you are probably thinking of it as a grid of integers like this:

   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:

|  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:

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.

#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:

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 !

[MeTh0Dz]

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.

[Jordan]

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



Posted via CodeCall Mobile

[WingedPanther]

@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.

[chili5]

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:

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:

while(in>>n>>m) {
      int a[n][m];
}

but is there a way around that in C++? In Java you can do this:

arnNums = new int[n][m];

but I can't seem to get that to work in C++. Thoughts?

[BlaineSch]

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++.