1 /* Boost.Flyweight example of flyweight-based memoization. 2 * 3 * Copyright 2006-2008 Joaquin M Lopez Munoz. 4 * Distributed under the Boost Software License, Version 1.0. 5 * (See accompanying file LICENSE_1_0.txt or copy at 6 * http://www.boost.org/LICENSE_1_0.txt) 7 * 8 * See http://www.boost.org/libs/flyweight for library home page. 9 */ 10 11 #include <boost/flyweight.hpp> 12 #include <boost/flyweight/key_value.hpp> 13 #include <boost/flyweight/no_tracking.hpp> 14 #include <boost/noncopyable.hpp> 15 #include <iostream> 16 17 using namespace boost::flyweights; 18 19 /* Memoized calculation of Fibonacci numbers */ 20 21 /* This class takes an int n and calculates F(n) at construction time */ 22 23 struct compute_fibonacci; 24 25 /* A Fibonacci number can be modeled as a key-value flyweight 26 * We choose the no_tracking policy so that the calculations 27 * persist for future use throughout the program. See 28 * Tutorial: Configuring Boost.Flyweight: Tracking policies for 29 * further information on tracking policies. 30 */ 31 32 typedef flyweight<key_value<int,compute_fibonacci>,no_tracking> fibonacci; 33 34 /* Implementation of compute_fibonacci. Note that the construction 35 * of compute_fibonacci(n) uses fibonacci(n-1) and fibonacci(n-2), 36 * which effectively memoizes the computation. 37 */ 38 39 struct compute_fibonacci:private boost::noncopyable 40 { compute_fibonaccicompute_fibonacci41 compute_fibonacci(int n): 42 result(n==0?0:n==1?1:fibonacci(n-2).get()+fibonacci(n-1).get()) 43 {} 44 operator intcompute_fibonacci45 operator int()const{return result;} 46 int result; 47 }; 48 main()49int main() 50 { 51 /* list some Fibonacci numbers */ 52 53 for(int n=0;n<40;++n){ 54 std::cout<<"F("<<n<<")="<<fibonacci(n)<<std::endl; 55 } 56 57 return 0; 58 } 59