LRU缓存通过哈希表和双向链表结合实现，get和put操作均O(1)时间复杂度，最近访问节点置于链表头部，满时淘汰尾部最久未用节点。
LRU（Least Recently Used）缓存淘汰算法的核心思想是：当缓存满时，优先淘汰最久未使用的数据。为了高效实现，通常结合哈希表和双向链表，C++中可以用 unordered_map 和自定义的双向链表来完成。
基本思路
使用一个双向链表维护访问顺序，最近访问的节点放在链表头部，最久未访问的在尾部。同时用哈希表快速定位节点位置：
get(key)：若存在，返回值并将该节点移到链表头；否则返回 -1put(key, value)：若已存在，更新值并移到头部；若不存在且缓存已满，删除尾部节点，插入新节点到头部
关键数据结构设计
定义双向链表节点和缓存容量：
struct ListNode { int key, value; ListNode *prev, *next; ListNode(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}};
成员变量包括：
立即学习“C++免费学习笔记（深入）”；
头尾指针：方便插入删除哈希表：unordered_map当前大小与最大容量
核心操作实现
封装两个辅助函数简化逻辑：
void removeNode(ListNode* node) { node->prev->next = node->next; node->next->prev = node->prev;}void addToHead(ListNode* node) {node->next = head->next;node->prev = head;head->next->prev = node;head->next = node;}
这两个函数用于调整节点位置，保证 O(1) 时间复杂度。
完整示例代码
#include #include using namespace std;class LRUCache {private:struct ListNode {int key, value;ListNode prev, next;ListNode(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}};
int capacity;unordered_map cache;ListNode *head, *tail;void removeNode(ListNode* node) { node->prev->next = node->next; node->next->prev = node->prev;}void addToHead(ListNode* node) { node->next = head->next; node->prev = head; head->next->prev = node; head->next = node;}void moveToHead(ListNode* node) { removeNode(node); addToHead(node);}ListNode* popTail() { ListNode* last = tail->prev; removeNode(last); return last;}
public:LRUCache(int cap) {capacity = cap;head = new ListNode(0, 0);tail = new ListNode(0, 0);head->next = tail;tail->prev = head;}
int get(int key) { if (cache.find(key) == cache.end()) return -1; ListNode* node = cache[key]; moveToHead(node); return node->value;}void put(int key, int value) { if (cache.find(key) != cache.end()) { ListNode* node = cache[key]; node->value = value; moveToHead(node); } else { ListNode* newNode = new ListNode(key, value); cache[key] = newNode; addToHead(newNode); if (cache.size() > capacity) { ListNode* removed = popTail(); cache.erase(removed->key); delete removed; } }}~LRUCache() { for (auto& pair : cache) { delete pair.second; } delete head; delete tail;}
};
使用示例
int main() { LRUCache lru(2); lru.put(1, 1); lru.put(2, 2); cout << lru.get(1) << endl; // 输出 1 lru.put(3, 3); // 淘汰 key=2 cout << lru.get(2) << endl; // 输出 -1 return 0;}
基本上就这些。用哈希表加双向链表，能保证 get 和 put 都是 O(1) 时间复杂度，符合 LRU 的高效要求。注意手动管理内存或改用智能指针避免泄漏。
以上就是c++++怎么实现一个LRU缓存淘汰算法_c++实现LRU缓存的思路与示例的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1481938.html
微信扫一扫 
支付宝扫一扫 
