手动实现 memoization 需用 std::map 或 std::unordered_map 管理缓存，注意键类型需支持比较或哈希、缓存生命周期须覆盖所有调用、递归中检查必须在调用前、线程安全需加锁或读写锁。
用 std::map 或 std::unordered_map 手动缓存结果最直接
手动实现 memoization 的核心是：函数第一次调用时计算并存入缓存，后续相同参数直接返回缓存值。C++ 没有内置装饰器，所以得自己管键构造、查表、回填。
常见错误是把参数直接当 key 用——比如传入 std::vector 或自定义类型却没提供 operator（对 <code>std::map）或哈希函数（对 std::unordered_map），导致编译失败或行为未定义。
- 简单参数组合（如两个
int）推荐拼成std::pair<int int></int>，它自带比较和哈希（C++17 起） - 字符串参数优先用
std::string作 key，别用 C 风格指针 - 避免在递归函数里把缓存对象声明为局部静态——它会随每次调用重建，起不到跨调用缓存作用
示例：斐波那契带缓存
int fib(int n, std::unordered_map<int, int>& cache) {
if (n <= 1) return n;
if (cache.find(n) != cache.end()) return cache[n];
cache[n] = fib(n-1, cache) + fib(n-2, cache);
return cache[n;
}
用 std::function + lambda 实现通用缓存包装器
想复用缓存逻辑？可以写一个模板函数，接收原函数对象，返回带缓存的新函数。但要注意：lambda 捕获的缓存容器生命周期必须覆盖所有调用，否则缓存失效甚至崩溃。
立即学习“C++免费学习笔记（深入）”；
典型坑是返回局部 lambda，里面捕获了局部 std::unordered_map —— 函数返回后 map 被析构，后续调用访问野指针。
- 安全做法是让缓存作为返回 lambda 的 mutable 捕获变量，或用
std::shared_ptr管理 - 不能用于带重载或模板函数名（如
std::abs），必须先绑定成具体std::function - 参数包展开要小心引用折叠，
const T&&可能意外延长临时对象生命，也可能截断 const 性质
简版示意：
template<typename F>
auto memoize(F f) {
std::unordered_map<std::tuple<int>, int> cache; // 单参 int 版本
return [f, cache = std::move(cache)](int x) mutable -> int {
auto key = std::make_tuple(x);
auto it = cache.find(key);
if (it != cache.end()) return it->second;
int res = f(x);
cache[key] = res;
return res;
};
}
递归函数里缓存位置不对会导致无限递归或漏缓存
在递归函数内部做缓存检查，必须放在递归调用之前；否则每次递归都重新算，缓存只对最外层有效。
另一个易错点：缓存键没包含全部影响结果的参数。比如函数实际依赖全局状态或某个隐藏上下文，但 key 只用了显式参数，结果缓存命中却返回错误值。
- 检查是否所有输入变量都参与了 key 构造（包括隐式 this 指针，如果方法是非 static）
- 避免用指针地址作 key——同一数据不同地址算不同 key，失去缓存意义
- 若函数有副作用（如打印日志），缓存后需确认是否仍需执行副作用，否则行为不一致
注意线程安全和移动语义的冲突
多个线程同时调用同一个缓存函数，std::unordered_map::operator[] 和 insert 都不是线程安全的。加锁会拖慢性能，但不加锁可能崩溃或读到脏数据。
更隐蔽的问题是：缓存值类型支持移动但不支持拷贝（比如 std::unique_ptr），而 std::map::operator[] 在 key 不存在时会默认构造再赋值，触发移动构造没问题；但某些封装逻辑若误用 cache.at(key)（抛异常）或手动 find 后解引用，就可能绕过默认构造路径，导致未定义行为。
- 多线程场景下，优先用
std::shared_mutex（C++17）读写锁，而非粗粒度std::mutex - 缓存值类型尽量保持 trivially copyable，避免移动语义引入生命周期歧义
- 不要假设
cache[key]总是“存在即返回”，它在不存在时会插入默认值——这本身也是副作用
if (cache.count(k)) 容易得多；多数 bug 都出在这两处，而不是算法逻辑本身。 
