c++中如何使用队列实现LRU_c++队列实现LRU缓存方法-C++-PHP中文网

c++中如何使用队列实现LRU_c++队列实现LRU缓存方法

尼克

发布： 2025-09-28 20:28:34

原创

210人浏览过

答案：使用队列模拟LRU缓存可通过惰性删除和重复入队实现，但效率低于哈希表+双向链表组合。

c++中如何使用队列实现lru_c++队列实现lru缓存方法

在C++中，使用队列单独实现LRU（Least Recently Used）缓存并不高效，因为队列无法快速定位和更新中间元素。真正的LRU需要支持快速查找、插入、删除以及标记“最近使用”操作。通常采用哈希表 + 双向链表的组合方式，但若坚持用“队列”的思路模拟，可以通过一些变通方法实现一个简化版的LRU。

基本思路：队列 + 辅助结构模拟LRU

虽然标准队列（如 std::queue）不支持随机访问或元素移动，但我们可以通过以下方式模拟LRU行为：

使用 std::queue 记录访问顺序（最老的在队头）
使用 std::unordered_set 或 std::unordered_map 快速判断元素是否在缓存中
当缓存满且新元素不存在时，从队列头弹出旧元素
关键问题：如果访问的是已存在的元素（命中），如何将其标记为“最近使用”？——队列本身无法删除中间元素，因此需要重建或打标记

由于这种限制，我们引入一种惰性删除 + 重复入队的方法。

立即学习“C++免费学习笔记（深入）”；

方法：惰性更新 + 队列重复入队

允许同一个key多次出现在队列中，但通过哈希表记录当前有效的值，并在弹出时判断是否过期。

数据结构：

ViiTor实时翻译

AI实时多语言翻译专家！强大的语音识别、AR翻译功能。

116

查看详情

std::queue<int>：记录访问顺序（包括重复）
std::unordered_map<int, int>：存储 key -> value 映射
std::unordered_set<int> 或直接用 map 判断存在性
int capacity：最大容量

put 操作逻辑：

如果 key 已存在，更新 value，并将 key 再次入队（表示最新使用）
如果 key 不存在且缓存已满，则从队列头开始“惰性弹出”：检查队头 key 是否仍有效（map 中是否存在且值未被覆盖），若无效则丢弃，直到腾出空间
插入新 key-value，key 入队

get 操作逻辑：

查 map 是否存在 key
存在则返回 value，并将 key 再次入队（标记为最近使用）
不存在返回 -1

代码示例

#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;

class LRUCache {
private:
    queue<int> q;
    unordered_map<int, int> cache;
    int capacity;

public:
    LRUCache(int cap) : capacity(cap) {}

    int get(int key) {
        if (cache.find(key) == cache.end()) {
            return -1;
        }
        // 标记为最近使用：重新入队
        q.push(key);
        return cache[key];
    }

    void put(int key, int value) {
        // 如果已存在，更新值并重新入队
        if (cache.find(key) != cache.end()) {
            cache[key] = value;
            q.push(key);
            return;
        }

        // 检查容量，惰性清理
        while (cache.size() >= capacity) {
            int oldKey = q.front(); q.pop();
            // 如果 map 中的值仍匹配（说明未被覆盖），则真正删除
            // 实际上我们只删一次，但可能遇到重复入队的旧记录
            if (cache.find(oldKey) != cache.end()) {
                cache.erase(oldKey);
            }
        }

        cache[key] = value;
        q.push(key);
    }
};

登录后复制

使用示例

int main() {
    LRUCache lru(2);
    lru.put(1, 1);
    lru.put(2, 2);
    cout << lru.get(1) << endl; // 1
    lru.put(3, 3);             // evicts key 2
    cout << lru.get(2) << endl; // -1
    cout << lru.get(3) << endl; // 3
    return 0;
}

登录后复制