LRU cache implementation: Here we have two methods get and set which are defined as follows:
get(x) : If the key x exists in the cache, returns its value and update reference position in the list. Else returns -1.
set(x,y) : Inserts the value if the key x is not already present.
If the cache reaches its capacity it should delete the least recently used item before inserting the new item. Update the value and reference of the key x in the map and the reference position in the list.
Examples:
Input : n=2 SET(1,2) SET(2,3) SET(1,5) SET(4,5) SET(6,7) GET 4 GET 1 Output : 5 -1 Here after setting values of 1,2,1 we set for 4 but cache is full. So we remove the least recently used:2. Similarly, while setting 6 we remove 1 from the cache.
RECOMMENDED: Find the Minimum element in a Sorted and Rotated Array
Approach:
We can use STL container list as a double ended queue to store the cache keys, with the descending time of reference from front to back and a map to store the values of the keys. But to fetch the address of the key in the list using find(), it takes O(N) time. This can be optimized by storing a reference(iterator) to each key along with its value as a pair in the map.
Now in the c++ implementation we use map so it may take O(lg N) time for the operations in the worst case. But assuming we have a good hash function for the hash table, both the set and get operations take O(1) time using the above algorithm.
Following is the implementation of the above:
#include <iostream> #include <map> #include <list> using namespace std; class LRUCache { //store key contents of cache list < int > dq; //store value and reference of key in cache map < int, pair < int, list < int > ::iterator > > ma; int size; //maximum capacity of cache public: LRUCache(int); void get(int); void set(int, int); void display(); }; LRUCache::LRUCache(int n) { size = n; } /*Sets the key x with value y in the LRU cache */ void LRUCache::set(int x, int y) { //not present in cache if (ma.find(x) == ma.end()) { //cache is full if (dq.size() == size) { //delete least recently used element int last = dq.back(); dq.pop_back(); ma.erase(last); } } //present in cache else { dq.erase(ma[x].second); } //update dq.push_front(x); ma[x] = make_pair(y, dq.begin()); } /*Returns the value of the key x if present else returns -1 */ void LRUCache::get(int x) { //present in cache if (ma.find(x) != ma.end()) { int val = ma[x].first; cout << val << endl; } //not found in cache else { cout << "not found\n"; return; } //update dq.erase(ma[x].second); dq.push_front(x); ma[x].second = dq.begin(); return; } //display contents of cache void LRUCache::display() { list < int > ::iterator it; for (it = dq.begin(); it != dq.end(); it++) cout << ( * it) << " "; cout << endl; } // Driver program to test above functions int main() { LRUCache ca(3); ca.set(1, 8); ca.set(2, 9); ca.set(3, 10); ca.get(3); ca.set(1, 6); ca.set(4, 7); ca.display(); return 0; }
Output:
10 4 1 3
Time Complexity: O(1)
Space Complexity: O(n)
Please write comments below if you find anything incorrect, or you want to share more information about the topic discussed above. A gentle request to share this topic on your social media profile.