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!

17 comments:

Ralph Zhang said...

That's quite interesting, but what compiler are you using? Gcc doesn't seem to support that even in 4.7

Sumant said...

I'm using clang.

fahad munir said...

Sumant its a good blog for beginners

im also a beginner
its my blog
http://fahad-cprogramming.blogspot.com

i followed kindly follow back to my blog thanks

xander345 said...

if you like c++ you can compile it online here: http://codecompiler.info/

32, 64 - windows & Linux - and more programming languages

Basmah said...

Dear Sumant,
I am a beginner in C++. I want to implement a grid file for records which may have 1-32 dimensions. For 32-dimensions how can I declare arrays. Please help.

Basmah said...

Dear Mr. Sumant,

Would you please help to declare 32-dimension arrays or any structure which can be used easily for direct access for 1-32 dimension data. I want to build a grid file system for direct access.

Anonymous said...

I thought it was going to be some boring old post, but it really compensated for my time. I will post a link to this page on my blog. I am sure my visitors will find that very useful.
best train institute in jaipur

sas said...

It amazing

Note: it works using GCC 4.7 on windows but you need to add the option
-std=c++0x

Dear Sumant did you manage to make the varidic template solution work?
I test it on GCC 4.7 It does not work

thanks

Anonymous said...

You can make it cleaner with alias:

template
struct GetMultiDimArray
{
using type = std::array::type, d1>;
};

template
struct GetMultiDimArray
{
using type = std::array, d1>;
};

template
using MultiDimArray = typename GetMultiDimArray::type;

// Usage:
MultiDimArray mdarr {1, 2, 3, 4, 5, 6};

sse said...

Thank you very much for posting and sharing this great article. It is so interesting. I want to know some other information about this site. So please give me this news quickly. I always will be aware of you. army combat boots

sse said...

No doubt this is often a wonderful post I got plenty of data when reading smart luck. Theme of web log is superb there's nearly everything to scan, sensible post.... Brighton Tiles

Jatinder Singh said...
This comment has been removed by the author.
Anonymous said...

http://cplusplus-in.blogspot.com/

Sayeed said...

Thanks Sumant, its a useful blog for the beginner. but how do i download and install clanng?

felix sander said...

I am glad to found such useful post. I really increased my knowledge after read your post which will be beneficial for me.
www.easywritinghelp.com

Holiday Packages to Mecca said...

This is true that without c++ no one can be a good developer because this language is the key of programming.

Anonymous said...

hi, thanks for the post, but you've syntax error in the template at the end instead of '>' you wrote '<'.