[InterviewBit] LRU Cache

LRU Cache

  • Time : O(1)
  • Space : O(capacity)
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
#include <list> 

list<int> lru;
unordered_map<int, list<int>::iterator> lrump;
unordered_map<int, int> cache;
int cap;

LRUCache::LRUCache(int capacity) {
cap = capacity;
cache.clear();
lru.clear();
lrump.clear();
}

int LRUCache::get(int key) {
if(!cache.count(key)) return -1;
set(key, cache[key]);
return cache[key];
}

void LRUCache::set(int key, int value) {
if(lrump.count(key)) lru.erase(lrump[key]);
lru.push_front(key);
lrump[key] = lru.begin();
cache[key] = value;
while(lru.size() > cap) {
int k = lru.back(); lru.pop_back();
lrump.erase(k);
cache.erase(k);
}
}
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/09/05/PS/interviewbit/lru-cache/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.