Temps de compilation d'initialisation de matrice - Séquence Constexpr

Question

Je lisais this question sur SO.

La question elle-même n'est pas très intéressante, mais je me demandais si elle existe et comment implémenter une solution de compilation.

Regard à la première séquence:

Tous les numéros, sauf ceux qui peuvent être divisés par 3.

La séquence devrait être quelque chose comme:

[1, 2, 4, 5, 7, 8, 10, 11, 13, 14, ...] 

par induction , J'ai trouvé la formule mathématique pour cette séquence:

f(0) = 0; 
f(x > 0) = floor[(3x - 1)/2]; 

J'ai donc mis en œuvre une fonction constexpr C++ qui génère le i-ème numéro dans la séquence:

#include <type_traits> 

template <typename T = std::size_t> 
constexpr T generate_ith_number(const std::size_t index) { 
    static_assert(std::is_integral<T>::value, "T must to be an integral type"); 

    if (index == 0) return 0; 
    return (3 * index - 1)/2; 
} 

Maintenant, j'aimerais générer un "tableau de compilation/séquence" qui stocke les premiers numéros N de la séquence.

La structure doit être quelque chose comme:

template <typename T, T... values> 
struct sequence {}; 

template <typename T, std::size_t SIZE> 
struct generate_sequence {}; // TODO: implement 

Questions (plus d'un, mais liés entre eux):

1) Comment mettre en œuvre ce genre de integer_sequence?

2) Est-il possible de construire un std::array à partir de ce integer_sequence au moment de la compilation?

Answer 1

1) Comment implémenter ce type de integer_sequence?

template <std::size_t... Is> 
constexpr auto make_sequence_impl(std::index_sequence<Is...>) 
{ 
    return std::index_sequence<generate_ith_number(Is)...>{}; 
} 

template <std::size_t N> 
constexpr auto make_sequence() 
{ 
    return make_sequence_impl(std::make_index_sequence<N>{}); 
} 

---

2) Est-il possible de construire un std::array de cette integer_sequence au moment de la compilation?

template <std::size_t... Is> 
constexpr auto make_array_from_sequence_impl(std::index_sequence<Is...>) 
{ 
    return std::array<std::size_t, sizeof...(Is)>{Is...}; 
} 

template <typename Seq> 
constexpr auto make_array_from_sequence(Seq) 
{ 
    return make_array_from_sequence_impl(Seq{}); 
} 

---

Utilisation:

int main() 
{ 
    constexpr auto arr = make_array_from_sequence(make_sequence<6>()); 
    static_assert(arr[0] == 0); 
    static_assert(arr[1] == 1); 
    static_assert(arr[2] == 2); 
    static_assert(arr[3] == 4); 
    static_assert(arr[4] == 5); 
    static_assert(arr[5] == 7); 
} 

live example on wandbox.org

Answer 2

Il est assez simple de générer le tableau en utilisant le code assez simple en C++ récent:

template<typename T, T N> 
constexpr auto make_constexpr_array(std::integral_constant<T, N>) 
{ 
    std::array<int,N> result = {}; 
    for (int i = 0; i < N; ++i) 
     result[i] = (3*i - 1)/2; 
    return result; 
} 

int main() 
{ 
    constexpr auto arr = make_constexpr_array(std::integral_constant<int, 6>{}); 
    static_assert(arr[0] == 0); 
    static_assert(arr[1] == 1); 
    static_assert(arr[2] == 2); 
    static_assert(arr[3] == 4); 
    static_assert(arr[4] == 5); 
    static_assert(arr[5] == 7); 
}