Program for implementing LRU cache.
#include<iostream>
#include<map>
#include<set>
using namespace std;
class LRUCache {
public:
map<int,pair<int,int>> cache; // Map of [ Key : <Value, Time> ]
set<pair<int,int>> minheap; // Heap of <Time, Key>
int time, capacity;
LRUCache (int arg_capacity) : time(0), capacity(arg_capacity) {}
// Update the time stamp of the key.
void UpdateTimeStamp (int key) {
// Remove old.
int old_timestamp = cache[key].second;
minheap.erase(make_pair(old_timestamp, key));
// Add new.
minheap.insert(make_pair(time, key));
}
int Get (int key) {
// Key found.
if (cache.find(key) != cache.end()) {
time++;
UpdateTimeStamp(key); // Update time-stamp of the key in minheap
cache[key].second = time; // Update the time-stamp in map.
return cache[key].first; // Return value.
}
return -1;
}
void Put (int key, int value) {
if (capacity == 0)
return;
time++;
// If key already exists in the cache.
if (cache.find(key) != cache.end()) {
UpdateTimeStamp(key);
// Update the key : <value, time> in cache.
cache[key].first = value;
cache[key].second = time;
} else {
// Cache is full.
if (cache.size() == capacity) {
int lru_key = (*minheap.begin()).second;
cache.erase(lru_key);
minheap.erase(*minheap.begin());
}
cache.insert(make_pair(key, make_pair(value, time)));
minheap.insert(make_pair(time, key));
}
}
};
int main() {
LRUCache cache(2);
cache.Put(1,1);
cache.Put(2,2);
cout << cache.Get(1) << " ";
cache.Put(3,3);
cout << cache.Get(2) << " ";
cache.Put(4,4);
cout << cache.Get(1) << " ";
cout << cache.Get(3) << " ";
cout << cache.Get(4) << " ";
return 0;
}
Output
1 -1 -1 3 4