如何筛选 std::integer_sequence

Question

如果我理论上有一个整数序列，比如

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

如何使用一些编译时谓词对其进行过滤以获得可能更小的 std::integer_sequence<int, ...>？

为了争论，假设我只想要偶数，这导致 "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) 之间的重复项，假设我们可以将位集表示为仅包含 0 和 1 的 integer_sequences。加分如果你也可以用这种方式解决那个问题}

Answer 1

编辑 2

在反复讨论 Barry 的回答后，我得出了以下答案，它融合了概念并处理了一些 empty-sequence 边缘情况 (Full code)：

只有当函数是 constexpr lambda 时，我们才允许将谓词传递给函数，因为 constexpr functions 中只允许文字类型，而正常的 free-floating 函数是不允许的' t 文字类型（虽然我想你可以在你的 lambda 中包装一个）。

我们的通用过滤器函数将接受一个序列和一个谓词，以及 return 一个新序列。我们将在谓词上使用 constexpr if to handle empty sequence cases (which also requires the maybe_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>{};
}

Filter 函数为提供的序列中的每个元素调用 FilterSingle，并将所有元素的结果连接起来：

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

要连接序列，基本方法是：

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

尽管由于模板扩展，我们很多时候会有 2 个以上的序列，所以我们需要一个递归案例：

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

而且由于我们可能会尝试连接空序列（如果没有元素通过过滤器，就会发生这种情况），我们需要另一个基本情况：

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

现在，对于我们的谓词，我们将使用 constexpr lambda。请注意，我们不需要将其明确指定为 constexpr，因为它已经满足自动变为 constexpr

的条件

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

所以我们的完整测试是这样的：

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

以前的方法

我的方法是重复构造和连接 sub-sequences，其中基本情况（一个的序列）将 return 空序列或相同序列（如果谓词满足）。

为了编写谓词，我将利用 C++17 的 constexpr if 来定义谓词。

谓词：

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

串联逻辑：

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...>{};
}

测试：

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

编辑：

我用这种方法解决了删除匹配位的“奖励”问题：

Answer 2

过滤一个序列相当于将一个值序列转换为一个至多一个值的序列序列，然后将它们串联起来。也就是说，从 <0,1,2,3> 中过滤偶数值与将其转换为序列 <<0>,<>,<2>,<>> 并连接以产生 <0,2>.

相同

对于 C++17，这需要非常少的代码。我们将从我们自己的值和序列类型开始（您可以轻松地将 std::integer_sequence 转换为 value_sequence）：

template <auto >
struct value { };

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

我们使用自己的原因是我们可以向其中添加运算符。点赞 +:

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

我们将使用它进行连接。接下来，我们添加一个函数，将单个值转换为零或一个元素的序列：

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

最后，我们只需要 top-level filter 将它们放在一起：

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

原始示例中的用法：

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

C++17 多酷啊！

Answer 3

利用元组的替代解决方案：

template <auto Pred, class Type, Type... I>
struct filter_integer_sequence_impl
{
    template <class... T>
    static constexpr auto Unpack(std::tuple<T...>)
    {
        return std::integer_sequence<Type, T::value...>();
    }

    template <Type Val>
    using Keep = std::tuple<std::integral_constant<Type, Val>>;
    using Ignore = std::tuple<>;
    using Tuple = decltype(std::tuple_cat(std::conditional_t<(*Pred)(I), Keep<I>, Ignore>()...));
    using Result = decltype(Unpack(Tuple()));
};

template <auto Pred, class Type, Type... I>
constexpr auto filter_integer_sequence(std::integer_sequence<Type, I...>)
{
    return typename filter_integer_sequence_impl<Pred, Type, I...>::Result();
}

template <class Pred, class Type, Type... I>
constexpr auto filter_integer_sequence(std::integer_sequence<Type, I...> sequence, Pred)
{
    return filter_integer_sequence<(Pred*)nullptr>(sequence);
}

这样使用：

constexpr auto predicate = [](int val) { return (val % 2) == 0; };

constexpr auto start = std::integer_sequence<int, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9>();
constexpr auto filtered = filter_integer_sequence(start, predicate);
constexpr auto expected = std::integer_sequence<int, 0, 2, 4, 6, 8>();

static_assert(std::is_same_v<decltype(filtered), decltype(expected)>);

filter_integer_sequence 的第二个重载仅对于 C++17 是必需的，它不允许我们将 lambda 用于非类型模板参数。 C++20 取消了该限制，因此在那种情况下只需要第一个重载。请注意，第一个重载在 C++17 中仍然是处理常规函数指针所必需的。

与此处的其他解决方案一样，第二个重载仅适用于非捕获 lambda。这就是为什么我们可以安全地将 (*(Pred*)nullptr)(I) 评估为 constexpr，因为 lambda 主体实际上并不使用 this 指针。

如何筛选 std::integer_sequence

How to filter a std::integer_sequence

c++

c++17

编辑 2

以前的方法

编辑：