使用gnu ++ 11和没有stdlib(Arduino环境)在编译时过滤值列表

Question

我正在研究一个Arduino项目,这意味着C++方言目前是C++ 11 的gnu ++ 11超集,并且stdlib不可用(没有元组,没有数组,没有任何东西;命名空间std只是空的!) .

出于优化原因(CPU有16K的FLASH,2K的RAM和这个特殊的低电压版本运行在8MHz)我希望编译器尽可能地预先计算以提供运行时代码,尤其是中断服务程序,"友好的"数据.

现在我想做的是以下内容:

给定一个(唯一的)整数列表,我想提取与任意过滤器匹配的值.然后我想构建一个索引表,允许通过它们的初始索引到达过滤后的元素

例如2,10,4,7,9,3,过滤器value < 8可以产生过滤列表2,4,7,3和索引表0,-1,1,2,-1,3.
只要索引表保持一致,过滤后的数组中元素的顺序就无关紧要了.

我坚持认为我需要不断的数组.动态生成这些数据是微不足道的,但我希望编译器能够完成这项工作,而无需在运行时执行单个指令.

初始列表将由plain提供#define,结果将是常量数组,例如:

#define my_list 2,10,4,7,9,3

constexpr bool filter (int value) { return value < 8; }

const int    filtered_list [] = filter_list <filter>(my_list);
const size_t filtered_index[] = filter_index<filter>(my_list);

问题是,如果可行的话,如何使用准系统C++ 11和没有stdlib 来实现这些filter_list和filter_index模板？

我对错误处理不感兴趣,已经处理了空列表或重复值等异常情况.我宁愿看到最简单的可能实现,即使对数据有效性做出了一些假设.

模板,过滤器或初始列表的确切形式也无关紧要.重要的是从唯一的列表定义中获取数组.
例如,我不介意一种语法,其中列表的每个元素是单独声明的(虽然我无法想象它是如何工作的).

我更喜欢拥有一个独立的C++源代码.另一方面,如果Python可以在几十行中实现,需要隐藏模板的页面,包括重写std :: array和std :: tuple,我宁愿写一些外部预处理器.

Answer 1

有一种方法可以使用函数模板而不是完整的类来避免大多数样板文件。需要最后一个类模板是因为 c++11 中的函数没有返回类型推导。使用int代替typename T来跳过不重要的模板参数。当 atmel 将其工具链更新到 gcc5 或具有 c++14 支持的更新版本时，代码可以进一步精简。

#define LIST  2,10,4,7,9,3
constexpr bool less8(int v) { return v < 8; }

typedef bool(*predicate)(int);

template<int... values>
struct seq {};

template<int N>
struct array {
      const int   data[N];
};

template<int... values>
constexpr array<sizeof...(values)> to_array(seq<values...>) { return {{ values... }}; }

template<typename trueType, typename falseType>
constexpr falseType select(seq<0>, trueType, falseType) { return {}; }

template<typename trueType, typename falseType>
constexpr trueType select(seq<1>, trueType, falseType) { return {}; }

template<int... first, int... second>
constexpr seq<first..., second...> append(seq<first...>, seq<second...>) { return {}; }

template<predicate p, typename N, typename V>
struct filter_impl;

template<predicate p, int next>
struct filter_impl<p, seq<next>, seq<>> {
      using type = seq<>;
};

template<predicate p, int next, int first, int... rest>
struct filter_impl<p, seq<next>, seq<first, rest...>> {
      using type = decltype(
            append(
                  select(seq<p(first)>{}, seq<next>{}, seq<-1>{}),
                  typename filter_impl<p, decltype(select(seq<p(first)>{}, seq<next+1>{}, seq<next>{})), seq<rest...>>::type{}
            )
      );
};

extern constexpr auto  const_indices = to_array(filter_impl<less8, seq<0>, seq<LIST>>::type{});