How to filter a std::integer_sequence

Question

If I theoretically have a sequence of integers like

std::integer_sequence<int, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9>

How can I filter it with some compile-time predicate to get a potentially smaller std::integer_sequence<int, ...>?

For the sake of argument, let's say that I want only the even values, which leads to the question of "How can I make the following static_assert (or something close) pass?"

static_assert(std::is_same_v<std::integer_sequence<int, 0, 2, 4, 6, 8>,
              decltype(FilterEvens(std::integer_sequence<int, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9>{}))>, 
              "Integer sequences should be equal");

^{This question was inspired by thinking about how we might accomplish removing duplicates between two bitsets (this question), assuming we could represent the bitsets as integer_sequences containing only 0 and 1. Bonus points if you can solve that one in this manner, too}

Answer 1

Filtering a sequence is equivalent to transforming a sequence of values into a sequence of sequences of at most one value and then concatenating them. That is, filtering the even values from <0,1,2,3> would be the same as transforming that into the sequence <<0>,<>,<2>,<>> and concatenating to yield <0,2>.

With C++17, this takes remarkably little code. We'll start with our own value and sequence type (you can easily convert a std::integer_sequence to a value_sequence):

template <auto >
struct value { };

template <auto... Vals>
struct value_sequence { };

The reason we use our own is so we can add operators to it. Like +:

template <auto... As, auto... Bs>
constexpr value_sequence<As..., Bs...> operator+(value_sequence<As...>,
                                                 value_sequence<Bs...> )
{
    return {};
}

We'll use that for concatenation. Next, we add a function to transform a single value into a sequence of zero or one element:

template <auto Val, class F>
constexpr auto filter_single(value<Val>, F predicate) {
    if constexpr (predicate(Val)) {
        return value_sequence<Val>{};
    }
    else {
        return value_sequence<>{};
    }
}

And lastly, we just need our top-level filter to put it all together:

template <auto... Vals, class F>
constexpr auto filter(value_sequence<Vals...>, F predicate) {
    return (filter_single(value<Vals>{}, predicate) + ...);
}

Usage from the original example:

constexpr auto evens = filter(
    value_sequence<0, 1, 2, 3, 4, 5, 6, 7, 8, 9>{},
    [](int i) constexpr { return i%2 == 0; });

How cool is C++17!

Answer 2

Edit 2

After some back and forth on Barry's answer, I've come up with the following answer that merges the concepts and handles some empty-sequence edge cases (Full code):

We are allowed to pass a predicate to a function only if it is a constexpr lambda, as only literal types are allowed in constexpr functions, and normal free-floating functions aren't literal types (although I suppose you could wrap one within your lambda).

Our generic filter function will accept a sequence and a predicate, and return a new sequence. We will use constexpr if to handle empty sequence cases (which also requires the maybe_unused attribute on the predicate, because it's unused) :

template<class INT, INT... b, class Predicate>
constexpr auto Filter(std::integer_sequence<INT, b...>, [[maybe_unused]] Predicate pred)
{
    if constexpr (sizeof...(b) > 0) // non empty sequence
       return concat_sequences(FilterSingle(std::integer_sequence<INT, b>{}, pred)...);
    else // empty sequence case
        return std::integer_sequence<INT>{};
}

The Filter function calls FilterSingle for each element in the provided sequence, and concatenates the result of all of them:

template<class INT, INT a, class Predicate>
constexpr auto FilterSingle(std::integer_sequence<INT, a>, Predicate pred)
{
    if constexpr (pred(a))
        return std::integer_sequence<INT, a>{};
    else
        return std::integer_sequence<INT>{};
}

To concatenate sequences, the basic approach is thus:

template<typename INT, INT... s, INT... t>
constexpr std::integer_sequence<INT,s...,t...>
concat_sequences(std::integer_sequence<INT, s...>, std::integer_sequence<INT, t...>){
    return {};
}

Although because of template expansion we'll have more than 2 sequences a lot of time, so we need a recursive case:

template<typename INT, INT... s, INT... t, class... R>
constexpr auto
concat_sequences(std::integer_sequence<INT, s...>, std::integer_sequence<INT, t...>, R...){
    return concat_sequences(std::integer_sequence<INT,s...,t...>{}, R{}...);
}

And since we may try to concatenate an empty sequence with nothing (can happen if no elements pass the filter), we need another base case:

template<typename INT>
constexpr std::integer_sequence<INT>
concat_sequences(std::integer_sequence<INT>){
    return {};
}

Now, for our predicate we will use a constexpr lambda. Note that we do not need to specify it as constexpr explicitly because it already satisfies the criteria to automatically become constexpr

auto is_even = [](int _in) {return _in % 2 == 0;};

So our full test looks like this:

auto is_even = [](int _in) {return _in % 2 == 0;};
using expected_type = std::integer_sequence<int, 0, 2, 4, 6, 8>;
using test_type = std::integer_sequence<int, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9>;
constexpr auto result = Filter(test_type{}, is_even);
using result_type = std::decay_t<decltype(result)>;
static_assert(std::is_same_v<expected_type, result_type>, "Integer sequences should be equal");

---

Previous approach

My approach is repeatedly construct and concatenate sub-sequences, where the base case (sequence of one) will either return an empty sequence or the same sequence if the predicate is satisfied.

For writing the predicate, I'll take advantage of C++17's constexpr if for defining a predicate.

Predicate:

// base case; empty sequence
template<class INT>
constexpr auto FilterEvens(std::integer_sequence<INT>)
{
    return std::integer_sequence<INT>{};
}

// base case; one element in the sequence
template<class INT, INT a>
constexpr auto FilterEvens(std::integer_sequence<INT, a>)
{
    if constexpr (a % 2 == 0)
        return std::integer_sequence<INT, a>{};
    else
        return std::integer_sequence<INT>{};
}

// recursive case
template<class INT, INT a, INT... b>
constexpr auto FilterEvens(std::integer_sequence<INT, a, b...>)
{
    return concat_sequence(FilterEvens(std::integer_sequence<INT, a>{}), 
                           FilterEvens(std::integer_sequence<INT, b...>{}));
}

Concatenation logic:

template <typename INT, INT ...s, INT ...t>
constexpr auto
concat_sequence(std::integer_sequence<INT,s...>,std::integer_sequence<INT,t...>){
   return std::integer_sequence<INT,s...,t...>{};
}

And the test:

int main()
{
   static_assert(std::is_same_v<std::integer_sequence<int, 0, 2, 4, 6, 8>, decltype(FilterEvens(std::integer_sequence<int, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9>{}))>, "Integer sequences should be equal");
}

Live Demo

---

Edit:

I used this approach to solve the "Bonus" question for removing matched bits here: https://stackoverflow.com/a/41727221/27678