題目： LeetCode - 146. LRU Cache

題目說明

建立一個類似快取記憶體的 Class，及對應的一些功能。

解題思路

使用 list<pair<int, int>> 儲存資料，再利用 unordered_map<int, list<pair<int, int>>::iterator> 達到減少時間複雜度的效果。
※ 對於 put 來說，如果資料已經滿了，那新的資料就要覆蓋最久沒有調用到的資料。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class LRUCache {
public:
    list<pair<int, int>> cache; // 儲存 key 及 value
    unordered_map<int, list<pair<int, int>>::iterator> hash; // 儲存 key 及對應的 node，方便尋找及刪除
    int Cap;

    LRUCache(int capacity) {
        Cap = capacity;
    }
    
    int get(int key) {
        // 先使用 key 尋找 node
        auto it = hash.find(key);
        // 如果找不到
        if(it == hash.end())
            return -1;
        // 將這個 node 移到最前面
        cache.splice(cache.begin(), cache, it->second);
        return it->second->second;
    }
    
    void put(int key, int value) {
        // 先使用 key 尋找 node
        auto it = hash.find(key);
        // 如果找到
        if(it != hash.end())
        {
            // 將原本的 value 改為新的 value
            it->second->second = value;
            // 將這個 node 移到最前面
            cache.splice(cache.begin(), cache, it->second);
            return;
        }
        // 如果 list 已經滿了
        if(cache.size() == Cap)
        {
            // 刪除最後一個 node，同時 hash 裡面也必須刪除
            hash.erase(cache.back().first);
            cache.pop_back();
        }
        // 將新的值插入，同時也在 hash 裡面插入
        cache.emplace_front(key, value);
        hash[key] = cache.begin();
    }
};

補充

  • splice() 的功能是串接 List。
  • emplace_front() 的功能和 push_front() 是一樣的，但是前者少了一個複製的動作，效率較高。

參考資料

花花酱 LeetCode 146. LRU Cache O(1)
list::splice()函数详解
STL - emplace 与 push 的区别
list::emplace_back - C++ Reference
list::splice - C++ Reference