在某些谓词下的编译时填充数组

Question

有没有办法制作一个 constexpr 无符号整数数组，它满足 constexpr 布尔函数 pred(std::size_t) 给出的某些谓词？

我尝试了很多，尤其是 indices trick，只是发现我的数据太大，以至于它超过了 256 的递归模板实例化限制。我将无法更改此限制，如果可能的话。

正如评论中所问，这是我想要实现的一些伪代码：

template<std::size_t... Is> 
struct Sequence{};

template<std::size_t N, std::size_t... Is> 
struct SequenceGenerator : SequenceGenerator<N-1, N-1, Is...>
{}; //obviously here it gets too deep into recursion, as mentioned

template<std::size_t... Is> 
struct SequenceGenerator<0, Is...> : Sequence<Is...>
{};

template<std::size_t N>
struct MyData
{
    std::size_t values[N];

    static constexpr std::size_t size()
    { return N; }
};

template<typename Lambda, std::size_t... Is> 
constexpr MyData<sizeof...(Is)> MyGen(Sequence<Is...>, Lambda func)
{
    if(func(Is)...)
        return {{ Is... }};
    else
        return /*some not-invalidating but current element discarding thing*/
}

template<std::size_t N, typename Lambda>
constexpr Generator<N> MyGen(Lambda func)
{
    return MyGen(SequenceGenerator<N>(), func);
}

constexpr bool pred(std::size_t i) noexcept
{
    //some condition making up a "range"
    return i < 360ULL && i > 2ULL;
}

Answer 1

我能想出的唯一解决方案是为序列使用一个生成器，它既是

O(log N)
在生成序列时过滤

就是说，我开始 with this O(log N) generator 并将谓词从 constexpr 函数更改为更方便的 std::integral_constant - 希望您能接受。结果是这样的：

#include <utility>
#include <iostream>
#include <type_traits>

template<std::size_t...> struct seq{ using type = seq; };

template<class S1, class S2> struct concat;

template<std::size_t... I1, std::size_t... I2>
struct concat<seq<I1...>, seq<I2...>>
  : seq<I1..., I2...>{};

template<template<std::size_t> class pred, std::size_t B, std::size_t N>
struct gen_seq : concat<typename gen_seq<pred, B, N/2>::type, typename gen_seq<pred, B + N/2, N - N/2>::type>::type {};

template<template<std::size_t> class pred, std::size_t B> struct gen_seq<pred, B, 0> : seq<> {};
template<template<std::size_t> class pred, std::size_t B> struct gen_seq<pred, B, 1> : std::conditional<pred<B>::value,seq<B>,seq<>>::type {};

template<std::size_t N>
struct MyData
{
    std::size_t values[N];

    static constexpr std::size_t size()
    { return N; }
};

template<std::size_t... Is>
constexpr MyData<sizeof...(Is)> MyGen(seq<Is...>)
{
    return {{ Is... }};
}

template<template<std::size_t> class pred, std::size_t N>
constexpr auto MyGen() -> decltype(MyGen(typename gen_seq<pred,0,N>::type()))
{
    return MyGen(gen_seq<pred,0,N>());
}

template< std::size_t N > struct my_pred : std::integral_constant< bool, N % 3 == 0 > {};

int main()
{
    auto data = MyGen<my_pred, 10>();
    static_assert( data.size() == 4, "Oops" );

    for ( auto i : data.values )
       std::cout << i << std::endl;

    auto data2 = MyGen<my_pred, 10000>();
    static_assert( data2.size() == 3334, "Oops" );
}

Live example

正如您在实际示例中看到的那样，即使 10000 个也有效:)

使用constexpr bool pred(std::size_t)的版本不太方便（你不能只"call"这个方法，你需要为每个pred多写一些代码），但是它也是可以的。

在某些谓词下的编译时填充数组

Filling an array on compiletime under some predicate

c++

c++11

variadic-templates

template-meta-programming

compile-time