c++11常量表达式将std：：数组的列表展平为数组

Question

我从c++11开始，constexpr和模板元编程似乎是在微型微控制器上保存稀有ram的一个很好的方法。

有没有一种方法可以写一个模板来扁平化constexpr数组列表，我需要的是一种方法：

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);

我使用的是gcc 4.8.4 (arm-none-eabi)，如果需要，可以使用std=c++11或c++1y选项进行编译。

Answer 1

注意--我对您的问题的理解如下:您希望将这两个数组连接起来，并将结果展平为一个包含它们的元素连接的新数组。

您可以通过以下三个C++11+概念来实现您的目标：

首先创建一个模板(一个空的shell)，以开始设计递归样式的列表展平函数：

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
}

到目前为止还不错：constexpr说明符将提示编译器在每次可以编译时对该函数进行求值。

现在到了有趣的部分: std::array有一个constexpr overload for the operator[] (从c++1y开始)，这意味着您可以编写如下内容

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]};
}

(注意从一系列整数值初始化对象的aggregate-initialization )

显然，手动硬编码对两个数组的值的所有索引访问并不比仅仅声明连接的数组本身更好。拯救世界的概念如下：Parameter Packs。模板参数包是接受0个或更多模板参数的模板参数。具有至少一个参数包的模板称为可变模板。

最酷的是能够将参数包扩展到指定的位置，例如：

#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;
}

因此，我们现在唯一需要的就是能够在编译时生成“索引系列”，比如

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

在这一点上，我们可以再次结合继承机制来利用参数包:其思想是拥有一个深度嵌套的derived : base : other_base : another_base : ...类层次结构，它会将索引“累积”到参数包中，并在索引达到0时终止“递归”。如果你不理解前面的句子，请不要担心，看看下面的例子：

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;

我们可以通过以下方式生成一系列索引：

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>{};

上面的代码将以gen_seq<3，(nothing)>开始并实例化指定的模板，该模板将实例化gen_seq<2，(nothing)>作为它的基类实例化gen_seq<1，(nothing)>作为它的基类实例化gen_seq<0，(nothing)>作为它的基类实例化seq<(nothing)>作为最终序列。

序列是'(nothing)'，有问题..

为了将索引“累积”到参数包中，您需要在每次递归时将减少的索引的“副本”添加到参数包中：

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,/> .

因此，现在我们可以将所有片段收集在一起，并生成两个索引序列:一个用于第一个数组，另一个用于第二个数组，并将它们连接到一个新的返回数组中，该返回数组将保存两个数组的连接和展平的联合(就像将它们附加在一起)。

在这一点上，以下代码应该很容易理解：

#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

参考文献：

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

http://en.cppreference.com/

http://en.wikipedia.org

Answer 2

对于C++1y，一个实现可以(尽管不是必需的)允许std::tuple_cat处理任何类似元组的类型，而不仅仅是std::tuple<T...>。在我们的例子中，std::array<T, N>就是这样一种类型。所以我们可以尝试：

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);

实际上，调用std::tuple_cat的结果是一个元组，而不是一个数组。然后，可以将std::tuple<T, T,… , T>转换为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> {} );
}

(事实证明，只要元组元素类型是兼容的，这个to_array实现就可以将任何类似元组的元素转换为数组。)

这里是a live example for GCC 4.8，填充了一些尚不支持的C++1y特性。

Answer 3

Luc的帖子回答了这个问题。

但有趣的是，这里有一个没有模板元编程的C++14解决方案，只是纯constexpr。

不过有一个问题，泛化的常量表达式在一年多前就被选为标准核心语言，但STL仍然没有更新……

作为实验，打开头<array>并为非常量operator[]添加一个明显缺少的常量open

constexpr reference operator[](size_type n);

还要打开<numeric>并将std::accumulate转换为常量open函数

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

现在我们可以这样做：

#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;
}

(在clang主干上编译和运行)