What is the purpose of multidimensional arrays? [closed]

Question

I have a few questions about multidimensional arrays. I understand how to allocate memory for them, but I don't see why there are needed (Other than to make things more readable).

The [] operator for the array is overloaded, right? So, why can't a single block of memory be allocated and access be granted by, 1dArray[i*nInRow][offset]?

Are there further performance gains by using an array in multiple dimensions? Also, when memory is dynamically allocated for a 2d array, are they stored in contiguous locations, or are they scattered around the heap? When the data is requested, can I assume that everything is pulled from memory as a block?

Most of the information that I have seen has just explained syntax. Any answers or suggested reading would be great.

The main purpose of multidimensional arrays in C++ is to confuse beginners and generate an endless stream of questions about how to allocate them dynamically, about how to delete them, or why they can't be converted to pointers to pointers. — R. Martinho Fernandes
– R. Martinho Fernandes, Commented Nov 7, 2012 at 16:29

Lightness Races in Orbit · Accepted Answer · 2012-11-07 18:01:11Z

The [] operator for the array is overloaded, right? So, why can't a single block of memory be allocated and access be granted by, 1dArray[i*nInRow][offset]?

It can, and in fact I would recommend this in the general case.

Are there further performance gains by using an array in multiple dimensions?

Not really. Depending on your layout you could optimize cache hits, but then precisely the same is true with the flattened 1D array. The memory layout between the two is (usually) precisely the same. The only difference is the semantic type of the array and the fact that you now have to implement the 2D element lookup yourself.

Also, when memory is dynamically allocated for a 2d array, are they stored in contiguous locations, or are they scattered around the heap? When the data is requested, can I assume that everything is pulled from memory as a block?

Arrays are always contiguous.

You should be careful though that you're actually allocating a 2D array. Some people write int** ptr = new int*[2] then allocate each "sub-array" manually and think that they have a 2D array. They do not. They have an array of pointers, and that's when you get your "scattered" layout. Your 2D array is int (*ptr)[3] = new int[2][3];.

For the last point: Yes, an array is contiguous. In this case, that means: An array of pointers to arrays is contiguous in that the pointers are contiguous, but not (as OP appears to ask) in that the inner arrays are contiguous.
@delnan: Who's asking about arrays of pointers to arrays? You're the first person to mention those.
"Multidimensional array" is overloaded (as other answers explain). You assume the "it's all one big blob, which is logically subdivided" (which is what T a[n][m] ...; declares). The other interpretation, which is also called multi dimensional array, is a jagged array.
@delnan: I would never call a jagged array a multi-dimensional array, for the simple reason that it isn't one.

Aki Suihkonen · Accepted Answer · 2012-11-07 16:31:30Z

First at all, there a multidimensional problems. Secondly, if the multidimensional problem is 'sparse' it doesn't make sense to allocate 99*99*99*99*...*99 elements, but only pointers to next level structures, which are hidden by the clever syntax array[n][i][j][k]...

Virtual memory and page tables for example operate that way in modern OS's and CPUs.

David Grayson · Accepted Answer · 2012-11-07 16:31:35Z

There are two types of 2d arrays:

1) the kind where all the memory is in one big block, and

2) the kind where every row (or every column) is contiguous but the individual rows are scattered around, and you have an array of pointers to point to each row.

Type #2 has better performance in case you want to do certain things like swapping rows, because all you have to do is swap two pointers.

@delnan I wouldn't call it a jagged array unless the row lengths were different.
@Rook Once you use that structure, it's possible for them to differ. And if they cannot ever differ, there's no reason to do this except if your language/library makes one much more convenient than the other.

Collectives™ on Stack Overflow

What is the purpose of multidimensional arrays? [closed]

3 Answers 3

9 Comments

Comments

3 Comments

Linked

Hot Network Questions