Szablony w C++ - Fibonacci

Hej!

A jakby połączyć szablony z C++ z programowaniem funkcyjnym rodem z F#?

Niesamowity pomysł, spróbujmy zaimplementować liczby Fibonacciego z użyciem mechanizmy szablonów C++!

Wykorzystamy częściowe specjalizacje szablonów i technikę tzw. metaprogramowania, a nasz wynik zostanie wyliczony już w czasie kompilacji. Brzmi fajniej niż wektor elementów typu T, co?

Rzućmy najpierw okiem na kod (działa i pod Visual C++ i pod g++), a potem pomyślmy dlaczego i jak to coś działa.

#include <iostream>

using namespace std;

typedef unsigned long long uint64;


template<int n>
struct Fib
{
  static const uint64 val = Fib<n-1>::val + Fib<n-2>::val;
};

template<>
struct Fib<0>
{
  static const uint64 val = 0;
};

template<>
struct Fib<1>
{
  static const uint64 val = 1;
};

int main()
{
  cout << Fib<93>::val << endl;
  return 0;
}

OK, czyli co widzimy:
1. Naszą "funkcją" jest struktura Fib, a argumentem jest parametr szablonu.
2. Wartość zwracana jest zapisywana w statycznym stałym polu.

Zapisujemy kroki początkowe (Fib(0) = 0, Fib(1) = 1), krok indukcyjny (Fib(n) = Fib(n-2) + Fib(n-1)) i... resztę robi za nas mechanizm specjalizacji szablonów, rekurencyjnie wykonujący kolejne specjalizacje!

Prześledźmy to dla Fib<4>::val:
Fib<4>::val
= Fib<3>::val + Fib<2>::val
= Fib<2>::val + Fib<1>::val + Fib<1>::val + Fib<0>::val
= Fib<1>::val + Fib<0>::val + Fib<1>::val + Fib<1>::val + Fib<0>::val
= 1 + 0 + 1 + 1 + 0
= 3

Czyli klasyczne wywołania rekurencyjne... Ale chwilę! Przeciez program powyżej wylicza 93. wyraz ciągu (więcej się nie mieści na 64 bitach, o czym Visual ostrzega zresztą) - czy nie potrwa, hm, długo?

Klasyczny Fibonacci w C++:

uint64 fib(int n)
{
  if (n == 0)
  {
    return 0;
  }
  if (n == 1)
  {
    return 1;
  }
  return fib(n-2) + fib(n-1);
}

wyliczenie już 43. wyrazu ciągu trwa u mnie jakieś 10 sekund - to co można powiedzieć o wyrazie o 50 dalszym? Dlaczego kompilacja trwa tak krótko?

Ponieważ kompilator każdy szablon konkretyzuje tylko raz - to tak, jakbyśmy nasze wyniki trzymali w tymczasowej tablicy. A tutaj mamy to wszystko za darmo!

Takiego zastosowania szablonów chyba nikt się nie spodziewał :)

Więcej o metaprogramowaniu w C++: http://mediawiki.ilab.pl/index.php/Zaawansowane_CPP/Wyk%C5%82ad_8:_Metaprogramowanie