Tuesday, October 11, 2011

Multi-dimensional arrays in C++11

What new can be said about multi-dimensional arrays in C++? As it turns out, quite a bit! With the advent of C++11, we get new standard library class std::array. We also get new language features, such as template aliases and variadic templates. So I'll talk about interesting ways in which they come together.

It all started with a simple question of how to define a multi-dimensional std::array. It is a great example of deceptively simple things. Are the following the two arrays identical except that one is native and the other one is std::array?

int native[3][4];
std::array<std::array<int, 3>, 4> arr;

No! They are not. In fact, arr is more like an int[4][3]. Note the difference in the array subscripts. The native array is an array of 3 elements where every element is itself an array of 4 integers. 3 rows and 4 columns. If you want a std::array with the same layout, what you really need is:

std::array<std::array<int, 4>, 3> arr;

That's quite annoying for two reasons. First of all, it is quite verbose. Think of three or higher dimensional arrays. It's just ugly. Worse yet, the array bounds must be spelled out in reverse order.

Fear not, help is on its way! Meet template aliases! It is a way of defining synonyms for other types including partially defined templates. With C++03 typedef, you must use a fully specialized template to create an alias. C++11 still has that restriction on typedefs but template aliases will let you create "typedefs" for template partial specializations. It is a C++11 solution for the Templated Typedef idiom. Lets try to write one for a two dimensional std::array.

template <class T, size_t ROW, size_t COL<
using Matrix = std::array<std::array<T, COL>, ROW>;
Matrix<float, 3, 4> mat;

This one is much nicer. Matrix is a template alias for a partial specialization of std::array. With that, defining a two dimensional matrix (mat) is really easy. Note that order of ROW and COL. An alias for two dimensional native array can also be defined similarly.

template <class T, size_t ROW, size_t COL>
using NativeMatrix = T[ROW][COL];
NativeMatrix<float, 3, 4> mat;

So far so good. Lets move on to multi-dimensional arrays. Using template aliases for arbitrary dimension arrays would need variadic templates. Unfortunately, it is not straightforward at all.

template <class T, size_t... DIMS>
using MultiDimArray = std::array<??? ...DIMS... ???>;
MultiDimArray<float, 3, 4, 5 , 6, 7> floats;

DIMS parameter pack can be expanded where a comma separated list is expected. However, multi-dimensional std::array definitions are hierarchical, which prevents straight-forward parameter pack expansion.

One way I could make it work was using a little meta-program.

template <class T, size_t I, size_t... J>
struct MultiDimArray
{
using Nested = typename MultiDimArray<T, J...>::type;
// typedef typename MultiDimArray<T, J...>::type Nested;
using type = std::array<Nested, I>;
// typedef std::array<Nested, I> type;
};

template <class T, size_t I>
struct MultiDimArray<T, I>
{
using type = std::array<T, I>;
// typedef std::array<T, I> type;
};

MultiDimArray<float, 3, 4, 5, 6, 7>::type floats;

MultiDimArray is a pair of meta-functions to compute nested type for multi-dimensional std::array. The most general MultiDimArray is a variadic template of unsigned integers to pass an arbitrary number of dimensions. The terminating MultiDimArray specialization defines the simplest case of single dimensional std::array. I'm using the "using" syntax instead of typedefs. The equivalent typedef are written in comments.

Similarly, MultiDimNative can also defined to create a native array of arbitrary dimensions.

template <class T, size_t I, size_t... J>
struct MultiDimNative
{
using Nested = typename MultiDimNative<T, J...>::type;
using type = Nested [I];
};

template <class T, size_t I>
struct MultiDimNative<T, I>
{
using type = T [I];
};

MultiDimNative<double, 3, 4, 5, 6, 7>::type doubles;

To make sure that the layout of all the arrays is the same I wrote a small test program.

template <class T, size_t I, size_t J>
union data
{
T native[I][J];
NativeMatrix<T, I, J> native_matrix;
Matrix<T, I, J> matrix;
typename MultiDimArray<T, I, J>::type multidim_array;
typename MultiDimNative<T, I, J>::type multidim_native;
};

template <class T>
void print(T & t, size_t rows, size_t columns)
{
for(size_t i = 0;i < rows; ++i)
{
for(size_t j = 0;j < columns; ++j)
printf("%d ", t[i][j]);

printf("\n");
}
printf("\n");
}
int main()
{
constexpr size_t I = 3;
constexpr size_t J = 4;

data<int, I, J> d;
size_t val = 0;

for(size_t i = 0;i < I; ++i)
{
for(size_t j = 0;j < J; ++j)
d.native[i][j] = val++;
}

print(d.native, I, J);
print(d.native_matrix, I, J);
print(d.matrix, I, J);
print(d.multidim_array, I, J);
print(d.multidim_native, I, J);

return 0;
}

This program defines a union of 5 different arrays, all of which have the same dimensions and layout. It populates a native two dimensional array and prints the contents using all other multi-dimensional arrays defined in the same union. As of today, only clang accepts this program.

That's it for now!