146. LRU Cache

題目網址：https://leetcode.cn/problems/lru-cache/

題意：設計並實現一個滿足 LRU（Least Recently Used）的資料結構。

實現 LRUCache class：

LRUCache(int capacity)：以 capacity 初始化 LRU cache 的大小。

int get(int key)：若 key 存在於 cache 中, 則返回其對應的 val, 否則返回 1。

void put(int key, int value)：

若 key 已經存在, 則變更其 value

若不存在, 則將該組 key-value insert 到 cache 中

若 insert 操作導致 pair 數量超過 capacity, 則移除最久未使用的 key-value pair

注意：get() 和 put() 必須是 $O(1)$ time

Solution：

想法：利用 hash table + list, 其中 cache 用來存放所有的 key, 用來記錄哪個 key 最近被使用、最久沒被使用。用 list 而非 forward_list 的原因是：「當 get() 訪問的是處於中間位置的節點時, 可以直接獲取其前一個節點和後一個節點, 從而省去了遍歷整個 linked list的時間」。若用 forward_list, 要獲取前一個節點和後一個節點必須從 linked list 的 head 開始遍歷

cache.begin() : 最久未用的 key

--cache.end() : 最近使用的 key

而 key2val 和 key2iter 分別存放 key 所對應到的 val 和 iterator

get(key) :

若 key 已在 cache 中, 則將其放到 cache 尾部

若 key 不在 cache 中, 則返回 1

put(key, value) :

若 key 已在 cache 中, 則更新其對應的 val

若 key 不在 cache 中, 則要新增該 key。若 capacity 已滿, 則要移除 cache.begin()

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

    int get(int key) {
        // 若 cache 已存在該 key, 則將其放到 cache 尾部
        if (key2val.find(key) != key2val.end()) {
            int val = key2val[key];
            auto it = key2iter[key];
            cache.erase(it);
            cache.push_back(key);
            key2iter[key] = --cache.end();
            return val;
        }
        return -1; // key not found
    }

    void put(int key, int value) {
        // cache 已存在該 key, 則更新其對應的 val
        // 直接調用 get(key), 若存在 key, 則 get 會將其放到 cache 尾端, 然後更新 val 即可
        if (get(key) != -1) {
            key2val[key] = value;
            return; // key 已存在, 因此 put 後 size 不變, 不會超過 cap, 所以直接返回
        }

        // cache 不存在該 key, 則要新增該 key
        // 若 cache 已滿, 則要先移除 cache.begin()
        if (key2val.size() == capacity_) {
            int keyDel = *cache.begin();
            cache.erase(cache.begin());
            key2val.erase(keyDel);
            key2iter.erase(keyDel);
        }
        
        cache.push_back(key);
        key2val[key] = value;
        key2iter[key] = --cache.end();
    }

private:
    int capacity_;
    list<int> cache; // 存放 "key" 的 list
    unordered_map<int, int> key2val; // {key, val}
    unordered_map<int, list<int>::iterator> key2iter; // {key, iterator}
};

time：$O(1)$
space：$O(capacity)$ ➔ cache, key2val, key2iter 的元素個數不超過 capacity