Filter a list of values at compile time with gnu++11 and no stdlib (Arduino environment)

Question

I'm working on an Arduino project, which means the C++ dialect is currently the gnu++11 superset of C++11, and stdlib is not available (no tuples, no arrays, no nothing; namespace std is just empty!).

For optimization reasons (the CPU has 16K of FLASH, 2K of RAM and this particular low-voltage version runs at 8MHz) I want the compiler to pre-compute as much as possible to provide runtime code, especially the interrupt service routines, with "friendly" data.

Now what I would like to do is the following:

given a list of (unique) integers, I want to extract the values that match an arbitrary filter. Then I want to build an index table that will allow to reach the filtered elements through their initial indices

For instance 2,10,4,7,9,3 with the filter value < 8 could yield the filtered list 2,4,7,3 and the index table 0,-1,1,2,-1,3.
The order of the elements in the filtered array does not matter as long as the index table remains consistent.

I insist on the fact that I want constant arrays. Producing these data dynamically would be trivial, but I want the compiler to do the job, without executing a single instruction at runtime.

The initial list would be given by a plain #define, and the results would be in constant arrays, e.g:

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

The question is, how to implement these filter_list and filter_index templates with barebone C++11 and no stdlib, if at all feasible?

I'm not interested in error handling, the abnormal cases like empty lists or duplicate values are already taken care of. I'd rather like to see the simplest possible implementation, even if some assumptions are made about data validity.

The exact form of the templates, filter or the initial list do not matter either. All that matters is to get the arrays from an unique list definition.
For instance I would not mind a syntax where each element of the list is declared separately (though I can't really imagine how that could work).

I would prefer to have a self-contained C++ source. On the other hand, if what Python could achieve in a couple dozen lines requires pages of cryptic templates, including the rewriting of std::array and std::tuple, I'd rather write some external preprocessor.

Answer 1

Here is a small implementation of compile-time filtering, reproducing small parts of the standard library in a minimalist way. It includes an example of usage at the end. (It probably isn't possible to implement the filtering as a function, since C++ doesn't allow the result type of a function to depend on the values of the arguments. So, you would have to have the result type have enough storage for the case where the predicate always returns true which seems like it would be a show-stopper for your use case. That is why the approach here is to do the filtering using template metaprogramming first, and then convert the results to an array wrapper object.)

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

Answer 2

There is a way to avoid most of the boilerplate using function templates instead of full classes. The last class template is needed because there is no return type deduction for functions in c++11. int is used instead of typename T to skip unimportant template parameters. The code could be slimmed further when atmel updates their toolchain to gcc5 or newer with c++14 support.

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