使用哈希表和双向链表实现LRU缓存，通过unordered_map映射键到节点，双向链表维护访问顺序，get和put操作均O(1)时间完成，访问或插入时将节点移至链表头部，容量满时删除尾部最久未使用节点。
在C++中实现LRU（Least Recently Used）缓存，核心思路是结合哈希表和双向链表，以达到O(1)的查找、插入和删除效率。LRU缓存会优先淘汰最久未使用的数据，因此需要快速定位元素并维护访问顺序。
使用unordered_map + 双向链表
标准做法是使用std::unordered_map存储键到节点的映射，配合自定义的双向链表管理访问顺序。
步骤说明：
每次访问某个键时，将其对应的节点移到链表头部（表示最新使用）插入新键值对时，添加到链表头部当缓存满时，删除链表尾部的节点（最久未使用）使用哈希表快速找到节点位置，避免遍历链表
代码实现：
立即学习“C++免费学习笔记（深入）”；
#include #includestruct ListNode {int key, value;ListNode prev;ListNode next;ListNode(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}};
class LRUCache {private:int capacity;std::unordered_map<int, ListNode> cache;ListNode head; // 指向最新使用的节点ListNode* tail; // 指向最久未使用的节点
// 将节点移动到头部void moveToHead(ListNode* node) { if (node == head) return; // 断开原连接 if (node == tail) { tail = tail->prev; tail->next = nullptr; } else { node->prev->next = node->next; node->next->prev = node->prev; } // 插入到头部 node->next = head; node->prev = nullptr; head->prev = node; head = node;}// 添加新节点到头部void addToHead(ListNode* node) { if (!head) { head = tail = node; } else { node->next = head; head->prev = node; head = node; }}// 删除尾部节点void removeTail() { ListNode* toDelete = tail; if (head == tail) { head = tail = nullptr; } else { tail = tail->prev; tail->next = nullptr; } cache.erase(toDelete->key); delete toDelete;}
public:LRUCache(int capacity) : capacity(capacity), head(nullptr), tail(nullptr) {}
int get(int key) { auto it = cache.find(key); if (it == cache.end()) return -1; ListNode* node = it->second; moveToHead(node); return node->value;}void put(int key, int value) { auto it = cache.find(key); if (it != cache.end()) { it->second->value = value; moveToHead(it->second); } else { ListNode* newNode = new ListNode(key, value); if (cache.size() >= capacity) { removeTail(); } addToHead(newNode); cache[key] = newNode; }}~LRUCache() { while (head) { ListNode* tmp = head; head = head->next; delete tmp; }}
};
使用std::list简化实现
可以借助std::list自动管理双向链表，减少手动指针操作。
#include #includeclass LRUCache {private:int capacity;std::list<std::pair> lst; // 存储 key-value 对std::unordered_map<int, std::list<std::pair>::iterator> cache;
public:LRUCache(int cap) : capacity(cap) {}
int get(int key) { auto it = cache.find(key); if (it == cache.end()) return -1; // 移动到链表前端 lst.splice(lst.begin(), lst, 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; lst.splice(lst.begin(), lst, it->second); return; } if (cache.size() >= capacity) { auto& last = lst.back(); cache.erase(last.first); lst.pop_back(); } lst.push_front({key, value}); cache[key] = lst.begin();}
};
这种方法更简洁，splice函数能高效地将节点移到头部。
关键点总结
性能要求：
get 和 put 操作均需 O(1) 时间复杂度哈希表提供 O(1) 查找，双向链表支持 O(1) 插入删除
常见错误：
忘记更新 head/tail 指针没处理单节点情况put 时未判断键已存在内存泄漏（尤其手动管理节点时）
基本上就这些。用 list 的版本更适合快速实现，手写链表则更能理解底层机制。
以上就是c++++中如何实现LRU缓存_c++ LRU缓存实现方法的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1477889.html
微信扫一扫 
支付宝扫一扫 
