// 演算法 / Algorithm:
//   unordered_map(雜湊表) + list(標準庫的雙向鏈結串列)。
//   unordered_map + std::list (the standard doubly-linked list).
//   list 頭=最新、尾=最舊；map 把 key 對應到 list 中的迭代器，
//   讓我們能 O(1) 找到並用 splice 移動節點。
//   The list keeps head=newest/tail=oldest; the map maps key to a list iterator,
//   so we can find and splice a node in O(1).

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

class LRUCache {
private:
    int cap;   // 容量 / capacity
    // list 每個元素是一對 {key, value}；pair.first=key, pair.second=value
    // Each list element is a pair {key, value}.
    list<pair<int,int>> items;
    // map: key -> 指向 list 中對應元素的迭代器(iterator，可想成「位置憑證」)
    // map: key -> an iterator (a handle to the element's position in the list)
    unordered_map<int, list<pair<int,int>>::iterator> pos;

public:
    LRUCache(int capacity) : cap(capacity) {}   // 成員初始化列表設定容量 / init capacity

    int get(int key) {
        auto it = pos.find(key);        // 在 map 中找 key / look up key in the map
        if (it == pos.end()) return -1; // 找不到就回傳 -1 / not found -> -1
        // splice 把節點從原位置搬到 items 的最前面，指標不失效、O(1)。
        // splice moves the node to the front of items in O(1) without invalidating iterators.
        // it->second 是那個節點的迭代器 / it->second is the node's iterator
        items.splice(items.begin(), items, it->second);
        return it->second->second;      // 迭代器指向 pair，.second 就是 value / the value
    }

    void put(int key, int value) {
        auto it = pos.find(key);        // 先看 key 在不在 / check existence
        if (it != pos.end()) {          // 已存在 / exists
            it->second->second = value; // 更新 value / update value
            items.splice(items.begin(), items, it->second);  // 移到最前 / move to front
            return;
        }
        if ((int)items.size() == cap) { // 滿了才淘汰(先淘汰再插入也可) / full -> evict LRU first
            auto &oldest = items.back();  // list 尾端是最舊的 / back of list is least recently used
            pos.erase(oldest.first);      // 用它的 key 從 map 移除 / erase from map by its key
            items.pop_back();             // 從 list 移除尾端 / remove it from the list
        }
        // emplace_front 直接在最前面就地建立 {key,value}，比 push_front 少一次複製
        // emplace_front constructs {key,value} in place at the front (fewer copies than push_front)
        items.emplace_front(key, value);
        pos[key] = items.begin();       // 登記新節點的迭代器 / record the new node's iterator
    }
};

/**
 * 你的 LRUCache 會被這樣使用 / Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */