Dense multidimensional arrays

There are several ways of declaring multidimensional arrays in D.

Multidimensional arrays and ranges

mir-algorithm library provides multidimensional shell over pointers, random access iterators, arrays, and random access ranges. Multidimensional arrays are located in mir.ndslice package.

import mir.ndslice;

auto slice = slice!int(5, 6, 7);
assert(slice.length == 5);
assert(slice.elementsCount == 5 * 6 * 7);
static assert(is(typeof(slice) == Slice!(Contiguous, [3], int*)));

slice[1, 3, 4] = 5;

auto matrix = slice[1];
matrix = slice.front; // Random Access Range API

auto matrix2 = slice.front!1; // Multidimensional Random Access Range API

Jagged arrays

The simplest way is to use an array of arrays:

int[][] matrix = [
    [ 1, 2, 3 ],
    [ 4, 5, 6 ],
    [ 7, 8, 9 ]
];
assert(matrix[0][0] == 1);
assert(matrix[1][1] == 5);

This creates a so-called jagged array, because each element of the outer array can have different lengths:

int[][] matrix = [
    [ 1, 2, 3 ],
    [ 4, 5, 6, 7, 8 ], // this is valid
    [ 9, 10, 11 ]
];

However, this approach is not so memory-efficient, because the outer array is a separate block of memory containing references to the inner arrays. Array lookups require multiple indirections, so there is a slight performance hit.

Note that with the "jagged" array scheme, the "2nd dimensions" arrays may either all be allocated individually, or simply be slices of a single very big 1D array. Both schemes are valid.

A dynamic rectangular jagged array may be dynamically allocated at once using the multi-dim allocation syntax:

//Allocates a dynamic array containing
//  2 dynamic arrays containing
//    5 ints
int[][] matrix = new int[][](5, 2);

Note that in this example, the dimensions don't need to be known at compile time. Also note that this works for any amount of dimensions.

Static arrays

D recognizes the inefficiency of jagged arrays, so when all the dimensions of the array are known at compile-time, the array is automatically implemented as a dense array: the elements are packed together into a single memory block, and array access requires only a single indexed lookup:

// This is a dense array
int[3][3] matrix = [
    [ 1, 2, 3 ],
    [ 4, 5, 6 ],
    [ 7, 8, 9 ]
];

Dense arrays are fast and memory-efficient. But it requires that all array dimensions be known at compile-time, that is, it must be a static array. But what about dynamic arrays?

Dense dynamic arrays

There is a way to make multidimensional dynamic arrays dense, if only the last dimension needs to be variable, or if the array is just too big to fit on stack:

enum columns = 100;
int rows = 100;
double[columns][] gridInfo = new double[columns][](rows);

This creates a multidimensional dynamic array with dense storage: all the array elements are contiguous in memory.

Credits

The idiom for creating dense multidimensional dynamic arrays was first posted to the D newsgroup by User:Monarchdodra.