Implementing LRU Cache

LRU_Cache



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


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