Implementing LRU Cache

LRU_Cache



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


Copyright (c) 2019-2022, Algotree.org.
All rights reserved.