答案：LRU缓存通过哈希表和双向链表实现，支持O(1)查找、插入与删除，访问或添加节点时移至链表头部，容量超限时删除尾部最久未使用节点。
实现一个LRU（Least Recently Used）缓存，核心在于快速访问数据的同时维护访问顺序，当缓存满时淘汰最久未使用的项。C++中可以通过结合哈希表和双向链表高效实现。
LRU缓存的基本原理
LRU缓存要求：
支持O(1)时间的插入、查找和删除操作。每次访问某个键值后，将其标记为“最近使用”。当容量超限时，自动删除最久未使用的条目。
为了满足这些需求，通常采用：
std::unordered_map：用于存储键到节点的映射，实现快速查找。自定义双向链表：维护访问顺序，头结点是最新的，尾结点是最旧的。
设计双向链表节点结构
每个缓存项需要保存键、值，并能前后连接：
立即学习“C++免费学习笔记（深入）”；
struct Node { int key, value; Node* prev; Node* next; Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}};
这个结构便于在链表中快速移动或删除节点。
LRUCache类的实现
完整类定义包括初始化、获取、插入等操作：
class LRUCache {private: int capacity; std::unordered_map cache; Node* head; // 指向最新使用的节点 Node* tail; // 指向最久未使用的节点// 将现有节点移到链表头部void moveToHead(Node* 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->prev = nullptr; node->next = head; head->prev = node; head = node;}// 添加新节点到头部void addToHead(Node* node) { node->next = head; node->prev = nullptr; if (head) head->prev = node; head = node; if (!tail) tail = node;}// 删除尾部节点（最久未使用）void removeTail() { if (!tail) return; Node* toDel = tail; tail = tail->prev; if (tail) tail->next = nullptr; else head = nullptr; cache.erase(toDel->key); delete toDel;}
public:LRUCache(int cap) : capacity(cap), head(nullptr), tail(nullptr) {}
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()) { cache[key]->value = value; moveToHead(cache[key]); } else { Node* newNode = new Node(key, value); if (cache.size() >= capacity) { removeTail(); } addToHead(newNode); cache[key] = newNode; }}
};
使用示例与注意事项
测试代码：
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;}
注意点：
指针操作要小心，避免内存泄漏或野指针。边界情况如空链表、单节点需正确处理。C++11以上可用智能指针进一步提升安全性，但会略微影响性能。
基本上就这些。用哈希表加双向链表的方式，既能保证查找效率，又能维护访问顺序，是实现LRU的经典做法。
以上就是C++怎么实现一个LRU缓存_C++缓存机制与LRU实现方法的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1483901.html
微信扫一扫 
支付宝扫一扫 
