LRU缓存通过哈希表+双向链表实现O(1)操作，最近访问节点置于链表头部，满时淘汰尾部节点。
LRU（Least Recently Used）缓存淘汰算法的核心思想是：当缓存满时，优先淘汰最久未使用的数据。在C++中，可以通过哈希表 + 双向链表高效实现O(1)的插入、查找和删除操作。
基本数据结构设计
使用std::unordered_map存储键到节点指针的映射，双向链表维护访问顺序——最近使用的放头部，淘汰从尾部进行。
定义链表节点结构：
struct ListNode {
int key, value;
ListNode* prev;
ListNode* next;
ListNode(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};
核心操作实现
封装LRUCache类，包含以下关键函数：
立即学习“C++免费学习笔记（深入）”；
get(int key)：若存在，将对应节点移到链表头并返回值；否则返回-1put(int key, int value)：新增或更新键值对，若超出容量则删除尾节点
辅助方法用于维护链表：
removeNode(ListNode* node)：从链表中移除指定节点addToHead(ListNode* node)：将节点插入链表头部
完整代码示例
class LRUCache {
private:
std::unordered_map cache;
ListNode* head;
ListNode* tail;
int capacity;
void removeNode(ListNode* node) {
if (node == head) head = node->next;
if (node == tail) tail = node->prev;
if (node->prev) node->prev->next = node->next;
if (node->next) node->next->prev = node->prev;
}
void addToHead(ListNode* node) {
node->next = head;
node->prev = nullptr;
if (head) head->prev = node;
head = node;
if (!tail) tail = node;
}
public:
LRUCache(int cap) : capacity(cap), head(nullptr), tail(nullptr) {}
int get(int key) {
if (cache.find(key) == cache.end()) return -1;
ListNode* node = cache[key];
removeNode(node);
addToHead(node);
return node->value;
}
void put(int key, int value) {
if (cache.find(key) != cache.end()) {
ListNode* node = cache[key];
node->value = value;
removeNode(node);
addToHead(node);
} else {
ListNode* newNode = new ListNode(key, value);
cache[key] = newNode;
addToHead(newNode);
if (cache.size() > capacity) {
ListNode* toDelete = tail;
removeNode(tail);
cache.erase(toDelete->key);
delete toDelete;
}
}
}
};
注意：实际项目中可考虑智能指针管理内存，避免手动new/delete。这个实现保证了get和put操作均摊时间复杂度为O(1)，符合高频访问场景需求。
基本上就这些。
以上就是c++++中如何实现一个LRU缓存淘汰算法_c++ LRU缓存算法实现的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1481946.html
微信扫一扫 
支付宝扫一扫 
