LRU缓存用unordered_map加list实现：get查哈希表并splice移至头部，put更新或插入并超容时删尾部；时间复杂度均为O(1)。
用 C++ 实现 LRU（Least Recently Used）缓存，核心是快速查找 + 快速移动“最近使用”项。标准做法是结合 std::unordered_map（O(1) 查找）和 std::list（O(1) 头尾插入/删除，支持手动调整顺序），避免手写双向链表的复杂性。
数据结构设计：哈希表 + 双向链表
LRU 要求：
- get(key)：存在则返回值，并将该 key 移到“最近使用”位置（头部）；不存在返回 -1。
- put(key, value)：若 key 已存在，更新 value 并移到头部；若不存在，插入新节点；若容量满，先淘汰尾部（最久未用）节点。
关键点：
- std::list 存键值对，头部为最近访问，尾部为最久未用。
- std::unordered_map 映射 key 到链表中对应节点的迭代器，实现 O(1) 定位。
put 操作：插入或更新 + 容量控制
执行步骤：
- 若 key 已存在：用 map 找到对应 list 迭代器，用 splice() 把该节点移到 list 开头，更新 value。
- 若 key 不存在：
• 先检查是否超容（map.size() == capacity）：是则删掉 list 尾节点，并从 map 中移除其 key。
• 然后在 list 头部插入新节点（push_front({key, value})），并将新节点迭代器存入 map。
get 操作：查表 + 提升热度
执行步骤：
- 在 map 中查找 key：
• 找不到 → 返回 -1。
• 找到 → 获取对应 list 迭代器，调用 splice(list.begin(), list, it) 将该节点移到开头，返回 value。
注意：不要用 erase + push_front，那样会额外分配内存；splice 是常数时间、原地移动，更高效。
完整可运行示例（C++11+）
不依赖外部库，仅用 STL：
class LRUCache {
int cap;
list> cache;
unordered_map>::iterator> map;
public:
LRUCache(int capacity) : cap(capacity) {}
int get(int key) {
if (map.find(key) == map.end()) return -1;
auto it = map[key];
cache.splice(cache.begin(), cache, it); // 移至头部
return it->s
econd;
}
void put(int key, int value) {
if (map.find(key) != map.end()) {
auto it = map[key];
it->second = value;
cache.splice(cache.begin(), cache, it);
return;
}
if (cache.size() == cap) {
auto last = cache.back();
map.erase(last.first);
cache.pop_back();
}
cache.push_front({key, value});
map[key] = cache.begin();
}};
立即学习“C++免费学习笔记（深入）”；
使用示例：
LRUCache lru(2);
lru.put(1, 1); // 缓存: [(1,1)]
lru.put(2, 2); // 缓存: [(2,2),(1,1)]
lru.get(1); // 返回 1，缓存: [(1,1),(2,2)]
lru.put(3, 3); // 淘汰 2，缓存: [(3,3),(1,1)]
econd;
}
void put(int key, int value) {
if (map.find(key) != map.end()) {
auto it = map[key];
it->second = value;
cache.splice(cache.begin(), cache, it);
return;
}
if (cache.size() == cap) {
auto last = cache.back();
map.erase(last.first);
cache.pop_back();
}
cache.push_front({key, value});
map[key] = cache.begin();
}
