12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758 |
- /* Boost.Flyweight example of flyweight-based memoization.
- *
- * Copyright 2006-2008 Joaquin M Lopez Munoz.
- * Distributed under the Boost Software License, Version 1.0.
- * (See accompanying file LICENSE_1_0.txt or copy at
- * http://www.boost.org/LICENSE_1_0.txt)
- *
- * See http://www.boost.org/libs/flyweight for library home page.
- */
- #include <boost/flyweight.hpp>
- #include <boost/flyweight/key_value.hpp>
- #include <boost/flyweight/no_tracking.hpp>
- #include <boost/noncopyable.hpp>
- #include <iostream>
- using namespace boost::flyweights;
- /* Memoized calculation of Fibonacci numbers */
- /* This class takes an int n and calculates F(n) at construction time */
- struct compute_fibonacci;
- /* A Fibonacci number can be modeled as a key-value flyweight
- * We choose the no_tracking policy so that the calculations
- * persist for future use throughout the program. See
- * Tutorial: Configuring Boost.Flyweight: Tracking policies for
- * further information on tracking policies.
- */
- typedef flyweight<key_value<int,compute_fibonacci>,no_tracking> fibonacci;
- /* Implementation of compute_fibonacci. Note that the construction
- * of compute_fibonacci(n) uses fibonacci(n-1) and fibonacci(n-2),
- * which effectively memoizes the computation.
- */
- struct compute_fibonacci:private boost::noncopyable
- {
- compute_fibonacci(int n):
- result(n==0?0:n==1?1:fibonacci(n-2).get()+fibonacci(n-1).get())
- {}
- operator int()const{return result;}
- int result;
- };
- int main()
- {
- /* list some Fibonacci numbers */
- for(int n=0;n<40;++n){
- std::cout<<"F("<<n<<")="<<fibonacci(n)<<std::endl;
- }
- return 0;
- }
|