代碼：
class LRUCache {
private:
int cap;
// 雙鏈表：裝著 (key, value) 元組
list<pair<int, int>> cache;
// 哈希表：key 映射到 (key, value) 在 cache 中的位置
unordered_map<int, list<pair<int, int>>::iterator> map;
public:
LRUCache(int capacity) {
this->cap = capacity;
}
int get(int key) {
auto it = map.find(key);
// 訪問的 key 不存在
if (it == map.end()) return -1;
// key 存在忽冻，把 (k, v) 換到隊頭
pair<int, int> kv = *map[key];
cache.erase(map[key]);
cache.push_front(kv);
// 更新 (key, value) 在 cache 中的位置
map[key] = cache.begin();
return kv.second; // value
}
void put(int key, int value) {
/* 要先判斷 key 是否已經存在 */
auto it = map.find(key);
if (it == map.end()) {
/* key 不存在，判斷 cache 是否已滿 */
if (cache.size() == cap) {
// cache 已滿赶盔，刪除尾部的鍵值對騰位置
// cache 和 map 中的數據都要刪除
auto lastPair = cache.back();
int lastKey = lastPair.first;
map.erase(lastKey);
cache.pop_back();
}
// cache 沒滿甘邀，可以直接添加
cache.push_front(make_pair(key, value));
map[key] = cache.begin();
} else {
/* key 存在，更改 value 并換到隊頭 */
cache.erase(map[key]);
cache.push_front(make_pair(key, value));
map[key] = cache.begin();
}
}
};
