递归函数加 std::map 缓存后更慢，因子问题无重叠、键不可哈希或缓存访问开销超收益；应优先用 std::unordered_map，确保键可哈希，避免无条件查表，合理控制缓存粒度与生命周期，并以性能分析为优化依据。
为什么递归函数加 std::map 缓存后反而更慢？
不是所有递归都适合 memoization，关键看子问题是否重叠、状态是否可哈希、缓存访问开销是否压倒重复计算成本。比如 fibonacci(n) 天然重叠，但若参数是浮点数、指针或自定义不可哈希类型，std::map 或 std::unordered_map 会因键构造/哈希/比较变慢，甚至编译失败。
实操建议：
- 优先用
std::unordered_map（平均 O(1)），但必须确保键类型支持std::hash和operator==；整数、字符串、std::pair<int int></int>没问题，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）：
立即学习“C++免费学习笔记（深入）”；
template<typename F>
auto memoize(F&& f) {
using Func = std::decay_t<F>;
using Ret = typename std::invoke_result_t<Func&>;
std::unordered_map<std::size_t, Ret> cache;
return [f = std::forward<F>(f), cache = std::move(cache)]
(auto&&... args) mutable -> Ret {
auto key = std::hash<std::string>{}(std::to_string(sizeof...(args)) +
std::to_string((std::hash<decltype(args)>{}(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)>(args)...);
cache[key] = result;
return result;
};
}
注意：上面 key 构造是示意，真实项目中推荐用 std::tuple 封装参数并实现专用哈希（或用 Boost.Hash）。直接拼字符串或异或哈希易冲突，尤其当参数含零值时。
static 局部变量缓存 vs 类成员缓存：选哪个？
缓存生命周期决定复用范围。用 static 局部变量最轻量，但所有调用共享同一缓存，不适合多线程或需要隔离上下文的场景；类成员缓存则绑定实例，可控但需管理对象生命周期。
常见选择依据：
- 纯函数、无副作用、参数范围固定（如
int n在 0–1000）→ 用static std::unordered_map<int int> cache;</int>最简 - 需并发安全 → 加
mutable std::shared_mutex和读写锁，或改用线程局部存储（thread_local），但后者无法跨线程复用 - 缓存需随输入配置变化（如不同精度要求）→ 必须放类里，配合构造参数初始化
- 递归深度大、中间结果多 → 避免
static导致内存常驻，考虑作用域内临时缓存（如函数参数传入std::unordered_map&）
什么时候该放弃 memoization？
缓存不是银弹。以下情况加了反而负优化：
- 子问题几乎不重叠（如每次参数都唯一），缓存命中率长期低于 5%，哈希+插入开销 > 节省的计算时间
- 单次调用即结束（如命令行工具只算一次），缓存毫无意义
- 参数空间极大且稀疏（如
int64_t x, y），unordered_map占用内存爆炸，还可能触发 rehash 拖慢单次操作 - 原始计算本身极快（如几个加法），缓存的分支判断和指针跳转比直接算还慢
真正关键的是先 profile：用 gprof 或 perf 看递归函数自身耗时占比、调用频次、是否热点；再对比加缓存前后 wall time 和 cache miss rate。没数据就加 memo，大概率在给代码埋坑。
