読者です 読者をやめる 読者になる 読者になる

Boost.Flyweightでメモ化

C++

Boost.Flyweightのexampleにあるやつです。

#include <iostream>
#include <boost/flyweight.hpp>
#include <boost/flyweight/key_value.hpp>
#include <boost/flyweight/no_tracking.hpp>
#include <boost/noncopyable.hpp>

using namespace boost::flyweights;

struct compute_fibonacci;

typedef flyweight<key_value<int, compute_fibonacci>, no_tracking> fibonacci;

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()
{
    for (int n = 0; n < 40; ++n)
        std::cout << "F(" << n << ")=" << fibonacci(n) << std::endl;
}