c++ - c++11 constexpr flatten list of std::array into array

Question

I am beginning with c++11, constexpr and template metaprogramming seems a nice way to save scarce ram on tiny microcontroler.

Is there a way to write a template to flatten a list of constexpr array, what I need is a way to do :

constexpr std::array<int, 3> a1 = {1,2,3};
constexpr std::array<int, 2> a2 = {4,5};
constexpr auto a3 = make_flattened_array (a1,a2);

I use gcc 4.8.4 (arm-none-eabi), and can compile with std=c++11 or c++1y option if it is needed.

Answer 1

Notice - I understood your question as follows: you want to join those two arrays and flatten the result into a single, new array containing the concatenation of their elements.

You can accomplish your goal with three C++11+ concepts:

1. Variadic templates
2. constexpr expressions
3. Parameter pack

You start by creating a template (an empty shell) to start designing your recursive-fashion list flattening function:

template<unsigned N1, unsigned N2>
constexpr std::array<int, N1+N2> concat(const std::array<int, N1>& a1, const std::array<int, N2>& a2){
  // TODO
}

so far so good: the constexpr specifier will hint the compiler to compile-time evaluate that function each time it can.

Now for the interesting part: std::array has (since c++1y) a constexpr overload for the operator[], this means you can write something like

template<unsigned N1, unsigned N2>
constexpr std::array<int, N1+N2> concat(const std::array<int, N1>& a1, const std::array<int, N2>& a2){
  return std::array<int,N1+N2>{a1[0],a1[1],a1[2],a2[0],a2[1]};
}

(notice the aggregate-initialization to initialize the object from a series of integer values)

Obviously manually hard-coding all the index accesses to the values of the two arrays is no better than just declaring the concatenated array itself. The concept that will save the day is the following: Parameter Packs. A template parameter pack is a template parameter that accepts 0 or more template arguments. A template with at least one parameter pack is called variadic template.

The cool thing is the ability of expanding the parameter pack into specified locations like:

#include <iostream>
#include <array>

template<unsigned... Num>
std::array<int, 5> function(const std::array<int,5>& source) {
    return std::array<int,5>{source[Num]...};
}


int main() {
    std::array<int,5> source{7,8,9,10,11};
    std::array<int,5> res = function<0,1,2,3,4>(source);

    for(int i=0; i<res.size(); ++i)
        std::cout << res[i] << " "; // 7 8 9 10 11

    return 0;
}

So the only thing we need right now is to be able to compile-time generate the "index series" like

std::array<int,5> res = function<0,1,2,3,4>(source);
                                 ^ ^ ^ ^ ^

At this point we can again take advantage of the parameter packs in conjunction with an inheritance mechanism: the idea is to have a deeply nested hierarchy of derived : base : other_base : another_base : ... classes which would "accumulate" the indices into the parameter pack and terminate the "recursion" when the index reaches 0. If you didn't understand the previous sentence don't worry and take a look at the following example:

std::array<int, 3> a1{42,26,77};

// goal: having "Is" = {0,1,2} i.e. a1's valid indices
template<unsigned... Is> struct seq;

we can generate a sequence of indices in the following way:

template<unsigned N, unsigned... Is>
struct gen_seq : gen_seq<N-1, Is...>{}; // each time decrement the index and go on
template<unsigned... Is>
struct gen_seq<0 /*stops the recursion*/, Is...> : /* generate the sequence */seq<Is...>{};

std::array<int, 3> a1{42,26,77};
gen_seq<3>{};

There's something missing anyway: the code above will start with gen_seq<3, (nothing)> and instantiate the specified template which will instantiate the gen_seq<2, (nothing)> as its base class that will instantiate the gen_seq<1, (nothing)> as its base class that will instantiate the gen_seq<0, (nothing)> as its base class that will instantiate the seq<(nothing)> as final sequence.

The sequence is '(nothing)', something is wrong..

In order to "accumulate" the indices into the parameter pack you need to "add a copy" of the decreased index to the parameter pack at each recursion:

template<unsigned N, unsigned... Is>
struct gen_seq : gen_seq<N-1, /*This copy goes into the parameter pack*/ N-1, Is...>{};

template<unsigned... Is>
struct gen_seq<0 /*Stops the recursion*/, Is...> : /*Generate the sequence*/seq<Is...>{};
template<unsigned... Is> struct seq{};

// Using '/' to denote (nothing)
gen_seq<3,/> : gen_seq<2, 2,/> : gen_seq<1,  1,2,/> : gen_seq<0, 0,1,2,/> : seq<0,1,2,/> .

so now we're able to recollect all the pieces together and generate two sequences of indices: one for the first array and one for the second array and concatenate them together into a new return array which will hold the concatenated and flattened union of the two arrays (like appending them together).

The following code, at this point, should be easily comprehensible:

#include <iostream>
#include <array>

template<unsigned... Is> struct seq{};
template<unsigned N, unsigned... Is>
struct gen_seq : gen_seq<N-1, N-1, Is...>{};
template<unsigned... Is>
struct gen_seq<0, Is...> : seq<Is...>{};

template<unsigned N1, unsigned... I1, unsigned N2, unsigned... I2>
// Expansion pack
constexpr std::array<int, N1+N2> concat(const std::array<int, N1>& a1, const std::array<int, N2>& a2, seq<I1...>, seq<I2...>){
  return { a1[I1]..., a2[I2]... };
}

template<unsigned N1, unsigned N2>
// Initializer for the recursion
constexpr std::array<int, N1+N2> concat(const std::array<int, N1>& a1, const std::array<int, N2>& a2){
  return concat(a1, a2, gen_seq<N1>{}, gen_seq<N2>{});
}

int main() {
    constexpr std::array<int, 3> a1 = {1,2,3};
    constexpr std::array<int, 2> a2 = {4,5};

    constexpr std::array<int,5> res = concat(a1,a2);
    for(int i=0; i<res.size(); ++i)
        std::cout << res[i] << " "; // 1 2 3 4 5

    return 0;
}

http://ideone.com/HeLLDm

---

References:

https://stackoverflow.com/a/13294458/1938163

http://en.cppreference.com/

http://en.wikipedia.org