页面置换算法c++

页面置换算法是操作系统中的重要概念之一，它主要用于在物理内存不足时，将内存中的某些页面移出到磁盘上，以腾出空间给新的页面使用。以下是一个简单的C++实现LRU算法的示例：

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

using namespace std;

class LRUCache {
public:
    LRUCache(int capacity) {
        cap = capacity;
    }

    int get(int key) {
        auto it = cache.find(key);
        if (it == cache.end()) {
            return -1;
        }
        // 将访问过的节点移至链表头部
        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()) {
            // 将访问过的节点移至链表头部
            cache_list.splice(cache_list.begin(), cache_list, it->second);
            it->second->second = value;
            return;
        }
        if (cache.size() == cap) {
            // 移除链表尾部的节点
            int key_to_remove = cache_list.back().first;
            cache.erase(key_to_remove);
            cache_list.pop_back();
        }
        // 插入新的节点
        cache_list.emplace_front(key, value);
        cache[key] = cache_list.begin();
    }

private:
    int cap;
    list<pair<int, int>> cache_list;
    unordered_map<int, list<pair<int, int>>::iterator> cache;
};

int main() {
    LRUCache 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
    cache.put(4, 4);
    cout << cache.get(1) << endl; // -1
    cout << cache.get(3) << endl; // 3
    cout << cache.get(4) << endl; // 4
    return 0;
}

该实现中，使用了一个哈希表和一个双向链表来维护缓存。哈希表中存储了每个节点的键值和指向链表中对应节点的迭代器。双向链表中存储了每个节点的键值和值。当访问一个节点时，将对应节点移至链表头部，这样链表尾部的节点就是最近最少使用的，可以直接移除。当插入一个新节点时，先检查缓存是否已满，如果已满则移除链表尾部的节点，然后在链表头部插入新节点。