lru页面置换算法c++

以下是 LRU 页面置换算法的 C++ 实现：

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

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 不存在，返回 -1
            return -1;
        }
        // 将当前节点移动到链表头部
        _cacheList.splice(_cacheList.begin(), _cacheList, it->second);
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = _cache.find(key);
        if (it != _cache.end()) {
            // 如果 key 已存在，则更新其值，并将其移动到链表头部
            it->second->second = value;
            _cacheList.splice(_cacheList.begin(), _cacheList, it->second);
            return;
        }
        if (_cache.size() == _capacity) {
            // 如果缓存已满，删除链表尾部节点和缓存中对应的 key
            int key_to_del = _cacheList.back().first;
            _cacheList.pop_back();
            _cache.erase(key_to_del);
        }
        // 在链表头部插入新的节点，并在缓存中添加对应的 key
        _cacheList.emplace_front(key, value);
        _cache[key] = _cacheList.begin();
    }

private:
    int _capacity;
    // 使用哈希表存储 key-value 对
    unordered_map<int, list<pair<int, int>>::iterator> _cache;
    // 使用双向链表存储 key-value 对的访问顺序
    list<pair<int, int>> _cacheList;
};

LRUCache 类中包含一个哈希表 `_cache` 和一个双向链表 `_cacheList`，其中哈希表用于快速查找指定键的值，双向链表用于维护键值对的访问顺序。

在 `get()` 函数中，首先在哈希表中查找指定键，如果该键不存在，则返回 -1；否则，将对应节点移动到链表头部，并返回其值。

在 `put()` 函数中，首先在哈希表中查找指定键，如果该键已存在，则更新其值，并将对应节点移动到链表头部；否则，如果缓存已满，则删除链表尾部节点和哈希表中对应的键，然后在链表头部插入新节点，并在哈希表中添加对应键值对。