vendredi 28 juillet 2017

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

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.

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 don't care about 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.

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.

Aucun commentaire:

Enregistrer un commentaire