lru页面置换算法cpp

LRU (Least Recently Used) 页面置换算法是一种常用的页面置换算法，其思想是将最近最少使用的页面淘汰掉。下面是 C++ 实现：

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

using namespace std;

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

    int get(int key) {
        if (cache.find(key) == cache.end()) return -1;
        auto it = cache[key];
        int val = it->second;
        lru.erase(it);
        lru.push_front({key, val});
        cache[key] = lru.begin();
        return val;
    }

    void set(int key, int value) {
        if (cache.find(key) == cache.end()) {
            if (lru.size() == cap) {
                auto last = lru.back();
                int delKey = last.first;
                lru.pop_back();
                cache.erase(delKey);
            }
            lru.push_front({key, value});
            cache[key] = lru.begin();
        }
        else {
            auto it = cache[key];
            lru.erase(it);
            lru.push_front({key, value});
            cache[key] = lru.begin();
        }
    }

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

int main() {
    LRUCache lru(2);
    lru.set(1, 1);
    lru.set(2, 2);
    cout << lru.get(1) << endl; // 1
    lru.set(3, 3);
    cout << lru.get(2) << endl; // -1
    lru.set(4, 4);
    cout << lru.get(1) << endl; // -1
    cout << lru.get(3) << endl; // 3
    cout << lru.get(4) << endl; // 4
    return 0;
}

在这个实现中，我们使用双向链表 `lru` 维护页面的使用顺序，使用哈希表 `cache` 存储页面的值和对应的迭代器。当访问一个页面时，我们将其从链表中删除，并添加到链表头部；当添加一个页面时，我们将其添加到链表头部，并且若链表长度超过了容量，则删除链表末尾的页面。注意，我们使用 `unordered_map` 而不是 `map`，因为前者的查找、插入和删除时间复杂度都是 $O(1)$。