LRU缓存通过哈希表和双向链表实现O(1)操作：1. 用unordered_map映射key到节点，双向链表维护访问顺序；2. get时查map并移至链表头；3. put时更新或插入，超容则删尾结点。
LRU（Least Recently Used）缓存是一种常见的缓存淘汰策略，核心思想是：当缓存满时，优先淘汰最久未使用的数据。C++ 中实现 LRU 缓存通常结合哈希表和双向链表，以达到 O(1) 的查找、插入和删除效率。
1. 数据结构选择
要高效实现 LRU 缓存，需要两种数据结构配合：
std::unordered_map：用于存储 key 到节点的映射，实现 O(1) 查找。双向链表：维护访问顺序，最近使用的放头部，最久未使用的在尾部，便于快速删除和移动。
我们自定义一个双向链表节点：
struct Node { int key, value; Node* prev; Node* next; Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}};
2. 核心操作设计
LRU 缓存需要支持两个主要操作：
立即学习“C++免费学习笔记（深入）”；
get(key)：获取键对应的值，若不存在返回 -1；存在则将其移到链表头部（表示最近使用）。put(key, value)：插入或更新键值对。若已存在，更新值并移至头部；若不存在且缓存已满，先删除尾部节点（最久未用），再插入新节点到头部。
3. 辅助函数：链表操作
为了简化逻辑，封装几个私有方法：
removeNode(node)：将节点从链表中摘除。addToHead(node)：将节点插入到链表头部。moveToHead(node)：将已有节点移动到头部（先删除再添加）。removeTail()：删除尾节点，并从 map 中移除对应 key。
4. 完整代码实现
#include #includeclass LRUCache {private:struct Node {int key, value;Node prev;Node next;Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}};
std::unordered_map cache;Node* head;Node* tail;int capacity;int size;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), size(0) {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); size++; if (size > capacity) { Node* removed = removeTail(); cache.erase(removed->key); delete removed; size--; } }}~LRUCache() { Node* curr = head; while (curr) { Node* temp = curr; curr = curr->next; delete temp; }}
};
5. 使用示例
int main() { LRUCache lru(2); lru.put(1, 1); lru.put(2, 2); std::cout << lru.get(1) << std::endl; // 输出 1 lru.put(3, 3); // 淘汰 key=2 std::cout << lru.get(2) << std::endl; // 输出 -1 return 0;}
基本上就这些。这个实现保证了 get 和 put 操作都在 O(1) 时间内完成，符合 LRU 缓存的基本要求。关键点在于双向链表与哈希表的协同管理，以及对边界情况（如空链表、单节点）的正确处理。
以上就是C++怎么实现一个LRU缓存_C++ LRU缓存算法实现步骤详解的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1480457.html
微信扫一扫 
支付宝扫一扫 
