CODEWITHSUNDEEP
c++c++11templatestemplate-meta-programmingtemplate-specialization
Nick
Nick

Reputation: 10539

calculating data compile time with template metaprogramming

Suppose we have code like this. It works well and pre-calculate first 5 Fibonacci numbers.

#include <iostream>

template <int T>
struct fib;

template <>
struct fib<0>{
    constexpr static int value = 1;
};

template <>
struct fib<1>{
   constexpr static int value = 1;
};

template <int I>
struct fib{
   constexpr static int value = fib<I - 1>::value + fib<I - 2>::value;
};

int main(){
    std::cout << fib<0>::value << std::endl;
    std::cout << fib<1>::value << std::endl;
    std::cout << fib<2>::value << std::endl;
    std::cout << fib<3>::value << std::endl;
    std::cout << fib<4>::value << std::endl;
    std::cout << fib<5>::value << std::endl;
}

However there is "small" problem with it.

What if we need to use this for values, that are not known at compile time?

For few values we can do this:

const int max = 5;

int getData(){
   return 5; // return value between 0 and max.
}

int something(){
   switch(getData()){
      case 0: return fib<0>::value;
      case 1: return fib<1>::value;
      case 2: return fib<2>::value;
      case 3: return fib<3>::value;
      case 4: return fib<4>::value;
      case 5: return fib<5>::value;
   }
}

This will works OK for 5 values, but what if we have 150 or 300?
Is not really serious to change the code with 300 rows...

What could be the workaround here?

Upvotes: 4

Views: 159

Answers (2)

max66
max66

Reputation: 66200

If you need to use a value at runtime that isn't known at compile time, you can't compute it at compile time. Obvious.

But... if you can impose a top value to values needed, you can compute all values (from zero to top) at compile time and store them in an std::array.

In the following example I have modified your fib structs (to use a std::size_t index and a template type (with default unsigned long) for the value) and I have added a templated struct fibVals that contain an std::array that is initialized using fib<n>::value

The following main() show that is possible to define a constexpr fibvals<N> (with N == 20 in the example) to compute (at compile time) all fib<n> values in range [0,N[.

#include <array>
#include <utility>
#include <iostream>

template <std::size_t, typename T = unsigned long>
struct fib;

template <typename T>
struct fib<0U, T>
 { constexpr static T value { T(1) }; };

template <typename T>
struct fib<1U, T>
 { constexpr static T value { T(1) }; };

template <std::size_t I, typename T>
struct fib
 { constexpr static T value { fib<I-1U>::value + fib<I-2U>::value }; };

template <std::size_t I, typename T = unsigned long>
struct fibVals
 {
   const std::array<T, I>  vals;

   template <std::size_t ... Is>
   constexpr fibVals ( std::index_sequence<Is...> const & )
      : vals { { fib<Is, T>::value ... } }
    { }

   constexpr fibVals () : fibVals { std::make_index_sequence<I> { } }
    { }
 };


int main()
 {
   constexpr fibVals<20>  fv;

   for ( auto ui = 0U ; ui < fv.vals.size() ; ++ui )
      std::cout << "fib(" << ui << ") = " << fv.vals[ui] << std::endl;
 }

Unfortunately this example use std::make_index_sequence<I> and std::index_sequence<Is...> that are C++14 features.

If you want implement struct fibVals in C++11, you can implement the following structs struct indexSeq and struct indexSeqHelper, to substitute std::index_sequence<Is...> and std::make_index_sequence<I>

template <std::size_t ...>
struct indexSeq
 { };

template <std::size_t N, std::size_t ... Next>
struct indexSeqHelper
 { using type = typename indexSeqHelper<N-1U, N-1U, Next ... >::type; };

template <std::size_t ... Next >
struct indexSeqHelper<0U, Next ... >
 { using type = indexSeq<Next ... >; };

and implement fibVals constructors as follows

template <std::size_t ... Is>
constexpr fibVals ( indexSeq<Is...> const & )
   : vals { { fib<Is, T>::value ... } }
 { }

constexpr fibVals () : fibVals { typename indexSeqHelper<I>::type { } }
 { }

Upvotes: 4

Rakete1111
Rakete1111

Reputation: 48948

Templates are evaluated at compile time, so there is no solution with templates that works at runtime.

You can make a constexpr function, which may be evaluated at compile time, depending on the value passed. Obviously, a runtime value may not be computed at compile time, as it is not known at compile time.

Upvotes: 1

Related Questions