LRU缓存通过哈希表和双向链表结合实现，get和put操作均达到O(1)时间复杂度；当缓存满时淘汰最久未使用数据，利用哨兵节点简化链表操作，确保高效访问与顺序维护。
LRU（Least Recently Used）缓存淘汰算法的核心思想是：当缓存满时，优先淘汰最久未使用的数据。为了高效实现“快速访问”和“快速调整使用顺序”，通常结合哈希表与双向链表来完成。
在C++中，我们可以利用自定义的双向链表节点和unordered_map哈希表，实现O(1)时间复杂度的get和put操作。
设计思路
使用双向链表维护访问顺序：最近使用的节点放在链表头部，最久未使用的放在尾部。哈希表用于存储键到链表节点的指针，实现O(1)查找。
关键操作包括：
立即学习“C++免费学习笔记（深入）”；
get(key)：若存在，从链表中取出并移到头部；否则返回-1put(key, value)：若已存在，更新值并移至头部；若不存在且缓存满，则删除尾部节点，插入新节点到头部
核心结构定义
struct Node { int key; int value; Node* prev; Node* next; Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}};
哈希表定义为：unordered_map cache;
维护两个哨兵节点：head 和 tail，简化边界处理。
主要操作实现
需要封装几个辅助函数：
removeNode(Node* node)：从链表中移除指定节点addToHead(Node* node)：将节点插入到头部moveToHead(Node* node)：将已有节点移到头部（表示最近使用）removeTail()：移除尾部节点，并返回其key，用于从哈希表中删除
完整代码示例
#include iostream>#include red_map>using namespace std;
struct Node {int key, value;Node prev, next;Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}};
class LRUCache {private:unordered_map> cache;Node head;Node* tail;int capacity;
void removeNode(Node* node) { node->prev->next = node->next; node->next->prev = node->prev;}void addToHead(Node* node) { node->next = head->next; node->prev = head; 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) {head = new Node(0, 0);tail = new Node(0, 0);head->next = tail;tail->prev = head;}
int get(int key) { if (cache.find(key) == cache.end()) return -1; Node* node = cache[key]; moveToHead(node); return node->value;}void put(int key, int value) { if (cache.find(key) != cache.end()) { Node* node = cache[key]; 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() { 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缓存，适用于频繁读写、容量受限的场景。注意内存释放，避免泄漏。
以上就是C++怎么实现一个LRU缓存淘汰算法_C++结合哈希表与双向链表实现LRU Cache的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1485451.html
微信扫一扫 
支付宝扫一扫 
