C++基于priority_queue实现LRU

LRU（Least Recently Used）是一种缓存淘汰策略，当缓存空间不足时，先淘汰最近最少使用的缓存块。在 C++ 中，可以使用 `std::priority_queue` 数据结构来实现 LRU。

下面是基于 `std::priority_queue` 实现 LRU 的代码示例：

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

template <typename T>
class LRUCache {
public:
    LRUCache(int capacity) : capacity_(capacity) {}

    void put(int key, const T& value) {
        if (cache_.find(key) != cache_.end()) {
            // 如果 key 已经存在，则更新 value 并移动到队首
            auto it = cache_[key];
            it->second = value;
            cache_list_.erase(it);
            cache_list_.push_front({key, value});
            cache_[key] = cache_list_.begin();
        } else {
            // 如果 key 不存在，则插入新的键值对，并将其移动到队首
            if (cache_list_.size() == capacity_) {
                // 如果队列已满，则删除队尾元素
                auto last = cache_list_.back();
                cache_list_.pop_back();
                cache_.erase(last.first);
            }
            cache_list_.push_front({key, value});
            cache_[key] = cache_list_.begin();
        }
    }

    const T* get(int key) {
        if (cache_.find(key) != cache_.end()) {
            // 如果 key 存在，则返回 value 并将其移动到队首
            auto it = cache_[key];
            cache_list_.erase(it);
            cache_list_.push_front(*it);
            cache_[key] = cache_list_.begin();
            return &it->second;
        } else {
            // 如果 key 不存在，则返回 nullptr
            return nullptr;
        }
    }

private:
    int capacity_;
    std::list<std::pair<int, T>> cache_list_;  // 双向链表存储键值对
    std::unordered_map<int, typename std::list<std::pair<int, T>>::iterator> cache_;  // 哈希表存储键值对的迭代器
};

int main() {
    LRUCache<int> cache(3);

    cache.put(1, 10);
    cache.put(2, 20);
    cache.put(3, 30);
    cache.put(4, 40);

    std::cout << *cache.get(2) << std::endl;  // 输出 20
    std::cout << *cache.get(3) << std::endl;  // 输出 30
    std::cout << (cache.get(5) == nullptr) << std::endl;  // 输出 1

    return 0;
}

在上述实现中，我们使用了一个双向链表 `cache_list_` 存储键值对，同时使用一个哈希表 `cache_` 存储每个键对应的迭代器。在 `put` 操作中，如果缓存中已经存在该键，则更新该键对应的值并将其移动到队首；如果不存在该键，则首先判断缓存是否已满，若已满则删除队尾元素，然后将新的键值对插入到队首。在 `get` 操作中，如果缓存中存在该键，则返回其对应的值并将其移动到队首；如果不存在该键，则返回 nullptr。