LRU缓存用unordered_map+list实现：哈希表O(1)查key，链表O(1)维护时序；get时命中则移至头部并更新迭代器，未命中返回-1；put时存在则更新并前置，不存在且满容则删尾部再头插。
用C++实现LRU缓存，核心是让“最近最少使用”的元素自动被淘汰，关键在于快速查找 + 快速移动到最新位置。标准做法是：哈希表（unordered_map） + 双向链表（list）组合——哈希表提供O(1)查找，链表维护访问时序，且支持O(1)头插、尾删和任意节点摘除。
数据结构选型与设计逻辑
不能只用map或vector：map按key排序不反映访问顺序；vector删除中间元素是O(n)。而list是双向链表，erase一个迭代器是O(1)；unordered_map存key→list迭代器，就能在查到节点的同时，立刻把它移到链表头部（表示最新访问）。
缓存结构通常包含：
- 一个std::list<std::pair<int, int>>：存(key, value)，头部为最新访问，尾部为最久未用
- 一个std::unordered_map<int, std::list<pair>::iterator>：通过key快速定位链表中对应节点
- 一个int capacity：最大容量，超限时删尾部节点
关键操作的实现要点
get(int key)：查map，存在则把对应节点移到list头部，更新map中该key的新迭代器，返回value；不存在返回-1。
立即学习“C++免费学习笔记（深入）”；
put(int key, int value)：
- 如果key已存在：更新value，移到头部，更新map迭代器
- 如果key不存在：检查是否已达capacity；若已满，先删list尾部节点，并从map中擦除其key；再头插新节点，map中加入新映射
注意：list::push_front()返回新插入元素的迭代器，可直接存入map；用list::erase()删尾部时，要先用back().first拿到key再删map，否则迭代器失效后无法反查key。
完整可运行代码示例
以下是最简实用版本（省略异常处理，适合学习和面试）：
class LRUCache {
int cap;
list<pair<int, int>> cache; // {key, value}
unordered_map<int, list<pair<int, int>>::iterator> map;
public:
LRUCache(int capacity) : cap(capacity) {}
int get(int key) {
if (map.find(key) == map.end()) return -1;
auto it = map[key];
int val = it->second;
cache.erase(it);
cache.push_front({key, val});
map[key] = cache.begin();
return val;
}
void put(int key, int value) {
if (map.find(key) != map.end()) {
cache.erase(map[key]);
} else if (cache.size() == cap) {
int lastKey = cache.back().first;
cache.pop_back();
map.erase(lastKey);
}
cache.push_front({key, value});
map[key] = cache.begin();
}
};
调用示例：LRUCache lru(2); lru.put(1,1); lru.put(2,2); lru.get(1); lru.put(3,3); → 此时缓存含{3,3}和{1,1}，{2,2}被淘汰。
进阶优化与注意事项
实际工程中可考虑：
- 用std::shared_ptr管理节点，避免迭代器失效风险（但增加开销）
- 封装为模板类，支持任意key/value类型
- 加锁支持多线程（如mutable shared_mutex + scoped_lock）
- 避免重复构造pair：用cache.emplace_front(key, value)替代push_front({key,value})
不复杂但容易忽略：每次移动节点后必须更新map里的迭代器，否则下次get会解引用已失效的迭代器，导致崩溃。
