#includeunordered_map#includelistclassLRUCache{private:intcap;// 链表头部是最近使用尾部是最久未使用std::liststd::pairint,intcache;// {key, value}std::unordered_mapint,std::liststd::pairint,int::iteratormap;public:LRUCache(intcapacity):cap(capacity){}intget(intkey){autoitmap.find(key);if(itmap.end())return-1;// 命中把该节点移到链表头部cache.splice(cache.begin(),cache,it-second);returnit-second-second;}voidput(intkey,intvalue){autoitmap.find(key);// key 已存在更新值并移到头部if(it!map.end()){it-second-secondvalue;cache.splice(cache.begin(),cache,it-second);return;}// 容量已满淘汰尾部节点最久未使用if((int)cache.size()cap){intoldKeycache.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)测试#includeiostreamintmain(){LRUCachecache(2);cache.put(1,1);cache.put(2,2);std::coutcache.get(1)std::endl;// 1cache.put(3,3);// 淘汰 2std::coutcache.get(2)std::endl;// -1cache.put(4,4);// 淘汰 1std::coutcache.get(1)std::endl;// -1std::coutcache.get(3)std::endl;// 3std::coutcache.get(4)std::endl;// 4return0;}补充如果面试要求手写双向链表有些面试官不允许直接用 std::list这时可以自己定义 Node { key, value, prev, next }并用两个哨兵 head / tail 简化边界处理。核心操作· addToHead(node)· removeNode(node)· moveToHead(node)· removeTail()逻辑和上面完全一致只是把 std::list 换成手写指针操作。