Sequence range unroll, using variadic templates

Question

Let's assume, I have some sequence, e.g. Fibonacci numbers, defined as a template:

template <unsigned int N> struct Fibonacci { unsigned int value = /*...*/; };

What I need is to obtain constexpr array with the first N elements of this sequence. I can do it, using variadic template:

template <unsigned int ... Numbers>
struct FibArray
{
    static constexpr array<unsigned int, sizeof...(Numbers)> value = { Fibonacci<Numbers>::value... };
};
// and then:
const auto fib_array = FibArray<1, 2, 3, 4, 5, 6, 7>::value;

Is it possible, to avoid manual enumeration of indexes, and get the same array with just a number of required values? Something like this:

const array<unsigned, 7> fib_array = GetFirstNFibValues<7>::value;

Xeo · Accepted Answer · 2012-10-12T14:34:08.173

5

You can get this behaviour by generating the indices:

template<unsigned...> struct indices{};

template<unsigned N, unsigned... Indices>
struct indices_gen : indices_gen<N-1, N-1, Indices...>{};

template<unsigned... Indices>
struct indices_gen<1, Indices...>{
  using type = indices<1, Indices...>;
};

#include <array>

template<unsigned N>
struct fibonacci{
  static constexpr unsigned value = N; // yes, lazyness on my part
};

template<class IPack>
struct first_n_fib_impl;

template<unsigned... Is>
struct first_n_fib_impl<indices<Is...>>
{
  using arr_type = std::array<unsigned, sizeof...(Is)>;
  static constexpr arr_type value = {{ fibonacci<Is>::value... }};
};

template<unsigned... Is>
constexpr std::array<unsigned, sizeof...(Is)> first_n_fib_impl<indices<Is...>>::value;

template<unsigned N>
struct first_n_fib
  : first_n_fib_impl<typename indices_gen<N>::type>
{
};

Live example (to show that [1..7] is indeed generated).

edited Oct 12 '12 at 14:34

answered Oct 03 '12 at 11:32

Xeo

129,499
52
291
397

I'm still reading your solution, so, I'll post my feedback later, but about you last notice - I can, actually, have static constexpr array inside class in g++-4.7.1 (but can't in icc). I don't know - whether it is some kind of non-standard extension in gcc, or just icc incomplete constexpr implementation (intel documents says constexpr feature is incomplete in 13.0, but doesn't say what was omitted) – Vasily Oct 03 '12 at 12:01
@Vasily: I actually tried a `static constexpr` array in the class with GCC 4.7.2 (on LWS, linked in my answer) and it complained about unresolved external symbol, but maybe that's because I used a reference to it in the ranged-for loop... hm. – Xeo Oct 03 '12 at 12:03
Yes. I see it. I can use this array, for example, to define array size `int arr[Struct::stat_arr[2]];`, but i can't use it in any for loop (range-based, or not). But i can use this array, to create another, using copy-constructor: `array myarray(Struct::stat_arr)`. I can't explain this – Vasily Oct 03 '12 at 12:25
@Vasily: Well, that's just how it works for POD types. :) Don't think too much about it, just stuff it in a `constexpr` function. – Xeo Oct 03 '12 at 12:27
I don't wanna use any loopholes just to make code works, where it should work without problems. I want to understand the cause. And I never saw this behavior with POD types. BTW, it works just fine, if static constexpr array was declared outside the class. – Vasily Oct 03 '12 at 12:38
Well, it looks like your solution works for my task, so, thank you. I'll maybe ask another question about static member issue. – Vasily Oct 03 '12 at 12:44
@Vasily: If you define it out-iof-class, I don't think you can still use it as an array size (without that array becoming a VLA in GCC) or any other context where a constant expression is needed. – Xeo Oct 03 '12 at 12:45
BTW, how are you answering me with "@Vasily" appeal? – Vasily Oct 03 '12 at 13:04
@Vasily: What exactly do you mean? I just type it. :) If you're writing "@Xeo" and wondering why it doesn't show up in your comments, well, this is my answer so I already get notified about your comment. :) – Xeo Oct 03 '12 at 13:06
http://stackoverflow.com/questions/8452952/c-linker-error-with-class-static-constexpr - this is actually an answer for static constexpr array issue – Vasily Oct 03 '12 at 13:28
I've found a solution for in-class static constexpr array: In order to use it in code and keep constexprness, you must initialize it inside the class, and then declare it (without initialization) in any c++ file. So, it looks like no loopholes are needed anymore. – Vasily Oct 03 '12 at 13:38
To clarify: a `constexpr` static data member always needs an in-class initializer (all `constexpr` variables need initializers), but what's in the class is still only a declaration. If the member is ODR-used, an implementation may need a definition. This definition can be provided just like any static data member (C++03 `const`integral constants have been following the same rules). [Modified example](http://liveworkspace.org/code/e8e4ce2152367d927dc018eefba3495e). – Luc Danton Oct 03 '12 at 15:38
Yeah, it's an explanation for the issue. It's odd I never encountered this issue before. – Vasily Oct 04 '12 at 07:17

Sequence range unroll, using variadic templates

1 Answers1