C++实现LRUCache装饰器：递归函数缓存失效问题求解

在Python中，@functools.lru_cache装饰器可以轻松为递归函数实现记忆化，大幅提升递归效率。但在C++中，常规的缓存包装类处理递归函数时会遇到问题：递归调用不会经过缓存逻辑，导致缓存命中率为0，完全起不到优化作用。

原实现代码 #

LRUCache类（核心缓存实现） #

template <typename Key, typename Val>
class LRUCache
{
public:
    LRUCache( int capacity = 100 ) : capacity{ capacity } {}

    Val get( Key key ) {... }    
    void put( Key key, Val value ) {... } 
    ...

private:
    int capacity;
    std::list<std::pair<Val, Key>> CACHE;
    std::unordered_map<Key, typename std::list<std::pair<Val, Key>>::iterator> LOOKUP;
};

_LruCacheFunctionWrapper类（函数包装器） #

template <typename Key, typename Val>
class _LruCacheFunctionWrapper
{
    struct CacheInfo {... };

public:
    _LruCacheFunctionWrapper( std::function<Val( Key )> func, int maxSize ) 
        : _wrapped{ func }
        , _cache{ maxSize }
        , _hits{ 0 }
        , _misses{ 0 }
        , _maxsize{ maxSize }
    {}

    template<typename... Args>
    Val operator()( Args... args )
    {
        auto res = _cache.get( args... );

        if( res == -1 )
        {
            ++_misses;
            res = _wrapped( args... );
            _cache.put( args..., res );
        }
        else
            ++_hits;

        return res;
    }

    CacheInfo getCacheInfo() {... }   
    void clearCache() {... }

private:
    std::function<Val( Key )> _wrapped;
    LRUCache<Key, Val> _cache;
    int _hits;
    int _misses;
    int _maxsize;
};

递归目标函数（斐波那契） #

long long fib( int n )
{
    if( n < 2 )
        return n;
    return fib( n - 1 ) + fib( n - 2 );
}

调用代码 #

_LruCacheFunctionWrapper<int, long long> wrapper( &fib, 50 );

for( auto i = 0; i < 16; ++i )
    std::cout << wrapper( i ) << " ";

问题根源 #

当前实现中，包装器的_wrapped存储的是原始fib函数指针。当调用_wrapped(args...)时，递归调用的是未被包装的原始fib函数，完全绕过了缓存逻辑。所有递归步骤都需要重新计算，导致缓存命中率为0。

解决方案 #

方案1：让递归函数依赖外部可调用对象（推荐） #

修改递归函数，使其接受一个可调用对象作为递归入口，这样所有递归调用都会指向带缓存的包装器：

// 改写后的递归实现，依赖外部传入的递归入口
long long fib_impl( int n, const std::function<long long(int)>& recursive_func )
{
    if( n < 2 )
        return n;
    // 递归调用传入的可调用对象，而非自身
    return recursive_func( n - 1 ) + recursive_func( n - 2 );
}

调整包装器，在构造时生成捕获自身的std::function，传递给递归实现：

template <typename Key, typename Val>
class _LruCacheFunctionWrapper
{
    struct CacheInfo {... };

public:
    // 构造函数接受带递归入口参数的函数
    _LruCacheFunctionWrapper( std::function<Val(Key, const std::function<Val(Key)>&)> impl_func, int maxSize ) 
        : _impl_func{ impl_func }
        , _cache{ maxSize }
        , _hits{ 0 }
        , _misses{ 0 }
        , _maxsize{ maxSize }
    {
        // 生成捕获当前包装器的lambda，作为递归入口
        _recursive_func = [this](Key key) {
            return (*this)(key);
        };
    }

    Val operator()( Key key )
    {
        auto res = _cache.get( key );

        if( res == -1 )
        {
            ++_misses;
            // 调用递归实现，传入带缓存的递归入口
            res = _impl_func( key, _recursive_func );
            _cache.put( key, res );
        }
        else
            ++_hits;

        return res;
    }

    CacheInfo getCacheInfo() {... }   
    void clearCache() {... }

private:
    std::function<Val(Key, const std::function<Val(Key)>&)> _impl_func;
    std::function<Val(Key)> _recursive_func;
    LRUCache<Key, Val> _cache;
    int _hits;
    int _misses;
    int _maxsize;
};

调用方式：

_LruCacheFunctionWrapper<int, long long> wrapper( fib_impl, 50 );

for( auto i = 0; i < 16; ++i )
    std::cout << wrapper( i ) << " ";

这种方式保留了包装器的灵活性，可以为不同场景配置不同缓存大小，也支持清空特定实例的缓存，同时让所有递归调用都经过缓存逻辑。

方案2：静态缓存（简单但不灵活） #

如果不想修改递归函数签名，可以将缓存作为函数内部的静态变量，但这样函数会变成有状态的，无法创建多个独立的缓存实例：

long long fib( int n )
{
    static LRUCache<int, long long> cache(50); // 静态缓存，全局唯一
    auto res = cache.get(n);
    if(res == -1) {
        res = (n < 2) ? n : fib(n-1) + fib(n-2);
        cache.put(n, res);
    }
    return res;
}

这种实现简单，但缺乏灵活性，无法动态调整缓存大小，也无法独立管理多个缓存实例。

总结 #

问题的核心是原始递归函数调用的是自身而非带缓存的包装器，解决的关键是让递归调用指向包装器的缓存逻辑。推荐使用方案1，通过让递归函数依赖外部可调用对象，在保留包装器灵活性的同时，确保所有递归步骤都能命中缓存。

内容的提问来源于stack exchange，提问作者user2376997