C++ Calcolo dei fattori


Esempio

I fattoriali possono essere calcolati in fase di compilazione utilizzando tecniche di metaprogrammazione del modello.

#include <iostream>

template<unsigned int n>
struct factorial
{
    enum
    {
        value = n * factorial<n - 1>::value
    };
};

template<>
struct factorial<0>
{
    enum { value = 1 };
};

int main()
{
    std::cout << factorial<7>::value << std::endl;    // prints "5040"
}

factorial è una struttura, ma nella metaprogrammazione del modello viene considerata una metafunzione del modello. Per convenzione, i metafunzionamenti dei template vengono valutati controllando un particolare membro, ::type per i metafunzioni che danno come risultato tipi: ::value per metafuntion che generano valori.

Nel codice sopra, valutiamo la metafunzione factorial istanziando il modello con i parametri che vogliamo passare, e usando il ::value per ottenere il risultato della valutazione.

La metafunzione stessa si basa sull'istanza ricorsiva della stessa metafunzione con valori più piccoli. La specializzazione factorial<0> rappresenta la condizione di chiusura. La metaprogrammazione dei modelli ha la maggior parte delle restrizioni di un linguaggio di programmazione funzionale , quindi la ricorsione è il costrutto di "looping" primario.

Poiché i metafuncoli del modello vengono eseguiti in fase di compilazione, i risultati possono essere utilizzati in contesti che richiedono valori in fase di compilazione. Per esempio:

int my_array[factorial<5>::value];

Gli array automatici devono avere una dimensione definita in fase di compilazione. E il risultato di una metafunzione è una costante in fase di compilazione, quindi può essere utilizzata qui.

Limitazione : la maggior parte dei compilatori non consente la profondità di ricorsione oltre un limite. Ad esempio, il compilatore g++ per impostazione predefinita limita la ricorsione a 256 livelli. Nel caso di g++ , il programmatore può impostare la profondità della ricorsione usando l' -ftemplate-depth-X .

C ++ 11

Dal momento che C ++ 11, il modello std::integral_constant può essere utilizzato per questo tipo di calcolo del modello:

#include <iostream>
#include <type_traits>

template<long long n>
struct factorial :
  std::integral_constant<long long, n * factorial<n - 1>::value> {};

template<>
struct factorial<0> :
  std::integral_constant<long long, 1> {};

int main()
{
    std::cout << factorial<7>::value << std::endl;    // prints "5040"
}

Inoltre, constexpr funzioni di constexpr diventano un'alternativa più pulita.

#include <iostream>

constexpr long long factorial(long long n)
{
  return (n == 0) ? 1 : n * factorial(n - 1);
}

int main()
{
  char test[factorial(3)];
  std::cout << factorial(7) << '\n';
}

Il corpo di factorial() è scritto come una singola istruzione perché in C ++ 11 constexpr funzioni di constexpr possono usare solo un sottoinsieme piuttosto limitato della lingua.

C ++ 14

Dal momento che C ++ 14, molte restrizioni per constexpr funzioni di constexpr sono state eliminate e ora possono essere scritte in modo molto più pratico:

constexpr long long factorial(long long n)
{
  if (n == 0)
    return 1;
  else
    return n * factorial(n - 1);
}

O anche:

constexpr long long factorial(int n)
{
  long long result = 1;
  for (int i = 1; i <= n; ++i) {
    result *= i;
  }
  return result;
}
C ++ 17

Dal momento che c ++ 17 si può usare espressione di piega per calcolare fattoriale:

#include <iostream>
#include <utility>

template <class T, T N, class I = std::make_integer_sequence<T, N>>
struct factorial;

template <class T, T N, T... Is>
struct factorial<T,N,std::index_sequence<T, Is...>> {
   static constexpr T value = (static_cast<T>(1) * ... * (Is + 1));
};

int main() {
   std::cout << factorial<int, 5>::value << std::endl;
}