答案：C++实现LRU缓存需结合哈希表和双向链表，利用unordered_map实现O(1)查找，list或自定义双向链表维护访问顺序，通过splice操作将最近访问节点移至头部，容量超限时删除尾部节点，兼顾效率与简洁性。
LRU（Least Recently Used）缓存是一种常见的缓存淘汰策略，核心思想是：当缓存满时，优先淘汰最久未使用的数据。C++中实现LRU缓存通常结合哈希表和双向链表，以达到O(1)的查找、插入和删除效率。
基本结构设计
一个高效的LRU缓存需要两个关键组件：
每次访问某个key时，将其对应节点移到链表头部；当缓存容量超限时，删除尾部节点。
使用STL实现简易LRU
借助C++标准库的std::list和std::unordered_map，可以简洁地实现LRU缓存。
立即学习“C++免费学习笔记（深入）”；
示例代码如下：
#include <iostream>
#include <list>
#include <unordered_map>
<p>class LRUCache {
private:
int capacity;
std::list<std::pair<int, int>> cacheList; // 存储 key-value 对
std::unordered_map<int, std::list<std::pair<int, int>>::iterator> hashMap;</p><p>public:
LRUCache(int cap) : capacity(cap) {}</p><pre class='brush:php;toolbar:false;'>int get(int key) {
auto it = hashMap.find(key);
if (it == hashMap.end()) return -1; // 未命中
// 将访问的节点移到链表头部
cacheList.splice(cacheList.begin(), cacheList, it->second);
return it->second->second;
}
void put(int key, int value) {
auto it = hashMap.find(key);
if (it != hashMap.end()) {
// 已存在，更新值并移到头部
it->second->second = value;
cacheList.splice(cacheList.begin(), cacheList, it->second);
return;
}
// 新插入
if (cacheList.size() >= capacity) {
// 删除尾部最久未使用项
int lastKey = cacheList.back().first;
hashMap.erase(lastKey);
cacheList.pop_back();
}
cacheList.emplace_front(key, value);
hashMap[key] = cacheList.begin();
}};
这里利用splice方法在O(1)时间内将节点移动到链表头，避免重新分配。
手动实现双向链表提升控制力
若需更精细控制内存或理解底层机制，可手动实现双向链表节点：
struct Node {
int key, value;
Node* prev;
Node* next;
Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};
维护头尾哨兵节点简化边界处理，插入和删除时手动调整指针。虽然代码量增加，但有助于深入理解LRU机制。
应用场景与优化建议
LRU缓存在数据库索引、网页缓存、操作系统页面置换等场景广泛应用。
实际使用中可考虑以下优化：
- 线程安全：在多线程环境下，加锁（如std::mutex）保护共享数据。
- 内存池：频繁创建销毁节点时，使用对象池减少动态分配开销。
- 只读操作无锁：读操作可尝试用shared_mutex提升并发性能。
基本上就这些。C++实现LRU的关键在于结构选择和操作的常数时间保证，合理利用STL能快速构建高效缓存。自己动手实现则更适合学习和特定需求定制。
