Dense multidimensional arrays

There are several ways of declaring multidimensional arrays in D.

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?

Using std.range

std.range.chunks can be used to provide a 2-dimensional view of a flat (1-dimensional) buffer:

unittest
{
    // 2D array
    int cols = 3, rows = 2;
    auto buf = new int[rows * cols];
    auto view = buf.chunks(cols);

    // Now access view[row][column]:
    view[1][2] = 2;

    // `view` is not a copy:
    ++buf[];
    assert(view[1][2] == 3);

    // Horizontal slicing works as usual:
    ++view[1][];
    assert(view[1][2] == 4);

    // Vertical slicing can be done using `transversal`:
    view.transversal(2).each!((ref n) => ++n);
    assert(view[1][2] == 5);
}

This can be further combined with std.algorithm.iteration.map to allow 3 or more dimensions:

unittest
{
    // 3D array
    int cols = 2, rows = 3, layers = 4;
    auto buf = new int[cols * rows * layers];
    auto view = buf.chunks(rows * cols)
        .map!(layer => layer.chunks(cols));

    // Now access view[layer][row][column]:
    view[3][2][1] = 5;
}

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.

Using mir

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

Credits

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