LRU缓存通过哈希表和双向链表实现，get和put操作均O(1)：访问时移至链表头，满时删尾部节点。
实现一个LRU（Least Recently Used）缓存淘汰算法，核心是结合哈希表和双向链表，做到查询和更新都在 O(1) 时间完成。C++ 中可以通过 unordered_map 和自定义的双向链表节点来高效实现。
基本思路
LRU 缓存需要满足：
访问某个键时，它变为“最近使用”当缓存满时，淘汰最久未使用的项get 和 put 操作都需在 O(1) 完成
为此，我们使用：
unordered_map：快速查找 key 是否存在，以及对应节点位置双向链表：维护使用顺序，头结点是最新的，尾结点是最老的
数据结构设计
定义双向链表节点和缓存类框架：
立即学习“C++免费学习笔记（深入）”；
struct Node { int key, value; Node* prev; Node* next; Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}};
缓存类包含：
容量 capacity当前大小 size哈希表 map伪头部和伪尾部简化边界处理
关键操作实现
封装两个辅助函数：
void removeNode(Node* node) { node->prev->next = node->next; node->next->prev = node->prev;}void addToHead(Node* node) {node->prev = head;node->next = head->next;head->next->prev = node;head->next = node;}
get 操作逻辑：
查 map 是否存在 key不存在返回 -1存在则将其移到链表头部（表示最近使用），并返回值
put 操作逻辑：
如果 key 已存在，更新值并移到头部如果不存在，新建节点插入头部若超出容量，删除尾部节点（最久未使用）及 map 中对应项
完整代码示例
#include using namespace std;class LRUCache {private:struct Node {int key, value;Node prev;Node next;Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}};
int capacity;unordered_map cache;Node* head;Node* tail;void removeNode(Node* node) { node->prev->next = node->next; node->next->prev = node->prev;}void addToHead(Node* node) { node->prev = head; node->next = head->next; head->next->prev = node; head->next = node;}void moveToHead(Node* node) { removeNode(node); addToHead(node);}Node* removeTail() { Node* node = tail->prev; removeNode(node); return node;}
public:LRUCache(int cap) : capacity(cap), size(0) {head = new Node(0, 0);tail = new Node(0, 0);head->next = tail;tail->prev = head;}
int get(int key) { auto it = cache.find(key); if (it == cache.end()) return -1; Node* node = it->second; moveToHead(node); return node->value;}void put(int key, int value) { auto it = cache.find(key); if (it != cache.end()) { Node* node = it->second; node->value = value; moveToHead(node); } else { Node* newNode = new Node(key, value); cache[key] = newNode; addToHead(newNode); if (cache.size() > capacity) { Node* removed = removeTail(); cache.erase(removed->key); delete removed; } }}~LRUCache() { Node* curr = head; while (curr) { Node* temp = curr; curr = curr->next; delete temp; }}
};
这个实现保证了 get 和 put 都是 O(1) 时间复杂度，适合高频访问场景。注意手动管理内存或可改用智能指针。基本上就这些，不复杂但容易忽略细节比如指针连接顺序和析构处理。
以上就是c++++怎么实现一个LRU缓存淘汰算法_c++最近最少使用缓存机制实现的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1480878.html
微信扫一扫 
支付宝扫一扫 
