Multidimensional Arrays and std::mdspan

In the beginner course, we introduced the concept of a multidimensional array (or vector), which we could use to represent more complex data structures.

For example, we could represent a 2D grid using an array of arrays:

1#include <vector>
2#include <iostream>
3
4int main(){
5  std::vector<std::vector<int>> Grid{
6    {
7      {1, 2, 3},
8      {4, 5, 6},
9      {7, 8, 9}
10    }};
11
12  std::cout << "Top Left: " << Grid[0][0];
13  std::cout << "\nBottom Right: " << Grid[2][2];
14}
15

1Top Left: 1
2Bottom Right: 9
3

There are a couple of problems with this approach. Firstly, we lose some capability to work with the collection as a whole. For example, we can no longer simply get the size of the collection (9, in this example) without doing some extra work. We’d need to iterate over every subarray and add all their sizes together.

Secondly, there is some performance overhead involved in using multidimensional arrays in this way. Working with 3 arrays of 3 elements is generally less efficient than working with a single array of 9 elements.

We could revert back to using a single array, and simply remember that this data structure is supposed to be a 3 by 3 grid:

1#include <vector>
2#include <iostream>
3
4int main(){
5  std::vector<int> Grid{
6    1, 2, 3,
7    4, 5, 6,
8    7, 8, 9
9  };
10
11  std::cout << "Top Left: " << Grid[0];
12  std::cout << "\nBottom Right: " << Grid[8];
13}
14

1Top Left: 1
2Bottom Right: 9
3

But, this then has the opposite problem. We can no longer work with our structure as a series of rows and columns. This is particularly problematic when that work is being done in a separate function, as we then also have to communicate the nature of the array to that function.

For example, a std::array<int, 12> could be a regular array of 12 integers, but it could also be a two-dimensional array such as a 6x2, 3x4, or 4x3 grid. It could even be a three-dimensional array, such as a 2x2x3 volume.

None of that is communicated through the type. When the type does not describe the type of data it’s referring to, that’s often a red flag that we have a problem.

These problems only compound when dealing with larger, more realistic examples. In most industries, we’ll often be working with arrays that can have millions of objects across 3 or more dimensions. Some machine-learning applications involve arrays with hundreds of dimensions. So, solving these problems can make our projects much easier to work with.

Multidimensional [] Operator

Note: The multidimensional [] operator is a recent addition to the language, added in C++23, and is not yet supported by all compilers.

A key component of being able to work with multidimensional arrays is the ability to pass multiple arguments to the [] operator.

For example, that might look like MyObject[x, y]. This has become possible since C++23

The following example shows a custom type implementing a basic multidimensional subscript operator:

1#include <iostream>
2
3class SomeType {
4public:
5  int operator[](int a, int b){
6    return a + b;
7  }
8};
9
10int main(){
11  SomeType SomeObject;
12  std::cout << "Result: " << SomeObject[2, 3];
13}
14

1Result: 5
2

Below, we show how we could start building a multidimensional array class using these ideas. In this example, it’s a class that stores a 3x3 matrix of integers by wrapping a one-dimensional array.

The process of mapping the two-dimensional arguments to a single index requires some maths. The offending line is highlighted below, but don’t worry if it doesn’t make sense - we’ll soon switch to using a standard library container to take care of this for us:

1#include <array>
2#include <iostream>
3
4class Grid {
5public:
6  int operator[](size_t Row, size_t Col){
7    return Data[Row * 3 + Col % 3];
8  }
9
10private:
11  std::array<int, 9> Data{
12    1, 2, 3,
13    4, 5, 6,
14    7, 8, 9
15  };
16};
17
18int main(){
19  Grid MyGrid;
20
21  std::cout
22    << "Top Left: " << MyGrid[0, 0]
23    << "\nBottom Right: " << MyGrid[2, 2];
24}
25

1Top Left: 1
2Bottom Right: 9
3

We could extend this idea, with the help of template parameters, to create a generalized form of multi-dimensional arrays that could be used in our projects. But, there are third-party libraries that we could use that have already done this.

As of C++23, we’re starting to see standard library classes be introduced to solve these problems too, starting with std::mdspan.

std::mdspan

Note: The standard library’s mdspan class is a recent addition to the language, added in C++23, and is not yet available in all compilers.

The standard library’s mdspan is, at its core, similar to the regular span, which we covered in the previous lesson. It provides a “view” of an underlying array.

It is performant to create and widely compatible with different array types, including C-style arrays, std::array, and std::vector

The key difference is, as we might expect, the mdspan is designed to create views that we can interact with as if we were working with a multidimensional array.

It is a template class that has four template parameters - two required, and two optional. We’ll discuss these template parameters in more detail a little later.

For now, let's just use class template argument deduction to show a basic example.

In the following code, we create a std::mdspan that views our 6-element array as a 2x3 matrix:

1#include <mdspan>
2#include <iostream>
3
4int main() {
5  std::array Array{
6    1, 2, 3,
7    4, 5, 6
8  };
9
10  std::mdspan Span{Array.data(), 2, 3};
11}
12

The first argument to the constructor is a pointer to where the source array begins in memory. With a C-style array, that is just the value of the object. For std::array and std::vector, we can get this pointer using the data() method.

After the pointer, we then have a variable number of additional arguments that represent the shape of our multidimensional view.

The number of additional arguments represents the number of dimensions our view will have, whilst the individual value of each argument represents the size of that dimension.

Above, we’re creating a two-dimensional view, so we provide two additional arguments. Their values are 2 and 3, so we’re creating a 2x3 span.

Access to elements is given through the [] operator, passing as many arguments as we have dimensions. In this example, we have two dimensions, so every use of the [] will receive two arguments:

1#include <array>
2#include <mdspan>
3#include <iostream>
4
5int main() {
6  std::array Array{
7    1, 2, 3,
8    4, 5, 6
9  };
10
11  std::mdspan Span{Array.data(), 2, 3};
12
13  std::cout << "Top Left: " << Span[0, 0];
14  std::cout << "\nBottom Right: " << Span[1, 2];
15}
16

1Top Left: 1
2Bottom Right: 6
3

std::mdspan Size and Rank

The total number of elements the mdspan is viewing is available through the size() method, or empty() if we specifically want to check if the size is 0.

We can also get the rank of the span (i.e., how many dimensions it has) using the rank() method.

1#include <array>
2#include <mdspan>
3#include <iostream>
4
5int main() {
6  std::array Array{
7    1, 2, 3,
8    4, 5, 6
9  };
10
11  std::mdspan Span{Array.data(), 2, 3};
12
13  std::cout << "Size: " << Span.size();
14  std::cout << "\nRank: " << Span.rank();
15}
16

1Size: 6
2Rank: 2
3

Getting the Extent of a Dimension

The extent (or size) of any dimension in a mdspan is available through the extent() method, passing in the index of the dimension we want to find. Similar to array indices, counting starts at 0, so the size of the first dimension is available at extent(0).

When we create a 2x3 view, extent(0) will return 2, and extent(1) will return 3:

1#include <array>
2#include <mdspan>
3#include <iostream>
4
5int main() {
6  std::array Array{
7    1, 2, 3,
8    4, 5, 6,
9  };
10
11  std::mdspan Span{Array.data(), 2, 3};
12
13  std::cout << "Rows: " << Span.extent(0);
14  std::cout << "\nCols: " << Span.extent(1);
15}
16

1Rows: 2
2Cols: 3
3

Iterating through std::mdspan

By using the extent method, we can set up iterations that navigate through our array in a way that is aware of its dimensionality:

1#include <array>
2#include <mdspan>
3#include <iostream>
4
5int main() {
6  std::array Array{
7    1, 2, 3,
8    4, 5, 6,
9  };
10
11  std::mdspan Span{Array.data(), 2, 3};
12
13std::cout << "Left Column: ";
14for (size_t i{0}; i < Span.extent(0); ++i)
15  std::cout << Span[i, 0] << ", ";
16
17std::cout << "\nTop Row: ";
18for (size_t i{0}; i < Span.extent(1); ++i)
19  std::cout << Span[0, i] << ", ";
20
21std::cout << "\nEverything: ";
22  for (size_t i{0}; i < Span.extent(0); ++i)
23    for (size_t j{0}; j < Span.extent(1); ++j)
24      std::cout << Span[i, j] << ", ";
25}
26

1Left Column: 1, 4, 
2Top Row: 1, 2, 3, 
3Everything: 1, 2, 3, 4, 5, 6,
4

std::mdspan Template Parameters

Previously, we used class template argument deduction (CTAD) to create our std::mdspan without providing the template parameters.

Let's discuss what those template parameters are now. There are four in total:

1. The type of data in the array
2. An extents type, documenting the shape of the std::mdspan
3. An optional layout policy, which allows us to customize the process whereby the multiple indices passed to the span’s [] operator get converted to the single, one-dimensional index that is used by the underlying array
4. An optional accessor policy, which allows us to customize how the single index returned from the LayoutPolicy is used to generate the return value of the span’s [] operator.

The first template parameter is pretty simple - it’s just the data type of each element in the view. This will be the same as the data type used by the underlying array. For example, if our array is storing ints, our span will be viewing ints too.

The extents argument is what we’ll spend the rest of this lesson covering.

The final two template parameters are optional and will be covered in a future lesson.

std::extents

The std::extents template class is how we define the shape of our multidimensional spans. The first template parameter allows us to customize what type we want to use as the index of the span. This will be an integer type, such as a size_t.

We then can provide a variable number of additional parameters. Similar to the arguments passed to the mdspan constructor, the number of additional parameters we pass will become the number of dimensions in our span. The value of each of the arguments will be the size of that dimension.

Below, we recreate our 2x3 matrix, but this time we explicitly provide the template parameters:

1#include <array>
2#include <mdspan>
3
4int main() {
5  std::array Array{
6    1, 2, 3,
7    4, 5, 6
8  };
9
10  using Extents = std::extents<size_t, 2, 3>;
11
12  std::mdspan<int, Extents> Span{Array.data()};
13}
14

Note, that we are no longer providing the dimension parameters to the mdspan constructor. They are now instead provided as template parameters to the std::extents template class at compile time.

If the extent of a dimension is not known at compile time, we can then specify it as a dynamic extent.

Dynamic Extents

Within the template parameters of std::extents, we can specify dimensions as having a dynamic extent, that is only known at run time. We do this by passing the std::dynamic_extent token in the appropriate position.

Below, we reference an extent type where the number of rows is known at compile time (2, in this example) but the number of columns is dynamic, as it is not known until run time:

1std::extents<size_t, 2, std::dynamic_extent>;
2

At runtime, we need to provide the value for any dynamic extents by passing arguments to the mdspan constructor. In the following example, we pass 3, thereby again recreating our 2x3 matrix, this time by combining static and dynamic extents:

1#include <array>
2#include <mdspan>
3
4int main(){
5  std::array Array{
6    1, 2, 3,
7    4, 5, 6
8  };
9
10  using Extents = std::extents<
11    size_t, 2, std::dynamic_extent
12  >;
13
14  std::mdspan<int, Extents> Span{
15    Array.data(), 3};
16}
17

std::dextents

Where we want the extent of every dimension to be dynamic, the std::dextents template class provides a more succinct syntax. It accepts two template parameters - the type of index to use, and the number of dimensions we want.

The following example creates a three-dimensional span, where the extent of every dimension is dynamically determined at run time.

1#include <array>
2#include <mdspan>
3#include <iostream>
4
5size_t GetDynamicValue(){ return 2; }
6
7int main(){
8  std::array Array{
9    1, 2, 3, 4,
10    5, 6, 7, 8
11  };
12
13  using Extents = std::dextents<size_t, 3>;
14
15  std::mdspan<int, Extents> Span{
16    Array.data(), GetDynamicValue(),
17    GetDynamicValue(), GetDynamicValue()};
18
19  std::cout << "Dimensions: " << Span.rank();
20}
21

1Dimensions: 3
2