Efficient LRU Cache Implementation with get() and set() Methods

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.

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.

Examples:

Approach:

Output:

Similar Reads