采用页式分配存储方案使用C++模拟页面置换算法实现LRU 算法 (Least Recently) 的模拟

以下是一个使用 C++ 实现的 LRU 页面置换算法的模拟程序。在这个程序中，我们使用了一个双向链表来存储缓存区中的页面，并使用一个哈希表来快速查找页面是否存在于缓存区中。

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

// 定义双向链表节点
struct Node {
    int key;
    int value;
    Node* prev;
    Node* next;
    Node(int k, int v): key(k), value(v), prev(nullptr), next(nullptr) {}
};

class LRUCache {
private:
    unordered_map<int, Node*> cache; // 哈希表
    Node *head, *tail; // 双向链表头尾指针
    int size; // 缓存区大小
public:
    LRUCache(int capacity) {
        size = capacity;
        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()) { // 如果哈希表中不存在该页面，则返回 -1
            return -1;
        }
        Node* node = cache[key];
        remove(node); // 将该页面从链表中删除
        addHead(node); // 将该页面添加到链表头部
        return node->value;
    }

    void put(int key, int value) {
        if (cache.find(key) != cache.end()) { // 如果哈希表中存在该页面，则更新其值并将其移动到链表头部
            Node* node = cache[key];
            node->value = value;
            remove(node);
            addHead(node);
        } else { // 如果哈希表中不存在该页面，则将其添加到链表头部，并将其添加到哈希表中
            if (cache.size() == size) { // 如果缓存区已满，则删除链表尾部节点
                Node* node = tail->prev;
                remove(node);
                cache.erase(node->key);
                delete node;
            }
            Node* node = new Node(key, value);
            cache[key] = node;
            addHead(node);
        }
    }

private:
    // 将节点添加到链表头部
    void addHead(Node* node) {
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    }

    // 将节点从链表中删除
    void remove(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
};

int main() {
    LRUCache cache(2); // 创建一个大小为 2 的缓存区
    cache.put(1, 1);
    cache.put(2, 2);
    cout << cache.get(1) << endl; // 返回 1
    cache.put(3, 3); // 将 2 从缓存区中删除
    cout << cache.get(2) << endl; // 返回 -1
    cache.put(4, 4); // 将 1 从缓存区中删除
    cout << cache.get(1) << endl; // 返回 -1
    cout << cache.get(3) << endl; // 返回 3
    cout << cache.get(4) << endl; // 返回 4
    return 0;
}

这个程序中，我们使用了 `unordered_map` 来实现哈希表，这是 C++ STL 中的一个容器，可以快速查找元素。我们定义了一个双向链表节点 `Node`，其中包含了页面的键值对以及前后指针。在 `LRUCache` 类中，我们使用了一个大小为 `size` 的缓存区来存储页面。在获取页面时，如果该页面存在于缓存区中，则将其从链表中删除并将其添加到链表头部；如果该页面不存在于缓存区中，则返回 -1。在添加页面时，如果该页面存在于缓存区中，则更新其值并将其移动到链表头部；如果该页面不存在于缓存区中，则将其添加到链表头部，并将其添加到哈希表中。如果缓存区已满，则删除链表尾部节点。