74. STL与缓存系统：LRU缓存、LFU缓存、缓存策略
缓存，说白了就是用空间换时间。你想想看，程序里最耗时的操作是什么？无非就是磁盘I/O、网络请求、数据库查询这些。如果每次都要去取，性能肯定扛不住。缓存就是把那些"热数据"留在内存里，下次直接拿，省去重复计算的成本。
我做了这么多年C++开发，几乎每个项目都离不开缓存。从Web服务器的页面缓存，到数据库的查询结果缓存，再到CPU的指令缓存——缓存无处不在。今天我们就来聊聊两种最经典的缓存策略：LRU和LFU，以及如何用STL来实现它们。
核心要点：LRU（最近最少使用）和LFU（最不经常使用）是两种最主流的缓存淘汰策略。LRU关注"时间局部性"，LFU关注"频率局部性"。实际项目中，我通常根据数据访问模式来选择。
LRU缓存：最近最少使用
LRU的思路很简单：如果数据最近被访问过，那么将来被访问的概率也更高。所以当缓存满了，就淘汰最久没被访问的那个。
实现LRU缓存，我们需要两个核心数据结构：
- 哈希表：用于O(1)时间查找缓存项
- 双向链表：用于维护访问顺序，最近访问的放在头部，最久未访问的放在尾部
STL里没有现成的双向链表？别急，std::list就是双向链表。哈希表用std::unordered_map。两者一结合，就能实现高效的LRU缓存。
#include <unordered_map>
#include <list>
#include <utility>
template<typename Key, typename Value>
class LRUCache {
public:
LRUCache(size_t capacity) : capacity_(capacity) {}
Value get(const Key& key) {
auto it = cache_.find(key);
if (it == cache_.end()) {
throw std::runtime_error("Key not found");
}
// 把访问的节点移到链表头部
access_list_.splice(access_list_.begin(), access_list_, it->second.second);
return it->second.first;
}
void put(const Key& key, const Value& value) {
auto it = cache_.find(key);
if (it != cache_.end()) {
// 更新值，并移到头部
it->second.first = value;
access_list_.splice(access_list_.begin(), access_list_, it->second.second);
return;
}
// 如果缓存满了，淘汰最久未使用的（链表尾部）
if (cache_.size() >= capacity_) {
Key old_key = access_list_.back();
access_list_.pop_back();
cache_.erase(old_key);
}
// 插入新节点到链表头部
access_list_.push_front(key);
cache_[key] = {value, access_list_.begin()};
}
private:
size_t capacity_;
std::list<Key> access_list_; // 维护访问顺序
std::unordered_map<Key, std::pair<Value, typename std::list<Key>::iterator>> cache_;
};我的经验：这里用std::list::splice而不是先erase再push_front，因为splice是O(1)的，而erase+push_front是O(n)。我曾经在一个高并发服务里用错了，结果性能直接掉了一个数量级。
LFU缓存：最不经常使用
LFU的思路不同：它记录每个缓存项被访问的次数，淘汰时选访问次数最少的。如果次数相同，再淘汰最久未访问的。
实现LFU要复杂一些。我习惯用三个哈希表：
- 一个存键值对
- 一个存每个键的访问频率
- 一个存每个频率对应的键集合（用
std::list）
#include <unordered_map>
#include <list>
#include <climits>
template<typename Key, typename Value>
class LFUCache {
public:
LFUCache(size_t capacity) : capacity_(capacity), min_freq_(0) {}
Value get(const Key& key) {
if (cache_.find(key) == cache_.end()) {
throw std::runtime_error("Key not found");
}
// 增加访问频率
increaseFreq(key);
return cache_[key].first;
}
void put(const Key& key, const Value& value) {
if (capacity_ == 0) return;
if (cache_.find(key) != cache_.end()) {
cache_[key].first = value;
increaseFreq(key);
return;
}
if (cache_.size() >= capacity_) {
// 淘汰频率最低且最久未使用的
Key old_key = freq_list_[min_freq_].back();
freq_list_[min_freq_].pop_back();
cache_.erase(old_key);
key_freq_.erase(old_key);
}
// 插入新节点，频率为1
cache_[key] = {value, 1};
key_freq_[key] = 1;
freq_list_[1].push_front(key);
min_freq_ = 1;
}
private:
void increaseFreq(const Key& key) {
int old_freq = key_freq_[key];
int new_freq = old_freq + 1;
key_freq_[key] = new_freq;
// 从旧频率列表移除
freq_list_[old_freq].remove(key);
if (freq_list_[old_freq].empty() && old_freq == min_freq_) {
min_freq_++;
}
// 插入新频率列表
freq_list_[new_freq].push_front(key);
}
size_t capacity_;
int min_freq_;
std::unordered_map<Key, std::pair<Value, int>> cache_; // 键 -> (值, 频率)
std::unordered_map<Key, int> key_freq_; // 键 -> 频率
std::unordered_map<int, std::list<Key>> freq_list_; // 频率 -> 键列表
};注意：LFU有一个经典问题——"缓存污染"。如果一个热点数据突然不再被访问，它可能因为之前的高频率而长期占据缓存。我曾经在广告推荐系统里遇到过这个问题，后来加了衰减机制才解决。
缓存策略的选择
实际项目中，选哪种策略要看数据访问模式：
| 场景 | 推荐策略 | 原因 |
|---|---|---|
| 网页缓存 | LRU | 用户通常短时间内反复访问同一页面 |
| 数据库查询缓存 | LFU | 某些查询被频繁执行，频率稳定 |
| CDN缓存 | LRU + TTL | 内容时效性重要，LRU配合过期时间 |
| 推荐系统 | LFU + 衰减 | 用户兴趣会变化，需要衰减历史频率 |
嗯，这里要补充一点：没有银弹。我见过很多团队一开始选了LRU，后来发现某些热点数据被频繁访问但间隔较长，LRU反而把它们淘汰了。这时候LFU可能更合适。反过来，如果数据访问模式变化很快，LFU的"记忆"反而成了负担。
SVG：LRU与LFU核心逻辑对比
实战中的坑与优化
我踩过不少缓存的坑，分享几个印象深刻的：
- 线程安全：STL容器不是线程安全的。高并发场景下，一定要加锁或用无锁数据结构。我习惯用
std::shared_mutex做读写分离。 - 内存管理：缓存项如果太大，要考虑内存上限。我曾经没做限制，结果缓存把堆内存吃光了，程序直接OOM。
- 过期策略：纯LRU/LFU没有过期机制。实际项目中要配合TTL（生存时间），定期清理过期数据。
- 缓存穿透：查询一个不存在的数据，每次都会穿透缓存打到数据库。可以用布隆过滤器做第一道防线。
我的建议：如果项目对性能要求极高，可以考虑用boost::intrusive::list替代std::list，减少内存分配开销。不过代码复杂度会上升，要权衡。
好了，关于LRU和LFU缓存，今天就聊到这里。这两种策略是缓存系统的基石，理解了它们，你就能应对大部分缓存场景。实际项目中，我通常还会结合TTL、预加载、异步刷新等机制，让缓存系统更健壮。