, dev
Nested Initializer Lists for Multidimensional Arrays
With the release of the template metaprogramming library m3ta, I’ve included in the documentation a few examples on how some utilities might prove useful.
I find one example particularly worth sharing here because I’ve been stuck on it for some times and thought that it might be useful to someone else. That’s the nested initializers trick.
But what exactly are those initializer thingies?
Initializer lists are a way to initialise objects using a curly braces syntax {} that encloses a list of values such as {4, 9, 8, 5}. Their nested version allows for more structured syntaxes like {{4, 9}, {8, 5}}.
Since they are well suited to define arrays, let’s see how they could be used in the context of a custom multidimensional array class that would mimic the curly braces initialization properties of the built-in arrays of C/C++.
The Built-In Curly Braces Syntax
The C & C++ languages have always provided a special curly braces syntax for the built-in arrays that allowed to define all their elements at once.
// Single curly braces syntax.
int array[3][2] = {
0, 1,
2, 3,
4, 5
};
On top of initialising the content of the array with the values passed, this syntax also comes with two neat features for the corner cases. Firstly, any element in excess is signalled with an error at compile time, and secondly, the end of the array is filled with zeroes if less values than expected are provided.
The nested flavour of this syntax allows to write as many levels of nested curly braces as there are of dimensions defined by the array.
// Nested curly braces syntax.
// 2-dimensional array -> 2 levels of braces
int array[3][2] = {
{0, 1},
{2, 3},
{4, 5}
};
The difference is not only aesthetic. This last version helps localising the behaviour of the “neat features”. Namely, it provides an error message with the precise location of any set of braces defining elements in excess, and likewise fills with zeroes the inner sets of braces that have some values missing.
Otherwise, and if provided with the expected number of values, both syntaxes produce the exact same content.
Curly Braces Initializers for All!
Now that the behaviours that needs to be reproduced are known, let’s get onto it—but not so fast! If you are not using C++11 or above, you are doomed.
Indeed, until C++11 this convenient syntax wasn’t available for user-defined types. It’s the addition of std::initializer_list that changed the deal.
If you are part of the cool kids, enabling the curly braces initializers for a type is done by simply defining a constructor taking a std::initializer_list argument.
In the case of the single curly braces syntax, the implementation of the constructor can actually be quite concise.
template<typename T, std::size_t ... T_dimensions>
class MultidimensionalArray
{
public:
MultidimensionalArray(std::initializer_list<T> values)
{
std::copy(values.begin(), values.end(), _data.begin());
}
private:
std::array<T, size()> _data;
};
This implementation wouldn’t take care of the corner cases though—what if the user writes 2 or 4 values when only 3 are expected?
What I previously called the “neat features” that are shipped with the built-in arrays are not a big deal to be implemented here.
template<typename T, std::size_t ... T_dimensions>
class MultidimensionalArray
{
static_assert(sizeof ... (T_dimensions) > 0,
"At least one dimension needs to be defined.");
public:
static constexpr std::size_t
size()
{
return m3ta::product(T_dimensions ...);
}
MultidimensionalArray(std::initializer_list<T> values)
{
if (values.size() > size()) {
std::ostringstream message;
message << "Elements in excess: "
<< "expected " << size() << ", "
<< "got " << values.size() << ".";
throw std::invalid_argument(message.str());
}
std::copy(values.begin(), values.end(), _data.begin());
if (values.size() < size()) {
std::size_t count = std::min(size(), values.size());
std::uninitialized_fill(
_data.begin() + count,
_data.end(),
static_cast<T>(0)
);
}
}
using Iterator = typename std::array<T, size()>::iterator;
private:
std::array<T, size()> _data;
};
Once again, only the single curly braces syntax is defined here, but otherwise the same “neat features” as the built-in arrays are provided.
MultidimensionalArray<float, 3, 2> array = {
0, 1,
2, 3,
4, 5
};
Implementing the nested curly braces variant is slightly more involved.
Firstly, a new constructor needs to be defined to accept nested initializer lists, that is for example a std::initializer_list<std::initializer_list<float>> in the case of a 2-dimensional array.
Creating a such type in a generic fashion isn’t a problem, as demonstrated with the m3ta::NestedInitializerLists trait.
But one thing to know is that it isn’t possible to directly iterate over all the values held within nested std::initializer_lists—pointers to the next deeper nested level are returned until the very last level is reached, at which point the values can finally be accessed.
m3ta::NestedInitializerListsT<float, 3> values = {
{
{0, 1},
{2, 3}
},
{
{4, 5},
{6, 7}
}
};
for (auto secondLevel : values) {
for (auto thirdLevel : secondLevel) {
for (auto value : thirdLevel) {
// Do something with the value.
}
}
}
Nesting as many for-loops as there are of levels is not something that can be done generically.
Iterating over Nested Initializer Lists
I initially tried to either flatten the nested lists into a linear sequence of elements or to find a trick based on std::array to automatically inherit its properties, but nothing gave me both the exact same syntax as the built-in arrays with the “neat features” that I wanted.
The solution had to pass by a recursive approach.
The values to recurse over are the number of elements per level of the nested initializer lists—that is, its shape.
The idea kinda goes like this: from the first level, check if the number of elements is as expected, recurse over the second level, then fill the missing elements with zeroes, and repeat until the last level is reached. At this point, do something with the values.
template<typename T, std::size_t ... T_shape>
struct NestedInitializerListsProcessor;
// Recursive part.
template<typename T, std::size_t T_first, std::size_t ... T_others>
struct NestedInitializerListsProcessor<T, T_first, T_others ...>
{
using NestedInitializerLists =
m3ta::NestedInitializerListsT<T, 1 + sizeof ... (T_others)>;
template<typename T_Function>
static void
process(NestedInitializerLists values, T_Function function)
{
if (values.size() > T_first) {
throw std::invalid_argument(
"Elements in excess within the initilizer list."
);
}
for (auto nested : values) {
NestedInitializerListsProcessor<T, T_others ...>::
process(nested, function);
}
if (values.size() < T_first) {
std::size_t count =
m3ta::Product<std::size_t, T_others ...>::value
* (T_first - values.size());
while (count-- > 0) {
function(static_cast<T>(0));
}
}
}
};
// Last level.
template<typename T, std::size_t T_last>
struct NestedInitializerListsProcessor<T, T_last>
{
using InitializerList = m3ta::NestedInitializerListsT<T, 1>;
template<typename T_Function>
static void
process(InitializerList values, T_Function function)
{
if (values.size() > T_last) {
std::ostringstream message;
message << "Elements in excess: "
<< "expected " << T_last << ", "
<< "got " << values.size() << ".";
throw std::invalid_argument(message.str());
}
std::for_each(values.begin(), values.end(), function);
if (values.size() < T_last) {
std::size_t count = T_last - values.size();
while (count-- > 0) {
function(static_cast<T>(0));
}
}
}
};
For more genericity, this NestedInitializerListsProcessor helper takes a function that it applies on each element iterated over. This way, the caller—the MultidimensionalArray constructors here—can decide what to do with those values.
The first template specialisation is the recursive part while the one with the T_last parameter is the equivalent of what was previously implemented within the MultidimensionalArray constructor for the single curly braces case.
Putting All the Things into the Multidimensional Array Class
Now that accessing the values of nested initializer lists is dealt with, the MultidimensionalArray class can define the constructor for the nested curly braces.
template<typename T, std::size_t ... T_dimensions>
class MultidimensionalArray
{
static_assert(sizeof ... (T_dimensions) > 0,
"At least one dimension needs to be defined.");
public:
static constexpr std::size_t
size()
{
return m3ta::product(T_dimensions ...);
}
// Single curly braces syntax.
MultidimensionalArray(m3ta::NestedInitializerListsT<T, 1> values)
{
initialize<size()>(values);
}
using NestedInitializerLists =
m3ta::NestedInitializerListsT<T, sizeof ... (T_dimensions)>;
// Nested curly braces syntax.
MultidimensionalArray(NestedInitializerLists values)
{
initialize<T_dimensions ...>(values);
}
private:
template<std::size_t ... T_shape, typename T_NestedInitializerLists>
void
initialize(T_NestedInitializerLists values)
{
auto iterator = _data.begin();
NestedInitializerListsProcessor<T, T_shape ...>::
process(
values,
[&iterator](T value) { *(iterator++) = value; }
);
}
std::array<T, size()> _data;
};
The private method initialize() defines a new template parameter T_shape which refers to the shape to expect from the initializer lists to iterate over—that is the number of values in the case of the single curly braces syntax, and the dimensions of the array for the nested syntax.
It then defines a lambda function which simply copies each value onto the _data member.
The MultidimensionalArray class is now almost good to go—the nested curly braces constructor needs to be disabled when the array contains a single dimension to avoid ambiguous calls, and a pair of begin()/end() methods need to be added to at least allow a sort of iteration. I’ll leave these as an exercise for the reader—if there is any reader left at this point? Or you can simply get the full code on this Gist.
Additional Notes
Admittedly the error messages could be improved but will hardly get nearly as good as what the compilers can generate for the built-in arrays.
Also, the conditions for these error messages are checked at run-time when, according to this question of mine on StackOverflow, it should have been possible to retrieve the size of a std::initializer_list at compile time and turn the whole check + exception combo into a simple static_assert. Maybe an oversight from the C++ committee?
Don’t be shy and follow me on GitHub if you want to check out the latest code that I’m sharing—it won’t always make it into a blog post.
