用priority_queue unordered_map实现lfu

LFU（Least Frequently Used）是一种缓存淘汰算法，它会淘汰最不经常使用的缓存块，以腾出空间给更频繁使用的缓存块。

在实现 LFU 算法时，可以使用一个哈希表（unordered_map）来存储缓存块及其对应的使用次数，使用一个优先队列（priority_queue）来按照使用次数从小到大排列缓存块。当需要淘汰缓存块时，从优先队列中取出使用次数最小的缓存块，如果有多个缓存块使用次数相同，则取最久未使用的缓存块。

下面是使用 priority_queue 和 unordered_map 实现 LFU 算法的示例代码：

#include <iostream>
#include <queue>
#include <unordered_map>

using namespace std;

struct CacheNode {
    int key;
    int value;
    int freq; // 使用次数
    int timestamp; // 最后使用时间
    CacheNode(int k, int v, int f, int t) : key(k), value(v), freq(f), timestamp(t) {}
};

// 定义优先队列的比较函数
struct CacheNodeCompare {
    bool operator() (const CacheNode& a, const CacheNode& b) {
        if (a.freq == b.freq) {
            return a.timestamp > b.timestamp;
        } else {
            return a.freq > b.freq;
        }
    }
};

class LFUCache {
public:
    LFUCache(int capacity) {
        this->capacity = capacity;
        timestamp = 0;
    }

    int get(int key) {
        if (cache.find(key) == cache.end()) {
            return -1;
        } else {
            CacheNode node = cache[key];
            node.freq++;
            node.timestamp = ++timestamp;
            cache[key] = node;
            freq_queue.push(node);
            return node.value;
        }
    }

    void put(int key, int value) {
        if (capacity <= 0) {
            return;
        }

        if (cache.find(key) == cache.end()) {
            if (cache.size() == capacity) {
                while (!freq_queue.empty() && cache.find(freq_queue.top().key) == cache.end()) {
                    freq_queue.pop();
                }
                if (!freq_queue.empty()) {
                    CacheNode node = freq_queue.top();
                    freq_queue.pop();
                    cache.erase(node.key);
                }
            }
            CacheNode node(key, value, 1, ++timestamp);
            cache[key] = node;
            freq_queue.push(node);
        } else {
            CacheNode node = cache[key];
            node.value = value;
            node.freq++;
            node.timestamp = ++timestamp;
            cache[key] = node;
            freq_queue.push(node);
        }
    }

private:
    int capacity;
    int timestamp;
    unordered_map<int, CacheNode> cache;
    priority_queue<CacheNode, vector<CacheNode>, CacheNodeCompare> freq_queue;
};

int main() {
    LFUCache cache(2);
    cache.put(1, 1);
    cache.put(2, 2);
    cout << cache.get(1) << endl; // 输出 1
    cache.put(3, 3);
    cout << cache.get(2) << endl; // 输出 -1
    cout << cache.get(3) << endl; // 输出 3
    cache.put(4, 4);
    cout << cache.get(1) << endl; // 输出 -1
    cout << cache.get(3) << endl; // 输出 3
    cout << cache.get(4) << endl; // 输出 4
    return 0;
}

在上面的代码中，我们定义了一个 `CacheNode` 结构体，用来存储缓存块的键值、使用次数和最后使用时间。我们还定义了一个 `CacheNodeCompare` 结构体，用来定义优先队列的比较函数，按照使用次数从小到大排列缓存块，如果使用次数相同，则按照最后使用时间从小到大排列。最后，我们使用一个 `unordered_map` 来存储缓存块，使用一个 `priority_queue` 来按照使用次数从小到大排列缓存块。

在 `get` 方法中，如果缓存中不存在指定的键，则返回 -1；否则，将缓存块的使用次数加一，最后使用时间更新，并将缓存块重新加入优先队列中，然后返回缓存块的值。

在 `put` 方法中，如果缓存中不存在指定的键，则需要判断缓存是否已满，如果已满，则从优先队列中取出使用次数最小的缓存块，并从缓存中删除它。然后创建一个新的缓存块，并将它加入缓存和优先队列中。如果缓存中存在指定的键，则更新缓存块的值、使用次数和最后使用时间，并将缓存块重新加入优先队列中。

最后，我们在 `main` 函数中测试了 LFU 算法的实现。当缓存容量为 2 时，我们先将键值对 (1, 1) 和 (2, 2) 存入缓存中，然后从缓存中取出键为 1 的值，输出 1。接着，我们再将键值对 (3, 3) 存入缓存中，此时键为 2 的缓存块已经被淘汰了。接下来，我们分别从缓存中取出键为 2 和 3 的值，都能够返回 -1 和 3，说明 LFU 算法的实现是正确的。