使用C++模拟页面置换算法实现LRU 算法 (Least Recently) 的模拟

LRU (Least Recently Used) 是一种常见的页面置换算法，在操作系统中被广泛使用。它的核心思想是，如果一个页面最近一段时间内没有被访问，那么它很可能在未来也不会被访问，因此可以将其替换出内存，腾出空间给其他页面使用。

下面是使用C++模拟LRU算法的示例代码：

#include <iostream>
#include <list>
#include <unordered_map>

using namespace std;

class LRUCache {
public:
    LRUCache(int capacity) : capacity(capacity) {}
    
    int get(int key) {
        auto it = cache.find(key);
        if (it == cache.end()) {  // 如果key不存在
            return -1;
        }
        // 将节点移动到链表头部，并返回value
        cache_list.splice(cache_list.begin(), cache_list, it->second);
        return it->second->second;
    }
    
    void put(int key, int value) {
        auto it = cache.find(key);
        if (it != cache.end()) {  // 如果key已经存在，更新value并将节点移动到链表头部
            it->second->second = value;
            cache_list.splice(cache_list.begin(), cache_list, it->second);
            return;
        }
        if (cache.size() == capacity) {  // 如果cache已满，删除链表尾部节点
            auto last = cache_list.back();
            cache.erase(last.first);
            cache_list.pop_back();
        }
        // 在链表头部插入新节点
        cache_list.emplace_front(key, value);
        cache[key] = cache_list.begin();
    }
    
private:
    int capacity;
    list<pair<int, int>> cache_list;  // 使用双向链表保存key-value对
    unordered_map<int, list<pair<int, int>>::iterator> cache;  // 使用哈希表快速查找key对应的节点
};

int main() {
    LRUCache cache(2);

    cache.put(1, 1);
    cache.put(2, 2);
    cout << cache.get(1) << endl;  // 返回 1
    cache.put(3, 3);  // 该操作会使得 key 2 作废
    cout << cache.get(2) << endl;  // 返回 -1
    cache.put(4, 4);  // 该操作会使得 key 1 作废
    cout << cache.get(1) << endl;  // 返回 -1
    cout << cache.get(3) << endl;  // 返回 3
    cout << cache.get(4) << endl;  // 返回 4

    return 0;
}

在上面的代码中，我们使用了双向链表和哈希表来维护LRU缓存。其中，双向链表用于按照访问时间排序缓存中的节点，哈希表则用于快速查找某个key对应的节点在链表中的位置。当有新的key-value对要插入缓存时，如果缓存已满，则删除链表尾部的节点；如果key已经存在，则更新value并将对应的节点移动到链表头部；否则，在链表头部插入新节点。当需要从缓存中获取某个key对应的value值时，我们在哈希表中查找key对应的节点，将其移动到链表头部，并返回value。