LRU缓存通过哈希表和双向链表组合实现，O(1)完成查找与顺序维护。1. 哈希表映射key到链表节点；2. 链表头部存最近使用项；3. 访问或插入时更新位置；4. 容量超限时删除尾部节点。
实现一个LRU（Least Recently Used）缓存淘汰算法，核心在于快速访问数据的同时维护访问顺序。当缓存满时，优先淘汰最久未使用的数据。C++中可以通过结合 哈希表（unordered_map） 和 双向链表（list） 高效实现，达到O(1)的查找、插入和删除效率。
基本思路与数据结构选择
为了同时满足快速查找和顺序管理：
- unordered_map：存储键（key）到双向链表节点的映射，实现O(1)查找。
- list（双向链表）：维护访问顺序，最近使用的放头部，最久未用的在尾部，便于O(1)移动和删除。
每次访问某个key，就将其对应节点移到链表头部；插入新元素时若超出容量，则删除尾部节点。
C++代码实现
以下是一个完整的LRU Cache类实现：
立即学习“C++免费学习笔记（深入）”；
#include <iostream>
#include <unordered_map>
#include <list>
class LRUCache {
private:
int capacity;
std::unordered_map<int, std::list<std::pair<int, int>>::iterator> cache;
std::list<std::pair<int, int>> used;
public:
LRUCache(int cap) : capacity(cap) {}
int get(int key) {
auto it = cache.find(key);
if (it == cache.end()) return -1; // 未命中
// 命中，将该元素移到链表头部
used.splice(used.begin(), used, it->second);
return it->second->second;
}
void put(int key, int value) {
auto it = cache.find(key);
if (it != cache.end()) {
// 已存在，更新值并移到头部
it->second->second = value;
used.splice(used.begin(), used, it->second);
return;
}
// 新插入，检查是否超容
if (cache.size() >= capacity) {
int old_key = used.back().first;
cache.erase(old_key);
used.pop_back();
}
// 插入新节点到链表头部
used.emplace_front(key, value);
cache[key] = used.begin();
}
};
关键操作说明
splice 是实现高效移动的核心：
- used.splice(used.begin(), used, it->second) 将指定节点直接移到链表头部，不涉及内存分配，时间复杂度为O(1)。
- 避免了先删除再插入带来的开销。
emplace_front 直接在链表头部构造新节点，比 push_front 更高效。
使用示例
int main() {
LRUCache lru(2);
lru.put(1, 1);
lru.put(2, 2);
std::cout << lru.get(1) << "\n"; // 输出 1
lru.put(3, 3); // 淘汰 key=2
std::cout << lru.get(2) << "\n"; // 输出 -1
return 0;
}
基本上就这些。通过哈希表+双向链表的组合，C++能简洁高效地实现LRU缓存，适合面试和实际应用。注意边界处理和STL成员函数的正确使用即可。
