LRU缓存通过哈希表和双向链表结合实现，get和put操作均O(1)：哈希表映射key到链表节点，链表维护访问顺序，最近使用置头，满时删尾。
实现一个LRU（Least Recently Used）缓存的核心思路是：当缓存满时，优先淘汰最久未使用的数据。为了高效地完成插入、查找和更新操作，C++中通常结合哈希表（unordered_map）和双向链表（list）来实现。
1. LRU缓存的基本要求
一个LRU缓存需要支持以下两个核心操作：
get(key)：如果键存在，返回对应的值，并将该键移到最近使用位置；否则返回 -1。 put(key, value)：插入或更新键值对。如果超出容量，删除最久未使用的条目。
这两个操作的时间复杂度都应为 O(1)。
2. 数据结构选择
要达到 O(1) 的时间复杂度，可以这样设计：
立即学习“C++免费学习笔记（深入）”；
unordered_mapair>::iterator>：用于快速定位某个 key 是否存在及其在链表中的位置。 list>：双向链表存储键值对，最近使用的放在链表头部，最久未使用的在尾部。
这种组合既能快速查找，又能高效地移动和删除节点。
3. 实现代码示例
#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; } // 插入新元素到链表头部 used.emplace_front(key, value); cache[key] = used.begin(); // 如果超过容量，删除尾部元素 if (cache.size() > capacity) { int lastKey = used.back().first; cache.erase(lastKey); used.pop_back(); } }};
4. 关键点说明
splice 是关键操作：它可以把链表中的某个迭代器指向的节点“剪切”并粘贴到另一个位置，不会导致迭代器失效，且时间复杂度为 O(1)。
每次 get 或 put 已存在的 key 时，都要调用 splice 将其移到链表头部。 新插入的元素直接加到头部，淘汰时从尾部移除。 哈希表保存的是 list 的 iterator，可以直接访问对应节点。
基本上就这些。这个实现简洁、高效，适合面试和实际项目中使用。注意边界情况处理，比如容量为 0 或重复插入等情况即可。不复杂但容易忽略细节。
以上就是c++++怎么实现一个LRU缓存算法_c++中LRU缓存的设计与实现的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1483379.html
微信扫一扫 
支付宝扫一扫 
