The basic idea is to store the key-value pair in some container. In the following code, we make three type definitions:
1 typedef list<int> LI; 2 typedef pair<int, LI::iterator> PII; 3 typedef unordered_map<int, PII> HIPII;
HIPII is the ultimate type for the container. It is essentially an unordered_map, using key as its key and a pair as its value. The first element of the pair is the value and the second element of it is the iterator of the key in a list (front elements are more recently used). So each element in the HIPII container is like a {int key, {int value, iterator}}.
Now the implementation of get and set is relatively straightforward: each time we access a key, touch it (making it at the beginning of the list) and then get or set its value. If the container has met its size and we need add a new key, just remove the key corresponding to the last element of list (least recently used).
The code is as follows.
1 class LRUCache{ 2 public: 3 LRUCache(int capacity) { 4 _capacity = capacity; 5 } 6 7 int get(int key) { 8 auto it = cache.find(key); 9 if (it == cache.end()) return -1; 10 touch(it); 11 return it -> second.first; 12 } 13 14 void set(int key, int value) { 15 auto it = cache.find(key); 16 if (it != cache.end()) touch(it); 17 else { 18 if (cache.size() == _capacity) { 19 cache.erase(used.back()); 20 used.pop_back(); 21 } 22 used.push_front(key); 23 } 24 cache[key] = {value, used.begin()}; 25 } 26 private: 27 typedef list<int> LI; 28 typedef pair<int, LI::iterator> LII; 29 typedef unordered_map<int, LII> HIPII; 30 31 int _capacity; 32 LI used; 33 HIPII cache; 34 35 void touch(HIPII::iterator it) { 36 int key = it -> first; 37 used.erase(it -> second.second); 38 used.push_front(key); 39 it -> second.second = used.begin(); 40 } 41 };
