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.

Gosling

You want to join those arrays? Something like this? – Telecast

@Rapptz why did you rollback the C++1y tag? As the answer by Luc Danton shows, this type of stuff becomes much easier with the index_sequence machinery. – Transmute

@Transmute This question has really nothing to do with C++1y. Using index_sequence isn't strictly C++1y as the trick has been used in a vast majority of C++11 answers. Doesn't dictate that those get turned into c++1y. – Devilish

@Devilish tags are not mutually exclusive, and it makes for easier searching for Q&A where C++1y techniques are used – Transmute

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://mcmap.net/q/16872/-concat-two-const-char-string-literals

http://en.cppreference.com/

http://en.wikipedia.org

Rurik

Thank you so much for that answer ! I finally understand pack sequences, which were still over my head after reading all references I could find. Question though : Why do we use both I1 and I2 ? Can't we reuse the same pack, since both expansions are independent ? – Borkowski

@Borkowski the two indices series might be different, that's why we use two of them – Rurik

And now I feel dumb. Well, time to sleep I guess. Thanks again ! – Borkowski

Nicely coded. However, constexpr and template metaprogramming seems a nice way to save scarce ram on tiny microcontroler - this solution creates copies of arrays. – Newhouse

@Telecast yes, that's why I wrote "C++11+", you need more than C++11 to get this working. Perhaps I should have specified that more clearly – Rurik

Ok, have not seen that + :) In C++1y, we'll have integer_sequence et al in the StdLib anyway, and we could just use a loop. – Telecast

I will look into that, I'm still even getting my hands warm on C++11 (I can't use it at work unfortunately.. retrocompatibility issues :( ) – Rurik

An example of C++1y string manipulation at compile time (shameless plug). The relaxed constexpr constraints really help. – Telecast

thanks for this step by step demonstration. I will spend my morning understand that ! Any good book about c++11(14) novelties to help understanding all theses new concepts ? – Gosling

@Gosling Regarding C++11 there are several but I'm afraid that C++14 is still in its infancy – Rurik

Note that the C++1y integer sequence is going to be able to build the sequrnce eith logarithmic depth (or better). The recursive inheritance trick above is linear template instantiation depth: so sequences larger than a few 100 will cause compilers to complain and fail. In template meta programming, recursion depth is to be minimized. – Rosana

Answer 2

With C++1y, an implementation may (although it is not required) allow std::tuple_cat to work with any tuple-like types, and not just std::tuple<T...>. In our case, std::array<T, N> is such a type. So we could attempt:

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

// not possible
// constexpr auto e = a3[3]

// instead
constexpr auto e = std::get<3>(a3);

As it so happens though, the result of a call to std::tuple_cat is a tuple, not an array. It is then possible to turn an std::tuple<T, T,… , T> into an std::array<T, N>:

template<
    typename Tuple,
    typename VTuple = std::remove_reference_t<Tuple>,
    std::size_t... Indices
>
constexpr std::array<
    std::common_type_t<std::tuple_element_t<Indices, VTuple>...>,
    sizeof...(Indices)
>
to_array(Tuple&& tuple, std::index_sequence<Indices...>)
{
    return { std::get<Indices>(std::forward<Tuple>(tuple))... };
}

template<typename Tuple, typename VTuple = std::remove_reference_t<Tuple>>
constexpr decltype(auto) to_array(Tuple&& tuple)
{
    return to_array(
        std::forward<Tuple>(tuple),
        std::make_index_sequence<std::tuple_size<VTuple>::value> {} );
}

(As it turns out this to_array implementation converts any tuple-like into an array as long as the tuple element types are compatible.)

Here’s a live example for GCC 4.8, filling in some of the C++1y features not yet supported.

Genipap

Answer 3

Luc's post answer the question.
But for fun, here is a C++14 solution without template metaprogramming, just pure constexpr.

There is a catch though, generalized constexpr was voted into the standard core language more than one year ago, but the STL still isn't updated yet...

As an experiment, open the header <array> and add an obviously missing constexpr for non-const operator[]

constexpr reference operator[](size_type n);

Also open <numeric> and turn std::accumulate into a constexpr function

template <class InputIterator, class T>
constexpr T accumulate(InputIterator first, InputIterator last, T init);

Now we can do :

#include <iostream>
#include <array>
#include <numeric>

template <typename T, size_t... sz>
constexpr auto make_flattened_array(std::array<T, sz>... ar)
{
   constexpr size_t NB_ARRAY = sizeof...(ar);

   T* datas[NB_ARRAY] = {&ar[0]...};
   constexpr size_t lengths[NB_ARRAY] = {ar.size()...};

   constexpr size_t FLATLENGTH = std::accumulate(lengths, lengths + NB_ARRAY, 0);

   std::array<T, FLATLENGTH> flat_a = {0};

   int index = 0;
   for(int i = 0; i < NB_ARRAY; i++)
   {
      for(int j = 0; j < lengths[i]; j++)
      {
         flat_a[index] = datas[i][j];
         index++;
      }
   }

   return flat_a;
}

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

  constexpr auto a = make_flattened_array(a1, a2, a3);

  for(int i = 0; i < a.size(); i++)
     std::cout << a[i] << std::endl;
}

(Compile and run on clang trunk)

Taitaichung

nice implementation which take a list of array as argument, indubitably easier to read and understand than the template meta programming solution. Unfortunately, gcc hasn't generalized constexpr support, even in 4.9, and i'm not sure if it's planned for 4.10, for now, it's not done and it's not even a work in progress. – Gosling

<array> has been updated sometime between 4.9 and 7.3 with constexpr element access, however std::accumulate still isn't constexpr, so this answer's usefulness is still limited by requiring modification of <numeric>. However, if you're willing to bump your compiler version up to C++17, you can use fold expressions instead of modifying std::accumulate: constexpr FLATLENGTH = ( sz + ... );. – Singleminded

Answer 4

Another way is using expression templates. It does not copy arrays.

A sketch:

#include <array>

template<class L, class R>
struct AddOp
{
    L const& l_;
    R const& r_;

    typedef typename L::value_type value_type;

    AddOp operator=(AddOp const&) = delete;

    constexpr value_type const& operator[](size_t idx) const {
        return idx < l_.size() ? l_[idx] : r_[idx - l_.size()];
    }

    constexpr std::size_t size() const {
        return l_.size() + r_.size();
    }

    // Implement the rest of std::array<> interface as needed.
};

template<class L, class R>
constexpr AddOp<L, R> make_flattened_array(L const& l, R const& r) {
    return {l, r};
}

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

int main() {
    constexpr auto x = a5[1];
    constexpr auto y = a5[4];
    constexpr auto z = a5[5];
}

Newhouse

with bare programming on microcontroler, .text segment is written in flash memory, not in ram, so static const variable are written in flash, so copy is not a problem. And what i need is having the entire array in continuous memory for the dma engine which will read that memory, so your solution will not work, but anyway, i have learn another c++ capability ! – Gosling

Answer 5

Here is a small solution for C++20 which works for a various number of std::arrays

template<class T, std::size_t... SIZE>
constexpr auto concat(const std::array<T, SIZE>... arrays) {
    constexpr std::size_t total_size = (SIZE + ...);

    auto all_elements = std::tuple_cat(arrays...);

    return [&]<std::size_t... Is>(std::index_sequence<Is...>) {
        return std::array<T, total_size>{{std::get<Is>(all_elements)...}};
    }(std::make_index_sequence<total_size>{});
}

Maryrosemarys