Go Back   CodeCall Programming Forum > Software Development > Tutorials > C Tutorials
Register Blogs Search Today's Posts Mark Forums Read

C Tutorials All C Tutorials and Code

Reply
 
LinkBack Thread Tools Search this Thread Display Modes
  #1 (permalink)  
Old 12-13-2008, 03:29 PM
WingedPanther's Avatar
Super Moderator
 
Join Date: Jul 2006
Age: 36
Posts: 11,435
WingedPanther has much to be proud ofWingedPanther has much to be proud ofWingedPanther has much to be proud ofWingedPanther has much to be proud ofWingedPanther has much to be proud ofWingedPanther has much to be proud ofWingedPanther has much to be proud ofWingedPanther has much to be proud ofWingedPanther has much to be proud of
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 | Shareware
Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!
Reply With Quote
  #2 (permalink)  
Old 12-13-2008, 03:37 PM
Banned
 
Join Date: Jul 2008
Posts: 126
MeTh0Dz|Reb0rn is a jewel in the roughMeTh0Dz|Reb0rn is a jewel in the roughMeTh0Dz|Reb0rn is a jewel in the roughMeTh0Dz|Reb0rn is a jewel in the rough
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.
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!
Reply With Quote
  #3 (permalink)  
Old 12-13-2008, 05:38 PM
Jordan's Avatar
Administrator
 
Join Date: Nov 2005
Location: Hendersonville, NC
Posts: 24,556
Jordan is a name known to allJordan is a name known to allJordan is a name known to allJordan is a name known to allJordan is a name known to allJordan is a name known to all
Send a message via ICQ to Jordan Send a message via AIM to Jordan Send a message via MSN to Jordan Send a message via Yahoo to Jordan
Re: Multi-dimensional arrays

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



Posted via CodeCall Mobile
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!
Reply With Quote
  #4 (permalink)  
Old 12-13-2008, 05:59 PM
WingedPanther's Avatar
Super Moderator
 
Join Date: Jul 2006
Age: 36
Posts: 11,435
WingedPanther has much to be proud ofWingedPanther has much to be proud ofWingedPanther has much to be proud ofWingedPanther has much to be proud ofWingedPanther has much to be proud ofWingedPanther has much to be proud ofWingedPanther has much to be proud ofWingedPanther has much to be proud ofWingedPanther has much to be proud of
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 | Shareware
Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!
Reply With Quote
  #5 (permalink)  
Old 11-15-2009, 08:50 PM
chili5's Avatar
Code Slinger
 
Join Date: Mar 2008
Posts: 7,018
chili5 has a reputation beyond reputechili5 has a reputation beyond reputechili5 has a reputation beyond reputechili5 has a reputation beyond reputechili5 has a reputation beyond reputechili5 has a reputation beyond reputechili5 has a reputation beyond reputechili5 has a reputation beyond reputechili5 has a reputation beyond reputechili5 has a reputation beyond reputechili5 has a reputation beyond repute
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
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!
Reply With Quote
  #6 (permalink)  
Old 11-15-2009, 09:40 PM
BlaineSch's Avatar
Code Warrior
 
Join Date: Apr 2009
Location: Trapped in my own little world.
Age: 19
Posts: 2,169
BlaineSch is a glorious beacon of lightBlaineSch is a glorious beacon of lightBlaineSch is a glorious beacon of lightBlaineSch is a glorious beacon of lightBlaineSch is a glorious beacon of lightBlaineSch is a glorious beacon of light
Send a message via MSN to BlaineSch
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++.
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!
Reply With Quote
Reply



Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Char arrays in C outsid3r C Tutorials 4 07-28-2009 04:38 PM
C++ How to use arrays, and why they're important WingedPanther C Tutorials 9 12-10-2008 11:40 AM
What arrays and pointers have in common - or - Why arrays start at zero Kernel News 0 05-07-2008 08:36 AM
Dynamic Arrays Fedex C and C++ 3 12-02-2007 05:45 PM
Arrays clookid PHP Tutorials 1 01-11-2007 09:30 PM


All times are GMT -5. The time now is 11:00 AM.


vBulletin v3.8.0 ©2010, Jelsoft Enterprises Ltd.


no new posts

LinkBacks Enabled by vBSEO 3.1.0