LRU 缓存原理与 C++ 实践示例-平芜编程栈

文章目录

LRU 缓存原理与 C++ 实践示例
- 什么是 LRU
- - LRU 需要满足的操作
  - 数据结构选型
- C++ 常见使用场景
- - 完整可运行示例
- 实际项目中的注意点
- 开源工业级实现参考
- 小结

LRU 缓存原理与 C++ 实践示例

什么是 LRU

LRU（Least Recently Used），最近最少使用，是一种常见的缓存淘汰算法。

核心思想：如果一个数据最近被访问过，那么它在未来被访问的概率也更高；反之，很久没有被访问的数据，未来访问概率低，缓存满的时候优先把它淘汰掉。

缓存容量是有限的，当缓存达到上限，插入新元素时，需要剔除掉「最久没有使用」的那条数据，腾出空间存放新数据。

LRU 需要满足的操作

get(key)：读取 key。
- key存在：返回 value，并且把该节点标记为最近使用；
- key不存在：返回空。
put(key, value)：写入键值对。
- key已存在：更新 value，标记为最近使用；
- key不存在：插入新节点。如果缓存已满，删除最久未使用的节点，再插入新节点。

数据结构选型

要做到get、put平均 O(1) 时间复杂度：

哈希表(unordered_map)：实现 key 到节点的快速映射，O(1) 查找。
双向链表：维护访问时序。链表头部代表最近使用，链表尾部代表最久未使用。
- 访问到某个节点：把节点移动到链表头部；
- 缓存淘汰：直接删除链表尾部节点。

单向链表无法 O(1) 删除中间节点，所以必须双向链表。

C++ 常见使用场景

服务端内存缓存：限制内存占用，缓存数据库查询结果，避免频繁查库。比如用户信息、配置信息缓存。
本地资源缓存：文件解析结果、图片解码结果缓存，防止内存暴涨。
中间件/网关：限流、会话缓存、请求结果缓存。
嵌入式程序：有限内存下缓存高频访问数据。

C++ 标准库没有直接提供 LRU 容器，一般两种方案：
自己实现unordered_map + list；
使用开源库（Abseilabsl::LRUCache，folly LRUCache）。

下面给出手写简易 LRUCache 实现，基于 C++17。

完整可运行示例

#include <iostream> #include <unordered_map> #include <list> #include <utility> /** * LRUCache 简易实现 * key: int, value: int */ class LRUCache { public: // list 存储 pair<key, value>，头部是最近使用，尾部最久未使用 using ListNode = std::pair<int, int>; std::list<ListNode> m_list; // key -> list 的迭代器 std::unordered_map<int, std::list<ListNode>::iterator> m_map; int m_capacity; explicit LRUCache(int capacity) : m_capacity(capacity) {} int get(int key) { auto it = m_map.find(key); if (it == m_map.end()) { return -1; // 不存在 } // 取出节点，移动到链表头部 auto node_it = it->second; int val = node_it->second; // splice：转移节点，不会拷贝，O(1) m_list.splice(m_list.begin(), m_list, node_it); return val; } void put(int key, int value) { auto it = m_map.find(key); if (it != m_map.end()) { // key已存在，更新value，挪到头部 auto node_it = it->second; node_it->second = value; m_list.splice(m_list.begin(), m_list, node_it); return; } // 容量满，淘汰尾部 if ((int)m_list.size() >= m_capacity) { auto last = m_list.back(); int del_key = last.first; m_map.erase(del_key); m_list.pop_back(); } // 插入新节点到头部 m_list.emplace_front(key, value); m_map[key] = m_list.begin(); } // 打印缓存内容，用于调试 void print() const { for (const auto& p : m_list) { std::cout << "[" << p.first << ":" << p.second << "] "; } std::cout << "\n"; } }; // 模拟业务场景：缓存数据库查询结果 int main() { // 缓存最多3条记录 LRUCache cache(3); std::cout << "put(1,100)\n"; cache.put(1, 100); cache.print(); std::cout << "put(2,200)\n"; cache.put(2, 200); cache.print(); std::cout << "put(3,300)\n"; cache.put(3, 300); cache.print(); std::cout << "get(1) -> " << cache.get(1) << "\n"; cache.print(); std::cout << "put(4,400) 缓存满，淘汰最久未使用的key=2\n"; cache.put(4, 400); cache.print(); std::cout << "get(2) -> " << cache.get(2) << "\n"; return 0; }

输出结果：

put(1,100) [1:100] put(2,200) [2:200] [1:100] put(3,300) [3:300] [2:200] [1:100] get(1) -> 100 [1:100] [3:300] [2:200] put(4,400) 缓存满，淘汰最久未使用的key=2 [4:400] [1:100] [3:300] get(2) -> -1