Filling an array on compiletime under some predicate

Question

Is there a way to make a constexpr-Array of unsigned integers which fulfill some predicate given by the constexpr boolean function pred(std::size_t)?

I tried a lot around, especially with the indices trick, just to find out that my data is too huge, such that it exceeds the recursive template instantiation limit of 256. I'll not be able to change this limit, if its possible to change it.

As asked in the comments, here is some pseudo code of what I would like to achieve:

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

Can you show us some (pseudo-)code of what you'd like to achieve? Maybe with a small data set which does not exceed the limit but otherwise works and shows us what you mean? — Daniel Frey, May 09 '15 at 18:06
So is your idea to "filter" a range by a given predicate? Also, if you're looking for an efficient "sequence generator", I wrote a library that provides [one with logarithmic instantiation depth](https://github.com/Arcoth/VTMPL/blob/master/index_list.hxx). — Columbo, May 09 '15 at 18:52
@Columbo Yes, but the range is bigger than 256 and obviously must be on compile-time. — NaCl, May 09 '15 at 18:56

score 5 · Accepted Answer · edited May 23 '17 at 11:43

The only solution I could come up with is to use a generator for the sequence which is both

O(log N)
Filter while generating the sequence

That said, I started with this O(log N) generator and I changed the predicate from a constexpr function to a more convenient std::integral_constant - I hope that is acceptable to you. The result is this:

#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

As you can see in the live example, even 10000 works :)

A version using a constexpr bool pred(std::size_t) is not so convenient (you can't just "call" the method, you need to write some more code for each pred), but it was also possible.

Filling an array on compiletime under some predicate

1 Answers1