C++如何实现计算结果的Memoization缓存 _ 极大提升递归效率【实战】-C++-PHP中文网

递归函数加 std::map 缓存后更慢，因子问题无重叠、键不可哈希或缓存访问开销超收益；应优先用 std::unordered_map，确保键可哈希，避免无条件查表，合理控制缓存粒度与生命周期，并以性能分析为优化依据。

c++如何实现计算结果的memoization缓存 _ 极大提升递归效率【实战】

为什么递归函数加 `std::map` 缓存后反而更慢？

不是所有递归都适合 memoization，关键看子问题是否重叠、状态是否可哈希、缓存访问开销是否压倒重复计算成本。比如 fibonacci(n) 天然重叠，但若参数是浮点数、指针或自定义不可哈希类型，std::map 或 std::unordered_map 会因键构造/哈希/比较变慢，甚至编译失败。

实操建议：

优先用 std::unordered_map（平均 O(1)），但必须确保键类型支持 std::hash 和 operator==；整数、字符串、std::pair 没问题，std::vector 默认不支持哈希，需自定义或改用 std::map
避免在递归入口无条件查表——先检查是否已存在，再决定是否计算；否则每次调用都触发一次哈希查找，白费开销
缓存粒度要匹配：例如 lcs(s1, s2) 用二维索引 std::make_pair(i, j) 作键，别把整个 std::string 当 key 传

如何用 `std::function` + lambda 实现泛型 memo 包装器？

手写每个函数的缓存逻辑太重复。一个通用方案是把原函数包装成带缓存的闭包，利用 lambda 捕获局部 std::unordered_map，同时保持类型安全。

示例（C++17）：

template<typename f>
auto memoize(F&& f) {
    using Func = std::decay_t<f>;
    using Ret = typename std::invoke_result_t<func>;
    std::unordered_map<:size_t ret> cache;
    return [f = std::forward<f>(f), cache = std::move(cache)]
           (auto&&... args) mutable -> Ret {
        auto key = std::hash<:string>{}(std::to_string(sizeof...(args)) + 
                                            std::to_string((std::hash<decltype>{}(args) ^ ...)));
        // ⚠️ 简化示意，实际应基于参数值构造唯一 key（如用 tuple + hash）
        auto it = cache.find(key);
        if (it != cache.end()) return it->second;
        Ret result = std::invoke(f, std::forward<decltype>(args)...);
        cache[key] = result;
        return result;
    };
}</decltype></decltype></:string></f></:size_t></func></f></typename>

注意：上面 key 构造是示意，真实项目中推荐用 std::tuple 封装参数并实现专用哈希（或用 Boost.Hash）。直接拼字符串或异或哈希易冲突，尤其当参数含零值时。