如何用C++设计LRU / LFU 缓存
C++ 设计要点详解
一、LRU —— std::list + std::unordered_map<K, list::iterator>
C++ 的核心技巧是把 list 的迭代器存进 map，而不是存值本身。
cpp
std::list<std::pair<K,V>> list_; std::unordered_map<K, list<pair<K,V>>::iterator> map_;
这里有两个关键性质：
list::splice 是 O(1) 且迭代器不失效。 把节点从当前位置移到链表头只需要修改三对指针，map 里存的迭代器根本不需要更新，这是和 Python 版手写链表截然不同的地方。
cpp
// 把 it 所指节点移到链表头，O(1)，it 依然有效 list_.splice(list_.begin(), list_, it->second);
淘汰时节点里必须存 key，因为从 list.back() 拿到淘汰节点后需要立即去 map 里 erase(key)，如果只存 value 就找不到 key 了。
cpp
if ((int)map_.size() == cap_) {
auto& lru = list_.back(); // pair<K,V>
map_.erase(lru.first); // 用 key 删 map
list_.pop_back();
}
二、LFU —— 双 unordered_map + 频率桶链表
cpp
std::unordered_map<K, NodeIter> key_map_; // key → 链表迭代器 std::unordered_map<int, NodeList> freq_map_; // freq → 按访问顺序的链表 int min_freq_;
Node 里必须同时存 key 和 freq，原因和 LRU 类似：淘汰时要拿 key 去 key_map_ 里删，频率变化时要知道从哪个桶迁出。
_bump_freq 是整个 LFU 的核心，同样利用 splice 做到 O(1)：
cpp
void _bump_freq(NodeIter node_it) {
int old_freq = node_it->freq;
node_it->freq++;
freq_map_[node_it->freq].splice(
freq_map_[node_it->freq].end(),
freq_map_[old_freq],
node_it // 迭代器迁移后依然有效
);
if (freq_map_[old_freq].empty() && old_freq == min_freq_)
min_freq_++;
}
min_freq 的维护规则只有两条：put 新节点时置 1；旧桶变空且等于 min_freq 时 +1。不能跳跃，因为频率只能逐步增长。
三、C++ vs Python 实现的关键差异
| 维度 | Python | C++ |
|---|---|---|
| 双向链表 | 手写 Node + 哨兵 |
std::list（标准库自带） |
| 节点移动 | 手动摘链 + 插入，O(1) | list::splice，O(1)，迭代器不失效 |
| 哈希表值 | 节点指针 | list::iterator（本质也是指针包装） |
| 模板化 | OrderedDict 天然泛型 |
template <typename K, typename V> |
| 内存 | GC 自动回收 | list.erase / pop_back 立即释放 |
四、工程扩展方向
线程安全：在 get/put 外层加 std::shared_mutex，读操作用 shared_lock，写操作用 unique_lock。但注意 LRU 的 get 也会修改链表顺序，所以 get 也需要 unique_lock，除非接受近似 LRU 语义。
过期时间（TTL）：Node 里加 std::chrono::steady_clock::time_point expire，get 时检查是否过期，过期视为 miss 并删除。
容量统计：如果 value 是变长数据（如字节串），可以改为按字节数限容，put 时循环淘汰直到剩余容量足够。