c++ - 在编译时使用 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 .
只要索引表保持一致，过滤后的数组中元素的顺序无关紧要。

我坚持要常量 数组这一事实。动态生成这些数据是微不足道的，但我希望编译器能够完成这项工作，而无需在运行时执行任何指令。

初始列表将由普通 #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);

问题是，如何实现这些filter_list和 filter_index具有准系统 C++11 且没有标准库的模板，如果可行的话？

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

模板、过滤器或初始列表的确切形式都无关紧要。重要的是从唯一列表定义中获取数组。
例如，我不介意单独声明列表的每个元素的语法(尽管我真的无法想象它是如何工作的)。

我更愿意拥有一个独立的 C++ 源代码。另一方面，如果 Python 可以在几十行代码中实现的目标需要一页纸神秘的模板，包括重写 std::array 和 std::tuple，我宁愿编写一些外部预处理器。

Answer 1

这里是编译时过滤的一个小实现，以极简主义的方式复制了标准库的一小部分。它在最后包含一个用法示例。 (可能无法将过滤实现为函数，因为 C++ 不允许函数的结果类型依赖于参数的值。因此，您必须让结果类型有足够的存储空间谓词总是返回 true 的情况，这似乎会成为您用例的障碍。这就是为什么这里的方法是首先使用模板元编程进行过滤，然后转换结果到一个 array 包装器对象。)

#include <sys/types.h>

template <typename T, size_t N>
struct array {
    T elem[N];
    constexpr size_t size() const { return N; }
    constexpr T operator[](size_t i) const { return elem[i]; }
    T* begin() { return elem; }
    const T* begin() const { return elem; }
    T* end() { return elem + N; }
    const T* end() const { return elem; }
};
template <typename T>
struct array<T, 0> {
    constexpr size_t size() const { return 0; }
    T* begin() { return nullptr; }
    const T* begin() const { return nullptr; }
    T* end() { return nullptr; }
    const T* end() const { return nullptr; }
};

template <typename T, T... x>
struct static_sequence { };

template <bool p, typename TrueT, typename FalseT>
struct conditional;
template <typename TrueT, typename FalseT>
struct conditional<true, TrueT, FalseT> {
    using type = TrueT;
};
template <typename TrueT, typename FalseT>
struct conditional<false, TrueT, FalseT> {
    using type = FalseT;
};
template <bool p, typename TrueT, typename FalseT>
using conditional_t = typename conditional<p, TrueT, FalseT>::type;

template <typename T, T x, typename S>
struct static_sequence_cons;
template <typename T, T x, T... Ss>
struct static_sequence_cons<T, x, static_sequence<T, Ss...>> {
    using type = static_sequence<T, x, Ss...>;
};
template <typename T, T x, typename S>
using static_sequence_cons_t = typename static_sequence_cons<T, x, S>::type;

template <typename T, bool(*pred)(T), T... N>
struct filter;
template <typename T, bool(*pred)(T)>
struct filter<T, pred> {
    using type = static_sequence<T>;
};
template <typename T, bool(*pred)(T), T hd, T... tl>
struct filter<T, pred, hd, tl...> {
private:
    using filter_tl = typename filter<T, pred, tl...>::type;
public:
    using type = conditional_t<pred(hd),
                               static_sequence_cons_t<T, hd, filter_tl>,
                               filter_tl>;
};
template <typename T, bool(*pred)(T), T... N>
using filter_t = typename filter<T, pred, N...>::type;

template <ssize_t curr_index, typename T, bool(*pred)(T), T... N>
struct filter_index;
template <ssize_t curr_index, typename T, bool(*pred)(T)>
struct filter_index<curr_index, T, pred> {
    using type = static_sequence<ssize_t>;
};
template <ssize_t curr_index, typename T, bool(*pred)(T), T hd, T... tl>
struct filter_index<curr_index, T, pred, hd, tl...> {
    using type = conditional_t<pred(hd),
        static_sequence_cons_t<ssize_t, curr_index, typename filter_index<curr_index + 1, T, pred, tl...>::type>,
        static_sequence_cons_t<ssize_t, -1, typename filter_index<curr_index, T, pred, tl...>::type>>;
};
template <typename T, bool(*pred)(T), T... N>
using filter_index_t = typename filter_index<0, T, pred, N...>::type;

template <typename T, T... x>
constexpr array<T, sizeof...(x)> static_sequence_to_array(
    static_sequence<T, x...>) {
    return array<T, sizeof...(x)> { x... };
}


//
// EXAMPLE USAGE
//
constexpr bool even(int n) {
    return n % 2 == 0;
}
constexpr auto x = static_sequence_to_array(
    filter_t<int, even, 0, 1, 2, 3, 4>{});
constexpr auto i = static_sequence_to_array(
    filter_index_t<int, even, 0, 1, 2, 3, 4>{});

static_assert(x.size() == 3, "Bad filter");
static_assert(x[0] == 0, "Bad filter");
static_assert(x[1] == 2, "Bad filter");
static_assert(x[2] == 4, "Bad filter");
static_assert(i.size() == 5, "Bad filter_index");
static_assert(i[0] == 0, "Bad filter_index");
static_assert(i[1] == -1, "Bad filter_index");
static_assert(i[2] == 1, "Bad filter_index");
static_assert(i[3] == -1, "Bad filter_index");
static_assert(i[4] == 2, "Bad filter_index");