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 #include #include class LRUCache {private: int capacity; std::unordered_map<int, std::list<std::pair>::iterator> cache; std::list<std::pair> 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成员函数的正确使用即可。
以上就是C++怎么实现一个LRU缓存淘汰算法_C++数据结构设计与LRU Cache实现的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1487346.html
微信扫一扫 
支付宝扫一扫 
