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

Question

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

我尝试了很多,特别是使用索引技巧,只是为了发现我的数据太大了,这样它超过了递归模板实例化限制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)
• 生成序列时进行过滤

也就是说,我从这个O(log N)生成器开始,我将谓词从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" );
}

实例

正如您在实例中看到的那样,即使10000个工作:)

使用a的版本constexpr bool pred(std::size_t)不太方便(你不能只是"调用"该方法,你需要为每个编写更多的代码pred),但它也是可能的.