Using Pointers to Create Multidimensional Arrays

[Sw07fSEw]

I've been trying to increase my understanding of pointers by doing examples using multidimensional arrays. Mentally, I have been trying to visualize multidimensional arrays like 'int table[3][5]' in the following manner:

[0][0][0][0][0]
[1][1][1][1][1]
[2][2][x][2][2]

Therefore if I wanted to access [x], I would have to traverse across two rows entirely and then move across 2 more elements in the third row to access [x]. The pointer arithmetic would look like something like *(table + 2 * 5 + 2) to access that element.

However, I've been having trouble relating this to dynamic memory and multidimensional arrays. From my understanding, we need to use pointers to pointers to dynamically allocate multidimensional arrays. So the first step would be to create a pointer to a pointer, such as int **table. I would think that the next step would be to allocate an array of pointers.

table = new int*[a]

This is where I'm getting confused. What I think is happening, is that 'table' is being assigned the address of an array of pointers that contains 'a' # of elements. I understand from pointer arithmetic that all multidimensional arrays need the last size included. (i.e. int table[][9]) because the 'width' or last size is essential for the arithmetic to work.

When I declare table = new int*[a] , what 'dimension' does this refer too in my table above? Is it the width (# columns), or height (# rows)? If I have a pointer that points to an array of 3 pointers, does that mean the 'width' of my two-dimensional array is 3? Or does it mean I have 3 'rows', with the width yet to be defined?

I think the number of elements in the array of pointers, refers to the height, but I'm not certain.

[Austin J]

Ok, understand that in conceptual grids, what's "width" and what's "height" can be considered somewhat arbitrary. You actually quite easily represent a 2D grid with a 1-dimensional array ( For serious work I would recommend this actually, Disch has an awesome article about this: http://www.cplusplus.com/forum/articles/17108/ )

When you create a multidimensional array in the way you describe, here's in a nutshell what you're really doing.

You first have what I think of as the "base" pointer. This pointer allocates an array of all the other pointers, nothing more. Calling this where you define "rows" or "columns" is arbitrary. You can think of it either way.

The elements of this dynamically allocated array of pointers can all be used to allocate their own arrays, and this is where you actually get your interesting data stored.

So, to try to illustrate my point, with this style of MD array, I'll show a visualization two ways.

* = pointer
d = variable/datum

3x3 array - Visualization 1

*0 d0 d1 d2
*1 d0 d1 d2
*2 d0 d1 d2

3x3 array - Visualization 2

*0   *1    *2
d0   d0   d0
d1   d1   d1
d2   d2   d2

Both of these visualizations are essentially the same when it comes to how you access them.

This is just a visualization though. How are these arrays actually stored in memory?

Well, I'll try explain ( note: If anybody see's something wrong please correct me, but this is my understanding of the subject )

First off, that "base" pointer I mentioned allocated an array of pointers, this array of pointers will be contiguous as you probably already know. The significance of this is that the subarrays themselves are also going to be contiguous, hence actually leading all of the data with this MD array to be in one region of the memory, itself contigous. So lets go back to the illustrations. What does it look like in a one-dimensional representation?

*0 d0 d1 d2 - *1 d0 d1 d2 - *2 d0 d1 d2

So, what if we want say, foo[1][2] , from this array, and we want to set it to 4?
(We'll use the name foo now)

*(*(foo + 1) + 2) = 4;

General formula for converting foo[a][b]

*(*(foo + a) + b) = ?;