题解 | #LRU Cache#

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

class LRUCache {
    using kv = pair<int, int>;  // <key, value>
    int capacity;
    list<kv> lis;
    unordered_map<int, list<kv>::iterator> keyToPtr;

    // 将指针指向的节点移动到链表头部，并更新指针信息
    void MoveToHead(list<kv>::iterator& p) {
        lis.push_front(*p);
        lis.erase(p);
        p = lis.begin();
    }

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

    int get(int key) {
        if (keyToPtr.count(key) == 0) return -1;
        MoveToHead(keyToPtr[key]);
        return keyToPtr[key]->second;
    }

    void set(int key, int value) {
        if (capacity <= 0) return; // 非法空间
        if (keyToPtr.count(key) == 0) {    // 没有这个 key，插入
            if (lis.size() >= capacity) {  // 容量满了，删除最久没有访问的
                keyToPtr.erase(lis.back().first);
                lis.pop_back();
            }
            lis.push_front({key, value});
            keyToPtr[key] = lis.begin();
        } else {  // 有这个 key，更新
            // MoveToHead(keyToPtr[key]); // 注意检查题干：“更新 value”是否需要更新访问时间
            keyToPtr[key]->second = value;
        }
    }
};

int main() {
    int n;
    cin >> n;
    LRUCache cache(n);
    char ch;
    int key, value;
    while (cin >> ch) {
        if (ch == 'p') {
            cin >> key >> value;
            cache.set(key, value);
        } else if (ch == 'g') {
            cin >> key;
            cout << cache.get(key) << endl;
        } else {
            
        }
    }
}
// 64 位输出请用 printf("%lld")