用于函数输出的C++简单缓存设计

Question

我认为这是众所周知的解决方案的一个常见问题,我无法找到.所以我在这里寻求建议.

问题陈述

请考虑以下设置:

class A; // some class

const A f(const A&); // an _expensive_ function

void do_stuff()
{
    A a;

    a.modify(...);

    do_stuff1(f(a));  // compute f(a)
    do_stuff2(f(a));  // use cached value of f(a)

    a.modify(...);

    do_stuff3(f(a));  // recompute f(a)
}

我想f(a)在第一次和第二次调用之间缓存返回值,但是在第二次调用之后要被丢弃a.modify(). 编辑:在实践中,调用f(a)将在不同的范围内.

以下是我探索过的解决方案,以及它的价值.

解决方案1:中央缓存

使用时间戳

我可以想象一个简单的解决方案,包括向类添加时间戳,A该函数f可以检查并确定是否需要更新其缓存结果,存储在中央缓存中的某个位置.我想这也意味着将签名f改为:

const A& f(const A&);

问题1:使用中央缓存,我们需要一种机制来销毁被销毁f(a)时的缓存结果a.

使用哈希码

除了问题1,这似乎很简单.但是当它A 代表时它会变得复杂std::vector<...>.我想这里应该排除动态多态性.因此,我们忘记了为子类添加时间戳std::vector<...>以及它所暗示的所有重写.但是,我们可以根据a--- 的内容计算一些哈希码或UUID,假设它比计算便宜得多 f(a),并将中央缓存基于这些哈希码.但我们再次面临问题1.

解决方案2:耦合对象

我还没有找到如何实现这一点,但这个想法是有a通知的缓存f(a)时,a写入或破坏,而不是在它仅仅是读取.我不知道如何在没有动态多态的情况下做到这一点,并且不operator[]通过向每个修改元素的缓存发送通知来减慢使用或迭代器的单元素访问.

问题2:找到一种分隔更改集的机制,以便a为每组更改仅使缓存无效一次.

我已经考虑过代理来启用写访问a(受到互斥体概念的启发),但是无法提供任何有效的代码.

有任何想法吗？

Answer 1

我已经用这样的接口做了类似的事情：

class F
{
public:
 virtual int f(int a)=0;
};

class Cache : public F
{
public:
   Cache(F &f) : f(f) { }
   int f(int a) { /*caching logic here, calls f.f() if not found from cache */ }
   F &f;
};

class Impl : public F
{
   int f(int a) { /* real implementation here */ }
};

然后它只是决定在哪里使用缓存逻辑：

   Impl i; 
   Cache c(i);
   c.f(10); // put to cache with key 10
   c.f(10); // found from cache
   c.f(11); // put to cache with key 11