通用非侵入式缓存包装器

Question

我正在尝试创建一个类,它为泛型类添加功能,而不直接与包装类接口.一个很好的例子是智能指针.具体来说,我想创建一个包装器来缓存通过包装器调用的一个(或任何？)方法的所有i/o.理想情况下,缓存包装器具有以下属性:

• 它不需要以任何方式更改包装类(即通用)
• 它不需要以任何方式更改包装类(即通用)
• 它不会显着改变使用该对象的界面或语法

例如,像这样使用它真的很好:

CacheWrapper<NumberCruncher> crunchy;
...
// do some long and ugly calculation, caching method input/output
result = crunchy->calculate(input); 
...
// no calculation, use cached result
result = crunchy->calculate(input); 

虽然像这样的傻瓜会没问题:

result = crunchy.dispatch (&NumberCruncher::calculate, input);

我觉得这应该可以在C++中实现,尽管可能在某个地方有一些句法体操.

有任何想法吗？

Answer 1

我想我已经找到了你正在寻找的答案，或者至少，我几乎找到了。它使用您建议的调度风格是愚蠢的，但我认为它满足您提出的前两个标准，并且或多或少满足第三个标准。

1. 包装类根本不需要修改。
2. 它根本不修改包装的类。
3. 它只是通过引入调度函数来改变语法。

基本思想是创建一个模板类，其参数是要包装的对象的类，并带有一个模板dispatch方法，其参数是成员函数的参数和返回类型。调度方法查找传入的成员函数指针以查看它之前是否被调用过。如果是这样，它将检索先前方法参数和计算结果的记录，以返回给定调度的参数的先前计算值，或者如果它是新的，则计算它。

由于这个包装类所做的也称为memoization，所以我选择调用模板，Memo因为它的输入时间比模板短CacheWrapper，而且我在晚年开始更喜欢较短的名称。

#include <algorithm>
#include <map>
#include <utility>
#include <vector>

// An anonymous namespace to hold a search predicate definition. Users of
// Memo don't need to know this implementation detail, so I keep it
// anonymous. I use a predicate to search a vector of pairs instead of a
// simple map because a map requires that operator< be defined for its key
// type, and operator< isn't defined for member function pointers, but
// operator== is.
namespace {
    template <typename Type1, typename Type2>
    class FirstEq {
        FirstType value;

    public:
        typedef std::pair<Type1, Type2> ArgType;

        FirstEq(Type1 t) : value(t) {}

        bool operator()(const ArgType& rhs) const { 
            return value == rhs.first;
        }
    };
};

template <typename T>
class Memo {
    // Typedef for a member function of T. The C++ standard allows casting a
    // member function of a class with one signature to a type of another
    // member function of the class with a possibly different signature. You
    // aren't guaranteed to be able to call the member function after
    // casting, but you can use the pointer for comparisons, which is all we
    // need to do.
    typedef void (T::*TMemFun)(void);

    typedef std::vector< std::pair<TMemFun, void*> > FuncRecords;

    T           memoized;
    FuncRecords funcCalls;

public:
    Memo(T t) : memoized(t) {}

    template <typename ReturnType, typename ArgType>
    ReturnType dispatch(ReturnType (T::* memFun)(ArgType), ArgType arg) {

        typedef std::map<ArgType, ReturnType> Record;

        // Look up memFun in the record of previously invoked member
        // functions. If this is the first invocation, create a new record.
        typename FuncRecords::iterator recIter = 
            find_if(funcCalls.begin(),
                    funcCalls.end(),
                    FirstEq<TMemFun, void*>(
                        reinterpret_cast<TMemFun>(memFun)));

        if (recIter == funcCalls.end()) {
            funcCalls.push_back(
                std::make_pair(reinterpret_cast<TMemFun>(memFun),
                               static_cast<void*>(new Record)));
            recIter = --funcCalls.end();
        }

        // Get the record of previous arguments and return values.
        // Find the previously calculated value, or calculate it if
        // necessary.
        Record*                   rec      = static_cast<Record*>(
                                                 recIter->second);
        typename Record::iterator callIter = rec->lower_bound(arg);

        if (callIter == rec->end() || callIter->first != arg) {
            callIter = rec->insert(callIter,
                                   std::make_pair(arg,
                                                  (memoized.*memFun)(arg)));
        }
        return callIter->second;
    }
};

这是一个显示其用途的简单测试：

#include <iostream>
#include <sstream>
#include "Memo.h"

using namespace std;

struct C {
    int three(int x) { 
        cout << "Called three(" << x << ")" << endl;
        return 3;
    }

    double square(float x) {
        cout << "Called square(" << x << ")" << endl;
        return x * x;
    }
};

int main(void) {
    C       c;
    Memo<C> m(c);

    cout << m.dispatch(&C::three, 1) << endl;
    cout << m.dispatch(&C::three, 2) << endl;
    cout << m.dispatch(&C::three, 1) << endl;
    cout << m.dispatch(&C::three, 2) << endl;

    cout << m.dispatch(&C::square, 2.3f) << endl;
    cout << m.dispatch(&C::square, 2.3f) << endl;

    return 0;
}

它在我的系统上产生以下输出（使用 g++ 4.0.1 的 MacOS 10.4.11）：

叫三（1）
3
叫三（2）
3
3
3
称为正方形(2.3)
5.29
5.29

笔记

• 这仅适用于采用 1 个参数并返回结果的方法。它不适用于采用 0 个参数、2 个、3 个或更多参数的方法。不过，这应该不是什么大问题。您可以实现调度的重载版本，它采用不同数量的参数，最多可达某个合理的最大值。这就是Boost Tuple 库的作用。他们实现最多包含 10 个元素的元组，并假设大多数程序员不需要更多元素。
• 为调度实现多个重载的可能性是我使用 FirstEq 谓词模板和 find_if 算法而不是简单的 for 循环搜索的原因。单次使用的代码会多一些，但如果您要多次执行类似的搜索，最终会导致整体代码更少，并且其中一个循环出现细微错误的机会也更少。
• 它不适用于不返回任何内容的方法，即void，但如果该方法不返回任何内容，则不需要缓存结果！
• 它不适用于包装类的模板成员函数，因为您需要传递实际的成员函数指针来调度，而未实例化的模板函数还没有指针。可能有办法解决这个问题，但我还没有尝试过。
• 我还没有对此进行太多测试，因此它可能存在一些微妙（或不那么微妙）的问题。
• 我认为在 C++ 中不可能有一个完全无缝的解决方案，无需更改语法即可满足您的所有要求。（尽管我很乐意被证明是错误的！）希望这足够接近。
• 当我研究这个答案时，我从这篇关于在 C++ 中实现成员函数委托的非常广泛的文章中得到了很多帮助。任何想要了解比他们意识到的更多关于成员函数指针的知识的人都应该好好阅读这篇文章。