Skip to main content

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!

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.
Unknown 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
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
Unknown 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?
Unknown 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
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 '<'.
Unknown said…
I think your comment about the order of indicies being backwards also applies to declaring vectors like this:

vector(cols)>(rows)
Unknown said…
The "int[3][4]" allocates 12 consecutive elements in memory, which means that a regular stride takes me from one row to the next. Does your clever programming give me that? The initial "array of arrays" definitely does not.
Sumant said…
@Victor Not sure why you say that the storage is not contiguous. std::array<std::array<T,J>,I> is layout compatible with T[I][J]. It's contiguous in all the examples. The last program proves that. Am I misunderstanding?
Unknown said…
Sumant, you're a better C++ coder than I am so I don't entirely understand your code. Your last example shows that "T[i][j]" gives the right output, but does it show that the object is allocated as MxN consecutive numbers? What in your code guarantees that?
Sumant said…
Ohh! That's because I use a union. See union data. All 5 members of the union share the same storage space and layout.
harada57 said…
This comment has been removed by the author.

Popular Content

Unit Testing C++ Templates and Mock Injection Using Traits

Unit testing your template code comes up from time to time. (You test your templates, right?) Some templates are easy to test. No others. Sometimes it's not clear how to about injecting mock code into the template code that's under test. I've seen several reasons why code injection becomes challenging. Here I've outlined some examples below with roughly increasing code injection difficulty. Template accepts a type argument and an object of the same type by reference in constructor Template accepts a type argument. Makes a copy of the constructor argument or simply does not take one Template accepts a type argument and instantiates multiple interrelated templates without virtual functions Lets start with the easy ones. Template accepts a type argument and an object of the same type by reference in constructor This one appears straight-forward because the unit test simply instantiates the template under test with a mock type. Some assertion might be tested in

Covariance and Contravariance in C++ Standard Library

Covariance and Contravariance are concepts that come up often as you go deeper into generic programming. While designing a language that supports parametric polymorphism (e.g., templates in C++, generics in Java, C#), the language designer has a choice between Invariance, Covariance, and Contravariance when dealing with generic types. C++'s choice is "invariance". Let's look at an example. struct Vehicle {}; struct Car : Vehicle {}; std::vector<Vehicle *> vehicles; std::vector<Car *> cars; vehicles = cars; // Does not compile The above program does not compile because C++ templates are invariant. Of course, each time a C++ template is instantiated, the compiler creates a brand new type that uniquely represents that instantiation. Any other type to the same template creates another unique type that has nothing to do with the earlier one. Any two unrelated user-defined types in C++ can't be assigned to each-other by default. You have to provide a