[C++]Contiguous allocation of 2-D arrays

In college, my professors always used this method for creating a dynamic 2-D array in C++:

int** matrix;

matrix = new int*[num_rows];

for(int i = 0; i < num_rows; i++) {
  matrix[i] = new int[num_cols];
}

//matrix is now allocated, but contains garbage data

For brevity I'll call this way the "traditional" way of allocating a 2-dimensional array.

The idea is pretty simple - C++ doesn't have true support for multi-dimensional arrays, so you instead allocate an array of pointers, with each pointer pointing to an array of integers. This is one of the quickest and intuitive ways to setup a 2-D array, as we can use the subscript operator to access data in the array:

int example = matrix[2][3]; //access the element in the 2nd row, third column

It turns out there's a slightly better, although less intuitive way of creating multi-dimensional arrays dynamically.

What's wrong with the method above?

One issue with the above method is how memory is allocated to the array. C++'s new/new[] operator is guaranteed to allocate a contiguous block of memory to whatever is being pointed to. For example:

int* array;

array = new int[20];

Assuming that an int is 4 bytes, and assuming array is located at 0x8000 in memory, then array[1] will be at 0x8004, array[2] will be at 0x8008, array[3] at 0x800C, etc.

What C++ does not guarantee is contiguous memory allocation between sequential new/new[] operator usage. What this means for our "traditional" method is that the arrays we're allocating in the for loop may not be contiguous to each other, e.g. If matrix was a 2x4 array, then matrix[0] could be at address 0x8000, while matrix[1] could be at 0x8010.. or matrix[1] could be at 0x2048. There's no guarantee. Ideally, we would want all arrays to be contiguous to each other in memory, as that would improve cache locality, which should give us better performance.

One technique to get around this issue is to allocate the 2-D array as a one-dimensional array:

int* matrix;

matrix = new int[num_cols * num_rows];

//matrix is now allocated, but contains garbage data

But this has the obvious problem of breaking our usage of the subscript operator to access the array like a matrix, instead forcing us to do something like:

//matrix[x][y] no longer works with this method, so we have to use:

int index(int row, int col) {
  return row + num_rows * col;
}

int example = matrix[index(x, y)];

Which is not ideal, since using it is less intuitive than the "traditional" method. And if I had to choose between the two options for allocating a 2-D array, I would never choose this one unless I was forced to. I'm of the opinion that using a structure should be as simple as reasonably possible - creating the structure can be complex as long as the tradeoff is understandable.

Going off-tangent, allocating a 2-D array like the method above is actually pretty common. National Instrument's LabVIEW allocates memory for multi-dimensional arrays like the above code snippet, as an example.

Another issue with the "traditional" method deals with a limitation of C/C++. when interacting with other languages. Languages such as C# have better support for multi-dimensional arrays, so when a 2-D array is created it is guaranteed that all elements in the array are contiguous. This can cause problems with sending multi-dimensional arrays from C/C++ when sending arrays to these languages, and it just so happens that the best way of dealing with most of these problems is to allocate the array in 1-D, like the example above.

The goal is to dynamically create a 2-D array that allows for the subscript operator usage of the "traditional" method, while guaranteeing that all elements in the array are contiguous in memory.

A better, less intuitive way of creating 2-dimensional arrays dynamically

int** matrix;

matrix = new int*[num_rows];
matrix[0] = new int[num_rows * num_cols];

for(int i = 1; i < num_rows; i++) {
  matrix[i] = matrix[i-1] + num_cols;
}

//matrix is now allocated, but contains garbage data

This looks complex, but it's surprisingly understandable once you understand what's going on. The idea is that we allocate memory for an array of pointers, of size num_rows. We then allocate memory for the first pointer's array, with length num_rows*num_cols - the number of elements we need for the matrix. The other pointers are then assigned positions in the first pointer's array, giving the appearance of an array of pointers that point to different arrays, but not the structure of one.

As expected, matrix[0] now points to the entire 2-D array, not just the first row. This has a side-effect of allowing us to interact with the array in the first two methods:

//we can now access matrix[x][y] using

int example1 = matrix[x][y];

//or, since matrix[0] points to the entire array,

int example2 = matrix[0][x + num_rows * y];

Which allows you to send arrays between languages (or functions) as 1-D arrays.

Note: The pointers are not guaranteed to be contiguous with the array, since they are created using two different new[] operators. But this is probably the best you're going to get without using a std collection or third-party solution.

Creating higher dimensional arrays using this method can be done using the same principles, and are left as an exercise.