#include<unordered_map>#include<list>classLRUCache{private:intcap;// 链表头部是最近使用，尾部是最久未使用std::list<std::pair<int,int>>cache;// {key, value}std::unordered_map<int,std::list<std::pair<int,int>>::iterator>map;public:LRUCache(intcapacity):cap(capacity){}intget(intkey){autoit=map.find(key);if(it==map.end())return-1;// 命中，把该节点移到链表头部cache.splice(cache.begin(),cache,it->second);returnit->second->second;}voidput(intkey,intvalue){autoit=map.find(key);// key 已存在：更新值并移到头部if(it!=map.end()){it->second->second=value;cache.splice(cache.begin(),cache,it->second);return;}// 容量已满：淘汰尾部节点（最久未使用）if((int)cache.size()==cap){intoldKey=cache.back().first;cache.pop_back();map.erase(oldKey);}// 插入新节点到头部cache.emplace_front(key,value);map[key]=cache.begin();}};思路
经典的 哈希表 + 双向链表：
· unordered_map 存 key -> 链表节点迭代器，实现 O(1) 查找。
· std::list 维护访问顺序：
· 头部 begin()：最近使用
· 尾部 back()：最久未使用
· splice 可以把节点在 O(1) 内移动到头部，且不会使迭代器失效，所以 map 里的迭代器始终有效。
复杂度
· 时间：get / put 均为 O(1)
· 空间：O(capacity)
测试
#include<iostream>intmain(){LRUCachecache(2);cache.put(1,1);cache.put(2,2);std::cout<<cache.get(1)<<std::endl;// 1cache.put(3,3);// 淘汰 2std::cout<<cache.get(2)<<std::endl;// -1cache.put(4,4);// 淘汰 1std::cout<<cache.get(1)<<std::endl;// -1std::cout<<cache.get(3)<<std::endl;// 3std::cout<<cache.get(4)<<std::endl;// 4return0;}补充：如果面试要求手写双向链表
有些面试官不允许直接用 std::list，这时可以自己定义 Node { key, value, prev, next }，并用两个哨兵 head / tail 简化边界处理。核心操作：
· addToHead(node)
· removeNode(node)
· moveToHead(node)
· removeTail()
逻辑和上面完全一致，只是把 std::list 换成手写指针操作。
