CODEWITHSUNDEEP
c++c++11variadic-templatestemplate-meta-programmingcompile-time
NaCl
NaCl

Reputation: 2723

Filling an array on compiletime under some predicate

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

Upvotes: 4

Views: 444

Answers (1)

Daniel Frey
Daniel Frey

Reputation: 56883

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.

Upvotes: 5

Related Questions