Program for implementing LRU cache.
#include<iostream>
#include<map>
#include<set>
using namespace std;
class LRUCache {
// Size of LRU cache
int size;
// LRU cache table, stores < key, <value, time>>
map <int, pair<int, int>> cache;
// Set would by default give a minheap_timestamp based on <first> of pair <time_stamp, key>
set <pair<int, int>> minheap_timestamp;
int time_stamp = 0;
public:
LRUCache (int arg_size) : size(arg_size) { }
void Update_MinHeap (int key) {
// Update would involve deleting the previous pair <time_stamp, key> and inserting a new pair.
minheap_timestamp.erase (make_pair(cache[key].second, key));
minheap_timestamp.insert (make_pair(time_stamp, key));
cache[key].second = time_stamp;
time_stamp++;
}
int Get (int key) {
cout << "\nGET : " << key << endl;
if (cache.find(key) != cache.end()) {
Update_MinHeap(key);
Display_MinHeap();
cout << "Return ---> " << cache[key].first << endl;
return cache[key].first;
}
return -1;
}
void Put (int key, int value) {
if (size == 0)
return;
cout << "\nOperation PUT : " << key << " : " << value << endl;
if (cache.find(key) != cache.end()) {
cache[key].first = value; // Update the cache
Update_MinHeap(key);
} else {
if (cache.size() == size) {
cout << "Cache full !!";
int tbd_key = (minheap_timestamp.begin())->second;
cout << "\nErasing LRU key " << tbd_key << endl;
minheap_timestamp.erase(*minheap_timestamp.begin());
cache.erase(tbd_key); // delete LRU <key, <value, time_stamp>>
}
cache.insert(make_pair(key, make_pair(value, time_stamp))); // add new key value
minheap_timestamp.insert(make_pair(time_stamp, key));
time_stamp++;
}
Display_MinHeap();
}
void Display_MinHeap () {
set<pair<int,int>> :: iterator itr;
for (const auto pair : minheap_timestamp)
cout << "\nTime [" << pair.first << "] Key [" << pair.second << "] | ";
cout << endl;
}
};
int main() {
LRUCache cache(2);
cache.Put(1,1);
cache.Put(2,2);
cout << cache.Get(1) << endl;
cache.Put(3,3);
cout << cache.Get(2) << endl;
cache.Put(4,4);
cout << cache.Get(1) << endl;
cout << cache.Get(3) << endl;
cout << cache.Get(4) << endl;
return 0;
}
Output
Operation PUT : 1 : 1
Time [0] Key [1] |
Operation PUT : 2 : 2
Time [0] Key [1] |
Time [1] Key [2] |
GET : 1
Time [1] Key [2] |
Time [2] Key [1] |
Return ---> 1
1
Operation PUT : 3 : 3
Cache full !!
Erasing LRU key 2
Time [2] Key [1] |
Time [3] Key [3] |
GET : 2
-1
Operation PUT : 4 : 4
Cache full !!
Erasing LRU key 1
Time [3] Key [3] |
Time [4] Key [4] |
GET : 1
-1
GET : 3
Time [4] Key [4] |
Time [5] Key [3] |
Return ---> 3
3
GET : 4
Time [5] Key [3] |
Time [6] Key [4] |
Return ---> 4
4